https://doi.org/10.26089/NumMet.v27r441

A Solution of a stochastic pickup and delivery problem with time windows by the adaptive large neighborhood search

Authors

  • Nikita V. Tsarkov

Keywords:

pickup and delivery problem
time windows
stochastic travel times
stochastic service time
adaptive large neighborhood search
heuristic algorithm

Abstract

The paper considers a stochastic pickup and delivery problem with time windows, where the travel time depends on the departure time and is a random variable, and the service time is also assumed to be random. A heuristic algorithm based on the adaptive large neighborhood search is proposed. Its route-feasibility test accounts for time windows, vehicle capacity, the probabilities of on-time arrival at each node, and the probabilities of successfully completing all routes. Computational experiments show that the proposed approach is substantially faster than an exact mixed-integer linear programming model and, in comparable scenarios, yields solutions with the same objective value or a small relative deviation. The impact of hyperparameters, stochasticity, speed profiles, and reliability requirements on the computation time and solution quality is analyzed.


Downloads

Published

2026-11-10

Issue

Vol. 27 (2026): Issue 4.

Section

Methods and algorithms of computational mathematics and their applications

Author

Nikita V. Tsarkov

Lomonosov Moscow State University, Faculty of Computational Mathematics and Cybernetics

• PhD Student

References

  1. M. M. Solomon, “Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints,” Operations Research 35 (2), 254–265 (1987).
    doi 10.1287/opre.35.2.254
  2. K. Braekers, K. Ramaekers, and I. Van Nieuwenhuyse, “The Vehicle Routing Problem: State of the Art Classification and Review,” Computers & Industrial Engineering 99, 300–313 (2016).
    doi 10.1016/j.cie.2015.12.007
  3. S. Ropke and D. Pisinger, “An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows,” Transportation Science 40 (4), 455–472 (2006).
    doi 10.1287/trsc.1050.0135
  4. N. V. Tsarkov and D. Yu. Golembiovsky, “A Review of Methods for Solving the Pickup and Delivery Problem with Time Windows. Part II: A Heuristic Approach,” International Journal of Open Information Technologies 13 (9), 91–102 (2025). [in Russian].
  5. I. Aziez, J.-F. Côté, and L. C. Coelho, “Exact Algorithms for the Multi-Pickup and Delivery Problem with Time Windows,” European Journal of Operational Research 284 (3), 906–919 (2020).
    doi 10.1016/j.ejor.2020.01.040
  6. Y. Dumas, J. Desrosiers, and F. Soumis, “The Pickup and Delivery Problem with Time Windows,” European Journal of Operational Research 54 (1), 7–22 (1991).
    doi 10.1016/0377-2217(91)90319-Q
  7. G. Desaulniers, J. Desrosiers, and M. M. Solomon (eds.), Column Generation(Springer, New York, 2005).
    doi 10.1007/b135457
  8. E. M. Bronshtein, E. V. Gindullina, and R. V. Gindullin, “Formalization of Pickup and Delivery Problem,” Vestn. Yuzhno-Ural. Gos. Un-ta. Ser. Matem. Mekh. Fiz. 9 (1), 13–21 (2017). [in Russian].
    doi 10.14529/mmph170102
  9. W. P. Nanry and J. W. Barnes, “Solving the Pickup and Delivery Problem with Time Windows Using Reactive Tabu Search,” Transportation Research Part B: Methodological 34 (2), 107–121 (2000).
    doi 10.1016/S0191-2615(99)00016-8
  10. H. Li and A. Lim, “A Metaheuristic for the Pickup and Delivery Problem with Time Windows,” in Proc. 13th IEEE Int. Conf. on Tools with Artificial Intelligence. ICTAI 2001, Dallas, TX, USA, November 07–09, 2001(IEEE Press, 2001), pp. 160–167.
    doi 10.1109/ICTAI.2001.974461
  11. P. Shaw, “Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems,” in Principles and Practice of Constraint Programming–CP98, Pisa, Italy, October 26–30, 1998.Lecture Notes in Computer Science, Vol. 1520. (Springer, Berlin, 1998), pp. 417–431.
    doi 10.1007/3-540-49481-2_30
  12. A. D. Yus’kov, I. N. Kulachenko, A. A. Mel’nikov, and Y. A. Kochetov, “A Hybrid Algorithm for a Two-Objective Traffic Engineering Problem,” Diskretn. Anal. Issled. Oper. 32 (3), 117–144 (2025).
    doi 10.33048/daio.2025.32.827
  13. D. Pisinger and S. Ropke, “A General Heuristic for Vehicle Routing Problems,” Computers & Operations Research 34 (8), 2403–2435 (2007).
    doi 10.1016/j.cor.2005.09.012
  14. M. Gendreau, G. Laporte, and R. Séguin, “Stochastic Vehicle Routing,” European Journal of Operational Research 88 (1), 3–12 (1996).
    doi 10.1016/0377-2217(95)00050-X
  15. U. M. Ritzinger, J. Puchinger, and R. F. Hartl, “A Survey on Dynamic and Stochastic Vehicle Routing Problems,” International Journal of Production Research 54 (1), 215–231 (2016).
    doi 10.1080/00207543.2015.1043403
  16. J. Oyola, H. Arntzen, and D. L. Woodruff, “The Stochastic Vehicle Routing Problem, a Literature Review, Part I: Models,” EURO Journal on Transportation and Logistics 7 (3), 193–221 (2018).
    doi 10.1007/s13676-016-0100-5
  17. J. Cai, Q. Zhu, Q. Lin, et al., “A Survey of Dynamic Pickup and Delivery Problems,” Neurocomputing 554 (C), Article Number 126631 (2023).
    doi 10.1016/j.neucom.2023.126631
  18. V. Ghilas, E. Demir, and T. Van Woensel, “A Scenario-Based Planning for the Pickup and Delivery Problem with Time Windows, Scheduled Lines and Stochastic Demands,” Transportation Research Part B: Methodological 91 (C), 34–51 (2016).
    doi 10.1016/j.trb.2016.04.015
  19. P. Györgyi and T. Kis, “A Probabilistic Approach to Pickup and Delivery Problems with Time Window Uncertainty,” European Journal of Operational Research 274 (3), 909–923 (2019).
    doi 10.1016/j.ejor.2018.10.031
  20. S. Ichoua, M. Gendreau, and J.-Y. Potvin, “Vehicle Dispatching with Time-Dependent Travel Times,” European Journal of Operational Research 144 (2), 379–396 (2003).
    doi 10.1016/S0377-2217(02)00147-9
  21. P. Sun, L. P. Veelenturf, M. Hewitt, and T. Van Woensel, “The Time-Dependent Pickup and Delivery Problem with Time Windows,” Transportation Research Part B: Methodological 116, 1–24 (2018).
    doi 10.1016/j.trb.2018.07.002
  22. Z. Wang, M. Dessouky, T. Van Woensel, and P. Ioannou, “Pickup and Delivery Problem with Hard Time Windows Considering Stochastic and Time-Dependent Travel Times,” EURO Journal on Transportation and Logistics 12 (2), Article Number 100099 (2023).
    doi 10.1016/j.ejtl.2022.100099
  23. N. V. Tsarkov and D. Yu. Golembiovsky, “A Review of Methods for Solving the Pickup and Delivery Problem with Time Windows. Part I: An Exact Approach,” International Journal of Open Information Technologies 13 (7), 60–70 (2025). [in Russian].
  24. H. Jula, M. Dessouky, and P. A. Ioannou, “Truck Route Planning in Nonstationary Stochastic Networks with Time Windows at Customer Locations,” IEEE Transactions on Intelligent Transportation Systems 7 (1), 51–62 (2006).
    doi 10.1109/TITS.2006.869596
  25. COPT Cardinal Optimizer.
    https://www.shanshu.ai/copt Cited October 23, 2026.
  26. G. Hendel, “Adaptive Large Neighborhood Search for Mixed Integer Programming,” Mathematical Programming Computation 14, 185–221 (2022).
    doi 10.1007/s12532-021-00209-7

License

Copyright (c) 2026 Н. В. Царьков

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.