Vehicle Routing Problem Of Simultaneous Deliveries And Pickups With Two-dimensional Loading Constraints

The existing researches of the vehicle routing problem of simultaneous deliveries and pickups (CVRPSDP) mainly focus on the weight constraint. However, there are many light cargoes the volume constraints of which are tighter than the weight constraints. Cargoes will be unable to be totally loaded into the truck when weight constraint is considered only. In view of the problem, this paper studies a special vehicle routing problem with loading constrains--the vehicle routing problem of simultaneous deliveries and pickups with two-dimensional loading constraints (2L-CVRPSDP), in which the customer demand can be simplified as a two-dimensional rectangular item with different sizes and weights, and the objective is to find a set of routes with the minimum cost under the loading and capacity constraints. This problem can be applied to the distribution of light cargoes which may not be stacked one over the other, such as household appliances, glassware, precision parts or other breakables.In this paper, a mathematical model is established for2L-CVRPSDP and an improved iterated local search algorithm is proposed to solve it:Firstly, an improved saving algorithm is used to produce the initial solution, then it is improved by the variable neighborhood descents search (VND). If the current solution has not been improved after VND is applied, a restart and perturbation strategy is employed to change the search direction and continue iterative search. It will be not stopped until the number of iterations is performed. To check the feasibility of volume constraints, the algorithm adopts a heuristic algorithm of two-dimensional packing problem based on four kinds of packing rules.To validate the effectiveness of the algorithm proposed, the benchmarks for2L-CVRPSDP are constructed based on Iori’s standard benchmark firstly. The related parameters in the algorithm and the effect of perturbation operator and VND on the results are determined by the experiment tests. After that, the proposed method is applied to2L-VRP, the special case of2L-CVRPSDP. And the computational results show that that it has updated some of the best-known solutions and improved the average values of them. Further, the computational results of2L-CVRPSDP are given.Finally, an intelligent distribution management system considering packing constraints has been designed based on the proposed algorithm. Through the system, delivery route arrangements and item layout on the compartment that meets the demands of customers can be generated quickly and presented to the users by the most intuitive way.This paper has extended studies on the existing researches of CVRPSDP by considering both the weight and volume dual constraints, which will enhance the range of application. What’s more, an optimization information system has been developed at the same time. It will provide important decision support for logistics enterprises in the future.