Multiobjective traveling salesperson problem on Halin graphs

Date

2009-07-01

Author

Ozpeynirci, Ozgur
Köksalan, Mustafa Murat

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

1
views

0
downloads

In this paper, we study traveling salesperson (TSP) and bottleneck traveling salesperson (BTSP) problems on special graphs called Halin graphs. Although both problems are NP-Hard on general graphs, they are polynomially solvable on Halin graphs. We address the multiobjective versions of these problems. We show computational complexities of finding a single nondominated point as well as finding all nondominated points for different objective function combinations. We develop algorithms for the polynomially solvable combinations.

Subject Keywords

Management Science and Operations Research, Modelling and Simulation, Information Systems and Management

URI

https://hdl.handle.net/11511/57206

Collections

Department of Industrial Engineering, Article