The Optimization Research of Multi-Category Unpaired Supply-Demand and Arbitrary Split Pickup and Delivery Vehicle Routing Problem with Multi-Depot and Multi-Type Trucks
XU Dongyang，LI Kunpeng，ZHENG Piao，TIAN Qiannan
1.Henan University, Kaifeng, Henan, China; 2. Huazhong University of Science and Technology, Wuhan, China; 3.Henan Tobacco Co.LTD, Zhengzhou, China; 4. Hubei University of Economics, Wuhan, China
Abstract To optimize the raw material allocation system of multi-point productionenterprises, this paper studies the pickup and delivery vehicle routing problem (PDVRP) by comprehensive considering several factors including multi-depot, multi-type, multi-category, unpaired supply-demand andarbitrary split pick up and delivery for customers. Based on the optimization objective of minimizing the transportation costs given by the travelling distances×the weight of transportation goods, a mixed integer optimization model is established, and a two-stage heuristic algorithm is designed.In the first stage, a greedy heuristic algorithm based on transportation efficiency is constructedto obtain the initial feasible solution. In the second stage, a variable neighborhood search algorithm is applied to improve the quality of initial solution.The effectiveness of the above model and algorithm are verified by 6 actual cases in an enterprise. Computational results show that: The construction of initial solution considering transportation efficiency has obvious advantages. The proposed algorithm is superior to the existing algorithm in terms of solution quality and computational time. Compared to the manual allocation scheme, the allocation scheme proposed in this paper can help related enterprises save transportation costs and vehicle trips.
XU Dongyang,LI Kunpeng,ZHENG Piao等. The Optimization Research of Multi-Category Unpaired Supply-Demand and Arbitrary Split Pickup and Delivery Vehicle Routing Problem with Multi-Depot and Multi-Type Trucks[J]. Chinese Journal of Management, 2020, 17(7): 1086-.
