IMPROVING APPROXIMATION RATIOS FOR THE CLUSTERED TRAVELING SALESMAN PROBLEM

• Kawasaki Masamune

  Tokyo Institute of Technology

• Takazawa Kenjiro

  Hosei University

抄録

The clustered traveling salesman problem (CTSP) is a generalization of the traveling salesman problem (TSP) in which the set of cities is divided into clusters and the salesman must consecutively visit the cities of each cluster. It is well known that TSP is NP-hard, and hence CTSP is NP-hard as well. Guttmann-Beck et al. (2000) designed approximation algorithms for several variants of CTSP by decomposing it into subproblems including the traveling salesman path problem (TSPP). In this paper, we improve approximation ratios by applying a recent improved approximation algorithm for TSPP by Zenklusen (2019).

収録刊行物

• 日本オペレーションズ・リサーチ学会論文誌

  日本オペレーションズ・リサーチ学会論文誌 63 (2), 60-70, 2020-04-30

  公益社団法人 日本オペレーションズ・リサーチ学会

キーワード

• Combinatorial optimization
• clustered traveling salesman problem
• traveling salesman problem
• approximation algorithms

詳細情報

• CRID: 1390285300155340672
• NII論文ID: 130007838841
• NII書誌ID: AA00703935
• DOI: 10.15807/jorsj.63.60
• ISSN: 21888299
• ISSN: 04534514
• NDL書誌ID: 030384339
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I030384339
• Web Site: https://www.jstage.jst.go.jp/article/jorsj/63/2/63_60/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • NDL
  • Crossref
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可