Pickup and Delivery Team Orienteering Problem with Pickup Option

Chenxiu Wang

《Frontiers in Economics and Management》 3卷2期 (2022/02) Pp. 505-518

https://doi.org/10.6981/FEM.202202_3(2).0062

摘要

With the rapid development of e-commerce and the rise of offline retail errand business, how to quickly distribute goods to customers while ensuring timeliness and low cost has become an urgent problem to be solved, and optimizing the distribution route through efficient planning algorithm is a feasible solution. Therefore, aiming at these problems, according to the actual situation of distribution, considering the collection of goods from multiple pickup points and the limited distribution resources, which can not meet all distribution needs but can only choose to distribute some needs, we construct a Pickup and Delivery Team Orienteering Problem with Pickup Option model. At the same time, because the model not only needs to optimize the distribution path, but also needs to make decisions on the pickup points of each demand to maximize the total distribution revenue, we design an Adaptive Large Neighborhood Search algorithm to solve the model, and designs a variety of efficient destroy and repair operators based on the characteristics of the model to expand the search space of the solution adaptive strategy is used to select efficient search operators to improve the search efficiency of understanding space. In addition, in order to improve the performance of the algorithm and avoid falling into the local optimal solution, a new solution acceptance strategy of Simulated Annealing is introduced. Finally, a large number of examples verify the effectiveness of the proposed model and algorithm.

關鍵字

Pickup Option ； Limited Distribution Resources ； Pickup and Delivery Problem ； Team Orienteering Problem ； Adaptive Large Neighborhood Search

參考文獻

Parragh S N, Doerner K F, Hartl R F: A Survey on Pickup and Delivery Problems, Management Review Quarterly, vol. 58(2008), No.1, p.21-51.

Gribkovskaia I, Laporte G: One-to-Many-to-One Single Vehicle Pickup andDelivery Problems (Springer, Boston, Britain, 2008), p.359-377.

Toth P, Vigo D: An Exact Algorithm for the Vehicle Routing Problem with Backhauls. Transportation Science, vol.31(1997), No.4, p.372-385.

Min H: The Multiple Vehicle Routing Problem with Simultaneous Delivery and Pick-up Points, Transportation Research Part A General, vol.23(1989), No.5, p.377-386.

Dethloff J: Vehicle Routing and Reverse Logistics: The Vehicle Routing Problem with Simultaneous Delivery and Pick-up, OR Spektrum, vol.23 (2001), No.1, p.79-96.