A NEW GENERALIZATION OF THE TRAVELING SALESMAN PROBLEM

作者：Alkaya Ali Fuat^*; Duman Ekrem

来源：Applied and Computational Mathematics, 2010, 9(2): 162-175.

• Traveling Salesman Problem
• Integer Programming
• Combinatorial Optimization

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.

• 出版日期2010