рус eng
«ИЗВЕСТИЯ ИРКУТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА». СЕРИЯ «МАТЕМАТИКА»
«IZVESTIYA IRKUTSKOGO GOSUDARSTVENNOGO UNIVERSITETA». SERIYA «MATEMATIKA»
«THE BULLETIN OF IRKUTSK STATE UNIVERSITY». SERIES «MATHEMATICS»
ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

Список выпусков > Серия «Математика». 2024. Том 48

Модели и алгоритмы локального поиска для маршрутизации транспортных средств с возвратами и временными окнами

Автор(ы)
Л. А. Заозерская1, Ю. В. Захарова1

1Институт математики им. С. Л. Соболева СО РАН, Омск, Российская Федерация

Аннотация
Рассматривается задача маршрутизации транспортных средств для обслуживания объектов с возможностью распределения работ и учетом временных окон. Обсуждаются подходы к построению моделей целочисленного линейного программирования и их модификаций. Для поиска приближенных решений предлагается алгоритм локального поиска с «большими» окрестностями, где на каждом шаге осуществляется поиск улучшающего решения при помощи стратегий «сломай» и «почини». Строятся серии тестовых примеров различной структуры, в том числе демонстрируется целесообразность рассмотрения постановки с возвратами транспортных средств на объекты. Представлены результаты экспериментального исследования моделей и алгоритмов.
Об авторах

Заозерская Лидия Анатольевна, канд. физ.-мат. наук, доц., Институт математики им. С. Л. Соболева СО РАН, Омск, 644090, Российская Федерация, zaozer@ofim.oscsbras.ru

Захарова Юлия Викторовна, канд. физ.-мат. наук, Институт математики им. С. Л. Соболева СО РАН, Омск, 644090, Российская Федерация, yzakharova@ofim.oscsbras.ru

Ссылка для цитирования
Заозерская Л. А., Захарова Ю. В. Модели и алгоритмы локального поиска для маршрутизации транспортных средств с возвратами и временными окнами // Известия Иркутского государственного университета. Серия Математика. 2024. Т. 48. C. 95–110. https://doi.org/10.26516/1997-7670.2024.48.95
Ключевые слова
маршрутизация, локальный поиск, целочисленное программирование, модель
УДК
519.8+519.6
MSC
90C59, 68W20
DOI
https://doi.org/10.26516/1997-7670.2024.48.95
Литература
  1. Еремеев А. В., Заозерская Л. А., Захарова Ю. В. Исследование моделей целочисленного программирования для задачи маршрутизации буровых установок с возвратами и временными окнами // PREPRINTS.RU. 2022. https://doi.org/10.24108/preprints-3112582
  2. Кулаченко И. Н., Кононова П. А. Гибридный алгоритм решения задачи маршрутизации буровых установок // Дискретный анализ и исследование операций. 2021. Т. 28, вып. 2. С. 35–59. https://doi.org/10.33048/daio.2021.28.703
  3. Bezerra S. N., Souza M. J. F., de Souza S. R. A variable neighborhood search-based algorithm with adaptive local search for the Vehicle Routing Problem with Time Windows and multi-depots aiming for vehicle fleet reduction // Comp. & Oper. Res. 2023. Vol. 149. 106016. https://doi.org/10.1016/j.cor.2022.106016
  4. Blum C., Eremeev A. V., Zakharova Y. V. Hybridizations of evolutionary algorithms with Large Neighborhood Search // Comp. Sci. Rev. 2022. Vol. 46. 100512. https://doi.org/10.1016/j.cosrev.2022.100512
  5. Rig routing with possible returns and stochastic drilling times / P. Borisovsky, A. Eremeev, Y. Kovalenko, L. Zaozerskaya // Proc. of Mathematical Optimization Theory and Operations Research. MOTOR 2021. LNCS. 2021. Vol. 12755. P. 51–66. https://doi.org/10.1007/978-3-030-77876-7_4
  6. Borisovsky P. A parallel greedy approach enhanced by genetic algorithm for the stochastic rig routing problem // Opt. Let. OnLine-First. 2023. P. 235–255. https://doi.org/10.1007/s11590-023-01986-x
  7. Groer C., Golden B., Wasil E. A library of local search heuristics for the vehicle routing problem // Math. Prog. Comp. 2010. Vol. 2. P. 79–101. https://doi.org/10.1007/s12532-010-0013-5
  8. Modeling and solving a multi-trip multi-distribution center vehicle routing problem with lower-bound capacity constraints / V. S. Nguyen, Q. D. Pham, T. H. Nguyen, Q. T. Bui // Comp. and Ind. Eng. 2022. Vol. 172, Part A. 108597. https://doi.org/10.1016/j.cie.2022.108597
  9. Sadati M. E. H., Akbari V., ¸Catay B. Electric vehicle routing problem with flexible deliveries // Int. Jour. of Prod. Res. 2022. Vol. 60, N 13. P. 4268–4294. https://doi.org/10.1080/00207543.2022.2032451
  10. Solving vehicle routing problem by memetic search with evolutionary multitasking / Q. Shang, Y. Huang, Y. Wang [et al.] // Memetic Comp. 2022. Vol. 14. P. 31–44. https://doi.org/10.1007/s12293-021-00352-7
  11. A simulated annealing algorithm for the vehicle routing problem with parcel lockers / V. F. Yu, H. Susanto, P. Jodiawan, T.-W. Ho, S.- W. Lin, Y.-T. Huang // IEEE Access. 2022. Vol. 10. P. 20764–20782. https://doi.org/10.1109/ACCESS.2022.3152062

Полная версия (русская)