A genetic algorithm for the biobjective traveling salesman problem with profits

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Mühendislik Fakültesi, Endüstri Mühendisliği Bölümü, Türkiye

Tezin Onay Tarihi: 2008

Öğrenci: SERDAR KARADEMİR

Eş Danışman: ESRA KARASAKAL, HALDUN SÜRAL

Özet:

In Traveling Salesman Problem (TSP) with profits, a profit is associated with each city and the requirement to visit all cities is removed. The purpose is to simultaneously minimize cost (excluding as many cities as possible) and maximize profit (including as many cities as possible). Although the reduced single-objective case of the problem has been well-studied, the true biobjective problem has been studied only by a few researchers. In this paper we study the true biobjective problem using the Multiobjective Genetic Algorithm NSGA II and the Lin-Kernighan Heuristic. We propose several improvements for NSGA II in solving the problem. Based on these improvements, we provide computational results of the approximated Pareto-optimal front for a set of practically large size TSP instances. Finally, we provide a framework and its computational results for a post-optimality analysis to guide the decision maker, using the data mining software Clementine.