A classification of formulations for the (time-dependent) traveling salesman problem

摘要

The time-dependent traveling salesman problem (TDTSP) is a generalization of the classical traveling salesman problem where the cost of any given arc is dependent of its position in the tour. The TDTSP can model several real world applications (e.g., one-machine sequencing). In this paper we present a classification of formulations for the TDTSP. This framework includes both new and old formulations. The new formulation presented in this paper is derived from a quadratic assignment model for the TDTSP. In a first step, Lawler's transformation procedure is used to derive an equivalent linearized version of the quadratic model. In a second step, a stronger formulation is obtained by tightening some constraints of the previous formulation. It is shown that, in terms of linear relaxations, the latter formulation is either equivalent or better than other formulations already known from the literature. Finally, we compare these formulations with other well known formulations for the classical traveling salesman problem.