Exact and anytime approach for solving the time dependent traveling salesman problem with time windows

• Published in: European journal of operational research 2023-12, Vol.311 (3), p.833-844
• Main Authors: Fontaine, Romain, Dibangoye, Jilles, Solnon, Christine
• Format: Article
• Language: English
• Subjects: Computer Science; Dynamic programming; Operations Research; Time-dependent cost functions; Travelling salesman
• ISSN: 0377-2217; 1872-6860
• DOI: 10.1016/j.ejor.2023.06.001

•We introduce a new bounding function based on an efficient feasibility check.•We combine it with an anytime and exact variant of A*, constraint propagation and LS.•We provide an experimental study on various time-dependent and constant benchmarks.•Our approach finds reference solutions faster than state-of-the-art approaches.•Our approach is competitive with state-of-the-art approaches for proving optimality. The Time Dependent (TD) Traveling Salesman Problem (TSP) is a generalization of the TSP which allows one to take traffic conditions into account when planning tours in an urban context, by making the travel time between locations dependent on the departure time instead of being constant. The TD-TSPTW further generalizes this problem by adding Time Window constraints. Existing exact approaches such as Integer Linear Programming and Dynamic Programming usually do not scale well. We therefore introduce a new exact approach based on an anytime extension of A*. We combine this approach with local search, to converge faster towards better solutions, and bounding and time window constraint propagation, to prune parts of the state space. We experimentally compare our approach with state-of-the-art approaches on both TD-TSPTW and TSPTW benchmarks.