Модифицированный метод ветвей и границ для решения задачи коммивояжера с временными окнами

Актуальность исследования обусловлена широким применением задачи коммивояжера с временными окнами (TSPTW) в логистике, производственном планировании и сервисном обслуживании, где требуется не только найти кратчайший маршрут, но и строго соблюдать заданные временные интервалы посещения объектов. Цель работы заключается в разработке и программной реализации модифицированного метода ветвей и границ для точного решения TSPTW, а также оценке его эффективности на тестовых задачах различных размерностей. Ведущим методом исследования выбран классический метод ветвей и границ, адаптированный к специфике временных окон. С этой целью в математическую модель задачи введены переменные времени прибытия, в алгоритме решения использовано последовательное ветвление из текущего города, реализована динамическая проверка допустимости переходов по временным окнам, а также применено отсечение неперспективных подмножеств на основе нижних оценок, получаемых из приведенной матрицы расстояний. Представлены детальная математическая постановка TSPTW, описание модифицированного алгоритма и результаты вычислительного эксперимента для матриц расстояний разных размерностей. Выявлено, что предложенный алгоритм находит оптимальное решение во всех случаях при наличии допустимых маршрутов. Показано, что наличие «хороших» окон приводит к существенному удлинению маршрута по сравнению с классической задачей коммивояжера, а время работы алгоритма значительно возрастает с увеличением размерности задачи. Если окна генерируются случайным образом, задача в большинстве своем не имеет решений, поэтому предлагается процедура формирования временных окон, обеспечивающая гарантированное существование маршрута. Обосновано, что модифицированный метод ветвей и границ является корректным инструментом для получения точного решения TSPTW для задач малой и средней размерности и приводит к сокращению перебора вариантов по сравнению с методом полного перебора.

1. Savelsbergh M.W.P. Local search in routing problems with time windows. Annals of Operations Research. 1985;4(1):285–305. https://doi.org/10.1007/BF02022044

2. Solomon M.M. Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research. 1987;35(2):254–265. https://doi.org/10.1287/opre.35.2.254

3. Gendreau M., Hertz A., Laporte G., et al. A generalized insertion heuristic for the traveling salesman problem with time windows. Operations Research. 1998;46(3):330–335. https://doi.org/10.1287/opre.46.3.330

4. López-Ibáñez M., Blum Ch. Beam-ACO for the travelling salesman problem with time windows. Computers & Operations Research. 2010;37(9):1570–1583. https://doi.org/10.1016/j.cor.2009.11.015

5. López-Ibáñez M., Blum Ch., Ohlmann J.W., et al. The travelling salesman problem with time windows: Adapting algorithms from travel-time to makespan optimization. Applied Soft Computing. 2013;13(9):3806–3815. https://doi.org/10.1016/j.asoc.2013.05.009

6. Ohlmann J.W., Thomas B.W. A compressed-annealing heuristic for the traveling salesman problem with time windows. INFORMS Journal on Computing. 2007;19(1):80–90. https://doi.org/10.1287/ijoc.1050.0145

7. Silva R.F., Urrutia S. A general VNS heuristic for the traveling salesman problem with time windows. Discrete Optimization. 2010;7(4):203–211. https://doi.org/10.1016/j.disopt.2010.04.002

8. Ascheuer N., Fischetti M., Grötschel M. Solving the asymmetric travelling salesman problem with time windows by branch-and-cut. Mathematical Programming. 2001;90(3):475–506. https://doi.org/10.1007/PL00011432

9. Dumas Y., Desrosiers J., Gelinas E., et al. An optimal algorithm for the traveling salesman problem with time windows. Operations Research. 1995;43(2):367–371. https://doi.org/10.1287/opre.43.2.367

10. Focacci F., Lodi A., Milano M. A hybrid exact algorithm for the TSPTW. INFORMS Journal on Computing. 2002;14(4):403–417. https://doi.org/10.1287/ijoc.14.4.403.2827