|
Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)
Local search metaheuristics for Capacitated Vehicle Routing Problem: a comparative study
[Эвристические методы конструирования маршрута для решения задачи маршрутизации с ограничением по грузоподъемности]
S. M. Avdoshin, E. N. Beresneva National Research University Higher School of Economics
Аннотация:
Задача маршрутизации — одна из широко известных задач комбинаторной оптимизации. Она состоит в отыскании оптимального множества маршрутов для транспортных средств с целью однократного обслуживания определенного множества клиентов. В данной работе исследуется подвид задачи маршрутизации — задача маршрутизации с ограничением по грузоподъемности, в которой каждое транспортное средство имеет свою грузоподъемность. Задача является NP-трудной, поэтому вместо точных алгоритмов решения исследуются только эвристические алгоритмы, позволяющие получить приближенные решения за полиномиальное время. Данная работа является продолжением исследования, посвященного алгоритмам конструирования маршрута; оно позволяет получить первоначальные решения для данной задачи. Было выяснено, что эвристика Clarke and Wright Savings (CWS) является одной из лучших, за исключением наборов данным с геометрическим расположением точек, для которых лучшим является алгоритм Nearest Neighbor (NN). Целью работы является сравнение локально-оптимальных метаэвристических алгоритмов решения задачи маршрутизации с ограничением по грузоподъемности по двум критериям: точность и время решения, для получения начального решения используются алгоритмы CWS и NN. Выявлено пять Парето оптимальных групп алгоритмов для различных типов входных данных. Интересно, что алгоритм «Lin, Kernighan and Helsgaun heuristic» (LKH-3), входящий во все Парето оптимальные группы для смежной задачи (задача коммивояжера), в данном случае вошел только в четыре группы из пяти.
Ключевые слова:
задача маршрутизации с ограничением по грузоподъемности, локально-оптимальные метаэвристики, LKH-3, алгоритм переменного перемещения, метод отжига, алгоритм управляемого поиска, алгоритм поиска с запретами.
Образец цитирования:
S. M. Avdoshin, E. N. Beresneva, “Local search metaheuristics for Capacitated Vehicle Routing Problem: a comparative study”, Труды ИСП РАН, 31:4 (2019), 121–138
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/tisp443 https://www.mathnet.ru/rus/tisp/v31/i4/p121
|
Статистика просмотров: |
Страница аннотации: | 203 | PDF полного текста: | 107 | Список литературы: | 18 |
|