Modified branch and bound method for solving the traveling salesman problem with time windows

The relevance of the research is due to the widespread application of the Traveling Salesman Problem with Time Windows (TSPTW) in logistics, production planning, and service maintenance, where it is required not only to find the shortest route but also to strictly adhere to given time intervals for visiting objects. The aim of the work is to develop and implement a modified branch-and-bound method for the exact solution of TSPTW, as well as to evaluate its performance on test problems of various dimensions. The leading research method is the classical branch-and-bound method adapted to the specifics of time windows. To this end, arrival time variables are introduced into the mathematical model of the problem, sequential branching from the current city is used in the solution algorithm, dynamic feasibility checking of transitions with respect to time windows is implemented, and unpromising subsets are pruned based on lower bounds obtained from the reduced distance matrix. The paper presents a detailed mathematical formulation of TSPTW, a description of the modified algorithm, and the results of a computational experiment for distance matrices of various dimensions. It is shown that the presence of "good" windows leads to a significant increase in route length compared to the classical traveling salesman problem, and the algorithm’s runtime increases substantially with problem dimension. When windows are generated randomly, the problem in most cases has no solution; therefore, a procedure for generating time windows that guarantees the existence of a route is proposed. It is substantiated that the modified branch-and-bound method is a correct tool for obtaining an exact solution of TSPTW for small- and medium-scale problems and leads to a reduction in the search space compared to the brute-force method.

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