A genetic algorithm for the biobjective traveling salesman problem with profits


Thesis Type: Postgraduate

Institution Of The Thesis: Orta Doğu Teknik Üniversitesi, Faculty of Engineering, Department of Industrial Engineering, Turkey

Approval Date: 2008

Student: SERDAR KARADEMİR

Co-Supervisor: HALDUN SÜRAL, ESRA KARASAKAL

Abstract:

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.