Том 22, номер 5, 2015 г., Стр. 5–29
УДК 519.85
Кочетов Ю. А., Хмелев А. В.
Гибридный алгоритм локального поиска для задачи маршрутизации разнородного ограниченного автопарка
Аннотация:
Рассматривается задача оптимизации маршрутов разнородных транспортных средств для обслуживания заданного множества клиентов. Предполагается, что клиенты представлены точками на плоскости, а число транспортных средств каждого типа ограничено. Для решения задачи разработан гибридный алгоритм локального поиска с кодировкой решений в виде последовательности клиентов. Для декодирования последовательности соответствующая NP-трудная задача решается методом лагранжевых релаксаций. Предложены новые процедуры интенсификации и диверсификации поиска, а также новая окрестность экспоненциальной мощности. Приводятся результаты численных экспериментов на известных тестовых примерах с числом клиентов до 255. Для 15 примеров получены новые рекордные значения целевой функции.
Табл. 7, ил. 5, библиогр. 26.
Ключевые слова: локальный поиск, экспоненциальная окрестность, лагранжева релаксация, субградиентная оптимизация.
DOI: 10.17377/daio.2015.22.479
Кочетов Юрий Андреевич 1,2
Хмелёв Алексей Владимирович 2
1. Институт математики им. С. Л. Соболева
пр. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет
ул. Пирогова, 2, 630090 Новосибирск, Россия
e-mail: jkochet@math.nsc.ru, avhmel@gmail.com
Статья поступила 13 марта 2015 г.
Исправленный вариант — 15 июня 2015 г.
Литература
[1] Давыдов И. А., Кононова П. А., Кочетов Ю. А. Локальный поиск с окрестностью экспоненциальной мощности для задачи балансировки нагрузки на серверы // Дискрет. анализ и исслед. операций. 2014. Т. 21, № 6. С. 21–34.
[2] Давыдов И. A., Кочетов Ю. А., Младенович Н., Уросевич Д. Быстрые метаэвристики для дискретной задачи о (r|p)-центроиде // Автоматика и телемеханика. 2014. № 4. P. 106–119.
[3] Кононова П. А., Кочетов Ю. А. Локальный поиск с чередующимися окрестностями для задачи Джонсона с пассивным буфером // Дискрет. анализ и исслед. операций. 2012. Т. 19, № 5. С. 63–82.
[4] Стецюк П. И. Методы эллипсоидов и r-алгоритмы. Кишинэу: Эврика, 2014. 488 с.
[5] Baldacci R., Battarra M., Vigo D. Routing a heterogeneous fleet of vehicles // The vehicle routing problem: latest advances and new challenges. Nerw York: Springer-Verl., 2008. P. 3–27.
[6] Baldacci R., Mingozzi A. A unified exact method for solving different classes of vehicle routing problems // Math. Program., Ser. A. 2009. Vol. 120, No. 2. P. 347–380.
[7] Boudia M., Prins C., Reghioui M. An effective memetic algorithm with population management for the split delivery vehicle routing problem // Hybrid Metaheuristics. 2007. Vol. 4771. P. 16–30. (Lect. Notes Comput. Sci; Vol. 4771).
[8] Brandão J. A deterministic tabu search algorithm for the fleet size and mix vehicle routing problem // Eur. J. Oper. Res. 2009. Vol. 195, No. 3. P. 716–728.
[9] Brandão J. A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem // Comput. Oper. Res. 2011. Vol. 38, No. 1. P. 140–151.
[10] Desrosiers J., Soumis F., Desrochers M., Sauvґe M. Methods for routing with time windows // Eur. J. Oper. Res. 1986. Vol. 23, No. 2. P. 236–245.
[11] Duhamel C., Gouinaud C., Lacomme P., Prodhon C. A multi-thread GRASPxELS for the heterogeneous capacitated vehicle routing problem // Hybrid Metaheuristics. Heidelberg: Springer-Verl., 2013. P. 237–269. (Stud. Comput. Intell.; Vol. 434).
[12] Duhamel C., Lacomme P., Prodhon C. A GRASPxELS with depth first search split procedure for the HVRP // Res. Rep. LIMOS/RR-10-08, LIMOS, 2010.
[13] Duhamel C., Lacomme P., Prodhon C. Efficient frameworks for greedy split and new depth first search split procedures for routing problems //Comput. Oper. Res. 2011. Vol. 38, No. 4. P. 723–739.
[14] Li F., Golden B., Wasil E. A record-to-record travel algorithm for solving the heterogeneous fleet vehicle routing problem // Comput. Oper. Res. 2007. Vol. 34, No. 9. P. 2734–2742.
[15] Penna P. H. V., Subramanian A., Ochi L. S. An iterated local search heuristic for the heterogeneous fleet vehicle routing problem // J. Heuristics. 2013. Vol. 19, No. 2. P. 201–232.
[16] Penna P. H. V., Vidal T., Ochi L. S., Prins C. New compound neighborhoods structures for the heterogeneous fixed fleet vehicle routing problem // Proc. Conf. Simp. Bras. Pesqui. Operac. (Natal, Brasil, Sept. 16–19, 2013). P. 3623–3633.
[17] Poljak B. T. Subgradient methods: a survey of Soviet research // Nonsmooth Optimization. IIASA Proc. Ser., 1977, Vol. 3.
[18] Potvin J.-Y., Naud M.-A. Tabu search with ejection chains for the vehicle routing problem with private fleet and common carrier // J. Oper. Res. Soc. 2011. Vol. 62, No. 2. P. 326–336.
[19] Prins C. Efficient heuristics for the heterogeneous fleet multitrip VRP with application to a large-scale real case // J. Math. Model. Algorithms. 2002. Vol. 1, No. 2. P. 135–150.
[20] Prins C. Two memetic algorithms for heterogeneous fleet vehicle routing problems // Eng. Appl. Artif. Intell. 2009. Vol. 22, No. 6. P. 916–928.
[21] Subramanian A., Penna P. H. V., Uchoa E., Ochi L. S. A hybrid algorithm for the heterogenous fleet vehicle routing problem // Eur. J. Oper. Res. 2012. Vol. 221, No. 2. P. 285–295.
[22] Taillard E. D. A heuristic column generation method for heterogeneous fleet VRP // RAIRO, Oper. Res. 1999. Vol. 33, No. 1. P. 1–14.
[23] Tarantilis C. D., Kiranoudis C. T., Vassiliadis V. S. A list based threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem // J. Oper. Res. Soc. 2003. Vol. 54, No. 1. P. 65–71.
[24] Tarantilis C. D., Kiranoudis C. T., Vassiliadis V. S. A threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem // Eur. J. Oper. Res. 2004. Vol. 152, No. 1. P. 148–158.
[25] Tarantilis C. D., Zachariadis E. E., Kiranoudis C. T. A guided tabu search for the heterogeneous vehicle routing problem // J. Oper. Res. Soc. 2008. Vol. 59, No. 2. P. 1659–1673.
[26] 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. P. 658–673.
