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 pres ent a formulation of the problem involving only 0/1 variables associated wi th the arcs of the underlying digraph, This has the advantage of avoiding a dditional variables as well as the associated (typically very ineffective) linking constraints. In the formulation, time-window restrictions are model ed using "infeasible path elimination" constraints. We present the basic fo rm of these constraints along with some possible strengthenings. Several ot her classes of valid inequalities derived from related asymmetric traveling salesman problems are also described, along with a lifting theorem. We als o study the ATSP-TW polytope, P-TW, defined as the convex hull of the integ er solutions of our model. We show that determining the dimension of P-TW i s a strongly, NP-complete problem, even if only one time window is present. In this latter case, we provide a minimal equation system for P-TW. Comput ational experiments on the new formulation are reported in a companion pape r, where we show that it outperforms alternative formulations on some class es of problem instances. (C) 2000 John Wiley & Sons, Inc.