The Research On The Two-dimensional Loading Capacitated Vehicle Routing Problem

With the rapid development of modern market economy and theelevation of logistics technology specialization, logistics distribution isgrowing more and more important in the logistics industry. VRP (VehicleRouting Problem) and VLP (Vehicle loading Problem), two key problemsin logistics distribution, have been a hot area of research for several years.It has important significance to design a rapid and efficient algorithm ofVRP and VLP for helping lower cost, improving efficiency of distribution,improving service quality, and enhancing the enterprise’s profit.Meanwhile, it plays a role in energy conservation, environmentalprotection, traffic congestion, and so on.VRP is a NP-hard (non-deterministic polynomial hard problem) inthe field of combinatorial optimization and operational research. Itspurpose is minimizing objective function without violating the vehiclecapacity or the normal route duration constraints. VLP is also a NP-hardproblem, its main purpose is to load the goods into the vehicles in areasonable way, and maximum loading rate of the vehicles as far aspossible, in doing that could reduce the number of vehicles anddistribution costs in capital asserts, and promote the interest of the firms.VRP and VLP are two key issues in logistics distribution. Therationality of the vehicle loading influences scheme of vehicle routing,and vice versa. This paper is to bond these two problems as a new combination optimization problem. The shortest travel distance and themaximization vehicle utilization rate are the main purpose. This paperstudied a combinatorial optimization problem of the two-dimensionalloading and capacitated vehicle routing problem (two-dimensionalloading capacitated vehicle routing problem,2L-CVRP for short). Themain research work of this paper as follows:(1) Review the research situation of the VRP,VLP and2L-CVRP inthe past.(2)Introduce the existing two-dimensional loading algorithms, andmake some improvements for specific circumstances of thetwo-dimensional loading capacitated vehicle routing problem, andconduct comparative analysis;(3) Use the improved savings-based ant colony optimizationalgorithm to solve two-dimensional loading capacitated vehicle routingproblem. Firstly, we construct initial path of the vehicle running with antsaccording to the probability rule of integration of conservation value andthe pheromone. In the process of constructing the initial path, the packingalgorithm is called to load the goods of current customer, when it isfeasible. Secondly, we use the local optimization method of2-opt andSwap to optimize the initial path. Finally, we update the pheromoneaccording to the elite ants and ant level. Repeat the process until thenumber of iterations to reach the output of the final solution.