2024, випуск 2, c. 11-30
Одержано 06.03.2024; Виправлено 07.04.2024; Прийнято 28.05.2024
Надруковано 09.06.2024; Вперше Online 14.06.2024
https://doi.org/10.34229/2707-451X.24.2.2
Попередня | ПОВНИЙ ТЕКСТ | Наступна
Математичні моделі задачі побудови маршрутів доставки вантажів у внутрішніх зонах магістральних вузлів ієрархічної транспортної мережі
Інститут телекомунікацій і глобального інформаційного простору НАН України, Київ
* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
Вступ. У статті розглядаються математичні моделі задач побудови кільцевих маршрутів транспортних засобів у багатопродуктовій ієрархічній мережі. Як правило, такі мережі складаються з децентралізованої магістральної мережі та мереж у внутрішніх зонах обслуговування магістральних вузлів (внутрішні мережі). У багатопродуктових мережах кожен вузол може обмінюватися продуктами (товарами, вантажами) з іншими вузлами. На відміну від задач розподілу однорідного взаємозамінного продукту, у багатопродуктових задачах потоки продуктів не взаємозамінні, потік кожного продукту має бути доставлений з певного первинного об’єкта до конкретного клієнта. Передбачається, що багаторівнева структура транспортної мережі визначена і відомі географічне розташування магістральних вузлів та його внутрішні зони обслуговування з множиною вузлів доставки і збору вантажів (клієнтів). Тому задачі визначення магістральних маршрутів транспортних засобів та побудови кільцевих маршрутів внутрішніх транспортних засобів розглядаються незалежно одна від одної. Обговорюються види витрат реальних транспортних процесів, які мають враховуватися при формуванні цільової функції задач маршрутизації та запропоновані математичні моделі задач побудови кільцевих маршрутів доставки із неоднорідним парком транспортних засобів. Зазначається можливість розв’язання сформульованих задач за допомогою відомих пакетів змішаного та цілочислового лінійного програмування.
Мета роботи полягає у формулюванні нових математичних моделей задачі побудови кільцевих маршрутів транспортних засобів у внутрішніх мережах обслуговування магістральних вузлів, у яких враховуються реальні витрати транспортних процесів та географічні особливості внутрішніх мереж.
Методика досліджень заснована на системному аналізу багатьох сучасних моделей, методів та алгоритмів вирішення задач побудови кільцевих маршрутів для обслуговування клієнтів у внутрішніх зонах магістральних вузлів ієрархічній мережі.
Результати. На основі огляду та аналізу відомих математичних моделей розроблено декілька нових варіантів математичної постановки задач проектування маршрутів транспортних засобів для перевезення дискретних вантажів у внутрішніх зонах центральних вузлів мережі. Для вирішення поставлених завдань можуть бути використані точні, евристичні та метаевристичні методи і алгоритми, реалізовані в багатьох комерційних і некомерційних пакетах програм змішаного і цілочислового програмування, наприклад, IBM ILOG CPLEX, GAMS, AIMMS, Gurobi Optimizer, ABACUS, COIN-OR, GLPK, lp_solve. Багато з них доступні безкоштовно на сервері NEOS (https://neos-server.org/neos/).
Наукова новизна і практична значимість. Новизна роботи полягає у формулюванні математичних моделей задачі побудови кільцевих маршрутів транспортних засобів, у яких враховуються реальні витрати транспортних процесів та географічні особливості внутрішніх мереж. Матеріали статті формують методологічну основу для розробки сучасного математичного забезпечення розв'язання задач довгострокового, поточного та оперативного планування та управління у внутрішніх зонах магістральних вузлів глобальної ієрархічної мережі.
Ключові слова: задачі комбінаторної оптимізації, математичні моделі кільцевих маршрутів транспортних засобів.
Цитувати так: Vasyanin V., Ushakova L. Mathematical Models of the Problem of Constructing Delivery Routes of Cargo in the Internal Zones of Trunk Nodes of a Hierarchical Transport Network. Cybernetics and Computer Technologies. 2024. 2. P. 11–30. https://doi.org/10.34229/2707-451X.24.2.2
Список літератури
1. Lenstra J.K., Rinnooy Kan A.H.G. Complexity of vehicle routing and scheduling problems. Networks. 1981. No. 11. P. 221–227. https://doi.org/10.1002/net.3230110211
2. Laporte G. Fifty Years of Vehicle Routing. Canada Research Chair in Distribution Management, HEC Montr´eal, 2009. 23 p.
3. Dantzig G.B., Fulkerson D.R. Minimizing the number of tankers to meet a fixed schedule. Naval Research Logistics Quarterly. 1954. No. 1. P. 217–222. https://doi.org/10.1002/nav.3800010309
4. Kirby D. Is Your Fleet the Right Size? Operational Research Quarterly. 1959. No. 10. P. 252. https://doi.org/10.2307/3006624
5. Golden B.L., Assad A., Levy L., Gheysens F. The Fleet Size and Mix Vehicle Routing Problem. Computers & Operations Research. 1984. No. 11. P. 49–66. https://doi.org/10.1016/0305-0548(84)90007-8
6. Clarke G., Wright J.W. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research. 1964. Vol. 12. P. 568–581. https://doi.org/10.1287/opre.12.4.568
7. Salhi S., Rand G.K. Incorporating vehicle routing into the vehicle fleet composition problem. European Journal of Operational Research. 1993. No. 66. P. 313–330. https://doi.org/10.1016/0377-2217(93)90220-H
8. Osman I.H., Salhi S. Local Search Strategies for the Vehicle Fleet Mix Problem. Modern heuristic search methods. John Wiley & Sons, Chichester, UK, 1996. P. 131–153.
9. Lee Y.H., Kim J.I., Kang K.H., Kim K.H. A heuristic for vehicle fleet mix problem using tabu search and set partitioning. The Journal of the Operational Research Society. 2008. Vol. 59. No. 6. P. 833–841. https://doi.org/10.1057/palgrave.jors.2602421
10. Baldacci R., Battarra M., Vigo D. Routing a Heterogeneous Fleet of Vehicles. Technical Report DEIS OR. INGCE 2007/1, University Bologna, Italy, 2007. 25 p.
11. Baldacci R., Battarra M., Vigo D. Routing a heterogeneous fleet of vehicles. In Golden B.L., Raghavan S., Wasil E.A. (Eds.). The vehicle routing problem: Latest advances and new challenges, New York: Springer, 2008. P. 1–25.
12. Hoff A., Andersson H., Christiansen M., Hasle G., Løkketangen A. Industrial Aspects and Literature Survey: Fleet Composition and Routing. SINTEF REPORT NO. A7029, 2008. 49 p.
13. Hoff A., Andersson H., Christiansen M., Hasle G., Løkketangen A. Industrial aspects and literature survey: Fleet composition and routing. Computers & Operations Research. 2010. No. 37. P. 2041–2061. https://doi.org/10.1016/j.cor.2010.03.015
14. Baldacci R., Battarra M., Vigo D. Valid inequalities for the fleet size and mix vehicle routing problem with fixed costs. Networks. 2009. Vol. 54. Iss. 4. P. 178–189. https://doi.org/10.1002/net.20331
15. Baldacci R., Mingozzi A. A unified exact method for solving different classes of vehicle routing problems. Mathematical Programming, Series A. 2009. Vol. 120. Iss. 2. P. 347–380. https://doi.org/10.1007/s10107-008-0218-9
16. Baldacci R., Bartolini E., Mingozzi A., Roberti R. An exact solution framework for a broad class of vehicle routing problems. Computational Management Science. 2010. Vol. 7. Iss. 3. P. 229–268. https://doi.org/10.1007/s10287-009-0118-3
17. Baldacci R., Toth P., Vigo D. Exact algorithms for routing problems under vehicle capacity constraints. Annals of Operations Research. 2010. Vol. 175. Iss. 1. P. 213–245. https://doi.org/10.1007/s10479-009-0650-0
18. Gheysens F., Golden B.L., Assad A. A Comparison of Techniques for Solving the Fleet Size and Mix Vehicle Routing Problem. OR Spectrum. 1984. No. 6. P. 207–216. https://doi.org/10.1007/BF01720070
19. Bräysy O., Dullaert W., Hasle G., Mester D., Gendreau M. An Effective Multi-restart Deterministic Annealing Metaheuristic for the Fleet Size and Mix Vehicle Routing Problem with Time Windows. Transportation Science. 2008. Vol. 42. Iss. 3. P. 371–386. https://doi.org/10.1287/trsc.1070.0217
20. Miller C.E., Tucker A.W., Zemlin R.A. Integer programming formulations and traveling salesman problems. ACM. 1960. Vol. 7. P. 326–329. https://doi.org/10.1145/321043.321046
21. Baldacci R., Battarra M., Vigo D. Valid inequalities for the fleet size and mix vehicle routing problem with fixed costs. Networks. 2009. Vol. 54. Iss. 4. P. 178–189. https://doi.org/10.1002/net.20331
22. Baldacci R., Mingozzi A. A unified exact method for solving different classes of vehicle routing problems. Mathematical Programming, Series A. 2009. Vol. 120. Iss. 2. P. 347–380. https://doi.org/10.1007/s10107-008-0218-9
23. Balinski M., Quandt R. On an integer program for a delivery problem. Operations Research. 1964. Vol. 12. P. 300–304. https://doi.org/10.1287/opre.12.2.300
24. Choi E., Tcha D. A column generation approach to the heterogeneous fleet vehicle routing problem. Computers & Operations Research. 2007. Vol. 34. P. 2080–2095. https://doi.org/10.1016/j.cor.2005.08.002
25. Golden B.L., Raghavan S., Wasil E.A. The Vehicle Routing Problem: Latest Advances and New Challenges. Springer Science & Business Media. 2008. 591 p. https://doi.org/10.1007/978-0-387-77778-8
26. Toth P., Vigo D. Vehicle Routing: Problems, Methods, and Applications. Second Edition, SIAM, 2014. 463 p. https://doi.org/10.1137/1.9781611973594
27. Vidal T., Crainic T.G., Gendreau M., Prins C. A unified solution framework for multi-attribute vehicle routing problems. European Journal of Operational Research. 2014. Vol. 234. Iss. 3. P. 658–673. https://doi.org/10.1016/j.ejor.2013.09.045
28. http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/index.html, http://www.gams.com/, http://aimms.com/, http:/www.gurobi.com/
29. http://www.informatik.uni-koeln.de/abacus/, http://www.coin-or.org/, http://www.gnu.org/software/glpk/glpk.html, http://groups.yahoo.com/group/lp_solve/info/
30. Trofymchuk O.M., Vasyanin V.A. Simulation of Packing, Distribution and Routing of Small-Size Discrete Flows in a Multicommodity Network. Journal of Automation and Information Sciences. 2015. Vol. 47. Iss. 7. P. 15–30. https://doi.org/10.1615/JAutomatInfScien.v47.i7.30.
31. Trofymchuk O.M., Vasyanin V.A., Kuzmenko V.N. Optimization Algorithms for Packing of Small-Lot Correspondence in Communication Networks. Cybernetics and Systems Analysis. 2016. Vol. 52. Iss. 2. P. 258–268. https://doi.org/10.1007/s10559-016-9822-5
32. Васянін В.А., Трофимчук О.М., Ушакова Л.П. Задачі побудови кільцевих маршрутів транспортних засобів у багатопродуктовій ієрархічній мережі. Міжнародний науково-технічний журнал «Проблеми керування та інформатики». 2022. Т. 67. № 3. С. 37–55. https://doi.org/10.34229/2786-6505-2022-3-3
33. Васянін В.А., Трофимчук О.М., Ушакова Л.П. Методологія математичного моделювання перспективного розвитку вузлів і транспортних маршрутів у багатопродуктовій ієрархічній мережі. I. Задачі оптимізації. Кібернетика та системний аналіз. 2024. Т. 60. № 1. С. 103–117. https://doi.org/10.1007/s10559-024-00648-9
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Попередня | ПОВНИЙ ТЕКСТ | Наступна