Invited Talks
Ruzica Piskac
Yale University
TBA
Anytime and exact extensions of A* for the TSP-TW
The Travelling Salesman Problem (TSP) may be solved by searching for a best path in a state-transition graph which is derived from Bellman equations, and this state-transition graph may be easily extended to solve the TSP with Time-windows (TSP-TW), where arrival times are constrained to belong to given time intervals, or with time-dependent cost functions, where travel times depend on departure times. In this talk, we will provide an overview of exact and anytime extensions of A* which may be used to search for best paths in state-transition graphs, and show how to combine them with local search (in order to faster find solutions of higher quality) and with bounding and time window constraint propagation (in order to filter the search space). We will present an experimental comparison with state-of-the-art approaches for solving the TSPTW and the time-dependent TSPTW.
