Сборники трудов ИСП РАН


Эвристические методы конструирования маршрута для решения задачи маршрутизации с ограничением по грузоподъемности

Авдошин С.М. (ВШЭ, Москва, Россия)
Береснева Е.Н. (ВШЭ, Москва, Россия)

Аннотация

Задача маршрутизации – одна из широко известных задач комбинаторной оптимизации. Она состоит в отыскании оптимального множества маршрутов для транспортных средств с целью однократного обслуживания определенного множества клиентов. В данной работе исследуется подвид задачи маршрутизации – задача маршрутизации с ограничением по грузоподъемности, в которой каждое транспортное средство имеет свою грузоподъемность. Задача является NP-трудной, поэтому вместо точных алгоритмов решения исследуются только эвристические алгоритмы, позволяющие получить приближенные решения за полиномиальное время. Данная работа является продолжением исследования, посвященного алгоритмам конструирования маршрута; оно позволяет получить первоначальные решения для данной задачи. Было выяснено, что эвристика Clarke and Wright Savings (CWS) является одной из лучших, за исключением наборов данным с геометрическим расположением точек, для которых лучшим является алгоритм Nearest Neighbor (NN). Целью работы является сравнение локально-оптимальных метаэвристических алгоритмов решения задачи маршрутизации с ограничением по грузоподъемности по двум критериям: точность и время решения, для получения начального решения используются алгоритмы CWS и NN. Выявлено пять Парето оптимальных групп алгоритмов для различных типов входных данных. Интересно, что алгоритм «Lin, Kernighan and Helsgaun heuristic» (LKH-3), входящий во все Парето оптимальные группы для смежной задачи (задача коммивояжера), в данном случае вошел только в четыре группы из пяти.

Ключевые слова

задача маршрутизации с ограничением по грузоподъемности; локально-оптимальные метаэвристики; LKH-3; алгоритм переменного перемещения: метод отжига; алгоритм управляемого поиска; алгоритм поиска с запретами

Издание

Труды Института системного программирования РАН, том 31, вып. 4, 2019, стр. 121-138.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2019-31(4)-8

Для цитирования

Авдошин С.М., Береснева Е.Н. Эвристические методы конструирования маршрута для решения задачи маршрутизации с ограничением по грузоподъемности. Труды Института системного программирования РАН, том 31, вып. 4, 2019, стр. 121-138. DOI: 10.15514/ISPRAS-2019-31(4)-8.

Полный текст статьи в формате pdf (на английском) Вернуться к содержанию тома