До класифiкацiї задач маршрутизацiї транспортних засобiв

Л. Ф. Гуляницький; А. А. Коткова

doi:10.24144/2616-7700.2020.1(36).73-84

Автор(и)

Л. Ф. Гуляницький Iнститут кiбернетики iм. В.М. Глушкова НАН України, Київ, Україна https://orcid.org/0000-0002-1379-4132
А. А. Коткова НТУУ «Київський полiтехнiчний iнститут iменi Iгоря Сiкорського», Київ,, Україна https://orcid.org/0000-0003-4163-1442

DOI:

https://doi.org/10.24144/2616-7700.2020.1(36).73-84

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

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

Анотація

Суть розглянутих задач полягає у розробцi маршрутiв для групи гетерогенних транспортних засобiв, якi базуються у певному мiсцi чи мiсцях (депо) i мають доставити товари клiєнтам згiдно їх обсягами замовлень. Класична задача маршрутизацiї транспортних засобiв вiдноситься до задач комбiнаторної оптимiзацiї, якi можна подати у виглядi графу, у якого множина вершин вiдображає як депо, так i точки доставки, тобто клiєнтiв, а множина ребер вiдповiдає шляхам. У цiй задачi вважаються заданими: матриця ваг ребер мiж вершинами, що визначаються вартостями/довжинами
шляхiв; кiлькiсть транспортних засобiв, задiяних у доставцi товару; обсяги товару, що має постачатися клiєнтам у кожну точку доставки.

Актуальнiсть задачi маршрутизацiї транспортних засобiв спричинила появу багаточисельних її дослiджень, якi проводилися протягом останнiх десятилiть, та вiдповiдних публiкацiй. При формуваннi наведеного в статтi перелiку наукових публiкацiй автори не ставили мету подати iсторичний ракурс дослiдження маршрутизацiї транспортних засобiв (вiн досить повно вiдображається в бiльшостi робiт), а надавали перевагу публiкацiям останнiх рокiв, якi дають картину актуальних нинi дослiджень.

У бiльшостi реальних задач маршрутизацiї транспортних засобiв присутнi додатковi обмеження, що породжують цiлий спектр нових задач. У роботi наведено низку класiв задач маршрутизацiї транспортних засобiв. Основним обмеженням є вантажопiдйомнiсть, а критерiєм – загальна вартiсть перевезень. У задачах маршрутизацiї з часовими обмеженнями або «часовими вiкнами» мiнiмiзацiя загальної вартостi перевезень поєднується з мiнiмiзацiєю кiлькостi задiяних транспортних засобiв та загального часу очiкування клiєнтами транспортних засобiв. Мiнiмiзацiя вартостi перевезень i
розмiру парку залучених транспортних засобiв може вiдбуватися i у випадку, коли цi транспортнi засоби вирушають iз декiлькох депо, причому як старт, так i завершення маршруту може вiдбуватися не у фiксованих, а iз/в альтернативних, зокрема, динамiчних депо. Розглядаються також проблеми маршрутизацiї за можливостi поверненням i доставкою товарiв, маршрутизацiя з двовимiрними обмеженнями завантаження транспортних засобiв, максимiзацiя заощаджень вiд перевезення товару, з рiзними видами транспорту, перiодична маршрутизацiя, з випадковими даними, з можливiстю
дозавантаження з дотриманням заданого термiну доставляння. Для кожного типу задач наведено додатковi обмеження, що вiдрiзняють їх вiд класичної задачi.

Посилання

Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80–91.

Toth, P., & Vigo, D. (Eds.) (2014). Vehicle Routing: Problems, Methods, and Applications, Second Edition. (MOS-SIAM Series on Optimization; No. 18). Philadelpia: SIAM.

Golden, B. L., Raghavan, S., Wasil, E. A. (Eds.). (2008). The vehicle routing problem: latest advances and new challenges (Vol. 43). Springer Science & Business Media.

Doerner, K., & Schmid, V. (2010). Survey: Matheuristics for rich vehicle routing problems. In M. Blesa, C. Blum, G. Raidl, A. Roli, & M. Sampels (Eds.) Hybrid metaheuristics. Lecture notes in computer science. Vol. 6373 (pp. 206–221). Berlin, Heidelberg: Springer.

Hulianytskyi, L. F., & Mulesa, O.Y. (2016). Applied methods of combinatorial optimization. Kyiv.: Vydavnycho-polihrafichnyi centr "Kyivskyi universytet"[in Ukrainian].

Braekers, K., Ramaekers, K., & Nieuwenh, I. V. (2016). The Vehicle Routing Problem: State of the Art Classification and Review. Computers & Industrial Engineering, 99, 300–313.

Eduardo, U., Diego, P. (2017). New benchmark instances for the Capacitated Vehicle Routing Problem. European Journal of Operational Research, 257, 3, 845–858.

Soysal, M., Bloemhof, J. M., & Bektas, T. (2015). The time-dependent two-echelon capacitated vehicle routing problem with environmental considerations. International Journal of Production Economics, 164, 366–378.

Ehsan, T., & Vahid, K. (2016). Enhanced intelligent water drops and cuckoo search algorithms for solving the capacitated vehicle routing problem. Information Sciences, 334, 354–378.

Maurizio, B., & Ferdinando, P. (2015). A Variable Neighborhood Search Branching for the Electric Vehicle Routing Problem with Time Windows. Electronic Notes in Discrete Mathematics, 47, 221–228.

Ilker, K., & Nursel, O. (2015). An advanced hybrid meta-heuristic algorithm for the vehicle routing problem with backhauls and time windows. Computers & Industrial Engineering, 86, 60–68.

Bin, Y., & Zhi-Hua H. (2015). Routing with time-windows for multiple environmental vehicle types. Computers & Industrial Engineering, 89, 150–161.

Li, J., Li, Y., & Pardalos, P. M. (2016). Multi-depot vehicle routing problem with time windows under shared depot resources. Journal of Combinatorial Optimization, 31(2), 515–532.

Montoya-Torres, J. R., Franco, J. L., Isaza, S. N., Jim´ enez, H. F., & Herazo-Padilla, N. (2015). A literature review on the vehicle routing problem with multiple depots. Computers & Industrial Engineering, 79, 115–129.

De Oliveira, F. B., Enayatifar, R., Sadaei, H. J., Guimar˜ aes, F. G., & Potvin, J. Y. (2016). A cooperative coevolutionary algorithm for the Multi-Depot Vehicle Routing Problem.Expert Systems with Applications, 43, 117–130.

Jairo, R. M.-T., Julian, L. F., & Santiago, N. I. (2015). A literature review on the vehicle routing problem with multiple depots. Computers & Industrial Engineering, 79, 115–129.

Li, J., Li, Y., & Panos, M. P. (2016). Multi-depot vehicle routing problem with time windows under shared depot resources. Journal of Combinatorial Optimization, 31, 2, 515–532.

Tania, R.P.R., Maria, I.G., & Ana B.P. (2019). Multi-depot vehicle routing problem: a comparative study of alternative formulations. International Journal of Logistics Research and Applications. Retrieved from https://www.tandfonline.com/loi/cjol20

Chávez, J. J. S., Escobar, J. W., & Echeverri, M. G. (2016). A Multiobjective Pareto and Colony Algorithm for the Multi-depot Vehicle Routing Problem with Backhauls. International Journal of Industrial Engineering Computations, 7, 35–48.

Zhang, Y., Qi, M., Miao L., & Wu, G. (2015). A Generalized Multi-depot Vehicle Routing Problem with Replenishment Based on LocalSolver. International Journal of Industrial Engineering Computations, 6, 81–98.

Braekers, K., Ramaekers, K., & Nieuwenh, I. V. (2016). The Vehicle Routing Problem: State the Art Classification and Review. Computers & Industrial Engineering, 99, 300–313.

Baldacci, R., Battarra, M., & Vigo, D. (2008). Routing a heterogeneous fleet of vehicles. In B. L. Golden, S. Raghavan, & E. Wasil (Eds.), The vehicle routing problem: latest advances and new challenges (pp. 3–27). Berlin: Springer. Vol. 43.

Saso, K., & Vili, P. (2015). A survey of genetic algorithms for solving multi depot vehicle routing problem. Applied Soft Computing, 27, 519–532.

Li, J., Li, Y., & Pardalos, P. M. (2016). Multi-depot Vehicle Routing Problem with Time Windows Under Shared Depot Resources. Journal of Combinatorial Optimization, 31, 515–532.

Bezerra, S. N., De Souza, S. R., & Souza, M. J. F. (2018). A GVNS Algorithm for Solving the Multi-depot Vehicle Routing Problem. Electronic Notes in Discrete Mathematics, 66, 167–174.

Horbulin, V.P., Hulianytskyi, L.F., & Serhienko, S.V. (2019). Formulations and Mathematical Models of the Optimizing Routes Problems for Aircraft with Dynamic Depots. Control systems & computers, 1, 3–10 [in Russian].

Hulianytskyi, L. F., & Storchevyi, V. V. (2019). One special problem of UAV routing, Scientific Bulletin of Uzhhorod University. Series of Mathematics and Informatics, 1(34), 60–78 [in Ukrainian].

Horbulin, V.P., Hulianytskyi, L.F., & Sergienko, I.V. (2020). Optimization of UAV team routes at the availablity of alternative and dynamic depots. Cybernetics and System analysis, 2, 31–41 [in Ukrainian].

Mustafa, A., & Seyda, T. (2015). An adaptive local search algorithm for vehicle routing problem with simultaneous and mixed pickups and deliveries. Computers & Industrial Engineering, 83, 15–29.

Baozhen, Y., & Bin, Y. (2016). An improved particle swarm optimization for carton heterogeneous vehicle routing problem with a collection depot. Annals of Operations Research, 242, 2, 303–320.

Meryem, B., & Abdelmadjid, B. (2016). Quantum Inspired Algorithm for a VRP with Heterogeneous Fleet Mixed Backhauls and Time Windows. International Journal of Applied Metaheuristic Computing, 21.

Lijun, W., & Zhenzhen, Z. (2015). A variable neighborhood search for the capacitated vehicle routing problem with two-dimensional loading constraints. European Journal of Operational Research, 16, 798–814.

Emmanouil, E., & Christos, D. (2016). The Vehicle Routing Problem with Simultaneous Pickups and Deliveries and Two-Dimensional Loading Constraints. European Journal of Operational Research, 251, 2, 369–386.

Cagri, K., & Gilbert, L. (2018). Vehicle routing with backhauls: Review and research perspectives. Computers & Operations Research, 91, 79–91.

Sebastian, R., & Andreas, B. (2018). Heuristics for vehicle routing problems with backhaul, time windows, and 3D loading constraints. European Journal of Operational Research, 266, 3, 877–894.

Joungsung, L., & Byung-In, K. (2015). Industrial ship routing problem with split delivery and two types of vessels. Expert Systems with Applications, 42, 22, 9012–9023.

James, C., & Shangyao, Y. (2017). A Multi-Trip Split-Delivery Vehicle Routing Problem with Time Windows for Inventory Replenishment Under Stochastic Travel Times. Networks and Spatial Economics, 17, 1, 41–68.

Mohammad, M.-J., & Seokcheon, L. (2016). The customer-centric, multi-commodity vehicle routing problem with split delivery. Expert Systems with Applications, 56, 335–348.

Florent, H., & Michel, G. (2017). Heuristics for tactical time slot management: a periodic vehicle routing problem view. International Transactions in Operational Research. 6(24), 1233–1252.

Ulrike, R., & Jakob, P. (2015). A survey on dynamic and stochastic vehicle routing problems. International Journal of Production Research, 54, 215–231

Briseida, S., & Karl, F. (2016). Variable neighborhood search for the stochastic and dynamic vehicle routing problem. Annals of Operations Research, 236, 2, 425–461

Iliya, M., & Sacha, V. (2016). Integrating a heterogeneous fixed fleet and a flexible assignment of destination depots in the waste collection VRP with intermediate facilities. Transportation Research Part B: Methodological, 84, 256–273.

Cagri, K., & Ismail, K. (2016). The green vehicle routing problem: A heuristic based exact solution approach. Applied Soft Computing, 39, 154–164.