On the Phase Transition of the Euclidean Travelling Salesman Problem with Time Windows

Abstract

Algorithms are often evaluated on randomly generated instances to study scale-up properties with respect to features such as the size, for example. Also, machine learning based approaches often train models on randomly generated instances as they need large sets of training instances. In this paper, we consider the Euclidean Travelling Salesman Problem with Time Windows (TSPTW), and we study the impact of parameters used to randomly generate TSPTW instances on hardness and feasibility. We first consider the decision version of the problem, where feasibility depends on start and end times of time windows. We introduce two parameters, α and β, for controlling the tightness of the time horizon and the time windows. We show that instance hardness is related to a phase transition phenomenon: as we increase α and β, we pass from an unfeasible region (where almost all generated instances have no solution) to a feasible region (where almost all generated instances have solutions), and the hardest instances are located within the transition zone. We formally relate this transition zone with respect to α and β, thus allowing us to control hardness and feasibility when randomly generating instances. Then, we study the optimization problem, the goal of which is to find the smallest tour that satisfies all time windows. We show that the empirical hardness is still related to the phase transition: hardness increases when moving from the infeasible region to the transition zone, as in the decision problem. However, unlike the decision problem, some hard instances are also located in the feasible region where instances are very loosely constrained.