A single Chinese Postman Problem with two objectives

---

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

Öğrenci: EZGİ EROĞLU

Danışman: MERAL AZİZOĞLU

Özet:

The Chinese Postman Problem (CPP) is an arc routing problem in which a single postman serves a number of streets starting from a post office. The postman has to visit the households on each street in his route, delivering and collecting letters and then returning to the post office. The single objective CPP minimizes the total cost of the travel. The multi-objective CPPs consider other attributes like total distance and total time, etc. In this thesis, we consider a multi-objective CPP where each street is represented by two weights, like cost and distance. We propose a branch and bound algorithm that generates all efficient points with respect to the total cost and total distance criteria. Our algorithm benefits from the optimal solutions of the linear programming relaxations in defining the branching scheme and providing lower and upper bounds. Our extensive computational results show that our algorithm generates the efficient solution set for large-sized problem instances in reasonable time.