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

DOI: https://doi.org/10.17308/sait.2021.1/3368
Ключевые слова: задача маршрутизации, дискретная модель, метод ветвей и границ, оценка множества

Аннотация

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

Скачивания

Данные скачивания пока не доступны.

Биография автора

Сергей Николаевич Медведев, Воронежский государственный университет

канд. физ.-мат. наук, доц., доцент кафедры вычислительной математики и прикладных информационных технологий факультета прикладной математики, информатики и механики Воронежского государственного университета.

Литература

1. Lenstra J. K. & Kan H. G. (1981) Complexity of vehicle routing and scheduling problemsm // Networks. 11(2). P. 221–227. Available from: DOI
2. Amberg A., Domschke W. & Voss S. (2000) Multiple center capacitated arc routing problems : A tabu search algorithm using capacitated trees // European Journal of Operational Research. 124.P. 360–376. Available from: DOI
3. Ishkov S. A. & Ishkova E. S. (2011) Matrix approach in solving the routing problem with several vehicles // Bulletin of the Samara Scientific Center of the Russian Academy of Sciences. 13(4). P. 189–164.
4. Ekici A., Özener O. & Kuyzu G. (2015) Cyclic Delivery Schedules for an Inventory Routing Problem // Transportation Science. 49(4). P. 817–829. Available from: DOI
5. I-Ming Ch., Golden B. & Wasil E. (1996) The Team Orienteering Problem // European Journal of Operational Research. 88(3). P. 464–474. Available from: DOI
6. Santos L., Coutinho-Rodriguesa J. & Currentb J. R. (2009) An improved heuristic for the capacitated arc routing problem // Computers and Operations Research. 6. P. 2632–2637. Available from: DOI
7. Tang K., Wang J., Li X. & Yao X. (2017) A Scalable Approach to Capacitated Arc Routing Problems Based on Hierarchical Decomposition // in IEEE Transactions on Cybernetics. 47(11). P. 3928–3940. Available from: DOI
8. Domínguez-Martín B., Rodríguez-Martín I. & Salazar-González J.-J. (2018) The driver and vehicle routing problem // Computers & Operations Research. 92. P. 56–64. Available from: DOI
9. Grigoriev V. P. & Kiselev K. A. (2007) Routing of delivery of retail products in the urban road network based on a genetic algorithm // Bulletin of the Tomsk Polytechnic University. 310(2). P. 195–199. (in Russian)
10. Medvedev S., Sorokina A. & Medvedeva O. (2019) The vehicle routing problem for several agents among the objects of two types // In: XXI International Conference Complex Systems: Control and Modeling Problems, CSCMP 2019, 3-6 September 2019, Samara, Russia. P. 535–540. Available from: DOI
11. Pozhidaev M. S. (2010) Algorithms for solving the problem of routing transport. Abstract PhD thesis. Tomsk State University. (in Russian)
12. Medvedev S. (2020) Comparative analysis of the exact and heuristic algorithms for solving the vehicle routing problem for several agents among the objects of two types // In: 2nd International Conference on Control Systems, Mathematical Modeling, Automation and Energy Efficiency, SUMMA 2020, 11-13 November 2020, Lipetsk, Russia. P. 817–822. Available from: DOI
13. Medvedev S. N., Medvedeva O. A., Zueva Y. R. & Chernyshova G. D. (2019) Formulation and algorithmization of the interleaved vehicle routing problem // Journal of Physics: Conference Series. 1203 (012053), 15. Available from: DOI
14. Korbut A. A. & Finkelstein Yu. Yu. (1969) Discrete programming, ed. D. B. Yudin. Moscow, Nauka.
Опубликован
2021-04-29
Как цитировать
Медведев, С. Н. (2021). Математическая модель и алгоритм решения задачи маршрутизации транспортных средств с несколькими центрами с чередованием и единым местом сбора. Вестник ВГУ. Серия: Системный анализ и информационные технологии, (1), 21-32. https://doi.org/10.17308/sait.2021.1/3368
Выпуск
№ 1 (2021): Январь – Март
Раздел
Математические методы системного анализа и управления
  1. Авторы сохраняют за собой авторские права и предоставляют журналу право первой публикации работы, которая по истечении 6 месяцев после публикации автоматически лицензируется на условиях Creative Commons Attribution License , которая позволяет другим распространять данную работу с обязательным сохранением ссылок на авторов оригинальной работы и оригинальную публикацию в этом журнале.
  2. Авторы имеют право размещать их работу в сети Интернет (например в институтском хранилище или персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу (См. The Effect of Open Access).
Crossref
Scopus
Google Scholar
Europe PMC