mirtrМир транспортаWorld of Transport and Transportation1992-3252Russian University of Transport (RUT)10.30932/1992-3252-2018-16-3-17mirtr-1476Research ArticleПРОБЛЕМЫ УПРАВЛЕНИЯADMINISTRATION, MANAGEMENT AND CONTROLДекомпозиция задачи маршрутизации по эвристикам метода Кларка-РайтаDECOMPOSITION OF THE ROUTING PROBLEM BASED ON THE CLARKE-WRIGHT HEURISTIC METHODПросовС. Н.ProsovS. N.sergeypros@mail.ruКузьменкоЕ. А.KuzmenkoE. A.kateya97@mail.ruМосковский автомобильно-дорожный государственный технический университет (МАДИ)Russian Federation201828062018163190199Copyright © Просов С.Н., Кузьменко Е.А., 20182018Просов С.Н., Кузьменко Е.А.Prosov S.N., Kuzmenko E.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://mirtr.elpub.ru/jour/article/view/1476

Текст аннотации на англ. языке и полный текст статьи на англ. языке находится в прилагаемом файле ПДФ (англ. версия следует после русской версии).Статья посвящена декомпозиции задачи маршрутизации транспорта по эвристическим оценкам метода Кларка-Райта. Предложена процедура проектирования развозочной автотранспортной системы по критерию минимизации суммарного общего пробега различными формализованными методами декомпозиции, в частности, с помощью алгоритма «функций выгоды» и формирования зон (кластеров, подмножеств, «кустов») обслуживания транспортного средства. Наглядно показаны преимущества предлагаемого метода по сравнению с методом «по матрице кратчайших расстояний» на примере доставки десяти единиц груза от поставщика десяти потребителям по одной грузовой единице. Эффект от сокращения суммарного пробега на построенных маршрутах составил 9,45 %.

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

задача маршрутизации транспортаметод Кларка-Райтакластерметод декомпозицииэвристическая оценкаматрица кратчайших расстояний«функция выгоды»ReferencesАксёнова О. А., Просов С.Н.Модель задачи о назначениях в эвристических алгоритмах маршрутизации транспорта с временными интервалами доставки // Вестник МАДИ. - 2017. - № 3. - С.127-134.Аксёнова О. А., Просов С.Н.Модель задачи о назначениях в эвристических алгоритмах маршрутизации транспорта с временными интервалами доставки // Вестник МАДИ. - 2017. - № 3. - С.127-134.Атрохов Н. А., Андроникова Л.Н.Алгоритм решения задачи перевозок мелких партий грузов с учётом ограничений на движение грузового автомобильного транспорта // Автоматизация и управление в технических системах. - 2015. - № 2. - С.73-82.Атрохов Н. А., Андроникова Л.Н.Алгоритм решения задачи перевозок мелких партий грузов с учётом ограничений на движение грузового автомобильного транспорта // Автоматизация и управление в технических системах. - 2015. - № 2. - С.73-82.Атрохов Н. А., Мороз Д.Г.Альтернативные технологии перевозок мелких партий грузов // Вестник МАДИ. - 2017. - № 4. - С.92-100.Атрохов Н. А., Мороз Д.Г.Альтернативные технологии перевозок мелких партий грузов // Вестник МАДИ. - 2017. - № 4. - С.92-100.Горев А.Э.Грузовые автомобильные перевозки: Учеб. пособие. - 5-е изд., испр. - М.: Академия, 2008. - 287 с.Горев А.Э.Грузовые автомобильные перевозки: Учеб. пособие. - 5-е изд., испр. - М.: Академия, 2008. - 287 с.Мороз Д. Г., Просов С.Н.Декомпозиционная модель маршрутизации перевозок грузов мелкими партиями с учётом мест хранения подвижного состава // Автотранспортное предприятие. - 2014. - № 5. - С.47-49.Мороз Д. Г., Просов С.Н.Декомпозиционная модель маршрутизации перевозок грузов мелкими партиями с учётом мест хранения подвижного состава // Автотранспортное предприятие. - 2014. - № 5. - С.47-49.Мороз Д. Г., Просов С.Н.Методические рекомендации по планированию перевозок мелкопартионных грузов с множеством конечных пунктов маршрутной сети // Автоматизация и управление в технических системах. - 2014. - № 12. - С.103-110.Мороз Д. Г., Просов С.Н.Методические рекомендации по планированию перевозок мелкопартионных грузов с множеством конечных пунктов маршрутной сети // Автоматизация и управление в технических системах. - 2014. - № 12. - С.103-110.Миргородский М. А., Витвицкий Е.Е., Афанасьев Н.Д.Выбор подвижного состава при перевозке грузов мелкими отправками в городах: Монография. - Омск: Полиграфический центр КАН, 2012. - 142 с.Миргородский М. А., Витвицкий Е.Е., Афанасьев Н.Д.Выбор подвижного состава при перевозке грузов мелкими отправками в городах: Монография. - Омск: Полиграфический центр КАН, 2012. - 142 с.Мельникова Т. Е., Филиппова Н.А.Методические материалы практических (семинарских) занятий по дисциплине (модулю) «Теория транспортных процессов и систем». - М.: Техполиграфцентр, 2017-87 с.Мельникова Т. Е., Филиппова Н.А.Методические материалы практических (семинарских) занятий по дисциплине (модулю) «Теория транспортных процессов и систем». - М.: Техполиграфцентр, 2017-87 с.Просов С.Н.Проектирование автотранспортных систем доставки: Учеб. пособие. - М.: МАДИ, 2017. - 100 с.Просов С.Н.Проектирование автотранспортных систем доставки: Учеб. пособие. - М.: МАДИ, 2017. - 100 с.Филиппова Н. А., Беляев В.М.Методология организации и функционирования систем доставки грузов в северные регионы. - М.: Техполиграфцентр, 2015. - 208 с.Филиппова Н. А., Беляев В.М.Методология организации и функционирования систем доставки грузов в северные регионы. - М.: Техполиграфцентр, 2015. - 208 с.Филиппова Н. А., Шилимов М.В., Кошкарев П.П., Суслакова Т.И.Проблемы автомобильного транспорта при движении в крупном городе // Наука сегодня: опыт, традиции, инновации / Материалы международной научно-практ. конференции. - М., 2017. - С.46-48.Филиппова Н. А., Шилимов М.В., Кошкарев П.П., Суслакова Т.И.Проблемы автомобильного транспорта при движении в крупном городе // Наука сегодня: опыт, традиции, инновации / Материалы международной научно-практ. конференции. - М., 2017. - С.46-48.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.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.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.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.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.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.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.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.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.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.Vacic V., Sobh T.M.Vehicle Routing Problem with Time Windows // International Journal of Computing. - 2004. - Vol. 3. - No. 2. - Pp. 72-80.Vacic V., Sobh T.M.Vehicle Routing Problem with Time Windows // International Journal of Computing. - 2004. - Vol. 3. - No. 2. - Pp. 72-80.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.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.

The authors declare that there are no conflicts of interest present.