Метод розв'язання періодичної задачі маршрутизації транспортних засобів

М.М. Ленський; Г.Й. Михальчук; Т.Г. Ємел’яненко

Метод розв'язання періодичної задачі маршрутизації транспортних засобів

М.М. Ленський, Г.Й. Михальчук, Т.Г. Ємел’яненко

Анотація

Розглянуто підходи до розв'язання періодичної задачі маршрутизації транспортних засобів. Запропоновано евристичний метод для розв'язання періодичної задачі маршрутизації з часовими вікнами, який ґрунтується на концепції локального пошуку. Розроблено програмне забезпечення, що реалізує запропонований метод, та дозволяє будувати маршрути для заданого періоду планування.

Ключові слова

періодична задача маршрутизації транспортних засобів; часові вікна; евристики; метод локального пошуку

Повний текст:

PDF

Посилання

Toth P. and Vigo D., editors. Vehicle Routing: Problems, Methods, and Applications // Society for Industrial and Applied Mathematics, Philadelphia, 2 edition. 2014. 481 р.

Cordeau J-F, Laporte G, Savelsbergh MWF, Vigo D. Vehicle routing. Barnhart C, Laporte G, eds. // Transportation. Handbooks in Operations Research and Management Science (North-Holland, Amsterdam). 2007. Р. 367–428.

Laporte G. Fifty years of vehicle routing. Transportation Sci. 2009. Vol. 43(4). P. 408–416.

Archetti C., Fernandez E., Huerta-Munoz D.L. The Flexible Periodic Vehicle Routing Problem // Computers and Operations Research. 2017. Vol. 85. P. 58–70.

Archetti C., Fernandez E., Huerta-Munoz D.L. A two-phase solution algorithm for the Flexible Periodic Vehicle Routing Problem // Computers and Operations Research. 2018. Vol. 99. P. 27–37.

Rodriguez-Martin I., Salazar-Gonzalez J.J., Yaman H. The periodic vehicle routing problem with driver consistency // European Journal of Operational Research. 2019. Vol. 273, Issue 2. P. 575–584.

Rahimi-Vahed A., Crainic T.G., Gendreau M., Rei W. Fleet-sizing for multi-depot and periodic vehicle routing problems using a modular heuristic algorithm // Computers & Operations Research. 2015. Vol. 53. P. 9–23.

Baldacci R., Bartolini E., Mingozzi A., Valletta A. An Exact Algorithm for the Period Routing Problem // Operations Research. 2011. Vol. 59. P. 228–241.

Rothenbächer A.K. Branch-and-Price-and-Cut for the Periodic Vehicle Routing Problem with Flexible Schedule Structures. Transportation science. 2019. Vol. 53. P. 850–866.

Cacchiani V., Hemmelmayr V.C., Tricoire F. A set-covering based heuristic algorithm for the periodic vehicle routing problem // Discrete Applied Mathematics. 2014. Vol. 163, Part 1. P. 53–64.

Wang Y., Wang L., Chen G., Cai Z., Zhou Y., Xing L. An Improved Ant Colony Optimization algorithm to the Periodic Vehicle Routing Problem with Time Window and Service Choice // Swarm and Evolutionary Computation. 2020. Vol. 55.

Norouzi N., Sadegh-Amalnick M., Alinaghian M. Evaluating of the particle swarm optimization in a periodic vehicle routing problem // Measurement. 2015. Vol. 62. P. 162–169

Vidal T, Crainic T.G., Gendreau M., Lahrichi N., Rei W. A Hybrid Genetic Algorithm for Multidepot and Periodic Vehicle Routing Problems // Operations Research. 2012. Vol. 60. P. 611–624.

Hougardy S., Zaiser F., Zhong X. The Approximation Ratio of the 2-Opt Heuristic for the Metric Traveling Salesman Problem // Operations Research Letters. 2020. Vol. 48, Issue 4. P. 401–404.

Toro E., Escobar A., Granada M. Literature review on the vehicle routing problem in the green transportation context // Luna Azul. 2016. No 42. P. 362–387.