A polyhedral study of the asymmetric traveling salesman problem with time windows

The asymmetric traveling salesman problem with time windows (ATSP-TW) is a basic model for scheduling and routing applications. In this paper, we present a formulation of the problem involving only 0/1 variables associated with the arcs of the underlying digraph. This has the advantage of avoiding additional variables as well as the associated (typically very ineffective) linking constraints. In the formulation, time-window restrictions are modeled using “infeasible path elimination” constraints. We present the basic form of these constraints along with some possible strengthenings. Several other classes of valid inequalities derived from related asymmetric traveling salesman problems are also described, along with a lifting theorem. We also study the ATSP-TW polytope, PTW, defined as the convex hull of the integer solutions of our model. We show that determining the dimension of PTW is a strongly 𝒩𝒫-complete problem, even if only one time window is present. In this latter case, we provide a minimal equation system for PTW. Computational experiments on the new formulation are reported in a companion paper, where we show that it outperforms alternative formulations on some classes of problem instances.