Том 27, номер 2, 2020 г., Стр. 43-64

УДК 519.8+518.25
Кулаченко И. Н., Кононова П. А.
Гибридный алгоритм локального поиска для задачи маршрутизации транспортных средств с многократным посещением клиентов

Аннотация:
Рассматривается задача построения маршрутов для транспортных средств на конечном временном интервале. Компания имеет множество транспортных средств ограниченной грузоподъёмности, находящихся в разных депо. Требуется построить такие маршруты посещения всех клиентов, чтобы суммарное пройденное расстояние было минимальным, а рабочее время водителей укладывалось в рабочую смену. Задана частота посещений каждого клиента, которые должны проходить через равные промежутки времени. Обслуживание клиента должно производиться одним и тем же транспортным средством. Построена модель частично-целочисленного линейного программирования. Разработан метод локального поиска с чередующимися окрестностями, усиленный методом поиска с запретами. Для рас- ширения пространства решений ограничение на длительность рабочей смены и грузоподъёмность заносятся в целевую функцию со штрафами, изменяемыми в ходе поиска. Процедуры интенсификации и диверсификации применяются для повышения эффективности метода. Приводятся результаты расчётов на реальных исходных данных.
Табл. 6, ил. 1, библиогр. 28.

Ключевые слова: метод штрафов, метаэвристика, окрестность Кернигана — Лина, транспортное средство ограниченной грузоподъёмности.

DOI: 10.33048/daio.2020.27.673

Кулаченко Игорь Николаевич ¹
Кононова Полина Александровна ²
1. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
2. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: soge.ink@gmail.com, pkononova@math.nsc.ru

Статья поступила 31 октября 2019 г.
После доработки — 27 декабря 2019 г.
Принята к публикации 19 февраля 2020 г.

Литература

[1] Dantzig G. B., Ramser J. H. The truck dispatching problem // Manage. Sci. 1959. Vol. 6, No. 1. P. 80–91.

[2] Salhi S., Imran A., Wassan N. A. The multi-depot vehicle routing problem with heterogeneous vehicle fleet: Formulation and a variable neighborhood search implementation // Comput. Oper. Res. 2014. Vol. 52. P. 315–325.

[3] Christofides N., Beasley J. E. The period routing problem // Networks. 1984. Vol. 14, No 2. P. 237–256.

[4] Kovacs A. A., Parragh S. N., Hartl R. F. A template-based adaptive large neighborhood search for the consistent vehicle routing problem // Networks. 2014. Vol. 63, No. 1. P. 60–81.

[5] Gaudioso M., Paletta G. A Heuristic for the Periodic Vehicle Routing problem // Transport. Sci. 1992. Vol. 26, No. 2. P. 86–92.

[6] Groër C., Golden B., Wasil E. The consistent vehicle routing problem // Manufacturing & Service Operations Manage. 2009. Vol. 11, No. 4. P. 630–643.

[7] Talbi E.-G. Metaheuristics: From design to implementation. Hoboken, NJ: Wiley, 2009.

[8] Mladenovic N., Hansen P. Variable neighborhood search // Comput. Oper. Res. 1997. Vol. 24. P. 1097–1100.

[9] Mladenovic N., Hansen P. Developments of variable neighborhood search // Essays and surveys in metaheuristics. Vol. 2. P. 415–439. Boston, MA: Springer, 2002.

[10] Kernighan B. W., Lin S. An efficient heuristic procedure for partitioning graphs // Bell Syst. Tech. J. 1970. Vol. 49, No. 2. P. 291–307.

[11] Кононова П. А., Кочетов Ю. А. Локальный поиск с чередующимися окрестностями для задачи Джонсона с пассивным буфером // Дискрет. анализ и исслед. операций. 2012. Т. 19, № 5. С. 63–82.

[12] Kulachenko I. N., Kononova P. A. The VNS approach for a consistent capacitated vehicle routing problem under the shift length constraints // Commun. Comput. Inform. Sci. 2019. Vol. 1090. P. 51–67.

[13] Kulachenko I. N., Kononova P. A., Kochetov Yu. A., Kurochkin A. A. The variable neighborhood search for a consistent vehicle routing problem under the shift length constraints // IFAC-PapersOnLine. 2019. Vol. 52, No. 13. P. 2314–2319.

[14] Aarts E. H. L., Lenstra J. K. Local search in combinatorial optimization New York: John Wiley & Sons, 1997.

[15] The vehicle routing problem: latest advances and new challenges. New York: Springer, 2008.

[16] Grover L. K. Local search and the local structure of NP-complete problems // Oper. Res. Lett. 1992. Vol. 12, No. 4. P. 235–243.

[17] Alekseeva E., Kochetov Yu., Plyasunov A. Complexity of local search for the $p$-median problem // Eur. J. Oper. Res. 2008. Vol. 191, No. 3. P. 736–752.

[18] Gutin G. Z., Yeo A. Small diameter neighbourhood graphs for the traveling salesman problem: at most four moves from tour to tour // Comput. Oper. Res. 1994. Vol. 26, No. 4. P. 321–327.

[19] Ahuja R. K., Ergun Ö., Orlin J. B., Punnen A. P. A survey of very largescale neighborhood search techniques // Discrete Appl. Math. 2002. Vol. 123, No. 1–3. P. 75–102.

[20] Kochetov Yu. A. Computational bounds for local search in combinatorial optimization // Comput. Math. Math. Phys. 2008. Vol. 48, No. 5. P. 747–763.

[21] Toth P., Vigo D. Vehicle routing: Problems, methods, and applications. Philadelphia, PA: SIAM, 2014.

[22] Kochetov Yu., Kononova P., Paschenko M. Formulation space search approach for the teacher/class timetabling problem // Yugoslav J. Oper. Res. 2008. Vol. 18, No. 1. P. 1–11.

[23] Hemmelmayr V. C., Doerner K. F., Hartl R. F. A variable neighborhood search heuristic for periodic routing problems // Eur. J. Oper. Res. 2009. Vol. 195, No. 3. P. 791–802.

[24] Кочетов Ю. А., Хмелёв А. В. Гибридный алгоритм локального поиска для задачи маршрутизации разнородного ограниченного автопарка // Дискрет. анализ и исслед. операций. 2015. Т. 22, № 5. С. 5–29.

[25] Khmelev A. V., Kochetov Yu. A. A hybrid VND method for the split delivery vehicle routing problem // Electron. Notes Discrete Math. 2015. Vol. 47. P. 5–12.

[26] Davydov I. A., Kochetov Yu. A., Carrizosa E. A local search heuristic for the ($r|p$)-centroid problem in the plane // Comput. Oper. Res. 2014. Vol. 52. P. 334–340.

[27] Diakova Z., Kochetov Yu. A double VNS heuristic for the facility location and pricing problem // Electron. Notes Discrete Math. 2012. Vol. 39. P. 29–34.

[28] Davydov I. A., Kochetov Yu. A., Carrizosa E. VNS heuristic for the ($r|p$)-centroid problem on the plane // Electron. Notes Discrete Math. 2012. Vol. 39. P. 5–12.