Multiobjective traveling salesperson problem on Halin graphs


Ozpeynirci O., Koksalan M.

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, vol.196, no.1, pp.155-161, 2009 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 196 Issue: 1
  • Publication Date: 2009
  • Doi Number: 10.1016/j.ejor.2008.04.011
  • Title of Journal : EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
  • Page Numbers: pp.155-161

Abstract

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. (C) 2008 Elsevier B.V. All rights reserved.