Том 28, номер 2, 2021 г., Стр. 35-59

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

Аннотация:
Исследуется задача маршрутизации буровых установок. Известно множество объектов, требующих изыскательных работ, и временное окно, т. е. период, в который необходимо успеть провести работы. На одном объекте может работать несколько установок, в этом случае работы будут проведены быстрее. Необходимо определить маршруты и график работ буровых установок на объектах так, чтобы все работы были выполнены вовремя, а суммарное время переезда было минимальным.
Для этой новой задачи составлена модель задачи смешанного целочисленного линейного программирования (СЦЛП). Для поиска допустимого решения используется метаэвристика поиска с чередующимися окрестностями. Алгоритм также включает в себя решение подзадачи СЦЛП для перераспределения работ на объектах. Полученный метод сочетает в себе достоинства как точных, так и эвристических подходов. Представлены результаты сравнения разработанного алгоритма с Gurobi и альтернативными схемами поиска с чередующимися окрестностями.
Табл. 3, ил. 1, библиогр. 30.

Ключевые слова: транспортное средство неограниченной грузоподъёмности, матэвристика, разделяемое обслуживание, временные окна.

DOI: 10.33048/daio.2021.28.703

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

Статья поступила 13 ноября 2020 г.
После доработки — 15 февраля 2021 г.
Принята к публикации 17 февраля 2021 г.

Литература

[1] Bräysy O., Gendreau M. Vehicle routing problem with time windows, part I: Route construction and local search algorithms // Transp. Sci. 2005. Vol. 39, No. 1. P. 104–118.

[2] Gendreau M., Tarantilis C. D. Solving large-scale vehicle routing problems with time windows: The state-of-the-art // CIRRELT-2010-04. Montreal: Interuniv. Res. Centre on Enterpr. Networks, Logist. and Transp., 2010.

[3] Ho S. C., Haugland D. A tabu search heuristic for the vehicle routing problem with time windows and split deliveries // Comput. Oper. Res. 2004. Vol. 31, No. 12. P. 1947–1964.

[4] Vidal T., Crainic T. G., Gendreau M., Prins C. A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows // Comput. Oper. Res. 2013. Vol. 40, No. 1. P. 475–489.

[5] Kulachenko I. N., Kononova P. A. A matheuristic for the drilling rig routing problem // Mathematical Optimization Theory and Operations Research. Proc. 19th Int. Conf. (Novosibirsk, Russia, July 6–10, 2020). Cham: Springer, 2020. P. 343–358. (Lect. Notes Comput. Sci.; Vol. 12095).

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

[7] Golden B. L., Raghavan S., Wasil E. A. The vehicle routing problem: Latest advances and new challenges. New York: Springer, 2008.

[8] Archetti C., Speranza M. G. Vehicle routing problems with split deliveries // Int. Trans. Oper. Res. 2012. Vol. 19, No. 1–2. P. 3–22.

[9] Braekers K., Ramaekers K., Van Nieuwenhuyse I. The vehicle routing problem: State of the art classification and review // Comput. Ind. Eng. 2016. Vol. 99. P. 300–313.

[10] Lambert V., Laporte G., Louveaux F. Designing collection routes through bank branches // Comput. Oper. Res. 1993. Vol. 20, No. 7. P. 783–791.

[11] Кулаченко И. Н., Кононова П. А. Гибридный алгоритм локального поиска для задачи маршрутизации транспортных средств с многократным посещением клиентов // Дискрет. анализ и исслед. операций. 2020. Т. 27, № 2. С. 43–64.

[12] 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.

[13] Li F., Golden B., Wasil E. The open vehicle routing problem: Algorithms, large-scale test problems, and computational results // Comput. Oper. Res. 2007. Vol. 34, No. 10. P. 2918–2930.

[14] Yakici E., Karasakal O. A min–max vehicle routing problem with split delivery and heterogeneous demand // Optim. Lett. 2013. Vol. 7. P. 1611–1625.

[15] Aloise D. J., Aloise D., Rocha C., Ribeiro C. C., Filho R., Moura L. Scheduling workover rigs for onshore oil production // Discrete Appl. Math. 2006. Vol. 154, No. 5. P. 695–702.

[16] Ribeiro G., Desaulniers G., Desrosiers J., Vidal T., Vieira B. Efficient heuristics for the workover rig routing problem with a heterogeneous fleet and a finite horizon // J. Heur. 2014. Vol. 20. P. 677–708.

[17] Pecin D., Contardo C., Desaulniers G., Uchoa E. New enhancements for the exact solution of the vehicle routing problem with time windows // INFORMS J. Comput. 2017. Vol. 29, No. 3. P. 489–502.

[18] Archetti C., Speranza M. G. A survey on matheuristics for routing problems // EURO J. Comput. Optim. 2014. Vol. 2. P. 223–246.

[19] Matheuristics: Hybridizing metaheuristics and mathematical programming. New York: Springer, 2009. (Ann. Inf. Syst.; Vol. 10).

[20] Talbi El-G. Hybrid metaheuristics. Berlin: Springer, 2013.

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

[22] Mladenovic N., Hansen P., Todosijevic R., Hanafi S. Variable neighborhood search: Basics and variants // EURO J. Comput. Optim. 2017. Vol. 5, No. 3. P. 423–454.

[23] Hemmelmayr V. C., Doerner K. F., Hartl R. F., Vigo D. Models and algorithms for the integrated planning of bin allocation and vehicle routing in solid waste management // Transp. Sci. 2014. Vol. 48. P. 103–120.

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

[25] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

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

[27] Nagata Y., Bräysy O., Dullaert W. A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows // Comput. Oper. Res. 2010. Vol. 37, No. 4. P. 724–737.

[28] Solomon M. M. Algorithms for the vehicle routing and scheduling problems with time window constraints // Oper. Res. 1985. Vol. 35. P. 254–265.

[29] Kirkpatrick S., Gelatt, Jr. C. D., Vecchi M. P. Optimization by simulated annealing // Science. 1983. Vol. 220, No. 4598. P. 671–680.

[30] Hutter F., Hoos H. H., Leyton-Brown K. Sequential model-based optimization for general algorithm configuration // Learning and Intelligent Opti?mization. Sel. Pap. 5th Int. Conf. (Rome, Italy, Jan. 17–21, 2011). Heidelberg: Springer, 2011. P. 507–523. (Lect. Notes Comput. Sci.; Vol. 6683).