A new generalization of the traveling salesman problem

Abstract

Traveling Salesman Problem (TSP) is one of the well-known NP-Complete combinatorial optimization problems. Adding new constraints yields different generalizations of the problem, and each new generalization forms the basis of a new research area. The main contribution of this study is to define and formulate a new generalization of the TSP, which we call the Sequence Dependent TSP (SDTSP). In SDTSP, the cost of traveling between two vertices depends not only on the distance between these vertices, but also on the characteristics of a number of vertices to be visited next. The problem is formulated as a nonlinear integer programming. Then a real life problem environment where this problem appears is described. Some discussions on previous solution attempts to this problem and on closely related problems are also given. We believe that with the definition of the SDTSP, a basis for new research area will be established.