A NEW GENERALIZATION OF THE TRAVELING SALESMAN PROBLEM


ALKAYA A. F., DUMAN E.

APPLIED AND COMPUTATIONAL MATHEMATICS, cilt.9, sa.2, ss.162-175, 2010 (SCI-Expanded) identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 9 Sayı: 2
  • Basım Tarihi: 2010
  • Dergi Adı: APPLIED AND COMPUTATIONAL MATHEMATICS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.162-175
  • Anahtar Kelimeler: Traveling Salesman Problem, Integer Programming, Combinatorial Optimization, PLACEMENT MACHINE
  • Marmara Üniversitesi Adresli: Evet

Özet

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.