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

Решение стохастической задачи о приемке и доставке грузов с временными ограничениями методом адаптивного поиска

Авторы

  • Н. В. Царьков

Ключевые слова:

задача о приёмке и доставке
временные окна
стохастическое время проезда
стохастическое время обслуживания
адаптивный поиск в больших окрестностях
эвристический алгоритм

Аннотация

В работе рассматривается задача о приемке и доставке грузов с временными ограничениями, в которой время проезда между пунктами зависит от момента выезда и является случайной величиной, а время обслуживания в пунктах также считается случайным. Для решения задачи предлагается эвристический алгоритм на основе адаптивного поиска в больших окрестностях. При проверке выполнимости маршрута в алгоритме учитываются временные окна, ограничения на вместимость, вероятности своевременного прибытия в каждый пункт и вероятности успешного выполнения всех маршрутов. Вычислительные эксперименты показывают, что предложенный подход существенно быстрее точной смешанно-целочисленной линейной модели и на сопоставимых сценариях дает решения с тем же значением целевой функции либо с малым относительным отклонением. Проводится анализ влияния гиперпараметров, стохастичности, функций скорости и требований к надежности на время счета и качество решения.


Загрузки

Опубликован

2026-11-10

Выпуск

Том 27 (2026): Выпуск 4.

Раздел

Методы и алгоритмы вычислительной математики и их приложения

Автор

Н. В. Царьков

Московский государственный университет имени М.В. Ломоносова, факультет вычислительной математики и кибернетики

• аспирант

Библиографические ссылки

  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

Лицензия

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

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.