Топологічна евристика в розв'язанні проблеми маршрутизації транспортних засобів (VRP)
DOI:
https://doi.org/10.15587/2313-8416.2015.44381Ключові слова:
маршрутизація, VRP, кластерна маршрутизація, CluVRP, задача комівояжера, евристики, топологія, теорія графів, «ядра і хвости»Анотація
Роботу присвячено створенню математичної моделі топології дорожньої мережі для розв'язання задач маршрутизації транспортних засобів. Пропонується евристика «ядер і хвостів» як спосіб зниження розмірності і композиції топологічно обґрунтованих наборів точок в єдину групу. У статті розкрито 4 етапи побудови моделі. Визначено перспективи подальшого вдосконалення алгоритму з переходом до паралельного наповнення маршрутів
Посилання
Applegate, D. L., Bixby, R. M., Chvátal, V., Cook, W. J. (2007). The Traveling Salesman Problem: a computational study. Princeton University Press, 608.
Dantzig, G. B., Ramser, J .H. (1959). The Truck Dispatching Problem. Management Science, 6 (1), 80–91. doi: 10.1287/mnsc.6.1.80
Baldacci, R., Christofides, N., Mingozzi, A. (2007). An exact algorithm for the vehicle routing prob-lem based on the set partitioning formulation with additional cuts. Mathematical Programming, 115 (2), 351–385. doi: 10.1007/s10107-007-0178-5
Ellabib, I., Otman, A. B., Calamai, P. (2002). An Experimental Study of a Simple Ant Colony System for the Vehicle Routing Problem with Time Windows. Lecture Notes in Computer Science, 2463, 53–64. doi: 10.1007/3-540-45724-0_5
Bianchessi, N., Righini (2007). Heuristic algorithms for the vehicle routing problem with simultane-ous pick-up and delivery. Computers & Operations Research, 34, 578–594. doi: 10.1016/j.cor.2005.03.014
Bräysy, O., Martínez, E., Nagata, Y., Soler, D. (2011). The mixed capacitated general routing problem with turn penalties. Expert Systems with Applications, 38 (10), 12954–12966. doi: 10.1016/j.eswa.2011.04.092
Sevaux, M., S¨orensen, K. (2008). Hamiltonian paths in large clustered routing problems. Proceed-ings of the EU/MEeting 2008 workshop on Metaheuristics for Logistics and Vehicle Routing. Troyes, France.
Battarra, M., Erdo˘gan, G., Vigo, D. (2014). The clustered vehicle routing problem. Operations Re-search, 62, 58–71.
Vidal, T., Battarra, M., Subramanian, A., Erdogˇan, G. (2015). Hybrid metaheuristics for the Clustered Vehicle Routing Problem. Computers & Operations Research, 58, 87–99. doi: 10.1016/j.cor.2014.10.019
Feed, T., Leiserson, C., Rivest, R., Stein, K. (2005). Chapter 16: Greedy algorithms. .Introduction to Algorithms (ed. 2nd). Moscow: Williams,1296.
Sanders, P., Schultes, D. (2007). Engineering Highway Hierarchies. 9th Workshop on Algorithm Engineering and Experiments, SIAM. Mehlhorn, 36–45. doi: 10.1137/1.9781611972870.4
Sharir, M. (1981). A strong connectivity algorithm and its applications to data flow analysis. Computers and Mathematics with Applications, 7 (1), 67–72. doi: 10.1016/0898-1221(81)90008-0
Tarjan, R. E. (1972). Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1 (2), 146–160. doi: 10.1137/0201010
Gabow, H. N. (2000). Path-based depth-first search for strong and biconnected components. Information Processing Letters, 74 (3-4), 107–114. doi: 10.1016/s0020-0190(00)00051-x
##submission.downloads##
Опубліковано
Номер
Розділ
Ліцензія
Авторське право (c) 2015 Іван Михайлович Найдьонов
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Наше видання використовує положення про авторські права Creative Commons CC BY для журналів відкритого доступу.
Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:
1. Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.
2. Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.
