The biobjective traveling salesman problem with profit


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: 2007

Öğrenci: ÖMÜR ŞİMŞEK

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

Özet:

The traveling salesman problem (TSP) is defined as: given a finite number of cities along with the cost of travel between each pair of them, find the cheapest way of visiting all the cities only once and returning to your starting city. Some variants of TSP are proposed to visit cities depending on the profit gained when the visit occurs. In literature, these kind of problems are named TSP with profit. In TSP with profit, there are two conflicting objectives, one to collect profit and the other to decrease traveling cost. In literature, TSP with profit are addressed as single objective, either two objectives are combined linearly or one objective is constrained with a specified bound. In this study, a multiobjective approach is developed by combining ε-constrained method and heuristics from the literature in order to find the efficient frontier for the TSP with profit. The performance of approach is tested on the problems studied in the literature. Also an interactive software is developed based on the multiobjective approach.