Scholarlink

Abstract <p>The traveling salesman (or salesperson) problem, short TSP, is of strong interest to many researchers from mathematics, economics, and computer science. Manifold TSP variants occur in nearly every scientific field and application domain: e.g.,&#xa0;engineering, physics, biology, life sciences, and manufacturing. Several thousand papers are published every year. This paper provides the first systematic survey on the best currently known approximability and inapproximability results for well-known TSP variants such as the “standard”, Path, Bottleneck, Maximum Scatter, Generalized, Clustered, Quota, Prize-Collecting, Time-dependent TSP, Traveling Purchaser Problem, Profitable Tour Problem, Orienteering Problem, TSP with Time Windows, and Orienteering Problem with Time Windows. The foundation of our survey is the definition scheme TSP-T3CO&#xa0;, which we propose as a uniform, easy-to-use and extensible means for the formal and precise definition of TSP variants. Applying TSP-T3CO&#xa0;to define a TSP variant reveals subtle differences within the same named variant and also brings out the differences between variants more clearly. We achieve the first comprehensive, concise, and compact representation of approximability results by using TSP-T3CO&#xa0;definitions. This makes it easier to understand the approximability landscape and the assumptions under which certain results hold. Open gaps become more evident and results can be compared more easily.</p> Graphical abstract <p></p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

A survey on approximability of traveling salesman problems using the TSP-T3CO definition scheme

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年7月1日

查看全文
  • Sophia Saller,
  • Jana Koehler,
  • Andreas Karrenbauer

摘要

Abstract

The traveling salesman (or salesperson) problem, short TSP, is of strong interest to many researchers from mathematics, economics, and computer science. Manifold TSP variants occur in nearly every scientific field and application domain: e.g., engineering, physics, biology, life sciences, and manufacturing. Several thousand papers are published every year. This paper provides the first systematic survey on the best currently known approximability and inapproximability results for well-known TSP variants such as the “standard”, Path, Bottleneck, Maximum Scatter, Generalized, Clustered, Quota, Prize-Collecting, Time-dependent TSP, Traveling Purchaser Problem, Profitable Tour Problem, Orienteering Problem, TSP with Time Windows, and Orienteering Problem with Time Windows. The foundation of our survey is the definition scheme TSP-T3CO , which we propose as a uniform, easy-to-use and extensible means for the formal and precise definition of TSP variants. Applying TSP-T3CO to define a TSP variant reveals subtle differences within the same named variant and also brings out the differences between variants more clearly. We achieve the first comprehensive, concise, and compact representation of approximability results by using TSP-T3CO definitions. This makes it easier to understand the approximability landscape and the assumptions under which certain results hold. Open gaps become more evident and results can be compared more easily.

Graphical abstract