Том 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).
|