DECOMPOSITION OF THE ROUTING PROBLEM BASED ON THE CLARKE-WRIGHT HEURISTIC METHOD
https://doi.org/10.30932/1992-3252-2018-16-3-17
Abstract
For the English abstract and full text of the article please see the attached PDF-File (English version follows Russian version).ABSTRACT The article is devoted to decomposition of the task of transport routing based on heuristic estimates with the Clarke-Wright method. A procedure is proposed for designing an automobile transport system based on the criterion of minimizing the total mileage by various formalized decomposition methods, in particular, using the «benefit functions» algorithm and formation of zones (clusters, subsets) of vehicle maintenance. The advantages of the proposed method are clearly shown in comparison with the method of «the shortest distance matrix», at the example of delivery of ten cargo units from a supplier to ten consumers. The effect of reducing the total mileage on the designed routes was 9,45 %. Keywords: transport routing, Clarke-Wright method, «benefit function», cluster, decomposition method, heuristic estimation, the shortest distances matrix
About the Authors
S. N. Prosov
Московский автомобильно-дорожный государственный технический университет (МАДИ)
Russian Federation
Russian Federation
E. A. Kuzmenko
Московский автомобильно-дорожный государственный технический университет (МАДИ)
Russian Federation
Russian Federation
References
1. Аксёнова О. А., Просов С.Н.Модель задачи о назначениях в эвристических алгоритмах маршрутизации транспорта с временными интервалами доставки // Вестник МАДИ. - 2017. - № 3. - С.127-134.
2. Атрохов Н. А., Андроникова Л.Н.Алгоритм решения задачи перевозок мелких партий грузов с учётом ограничений на движение грузового автомобильного транспорта // Автоматизация и управление в технических системах. - 2015. - № 2. - С.73-82.
3. Атрохов Н. А., Мороз Д.Г.Альтернативные технологии перевозок мелких партий грузов // Вестник МАДИ. - 2017. - № 4. - С.92-100.
4. Горев А.Э.Грузовые автомобильные перевозки: Учеб. пособие. - 5-е изд., испр. - М.: Академия, 2008. - 287 с.
5. Мороз Д. Г., Просов С.Н.Декомпозиционная модель маршрутизации перевозок грузов мелкими партиями с учётом мест хранения подвижного состава // Автотранспортное предприятие. - 2014. - № 5. - С.47-49.
6. Мороз Д. Г., Просов С.Н.Методические рекомендации по планированию перевозок мелкопартионных грузов с множеством конечных пунктов маршрутной сети // Автоматизация и управление в технических системах. - 2014. - № 12. - С.103-110.
7. Миргородский М. А., Витвицкий Е.Е., Афанасьев Н.Д.Выбор подвижного состава при перевозке грузов мелкими отправками в городах: Монография. - Омск: Полиграфический центр КАН, 2012. - 142 с.
8. Мельникова Т. Е., Филиппова Н.А.Методические материалы практических (семинарских) занятий по дисциплине (модулю) «Теория транспортных процессов и систем». - М.: Техполиграфцентр, 2017-87 с.
9. Просов С.Н.Проектирование автотранспортных систем доставки: Учеб. пособие. - М.: МАДИ, 2017. - 100 с.
10. Филиппова Н. А., Беляев В.М.Методология организации и функционирования систем доставки грузов в северные регионы. - М.: Техполиграфцентр, 2015. - 208 с.
11. Филиппова Н. А., Шилимов М.В., Кошкарев П.П., Суслакова Т.И.Проблемы автомобильного транспорта при движении в крупном городе // Наука сегодня: опыт, традиции, инновации / Материалы международной научно-практ. конференции. - М., 2017. - С.46-48.
12. Prosov S. N., Gayazova Z.M. A modification of the method called «sum» with the time constraints of delivery of goods // International journal of advanced studies. - 2016. - № 4. - С.56-62.
13. Aleman R. E., Hill R.R. A tabu search with vocabulary building approach for the vehicle routing problem with split demands // Int. J.Metaheuristics. - 2010. - Vol. 1. - No. 1. - Pp. 55-80.
14. Berbotto L., Garcia S., Nogales F.G. A randomized granular tabu search heurstic for the split del ivery vehicle routing problem // Annals of Operations Research. - 2014. - Vol. 222. - Pp. 153-173.
15. Duhamel C., Lacomme P., Prodhon C.Efficient frameworks for greedy split and new depth first search split procedures for routing problems // Comp. Oper. Res. - 2011. - Vol. 38. - No. 4. - Pp. 723-739.
16. Ropke S., Pisinger D. A unified heuristic for a large class of vehicle routing problems with backhauls // European Journal of Operational Research. - 2006. - Vol. 171. - No. 3. - Pp. 750-775.
17. Vacic V., Sobh T.M.Vehicle Routing Problem with Time Windows // International Journal of Computing. - 2004. - Vol. 3. - No. 2. - Pp. 72-80.
18. Vidal T., Crainic T.G., Gendreau M., Prins C. A Unified Solution Framework for Multi-Attribute Vehicle Routing Problems // Eur. J.Oper. Res. - 2014. - Vol. 234. - No. 3. - Pp. 658-673.
Review
For citations:
Prosov S.N., Kuzmenko E.A. DECOMPOSITION OF THE ROUTING PROBLEM BASED ON THE CLARKE-WRIGHT HEURISTIC METHOD. World of Transport and Transportation. 2018;16(3):190-199. https://doi.org/10.30932/1992-3252-2018-16-3-17
Views:
521
Email this article 