On methods for solving pickup and delivery problem with time windows. Part I: exact approach

Nikita Tsarkov, Dmitry Golembiovsky

Abstract


The paper considers an exact approach based on the branch-and-cut method to solve the pickup and delivery problem with time windows (PDPTW), an important class of vehicle routing problems in transportation logistics. Four mathematical formulations are analyzed in detail: 3-index, 2- index with pairwise and order constraints, compact 2-index and asymmetric representatives one, each of which has its own characteristics in terms of computational complexity and symmetry of solutions. Numerical experiments based on a modified Li & Lim dataset demonstrate that the compact 2- index formulation has the lowest computational complexity and the best speed of finding the exact solution, especially when using efficient ILP solvers. The paper is aimed at researchers and professionals interested in applying exact methods to solve PDPTW.

Full Text:

PDF (Russian)

References


Toth, P., & Vigo, D. (2002). An Overview of Vehicle Routing Problems. The Vehicle Routing Problem, 1–26.

Laporte, G. (2009). Fifty Years of Vehicle Routing. Transportation Science, 43(4), 408–416.

Semet, F., & Taillard, E. (1993). Solving real-life vehicle routing problems efficiently using tabu search. Annals of Operations Research, 41(4), 469–488.

Pisinger, D., & Ropke, S. (2007). A general heuristic for vehicle routing problems. Computers & Operations Research, 34(8), 2403–2435.

Naccache, S., Côté, J.-F., & Coelho, L. C. (2018). The multi-pickup and delivery problem with time windows. European Journal of Operational Research, 269(1), 353–362.

Mancini, S. (2016). A real-life multi depot multi period vehicle routing problem with a heterogeneous fleet: Formulation and adaptive large neighborhood search based methaeuristic. Transportation Research Part C: Emerging Technologies, 70, 100–112.

Cordeau, J.-F. & Maischberger, M. (2012). A parallel iterated tabu search heuristic for vehicle routing problems. Computers & Operations Research, 39(9), 2033–2050.

Ropke, S., & Pisinger, D. (2006). An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows. Transportation Science, 40(4), 455–472.

P. Shaw. (1998). Using constraint programming and local search methods to solve vehicle routing problems. International Conference on Principles and Practice of Constraint Programming, 417–431.

Aziez, I., Côté, J.-F., & Coelho, L. C. (2020). Exact algorithms for the multi-pickup and delivery problem with time windows. European Journal of Operational Research, 284(3), 906–919

Cordeau, J.-F. (2006). A Branch-and-Cut Algorithm for the Dial-a-Ride Problem. Operations Research, 54(3), 573-586.

Ropke, S., and Cordeau, J. F. (2009). Branch and cut and price for the pickup and delivery problem with time windows. Transportation Science, 43, 267–286.

Ropke, S. & Cordeau, J.-F. (2007). Models and branch-and-cut algorithms for pickup and delivery problems with time windows. Networks, 49(4), 258-272.

Lu, Q., & Dessouky, M. (2004). An exact algorithm for the multiple vehicle pickup and delivery problem. Transportation Science, 38, 503–514.

Furtado, M. G. S., Munari, P., & Morabito, R. (2017). Pickup and delivery problem with time windows: A new compact two-index formulation. Operations Research Letters, 45(4), 334–341.

Ascheuer, N., Fischetti, M., & Grötschel, M. (2001). Solving the asymmetric travelling salesman problem with time windows by branch-and-cut. Mathematical Programming, 90(3), 475–506.

Li, H & Lim, A. (2001). A metaheuristic for the pickup and delivery problem with time windows. International Journal of Artificial Intelligence Tools, 12(2), 160–170.

Набор данных Li & Lim Benchmark. [Электронный ресурс]. URL: https://www.sintef.no/projectweb/top/pdptw/li-lim-benchmark/ (дата обращения: 01.02.2025)

D. Ge, Q. Huangfu, Z. Wang, J. Wu and Y. Ye. (2023). Cardinal Optimizer (COPT) user guide. [Электронный ресурс]. URL: https://guide.coap.online/copt/en-doc (дата обращения 01.02.2025)

Baldacci, R., Bartolini, E., & Mingozzi, A. (2011). An Exact Algorithm for the Pickup and Delivery Problem with Time Windows. Operations Research, 59(2), 414–426.

Sartori, C. S., & Buriol, L. S. (2020). Instances for the Pickup and Delivery Problem with Time Windows based on open data. Mendeley Data, V2. [Электронный ресурс]. URL: https://data.mendeley.com/datasets/wr2ct4r22f/2 (дата обращения 01.02.2025)


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность ИБП для ЦОД СНЭ

ISSN: 2307-8162