# A Systematic Review of Approximability Results for Traveling Salesman
Problems leveraging the TSP-T3CO Definition Scheme

Sophia Saller<EMAIL_ADDRESS>0000-0003-4817-8601 Deutsches
Forschungszentrum für Künstliche IntelligenzSaarland Informatics Campus D3
2SaarbrückenGermany66123 ,  Jana Koehler<EMAIL_ADDRESS>0000-0001-9000-9188 Lucerne University of Applied Sciences and Arts, School of
Information TechnologySuurstoffi 1RotkreuzZugSwitzerland6343 and  Andreas
Karrenbauer<EMAIL_ADDRESS>0000-0001-6129-3220 Max Planck
Institute for InformaticsSaarland Informatics Campus E1
4SaarbrückenGermany66123

###### Abstract.

The traveling salesman (or salesperson) problem, short TSP, is a problem of
strong interest to many researchers from mathematics, economics, and computer
science. Manifold TSP variants occur in nearly every scientific field and
application domain: engineering, physics, biology, life sciences, and
manufacturing just to name a few. Several thousand papers are published on
theoretical research or application-oriented results each 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" TSP, Path TSP, Bottleneck TSP, Maximum Scatter TSP,
Generalized TSP, Clustered TSP, Traveling Purchaser Problem, Profitable Tour
Problem, Quota TSP, Prize-Collecting TSP, Orienteering Problem, Time-dependent
TSP, TSP with Time Windows, and the Orienteering Problem with Time Windows.

The foundation of our survey is the definition scheme TSP-T3CO (pronounced ti:
Es pi: ti:ko), 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
formally define the variant studied by a paper reveals subtle differences
within the same named variant and also brings out the differences between the
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.

Traveling Salesperson, Traveling Salesman, definition scheme, approximation
algorithms

††ccs: Theory of computation Graph algorithms analysis

##  1\. Introduction

The traveling salesman problem, the gender-neutral name being the traveling
salesperson problem, short TSP, is a problem of strong interest to many
researchers and practitioners in the fields of mathematics, economics,
computer science, and engineering. In practice, a huge variety of variants of
the TSP occurs in almost every scientific field or application domain:
engineering, physics, biology, life sciences, and manufacturing, just to name
a few.

Although the ``general'' TSP is NP-hard, constraints on the tour or the
targeted cities can lead to problem variants for which polynomial-time exact
solution or approximation algorithms exist. The existence of lower and upper
approximation bounds helps to further classify problem variants. Lower and
upper bounds characterize the difficulty of a variant and indicate how well a
variant can be solved with an efficient, i.e., polynomial-time, algorithm. In
particular, most upper-bound results, which we review in this paper, devise
such an algorithm that guarantees a certain solution quality. It is of high
relevance to researchers and practitioners alike to easily determine whether a
particular result applies to a variant under study.

The amount of papers published about the TSP is impressive. Searching for
``traveling salesman'' on Google Scholar returned about 278,000 publications
in total.111Accessed on August 02, 2023. 18,000 of these have been published
since 2019. Searching for ``traveling salesperson'' returns 17,100
publications published since 2019. These publications reveal the almost
endless number of variants being studied. It is not only the sheer number of
publications, but in particular the many variants in which the TSP is studied
that complicates further progress in research and the transfer of theoretical
results into practice.

When taking a closer look at some publications, one realizes that is often
difficult to precisely identify the variant that it is studied due to the non-
uniform terminology that is used when describing a variant. As a consequence,
it is hard to find related work because the same problem variant may be named
differently, or different problem variants may be named similarly or even
identically. The non-uniform representation of variants makes it challenging
to understand whether a theoretical or empirical result applies to the variant
under consideration as details of the problem definition often remain unclear
or have to be identified by carefully reading formal proofs where additional
assumptions are described. The current ``muddle'' of variant definitions also
hinders the communication between interested parties and the transfer of
theoretical results into practice. Notably, practitioners find it impossible
or far too time-consuming to position their problem w.r.t. a known problem
variant and to benefit from existing research results. It is too cumbersome to
judge whether an approximation result is applicable to a specific problem
variant and whether or not an algorithm can be reused if a review of the proof
behind the result is required.

In this paper, we review approximability results for TSP variants and propose
a uniform, systematic and extensible definition scheme named TSP-T3CO
(pronounced ti: Es pi: ti:ko) that we believe is equally well-suited to
satisfy the needs of researchers from computer science, economics, and
mathematics as well as practitioners. The definition scheme takes inspiration
from similar scheme(s) from the domain of scheduling problems (conway1967, ;
graham1979, ; pinedo2012, ), which use a tuple of parameters for the
characterization of a scheduling variant, where each parameter is
characterized by one or several attribute-value fields. Existing work on
scheduling classification schemes also shows that slightly different
classification schemes have emerged from the early work introduced in
(graham1979, ) and that it is not always fully clear which scheme is adopted
in a scientific publication as the schemes do not have a clearly recognizable
name and the definition of attributes and values may slightly differ. The lack
of a name also makes it impossible to directly search for publications using a
specific scheme. Therefore, we decided to name the proposed definition scheme
for TSP variants TSP-T3CO , which represents the five parameters we use to
characterize TSP: the Traveler, the Targets, the Tour, the Costs, and the
Objectives. We also opted for strict mathematical rigor when defining the
tuple of parameters and their associated attributes and values. We also added
the year to the TSP-T3CO name and speak of "TSP-T3CO 2023" to support the
versioning of the definition scheme and to facilitate a concise reference in
publications as the set of attributes and values used to specify a parameter
may change over time.

This paper is organized as follows: Section 2 introduces the TSP and gives
basic definitions as well as an example to illustrate the definitions. Section
3 discusses earlier reviews of approximability results and reviews related
work on the definition and taxonomic classification of problem variants for
scheduling, traveling salesperson, and vehicle routing problems as well as
selected subfields of artificial intelligence research. Section 4 formally
introduces the definition scheme TSP-T3CO using an EBNF grammar. We
distinguish a longhand and a shorthand notation for the definition scheme, the
former supporting a detailed, well-structured, and easily readable variant
definition and the latter allowing for a very compact precise definition of
TSP variants. In Section 5, attributes and values for the fields of the
TSP-T3CO 2023 definition scheme are formally defined. These attributes and
values are used to characterize TSP variants in our review of approximability
results. In Section 6, we present our review of approximability and
inapproximability results for TSP variants. We use TSP-T3CO 2023 to define
commonly known variants of the TSP that are widely studied, which include the
"standard" TSP, Path TSP, Bottleneck TSP, Maximum Scatter TSP, Generalized
TSP, Clustered TSP, Traveling Purchaser Problem, Profitable Tour Problem,
Quota TSP, Prize-Collecting TSP, Orienteering Problem, Time-dependent TSP, TSP
with Time Windows, and the Orienteering Problem with Time Windows. Based on
our insights from Section 6, we propose definitions for these variants in
Section 7. In Section 8, we briefly discuss how TSP-T3CO 2023 can be extended
to define vehicle routing problem variants involving more than one traveler.
Finally, in Section 9, we summarize the contributions of this paper. Appendix
A provides a cheat sheet for TSP-T3CO 2023.

##  2\. The Traveling Salesman Problem

TSP is one of the best-known combinatorial optimization problems. Given a list
of cities and distances between them, a traveling salesperson needs to find a
shortest possible route to visit the cities. There are many variants of this
problem, which makes it hard to formally define a generic version. However,
many variants of TSP (if not all) can be formulated over a graph. Let
$G=(V,E)$ be a graph with $n$ nodes in $V$ representing the cities and $m$
edges in $E$ representing connections between cities. The edges can either be
directed or undirected where the latter implies that the direction of travel
does not matter, and the former allows us to model one-way roads and
asymmetries, e.g., between uphill and downhill travel times. An undirected
edge $e$ is an unordered two-element subset of the node set, i.e.,
$e=\\{v,w\\}\subseteq V$. If it is directed, it is an ordered pair of nodes,
i.e., $e=(v,w)$, which means that the edge is directed from $v$ to $w$.
Generally speaking, TSP are concerned with _walks_ in the given graph, which
can formally be defined as follows, see (schrijver2003combinatorial, ).

###### Definition 2.1 (Walk).

A walk in a graph $G=(V,E)$ is a sequence

$\mathcal{S}=\left(v_{0},e_{1},v_{1},\ldots,e_{k},v_{k}\right),$

where $e_{i}=\\{v_{i-1},v_{i}\\}$ or $e_{i}=(v_{i-1},v_{i})$ for all
$i\in[k]:=\\{1,\ldots,k\\}$ in an undirected or directed graph, respectively.
A walk is called _closed_ if $v_{k}=v_{0}$. A walk is called _simple_ if no
nodes appear more than once in the sequence except for potentially
$v_{0}=v_{k}$. A simple closed walk is called _circuit_. A simple walk that is
not a circuit is called _path_.

A walk in an undirected graph implicitly defines a direction for the edges on
the walk. A circuit containing all nodes of the graph is usually referred to
as a Hamiltonian Circuit and a path containing all nodes is accordingly called
Hamiltonian Path.

There are variants of TSP that distinguish between _visiting_ and _traversing_
a node, e.g., depending on whether a traveler stops in a city or just passes
through. To this end, we allow to drop nodes from a walk, i.e., more than one
edge may appear in the sequence between two nodes provided that
consistency222Should a walk consist solely of undirected edges between the
same two nodes, dropping both nodes may lead to an ambiguity about the
direction. In this case, we assume that the originating proper walk can be
restored from the context. is maintained. In this light, $v\in\mathcal{S}$
refers to a node that is visited by $\mathcal{S}$, i.e., explicitly appears in
$\mathcal{S}$. We call a walk proper if it is an alternating sequence of nodes
and edges. If a walk $\mathcal{S}$ is not proper, then we call the inclusion-
wise maximal walk with the same set of edges the _originating proper walk_ of
$\mathcal{S}$. Let $(v_{1},\ldots,v_{k})$ be the sequence of visited nodes of
some walk. Accordingly, we define $visits_{\mathcal{S}}(v):=|\\{i:v_{i}=v\\}|$
as the multiplicities in $\mathcal{S}$ for all $v\in V$. If the walk is clear
from the context, we may omit the subscript $\mathcal{S}$. Moreover, we define
the sequence of traversed nodes of $\mathcal{S}$ as the sequence of visited
nodes of the originating proper walk $\mathcal{W}$. Accordingly, we have
$traversals_{\mathcal{S}}(v):=visits_{\mathcal{W}}(v)$. If no distinction is
made between visited and traversed nodes, then, as the default, the node is
traversed.

In what follows, we sometimes refer to parts of a walk. For convenience, we
define the following notation.

###### Definition 2.2 (Parts of a Walk).

Let $\mathcal{S}:=(v_{0},e_{1},\ldots,v_{k})$ be a walk. We use the notation

  * •

$\mathcal{S}_{V}$ for the sequence of visited nodes of a walk,

  * •

$V_{\mathcal{S}}:=\\{v\in V:v\in\mathcal{S}\\}$ for the set of visited nodes
of a walk,

  * •

$\mathcal{S}_{E}$ for the sequence of edges of a walk,

  * •

$E_{\mathcal{S}}:=\\{e\in E:e\in\mathcal{S}\\}$ for the set of traversed edges
of a walk,

  * •

$\mathcal{S}_{\leq i}:=(v_{0},e_{1},\ldots,v_{i})$ for the prefix of a walk
ending at its $i$-th visited node where $i\leq k$,

  * •

$\mathcal{S}_{<i}:=\mathcal{S}_{\leq i}-v_{i}$ where the last node is removed
from the sequence,

  * •

$\mathcal{S}_{i}:=\mathcal{S}_{\leq i}-\mathcal{S}_{<i}$, which is the $i$-th
visited node of the sequence,

  * •

$start(\mathcal{S})$ is the first traversed node of $\mathcal{S}$, i.e.,
$start(\mathcal{S})=\mathcal{W}_{V}(0)$ where $\mathcal{W}$ is the originating
proper walk of $\mathcal{S}$,

  * •

$end(\mathcal{S})$ is the last traversed node of $\mathcal{S}$, i.e.,
$end(\mathcal{S})=\mathcal{W}_{V}(k)$ where $\mathcal{W}$ is the originating
proper walk of $\mathcal{S}$ and $k=|\mathcal{W}_{V}|-1$.

The difference between $\mathcal{S}_{V}$ and $V_{\mathcal{S}}$ is that the
former is a sequence with potentially multiple occurrences of some nodes,
while the latter is a set of nodes without multiplicities. This distinction is
necessary to model the objective for some TSP variants.

A _cost function_ $c$ can be any map from the set of walks to the reals.
However, it is most common to consider separable functions that are sums over
costs of visited nodes and edges of the walk where occurrences are counted
with multiplicities, i.e.,

$c(\mathcal{S})=\underbrace{\sum_{e\in\mathcal{S}_{E}}c_{1}(e)}_{=:c_{2}(\mathcal{S}_{E})}+\underbrace{\sum_{v\in\mathcal{S}_{V}}c_{2}(v)}_{=:c_{1}(\mathcal{S}_{V})},$

where $c_{1}:E\to\mathbb{R}$ and $c_{2}:V\to\mathbb{R}$. Moreover, there are
variants that do not require to visit all nodes, but penalties $p$ occur for
nodes that are not visited. For convenience, we use the notation

$\overline{p}(\mathcal{S}_{V}):=\sum_{v\in V\setminus V_{\mathcal{S}}}p(v).$

For a directed edge $(u,v)\in E$, we will use the notation $c(u,v)$ to refer
to its cost instead of $c((u,v))$. Similarly, we write $c(u,v)$ for an
undirected edge $\\{u,v\\}$ instead of $c(\\{u,v\\})$, where it is implicitly
assumed that $c(u,v)=c(v,u)$. Moreover, $c(\mathcal{S})$ always refers to the
total costs even if the domain of $c$ is not the set of walks, i.e., we
consider a suitable lifting of $c$. For some TSP variants, it is necessary to
consider parallel edges between the same pair of nodes, e.g., when their costs
are time-dependent or multiple cost functions are involved where no edge
dominates the other in all aspects.

edge $e$ | $c_{1}(e)$
---|---
$e_{1}$ | 2
$e_{2}$ | 1
$e_{3}$ | 2
$e_{4}$ | 2
$e_{5}$ | 3

node $v$ | $c_{2}(v)$
---|---
$v_{1}$ | 1
$v_{2}$ | 1
$v_{3}$ | 1
$v_{4}$ | 1

Figure 1. Example graph and edge and node costs of a TSP.

Figure 1 shows an example graph of a TSP with
$V=\\{v_{1},v_{2},v_{3},v_{4}\\}$ and $E=\\{e_{1},e_{2},e_{3},e_{4},e_{5}\\}$
as well as associated edge and node costs. Let us consider the following three
walks in the graph from Figure 1:
$\mathcal{S}_{1}=(v_{1},e_{1},v_{2},e_{2},v_{3},e_{2},e_{3},v_{4},e_{4})$, in
which node $v_{2}$ is visited before node $v_{3}$, the walk
$\mathcal{S}_{2}=(v_{1},e_{1},v_{2},e_{2},v_{3},e_{2},v_{2},e_{3},v_{4},e_{4})$,
in which node $v_{2}$ is visited twice, and the walk
$\mathcal{S}_{3}=(v_{1},e_{1},v_{2},e_{2},v_{3},e_{2},e_{3},v_{4},e_{5})$,
which uses an alternative edge $e_{5}$ to close the circuit. The sequence
$\mathcal{S}_{E}=(e_{1},e_{2},e_{2},e_{3},e_{4})$ describes the edges of the
first two walks. In this sequence, visited vertices remain implicit and the
sequence leaves open whether the traveler visits node $v_{2}$ before or after
node $v_{3}$ or even twice. The costs of these walks in our example are
$c(\mathcal{S}_{E})=8$, $c(\mathcal{S}_{1})=12$, $c(\mathcal{S}_{2})=13$, and
$c(\mathcal{S}_{3})=13$. In a TSP variant where we do not care about node
costs and only consider the length of the tour, $\mathcal{S}_{E}$ is
sufficient as a representation of a solution.

##  3\. Related Work

Until today, there is no comprehensive review of polynomial-time
approximability and inapproximality results available. Papers that publish new
theoretical results usually limit their related work section to earlier work
with results for the TSP variant studied in the paper or on publications of
algorithmic techniques that are used or improved to achieve a new result.
Excellent examples are (vygen2012, ), which focuses on the asymmetric,
symmetric, and graphic variants of the "standard" TSP, and
(traub2020approximation, ), which focuses on asymmetric and symmetric variants
of the "standard" TSP and the path TSP. A recent and comprehensive survey on
the Generalized TSP was published in (pop2023comprehensive, ), which provides
an overview on exact and approximate algorithms, transformation methods, and
heuristic and metaheuristic algorithms. A survey on heuristic approximations
was published in (kongkaew2014survey, ). Older surveys are (BDDVW1998, ),
which resents an overview of polyniomal-time solvable TSP variants known until
1998, and (laporte1992traveling, ; bern1997approximation, ), which review
selected exact and approximate algorithms for the "standard" TSP. A very good
overview on the TSP and a bibliography of historic TSP publications can be
found at https://www.math.uwaterloo.ca/tsp/index.html.

With the growing number of publications on the TSP in the 1990s, an increasing
desire to classify problem variants and to clarify the relationships between
published results can be observed. A paper published in 1991 by Langevin et
al. (langevin1990, ) reviews and compares different formulations of the TSP
with the goal of establishing correspondences between the different published
results. Another analysis and review of publications on time-dependent TSP
variants was published in 1995 by Gouveia and Voß (gouveia1995classification,
). A bibliography of 500 publications on TSP, vehicle routing, chinese
postman, and rural postman problems was published in 1995 by Laporte and Osman
(laporte1995, ), which was motivated by ``the abundant and somewhat
disorganized literature'' on these problems. This paper used a ``simple and
relatively broad classification scheme'' specifying the properties of the
graph, the objective, and a set of constraints. However, none of the
attributes or their values were formally defined because the focus of this
classification scheme was more on providing a taxonomy to organize and
structure the comprehensive list of references collected in the paper.

A successful attempt to classify TSP variants was published in 1991 by Reinelt
with the Traveling Salesperson Problems Library TSPLIB (reinelt1991, ). TSPLIB
had the goal of providing the community with challenge problems and solutions.
It was, to our knowledge, the first attempt that introduced specific
attribute/value pairs to define TSP variants. For example, the keyword TYPE
with possible values such as TSP, ATSP, or CVRP identifies symmetric TSP,
asymmetric TSP, or vehicle routing problems. The attribute CAPACITY is used to
denote the capacity of vehicles in a vehicle routing problem, GRAPH_TYPE
specifies whether the graph is complete or sparse, and EDGE_TYPE specifies
whether edges are directed or undirected. Costs are defined in the
EDGE_WEIGHT_TYPE attribute and can comprise different distance metrics such as
euclidean, Manhattan, or geographical distances. Some of Reinelt's keywords
and values also occur in our definition scheme.

In the decades following the work on TSPLIB, many new TSP variants were
studied; however, less interest can be observed in the community to adopt a
uniform scheme for defining these variants. The book by Applegate et al.
(applegate2011, ) from 2011 touches upon ``the many flavors of the TSP'' in
its introductory chapter but only consider the ``standard'' TSP that is
equivalent to computing a Hamiltonian circuit. In (deineko2014, ), a complete
classification for restricted polynomially-time solvable variants of the TSP
with so-called four-point conditions is presented to establish a precise
border between polynomially-time solvable and NP-hard variants of this
restricted problem.

For the TSP with several travelers, also known as the multiple TSP or MTSP,
and commonly denoted as the vehicle routing problem (VRP), several proposals
for a classification scheme or taxonomy have been made over the last decades.
They are motivated by the high practical relevance of the problem and the huge
number of variants in which a VRP can occur in practice. Interestingly, work
on systematizing VRP variants is more focused on defining taxonomies rather
than on formally defining the properties that characterize a variant.
Researchers implicitly seem to take it for granted that there is a uniform and
precise understanding of a problem variant and, therefore, naming the problem
variant is sufficient for its precise identification.

The first VRP taxonomy dates back to Bodin (bodin1975, ) in 1975, who observed
that ``this problem has a reasonably natural taxonomic structure'' and that
``many vehicle routing and scheduling problems can be classified by their
underlying properties''. Bodin introduced three characteristics of a VRP:
First, the network classification that specifies whether it is a node routing,
branch routing, or general routing problem. Second, the number of vehicles,
and third, the type of the algorithm or solution method, which is used to
solve a problem, e.g., exact or heuristic methods. In (bodingolden1981, ), the
attributes to characterize a VRP variant were refined into 13 different
categories and 7 different types of solution methods were distinguished. All
later proposals for the classification of VRPs are variations of this early
work.

In 1990, Desrocher et al. (desrochers1999, ) introduced a TSP classification
scheme with four fields: addresses, vehicles, problem characteristics, and
objectives. A wide variety of attributes and possible values is introduced for
each field, but the paper does not provide a formal definition for the
attributes. To specify the scheme, a context-free grammar was used and several
examples of well-known VRP and TSP were classified. For example, the TSP with
time windows is denoted by $1,tw_{j}\mid 1\mid\Delta\mid T$. The proposal
nevertheless was not successful, perhaps due to the lack of formal definitions
for the attributes and values. Several different taxonomies were published
over time, many of them with the goal of systematically reviewing the abundant
literature on TSP/VRP variants; for example, comprehensive reviews on
transportation network design and routing problems can be found in
(current1986, ; current1993, ). Dynamic VRP variants where ``part of the input
required to solve it (that is, which nodes actually request service) is
revealed to the dispatcher concurrently with the determination of the route''
are reviewed in (psaraftis1995, ). Variants of the location-routing problem
LRP that combines tour planning and facility location planning within the same
problem are reviewed in (min1998, ). An overview on variants of the dynamic
resource transformation problem can be found in (powell2001, ). A critical
review of these classification proposals was published in (eksioglu2009, ) in
2009, which proposes yet another taxonomy to classify so-called generalized
routing problems. This taxonomy is meant to be extensible and provides the
following 7 classes: (1) shortest path problem, (2) Chinese postman problem,
(3) rural postman problem, (4) dial-a-ride service route problem, (5) arc
routing problem, (6) TSP, and (7) VRP. None of these problem classes is
formally and precisely defined.

The literature survey in (pillac2013, ) from 2013 reviews VRP application
areas and algorithm types based on the taxonomy from (psaraftis1995, ) and
simplifies it into a 4-quadrants model using information quality
(stochastic/deterministic) and information evolution (static/dynamic) as its
two axes. A literature review of green vehicle routing problems can be found
in (lin2014, ), which introduces a large set of names for various problem
variants, but again without providing precise formal definitions. Further
taxonomic variations are introduced in these VRP surveys (montoya2015, ;
lahyani2015, ; psaraftis2016, ; braekers2016, ; Cheikhrouhou2021, ) published
between 2015 and 2021. A more formally defined classification scheme of VRPs
can be found in (irnich2014, ) from 2014. Formal definitions for various VRP
variants are given and problems are classified based on the (road) network
structure, the type of transportation requests, constraints that affect each
route individually, the fleet composition and location, inter-route
constraints, and optimization objectives. Formal definitions of attributes and
values to characterize the problems along these properties are not given.
Instead, the paper informally reviews possible definitions from related work.

The literature offers all these proposals, none of which seem to have
convinced researchers and practitioners. As evidence, take for example the
fact that none of the available proposals is uniformly adopted by all papers
within the research paper collections published between 2008 and 2020
(golden2008, ; Toth2014, ; derbel2020, ). We see several reasons for this
ongoing quest for an easy-to-use and extensible approach to precisely
characterize TSP/VRPs: First, a taxonomy introduces a predefined hierarchical
structure to align or separate problem classes, which is too rigid to cover
the manifold variants under study. Secondly, most of the proposals introduce
problem attributes without providing precise mathematical definitions of these
attributes and their possible values. This has the consequence that the
classification of a problem instance often depends on the informal problem
description of a problem class, which might give room for interpretation.
Thirdly, most VRP taxonomies serve as a basis to organize a survey of the
scientific literature and are less aimed at providing a formalism that would
support researchers and practitioners in the precise definition of their
problem variant. Last but not least, we believe that the definition of the
problem and possible solution methods/algorithms should be clearly separated.
However, as most VRP taxonomies are used to review the scientific literature,
it is not surprising that adopted solution methods are an essential part of
most taxonomies.

The work on TSP-T3CO is inspired by classification schemes used to
characterize scheduling problems. A first such scheme was introduced by
Conway, Maxwell, and Miller in their seminal book from 1967 (conway1967, ). It
uses four information categories to describe a scheduling problem, where each
category introduces different attributes and possible values and is denoted
with an upper-case letter: A \- jobs and operations to be processed, B \-
number and types of machines available for processing, C \- the variant of the
scheduling problem such as, for example, flow-shop or randomly routed job-
shop, D \- evaluation criteria (objective) for the evaluation of a schedule
such as, for example, the average or maximum completion time, flow time,
lateness or tardiness. A notation was defined that separates each category by
a slash and lists the attribute values. As examples for this notation, the
problem $n/2/F/F_{max}$ asks to minimize the maximum flow-time, which is the
time the last job is finished, for $n$ jobs in a 2-machine flow shop, whereas
the problem $n/m/G/F_{max}$ asks to schedule $n$ jobs in a job shop with $m$
machines using the same objective.

It took some time for this classification scheme to gain influence. A survey
paper (BakshiArora1969, ) from 1969 and the textbook by Baker from 1974
(baker1974, ) do not make use of it although both give a comprehensive
overview on classes of scheduling problems. The collection edited by Coffman
(coffman1976, ) in 1976 also provides a detailed review of the state of the
art in scheduling algorithms in the 1970s but uses its own scheduling model
with the elements resources, task systems, sequencing constraints (focusing on
preemption/non-preemption and task priorities), and performance measures. A
task system is specified by a set of tasks, precedence constraints, execution
times, resource requirements, and weights being interpreted as deferral costs.
The model is described using a specific notation and was used by all
contributing authors of this book.

It was not until the paper by Graham et al. in 1979 (graham1979, ) that a
3-field classification scheme $\alpha\mid\beta\mid\gamma$ was introduced, but
it does not explicitly refer to the work by Conway (conway1967, ). In this
scheme, $\alpha$ characterizes the machine environment, $\beta$ specifies the
job characteristics, and $\gamma$ refers to the objective. Similarly to
(conway1967, ), a shorthand notation was introduced that separates fields by
vertical lines and only lists attribute values between the lines. In this
notation, the example $1\mid prec\mid L_{max}$ specifies the problem to
minimize the maximum lateness of jobs with precedence constraints on a single
machine. We build on the idea of clearly separated fields denoted by Greek
letters and also make use and extend the idea of the shorthand notation.

Comparing both (graham1979, ) and (conway1967, ), one notices that the
$\alpha$-field combines information from the B- and C-field and that the
$\gamma$-field corresponds to the D-field. The $\beta$-field is a new field
and is refined further to specify job characteristics such as preemption or
required resources. The data that defines a specific problem instance is
separated as so-called ``job data'' and is not part of the classification
scheme defined in (graham1979, ), whereas in (conway1967, ) it is part of the
A-field in the classification scheme. The book chapter by Lawler et al.
(lawler1993, ) in 1993 makes extensive use of the classification scheme by
Graham et al (graham1979, ). The textbook by Brucker (brucker1995, ) from 1995
uses, refines, and slightly modifies this classification scheme further. For
example, additional attributes are introduced for the $\alpha$-field to
characterize more complex machine environments involving multi-processor
tasks. Both publications (lawler1993, ; brucker1995, ) also make extensive use
of the shorthand notation introduced in (graham1979, ) to specify a wide range
of problem variants and to provide an overview of known complexity-theoretic
results and algorithms for these variants.

Today, the classification scheme $\alpha\mid\beta\mid\gamma$ is widely
established to characterize scheduling problems and is used, for example, in
(dawande2005sequencing, ; pan2013comprehensive, ; pfund2004survey, ;
ruiz2005comprehensive, ; sayadi2010discrete, ) to name a few publications with
an overview character. In the influential textbook by Pinedo (pinedo2016, ),
the $\alpha$-field contains a single entry with one out of 9 possible values
to characterize the machine environment. The $\beta$-field is more flexibly
used to specify processing characteristics and constraints and can contain
several entries that are separated by ``,''. Pinedo lists an initial set of 12
possible entries emphasizing that ``any other entry that may appear in the
$\beta$-field is self explanatory'' (pinedo2016, , p. 17). The $\gamma$-field
describes the single (and to be minimized) objective. In the handbook on
scheduling by Błażewicz et al. (blazewicz2019, ) from 2019, the
$\alpha\mid\beta\mid\gamma$ classification scheme is used with the
$\alpha$-field being refined into two subfields and the $\gamma$-field being
refined into 8 subfields.

Other fields tackling optimization problems have also developed classification
schemes: a taxonomy to classify black-box and simulation-based optimization
problems based on constraint classes is proposed in (digabel2015, ), multi-
disciplinary design optimization architectures are surveyed and classified in
(martins2013, ), and a classification of formulations for the optimization of
distributed systems can be found in (tosserams2009, ). A comprehensive
overview on graph problems and the P/NP boundary can be found in (isgci, ).

Researchers in Artificial Intelligence have also developed formally defined
definition schemes and taxonomies to characterize problem variants. A well-
known example is the work on ontological representations using so-called
description logics (also known as concept languages or terminological logics),
which are fragments of first-order predicate logic. A large family of language
variants is defined with the goal to determine decidable fragments of first-
order predicate logic and to study the complexity of reasoning algorithms
deciding for example subsumption in these fragments, see (baader2007, ;
baader2017, ) for an overview. The theoretical work on the decidability and
complexity of various description-logic variants has provided the foundation
for the semantic web (Berners-Lee2001, ) and the Ontology Web Language OWL
(owl2012, ). In AI planning, the Planning Domain Definition Language PDDL was
introduced in 1998 (mcdermott2000, ) and extended in 2003 (foxlong2003, ;
mcdermott2003, ) to achieve a standardized representation of planning problems
as the foundation to hold a regular competition among different planning
algorithms.333See https://www.icaps-conference.org/competitions/ PDDL
fragments of different expressivity were identified and defined the tracks
within this competition. The definition of the PDDL language was preceded by
research results on the complexity of planning problems in different planning
formalisms, e.g., (bylander1991, ; backstrom1995, ). Research results aiming
at understanding the border between tractable and intractable (NP-hard)
subclasses of problems were published for temporal reasoning using Allen's
Interval Algebra (nebel95, ) and for spatial reasoning using the Region
Connection Calculus (renz99, ).

##  4\. The TSP Definition Scheme TSP-T3CO

The TSP definition scheme TSP-T3CO is defined by the EBNF grammars444Following
the EBNF style introduced in (pattis1994, ), we use ( $\mid$ ) to list choices
and $\\{\\}$ to denote repetitions of 0 or more occurrences. Non-terminal
symbols are written in italics and terminal symbols are written within “”.
Strings in normal font such as ‘mathematical expression’, ‘string’, or ‘set’
have the standard meaning from computer science. in Figures 2 and 3, which
introduce a longhand and a shorthand notation for the definition of a TSP
variant using five different fields: The $\alpha$-field characterizes the
travelers, who are usually salespeople in TSP, but can also be vehicles,
robots, or any other entity that can move and is not stationary. The
$\beta$-field describes how often (each or a particular) node in the graph
needs to be visited by a traveler. The $\gamma$-field describes the tours or
constraints on possible tours a traveler may take. The $\delta$-field
describes the cost functions existing in the problem. Finally, the
$\epsilon$-field describes the objective(s) in the form of optimization
criteria or bounds on the costs. As already mentioned, these five fields give
the name to the definition scheme TSP-T3CO : the Traveler, the Targets, the
Tour, the Costs, and the Objectives.

TSP-T3CO $\Leftarrow$ ``$\langle\,$'' $\alpha$-field $\beta$-field
$\gamma$-field $\delta$-field $\epsilon$-field $\,``\rangle$'' $\alpha$-field
$\Leftarrow$ (``$\alpha$'' $\mid$ ``traveler'') ``:'' $\\{$ attribute ``;''
$\\}$ $\beta$-field $\Leftarrow$ (``$\beta$'' $\mid$ ``target'') ``:'' $\\{$
attribute ``;'' $\\}$ $\gamma$-field $\Leftarrow$ (``$\gamma$'' $\mid$
``tour'') ``:'' $\\{$ attribute ``;'' $\\}$ $\delta$-field $\Leftarrow$
(``$\delta$'' $\mid$ ``costs'') ``:'' $\\{$ cost function ``;'' $\\}$
$\epsilon$-field $\Leftarrow$ (``$\epsilon$'' $\mid$ ``objective'') ``:''
$\\{$objective ``;''$\,\\}$ attribute $\Leftarrow$ name value name
$\Leftarrow$ string value $\Leftarrow$ relation mathematical expression
relation $\Leftarrow$ ``='' $\mid$ ``$\leq$'' $\mid$ ``$<$'' $\mid$ ``$\geq$''
$\mid$ ``$>$'' $\mid$ ``$\in$'' cost function $\Leftarrow$ name ``:'' domain
``$\mapsto$'' range $\,\\{$``,'' attribute$\\}$ domain $\Leftarrow$ set range
$\Leftarrow$ set objective $\Leftarrow$ mathematical expression

Figure 2. EBNF for the TSP-T3CO longhand notation.

In the TSP-T3CO longhand notation, a pair of angle brackets encloses the five
fields. The description of each field begins with either a Greek letter or a
keyword denoting the field's name followed by a colon. In the $\alpha$,
$\beta$, and $\gamma$ field, a sequence of attribute-value pairs separated by
semicolons follows. An attribute is described by a name, a relation, and a
value. Names can be arbitrary strings, and values can be arbitrary
mathematical expressions, as TSP-T3CO is intended to be extensible and thus
does not impose a specific notation for attribute-value pairs. Accordingly,
also the list of relations to be used between names and values shown in Figure
2 is not meant to be final. Attribute-value pairs should be meaningful
mathematical expressions; for example, the $\in$-relation should only be used
with a set as a possible value.

In the $\delta$-field, the colon is followed by one or more definitions of
cost functions. A cost function is defined by a name, followed by a colon
after which the domain and range of the cost function are defined. An optional
sequence of attribute definitions may follow, which is separated by a comma
from the definition of the cost function(s). Domain and range specifications
can be arbitrary sets and no specific notation is imposed except the $\mapsto$
arrow between them.

In the $\epsilon$-field, the colon is followed by a sequence of objective
functions separated by semicolons. An objective function can be any
mathematically meaningful combination of cost functions from the
$\delta$-field and, hence, is only defined as an arbitrary string by the EBNF.
Usually, the objective may be either to minimize, maximize or bound (above or
below) the objective function(s) or any combination thereof.

The example below illustrates the longhand notation by defining a variant of
the ``standard'' TSP.555See Section 6.1 for a more detailed discussion of the
“standard” TSP. Attributes and values will be formally defined in Section 5.
We give here a brief informal explanation of each attribute as the example is
intended to illustrate the EBNF notation. In this ``standard'' TSP variant, a
single traveler (count = 1) visits each of the $n$ nodes of the graph exactly
once (visits = 1). The traveler may start at any node (start = False) and has
to return to the starting node at the end of the tour (circuit = True, end =
False). An undirected edge (undirected = True) exists between any two nodes
(complete = True). A cost function $c$ is defined with the set of edges $E$ as
its domain and the range being in the non-negative rational numbers. The
objective is to minimize the tour costs $\min c(\mathcal{S})$.

$\langle$ |  $\alpha:$ | count $=1$;
---|---|---
|  $\beta:$ | visits $=1$;
|  $\gamma:$ | start = False;
|  | end = False;
|  | circuit = True;
|  | complete = True;
|  | undirected = True;
|  $\delta:$ | c: $E\mapsto\mathbb{R}_{\geq 0}$;
|  $\epsilon:$ |  $\min c(\mathcal{S})$; $\rangle$

The EBNF for the shorthand notation of TSP-T3CO in Figure 3 introduces a very
compact notation that omits the names of fields and that separates fields by
vertical lines. For this purpose, the EBNF in Figure 3 redefines attribute
definitions, making the name, relation, and value optional. The intended usage
is as follows: As long as attribute values are uniquely defined across all
attributes and the same value is not used by different attributes, only the
value is listed in a field. If the value is non-unique or there is more than
one attribute defined for a field sharing the same range of values, the
attribute-value pair must be listed completely to achieve a precise
definition. For Boolean attributes with values True and False, the attribute
name is listed if the attribute has value True. The absence of a Boolean
attribute name indicates that the attribute has value False. The definition of
the $\delta$ and $\epsilon$ fields remains unchanged except that the name of
the fields are omitted. In this shorthand notation, there is no last semicolon
to end each field as vertical lines serve as separators between fields.

TSP-T3CO $\Leftarrow$ ``$\langle$'' $\alpha$-field ``$\mid$'' $\beta$-field ``$\mid$'' $\gamma$-field ``$\mid$'' $\delta$-field ``$\mid$'' $\epsilon$-field ``$\rangle$'' $\alpha$-field $\Leftarrow$ $\\{$attribute ``;''$\\}$ attribute $\beta$-field $\Leftarrow$ $\\{$attribute ``;''$\\}$ attribute $\gamma$-field $\Leftarrow$ $\\{$attribute ``;''$\\}$ attribute $\delta$-field $\Leftarrow$ $\\{$cost function ``;'' $\\}$ cost function $\epsilon$-field $\Leftarrow$ $\\{$objective ``;'' $\\}$ objective attribute $\Leftarrow$ (name $[$value]) | ($[$relation] mathematical expression) cost function $\Leftarrow$ name ``:'' domain ``$\mapsto$'' range $\,\\{$``,'' attribute$\\}$

Figure 3. EBNF for the TSP-T3CO shorthand notation. Rules for non-terminal
symbols not defined here can be found in Figure 2.

The TSP variant, which we defined above in the longhand notation, now simply
reads

$\langle\,=1\,|\,=1\,|\,\mbox{circuit; complete;
undirected}\,|\,c:E\mapsto\mathbb{R}_{\geq 0}\,|\,\min
c(\mathcal{S})\,\rangle$

in the TSP-T3CO shorthand notation. Only listing the relation and numeric
value $=1$ without the attribute name in the $\alpha$ and $\beta$-field yields
a unique definition of this TSP variant based on the initial list of
attributes that we propose for these fields in Section 5. All attributes in
the $\gamma$-field are Boolean attributes and therefore only the names of
these attributes that all have the value True are listed.

In Section 6, manifold examples of the shorthand notation will be shown. Some
of these examples impose additional constraints on a problem variant that are
for example exploited in the formal proof of an approximability result. These
constraints are often specific to a certain theoretical result. In this case,
the TSP-T3CO shorthand notation ends with $\rangle^{\oplus}$ and the
constraints are stated separately as text or formal definitions. If several
TSP-T3CO definitions in a publication require extensions, a running number
such as $\oplus 1$ can be added. In Section 8, we discuss how TSP-T3CO can be
extended to deal with MTSP and VRPs by introducing additional attributes for
the $\alpha$-field. An extension of TSP-T3CO may invalidate the uniqueness of
earlier attribute definitions. For example, it seems natural for a VRP to
describe the number and capacities of moving vehicles in the $\alpha$-field,
which would make a definition of just $=1$ in this field non-unique. We
therefore use versioning and explicitly state the year of publication of a
specific TSP-T3CO version.

##  5\. Formal Definition of Attribute-Value Pairs

In this section, we proceed with the formal definition of an initial set of
attributes and values r the $\alpha$, $\beta$, $\gamma$, and $\delta$-field
that we propose to start with in TSP-T3CO 2023. As the definition scheme is
extensible, we understand these definitions as an initial core set that can be
easily extended by researchers, with new values or attributes as needed. We
also develop the notation for the $\epsilon$-field further.

###  5.1. The Travelers Field $\alpha$

The $\alpha$-field describes the number of salespeople traveling
simultaneously, or equivalently the number of visiting sequences that are to
be found. In the case of multiple salespeople, it may also describe their
characteristics, such as capacities. For the ``standard'' TSP, there is just a
single salesperson who has to visit given cities. The case of several
salespeople leads to the vehicle routing problem, for which we briefly discuss
possible extensions of the $\alpha$-field in Section 8.

count: int | expression
The _count_ attribute describes the number of salespeople considered in the
problem; for example, the _count_ entry of the ``standard'' TSP is $=1$ as
exactly one salesperson exists in the problem (dantzig1954solution, ). The
classical vehicle routing problem (bellmore1974transformation, ; rao1980note,
), on the other hand, has _count_ $=k$ for some constant $k$.

  * $=1$

A solution consists of a single finite sequence.

  * $=\Theta(1)$

A solution consists of $k$ finite sequences, where $k=\Theta(1)$ is a fixed
parameter that is not part of the input.

  * $=k$

A solution consists of $k$ finite sequences, where $k\geq 2$ is part of the
input.

  * $\geq 1$

A solution consists of at least one finite sequence.

###  5.2. The Targets Field $\beta$-Field

The $\beta$-field describes which cities and how often each city has to be
visited and describes the targets of the tour. In the ``standard'' TSP, each
city has to be visited exactly once or at least once, but other variants
exist, which allow for certain cities not to be visited or ask for some cities
to be visited multiple times. A _solution_ of a TSP is a walk (see Section 2)
and the $\beta$-field describes properties a solution must satisfy.

_traversals_ : int | expression
The _traversals_ attribute describes how often each city is to be traversed in
a solution sequence. In the ``standard'' TSP (miller1960integer, ), in which
each city must be traversed exactly once, the attribute takes value $=1$. If
cities may be traversed multiple times, but must be traversed at least once,
the value of the _traversals_ attribute is $\geq 1$, which is the case for
example in the TSP with multiple visits (TMSP) (gutin2006traveling, ).
Furthermore, if each city should be traversed at most once and is allowed to
not be traversed at all, the _traversals_ attribute takes value $\leq 1$, cf.
(feillet2005traveling, ).

  * $=1$

For any solution $\mathcal{S}$ and all $v\in V$, it must hold that
$traversals_{\mathcal{S}}(v)=1$.

  * $=d$

For any solution $\mathcal{S}$ and all $v\in V$ it must hold that
$traversals_{\mathcal{S}}(v)=d$, where $d\geq 2$.

  * $=d(v)$

For any solution $\mathcal{S}$ and all $v\in V$, it must hold that
$traversals_{\mathcal{S}}(v)=d(v)$.

  * $\geq 1$

For any solution $\mathcal{S}$ and all $v\in V$, it must hold that
$traversals_{\mathcal{S}}(v)\geq 1$.

  * $\mathit{\geq 0}$

For any solution $\mathcal{S}$ and all $v\in V$, it must hold that
$traversals_{\mathcal{S}}(v)\geq 0$.

  * $\geq d(v)$

For any solution $\mathcal{S}$ and all $v\in V$, it must hold that
$traversals_{\mathcal{S}}(v)\geq d(v)$.

  * $\leq 1$

For any solution $\mathcal{S}$ and all $v\in V$, it must hold that
$traversals_{\mathcal{S}}(v)\leq 1$.

If one wants to further specify the value of an attribute, it is possible to
extend the string value. As an example, suppose one wishes to express that for
a given subset $D$ of $V$ any solution $\mathcal{S}$ must traverse each node
in $D$ at least once with no restrictions on the number of traversals of other
nodes. To express this, the value $\geq d(v)$ may be extended to $\geq
d(v)\in\\{0,1\\}$.

_visits_ : string
The _visits_ attribute describes how often each node is to be visited, i.e.,
how often each node occurs in a solution. Recall from Section 2 that a node
may be traversed without being visited. If every node is visited on each
traversal, it takes value _always_. If each traversed node is only visited
once, the attribute takes value _once_. If the traveler receives a bonus for
each visit of a node, but also consumes time when visiting a node, the
_visits_ attribute may have value $\geq once$ to say each node must be visited
at least once, but may also be visited multiple times, or it may have value
$\leq once$ to say that some nodes must not be visited.

  * = _always_

For any solution $\mathcal{S}$ and all $v\in V$, it must hold that
$visits_{\mathcal{S}}(v)=traversals_{\mathcal{S}}(v)$.

  * = _once_

For any solution $\mathcal{S}$ and all $v\in V$ such that
$traversals_{\mathcal{S}}(v)>0$, it must hold that
$visits_{\mathcal{S}}(v)=1$.

  * $\geq$ _once_

For any solution $\mathcal{S}$ and all $v\in V$ such that
$traversals_{\mathcal{S}}(v)>0$, it must hold that
$visits_{\mathcal{S}}(v)\geq 1$.

  * $\leq$ _once_

For any solution $\mathcal{S}$ and some $v\in V$ such that
$traversals_{\mathcal{S}}(v)>0$, it can hold that $visits_{\mathcal{S}}(v)\leq
1$.

If no distinction is made between visited and traversed nodes, then the visits
attribute does not appear in the TSP-T3CO variant definition. In the short-
hand notation, we can leave out the $=$ sign if there is no ambiguity, i.e.,
we write _always_ instead of _=always_.

_group_ : string
The nodes in the graph can be grouped into sets $\\{P_{1},\dots,P_{k}\\}$. The
_group_ attribute describes the properties of these groups/sets and how many
nodes in each group must be visited. Groups can be disjoint or overlapping and
exactly one or at least one node from each group must be visited, which is
described by the parameter = once or $\geq$ once in parentheses behind the
property value.

  * = partition (once)

For all $v\in V$, there exists a unique $i\in\\{1,\dots,k\\}$ such that $v\in
P_{i}$, and for any solution $\mathcal{S}$ and all $j\in\\{1,\dots,k\\}$,
there exists a unique $u\in V_{\mathcal{S}}$ such that $u\in P_{j}$.

  * = partition ($\geq$ once)

For all $v\in V$, there exists a unique $i\in\\{1,\dots,k\\}$ such that $v\in
P_{i}$, and for any solution $\mathcal{S}$ and for all $j\in\\{1,\dots,k\\}$,
there exists at least one $u\in V_{\mathcal{S}}$ such that $u\in P_{j}$.

  * = _cover_ (once)

For all $v\in V$, there exists at least one $i\in\\{1,\dots,k\\}$ such that
$v\in P_{i}$, and for any solution $\mathcal{S}$ and all
$j\in\\{1,\dots,k\\}$, there exists a unique $u\in V_{\mathcal{S}}$ such that
$u\in P_{j}$.

  * = _cover_ ($\geq$ once)

For all $v\in V$, there exists at least one $i\in\\{1,\dots,k\\}$ such that
$v\in P_{i}$, and for any solution $\mathcal{S}$ and all
$j\in\\{1,\dots,k\\}$, there exists at least one $u\in V_{\mathcal{S}}$ such
that $u\in P_{j}$.

The set of parameters may also be extended to include further information, for
example specify the number of nodes that should be traversed in each cluster
or how many clusters exist in the problem. Further, the number of clusters may
also be described by replacing the _partition_ value by _bipartition_ (if
there are exactly two clusters) or $k$-partition (if there are exactly $k$
clusters). Examples of such value specifications can be found in Section 6.5.

_covering_ : string
The _covering_ attribute describes the subset of nodes that is to be covered
by a solution walk, where a node $v$ is covered by a solution $\mathcal{S}$ if
it is either on the tour, i.e., $v\in V_{\mathcal{S}}$, or within a
predetermined cost bound to an arbitrary node on the tour. The values include
two parameters. The first parameter $c$ is the cost function used to measure
the shortest-path distance from a node to the solution walk, where $c$ must be
a cost function or expression over cost functions defined in the
$\delta$-field. The second parameter gives the bound $b$ on how far nodes are
allowed to be from the solution walk.

  * = _all_ $(c,\leq b)$

For any solution $\mathcal{S}$ and for all $v\in V$ there exists $u\in
V_{\mathcal{S}}$ such that, $u=v$ or $dist_{c}(u,v)\leq b$.

  * = _subset_ $(c,\leq b)$

For any solution $\mathcal{S}$ and for all $v\in D\subset V$ there exists
$u\in V_{\mathcal{S}}$ such that, $u=v$ or $dist_{c}(u,v)\leq b$.

###  5.3. The Tours Field $\gamma$

The $\gamma$-field characterizes the graph of the problem and defines possible
constraints on the tour such as a fixed start or end node or precedence
constraints. In many variants of the TSP, the underlying graph is complete,
i.e., every node can be reached from every other node, the salesperson needs
to return to its origin node at the end and neither start nor end node are
fixed.

_start_ : bool
The _start_ attribute defines whether the starting node of the tour is fixed
as for example in (an2015improving, ) or not.

  * = _True_

Given start node $s$, every solution $\mathcal{S}$ must satisfy
$start(\mathcal{S})=s$.

  * = _False_

For any solution $\mathcal{S}$, $start(\mathcal{S})$ can be any node in $V$.

_end_ : bool
The _end_ attribute defines whether the end node of the tour is fixed, as, for
example, in (an2015improving, ), or not.

  * = _True_

Given end node $t$, every solution $\mathcal{S}$ must satisfy
$end(\mathcal{S})=t$.

  * = _False_

For any solution $\mathcal{S}$, $end(\mathcal{S})$ can be any node in $V$.

_circuit_ : bool
The _circuit_ attribute describes whether solutions are closed walks and the
traveler returns to its start node at the end of the walk or not.

  * = _True_

Every solution $\mathcal{S}$ satisfies $start(\mathcal{S})=end(\mathcal{S})$.

  * = _False_

There may exist a solution $\mathcal{S}$ such that $start(\mathcal{S})\neq
end(\mathcal{S})$.

_graphtype_ : string
The _graphtype_ attribute defines characteristics of the underlying graph. For
example, a complete graph is considered in (dantzig1954solution, ).

  * = _complete_

For all $u,v\in V$: $\\{u,v\\}\in E$ if $G$ is undirected, or $(u,v)\in E$ and
$(v,u)\in E$ if $G$ is directed.

  * = _planar_

The graph is planar.

  * = _path_

The graph is a path, i.e., a tree with only 2 leaves.

  * = _cycle_

The graph is a circular graph.

  * = _binary tree_

The graph is a binary tree.

  * = _tree(b)_

The graph is a tree with $b$ leaves. Without the parameter $b$, the number of
leaves is arbitrary.

  * = _grid(m,n)_

The graph is a grid of size $m\times n$.

If none of the above attribute values are specified, the graph can be
arbitrary.

_edgetype_ : string
The _edgetype_ attribute defines properties of edges present in the graph.
Commonly occurring values are undirected, directed, or bidirected. In a
bidirected graph as, for example, considered in
(papadimitriou2006approximability, ), edges are directed, but whenever an edge
from some node $u$ to some node $v$ exists, the return edge from $v$ to $u$
must also exist. This enables the definition of problems where it is always
guaranteed that if one can travel directly between two nodes, one can travel
in both directions, but the edge costs depend on the traversal direction, such
as for example when cycling up or down a hill.

  * = _undirected_

Each edge $\\{u,v\\}$ is an unordered two-element subset of $V$.

  * = _directed_

Each edge $(u,v)$ is an ordered pair in $V\times V$.

  * = _bidirected_

Each edge $(u,v)$ is an ordered pair in $V\times V$ and $(v,u)\in E$.

_precedences_ : string
The _precedences_ attribute describes whether precedence constraints exist
between nodes in the graph, which specify whether certain cities have to be
visited before others, see, for example, (balas1995precedence, ;
koehler2021cable, ).

  * = _atomic_

There exists a set of atomic precedence constraints $A\subset V\times V$. Any
solution $\mathcal{S}$ must satisfy that for all $(u,v)\in A$, if there exists
$j$ such that $\mathcal{S}_{V}(j)=v$, then there must exist $i$ such that
$i<j$ and $\mathcal{S}_{V}(i)=u$.

  * = _arbitrary_

There exist constraints defined in some constraint language that are specified
outside the definition scheme. These constraints should be described in the
$\oplus$ extension of the TSP-T3CO definition.

The values are currently stated for visited nodes rather than traversed nodes
in a solution. However, they can be extended to traversed nodes.

_cluster_ : string
The _cluster_ attribute restricts the visiting order of nodes in the graph.
Nodes are grouped into clusters $\\{P_{1},\dots,P_{k}\\}$ and all nodes within
each cluster must be visited consecutively in a solution sequence. The cluster
can be partitions, where each node is in exactly one cluster (laporte1997tabu,
), or covers (hansknecht2021dynamic, ), where nodes may be in more than one
cluster. Two optional parameters in parentheses can follow the attribute value
to define further restrictions on the order in which the nodes are to be
visited. The first parameter order restricts a possible visiting order between
the clusters and the second parameter sequence restricts the visiting sequence
within a cluster, often specifying entry and exit nodes in a cluster.

  * = _partition_(order, sequence)

For all $v\in V$, there exists a unique $a\in\\{1,\dots,k\\}$ such that $v\in
P_{a}$ and any solution $\mathcal{S}$ must satisfy that if $i<j<l$ and
$\mathcal{S}_{V}(i)\in P_{a}$ and $\mathcal{S}_{V}(l)\in P_{a}$ then
$\mathcal{S}_{V}(j)\in P_{a}$.

  * = _cover( order, sequence)_

For all $v\in V$, there exists at least one $a\in\\{1,\dots,k\\}$ such that
$v\in P_{a}$ and any solution $\mathcal{S}$ must satisfy that if $i<j<l$ and
$\mathcal{S}_{V}(i)\in P_{a}$ and $\mathcal{S}_{V}(l)\in P_{a}$ then
$\mathcal{S}_{V}(j)\in P_{a}$.

For the optional order parameter, the value _ordered_ is defined:666The value
_unordered_ is the default value and the parameter can be omitted in this
case.

  * _ordered_

For any solution $\mathcal{S}$ and for all $i<j$ with $\mathcal{S}_{V}(i)\in
P_{a}$ and $\mathcal{S}_{V}(j)\in P_{b}$, it must hold that $a\leq b$.

For the optional sequence parameter, the following values are defined:

  * _start_

Given start nodes $\\{s_{1},\dots,s_{k}\\}\subset V$, any solution
$\mathcal{S}$ must satisfy that
$s_{j}=\mathcal{S}_{V}(\min\\{i:\mathcal{S}_{V}(i)\in P_{j}\\})$ for all
$j\in\\{1,\dots,k\\}$.

  * _startend_

Given start nodes $\\{s_{1},\dots,s_{k}\\}\subset V$ and end nodes
$\\{t_{1},\dots,t_{k}\\}\subset V$, any solution $\mathcal{S}$ must satisfy
that $s_{j}=\mathcal{S}_{V}(\min\\{i:\mathcal{S}_{V}(i)\in P_{j}\\})$ and
$t_{j}=\mathcal{S}_{V}(\max\\{i:\mathcal{S}_{V}(i)\in P_{j}\\})$ for all
$j\in\\{1,\dots,k\\}$.

  * _terminals_

Given a set of potential start and end nodes $T_{a}\subseteq P_{a}$ for each
$a\in\\{1,\dots,k\\}$, any solution $\mathcal{S}$ must satisfy that
$\\{\mathcal{S}_{V}(\min\\{i:\mathcal{S}_{V}(i)\in
P_{a}\\}),\mathcal{S}_{V}(\max\\{i:\mathcal{S}_{V}(i)\in P_{a}\\})\\}\subseteq
T_{a}$.

As before, the values can be extended to traversed nodes.

###  5.4. The Costs Field $\delta$

Several cost functions can be defined for a problem in the $\delta$-field.
They are identified by a unique name and specified by domain and range. The
syntax is uniformly defined for the longhand and the shorthand notation,
recall Figures 2 and 3:

$\textit{cost function}\Leftarrow\textit{name ``:'' domain ``$\mapsto$'' range
\\{ ``,'' attribute \\} }$

The _domain_ of the cost function is usually taken from the set of edges $E$
(edge costs) or nodes $V$ (node costs) in the graph. An example of using node
costs can be found in (laporte1990selective, ). The quadratic TSP as described
in (fischer2013symmetric, ) uses the pair of edges $E\times E$. The _range_ of
the cost function can be any subset of the real numbers $\mathbb{R}$. The
subsequent attributes are used to further characterize a cost function in the
$\delta$-field.

_property_ : string
The _property_ attribute is defined for cost functions with domain $E$. For
example, edge costs may satisfy the triangle inequality (ding2007two, ), be
determined by a pseudometric (glebov20175, ), a metric (karlin2021slightly, ),
a graphic metric (momke2011approximating, ), a planar metric (Kle2005, ) or a
euclidean metric (arora1996polynomial, ). Due to the non-uniform definitions
of pseudometric and quasimetric that we observed in the literature, we
introduce parameters to further characterize cost functions. Any premetric
properties are explicitly listed in "()". If multiple properties apply, the
most specific one should be listed. For example, _euclid_ is more specific
than _metric_ , _planar_ is more specific than _graphic_ , and _graphic_
implies _triangle_.

  * = (params)

The edge cost function satisfies some attributes of a metric that are
specified by parameters in "()".777In particular, self loops have costs 0,
i.e., if $(u,u)\in E$ then $c(u,u)=0$ for all $u\in V$, and edge costs are
non-negative. TSP with self loops with costs strictly larger than 0 or TSP
with negative edge costs, do not define a premetric.

  * = _metric_

The edge cost function satisfies the parameters _symmetry_ , _identity_ , and
_triangle_.

  * = _graphic_

The edge cost function is a metric and corresponds to the number of edges of
the shortest path between two nodes in an unweighted graph.

  * = _planar_

The edge cost function is a metric and corresponds to the cost of the shortest
path between two nodes in a planar graph with non-negative weights.

  * = _euclidean_

The edge cost function is determined by the euclidean metric.

  * = _euclidean plane_

The edge cost function is determined by a euclidean metric in the plane.

  * = _euclidean fixed dim_

The edge cost function is determined by a fixed-dimensional euclidean metric.

As possible parameters params, a subset of the following can occur in "()":

  * _identity_

For all $(u,v)\in E$, it holds that $c(u,v)>0$ if and only if $u\neq v$.

  * _triangle_

For all $u,v,w\in V$, it holds that $c(u,v)\leq c(u,w)+c(w,v)$.

  * _$\alpha$ -triangle_

For all $u,v,w\in V$, it holds that $c(u,v)\leq\alpha\cdot(c(u,w)+c(w,v))$.

  * _symmetric_

For all $(u,v)\in E$, it holds that $(v,u)\in E$ and $c(u,v)=c(v,u)$.888Note
that the value _undirected_ of the attribute _edgetype_ implies the parameter
_symmetric_ of the cost function. If symmetry is not required, then asymmetric
costs are permitted.

For cost functions with domain $E$ or domain $V$ or a combinations of both, we
define the following two attributes:

_partial_ : bool
The _partial_ attribute describes whether only some of the edge or node cost
are incurred on a tour. For example, if the cost corresponds to the
availability of produce in certain cities, then the traveler may only buy some
of the available produce, see for example (manerba2017traveling, ;
bontoux2008ant, ).

  * = _True_

A tour only incurs partial edge or node costs.

  * = _False_

A tour always incurs the full cost values.

_temporal_ : string
The _temporal_ attribute describes whether the cost function has a temporal
dependency and may thus change over time. Typical examples are cost functions
that depend on the cost of nodes or edges (hansknecht2021dynamic, ;
malandraki1996restricted, ) or on the number of edges
(gouveia1995classification, ; picard1978time, ) of the prefix of the walk at
the current node. Such cost functions may also only change a fixed number of
times, e.g., (broden2004online, ). In the Kinetic-based TSP or Moving-target
TSP, e.g., (helvig1998moving, ), nodes move with constant speed in a fixed
direction and edge costs between nodes change continuously.

  * = _time_

For all $u,v\in V$, $c(u,v)$ or $c(u)$ is a function of the arrival time of
the prefix of the walk at node $u$.

  * = _position_

For all $u,v\in V$, $c(u,v)$ or $c(u)$ depends on the number of edges and/or
nodes of the prefix of the walk at node $u$.

  * = _costzone_ $(k)$

The cost function satisfies the conditions of value _time_ and changes at most
$k-1$ times.

  * = _poszone_ $(k)$

The cost function satisfies the conditions of value _position_ and changes at
most $k-1$ times.

  * = _waiting_

When travelers arrive at a node $u$, they may wait before they visit the node
$u$.

  * = _kinetic_

Each node moves with constant speed in a fixed direction and edge costs
between nodes change continuously.

###  5.5. The Objectives Field $\epsilon$

The objectives field defines the objective(s) in the problem, i.e., which
costs are to be bounded, maximized or minimized and be written as an arbitrary
string. Suppose $c$ is a cost function specified in the $\delta$-field, then
$c(\mathcal{S})$ denotes the sum of costs of the walk $\mathcal{S}$ and
$\overline{c}(\mathcal{S})$ denotes the complement of these costs.

We will use simple arithmetic expressions in these strings, which are mostly
self-explanatory. For example, if two cost models $c_{1}$ and $c_{2}$ were
defined in the $\delta$-field and the objective is to minimize their sum, we
write $\min c_{1}(\mathcal{S})+c_{2}(\mathcal{S})$ in the $\epsilon$-field. If
the objective is to maximize their sum, we write $\max
c_{1}(\mathcal{S})+c_{2}(\mathcal{S})$ in the $\epsilon$-field. If there is a
constraint on the maximum value of the function over cost models, i.e., an
upper bound $b$, we write $c_{1}(\mathcal{S})+c_{2}(\mathcal{S})\leq b$. In
case of a lower bound $b$, we write for example
$c_{1}(\mathcal{S})+c_{2}(\mathcal{S})\geq b$.

##  6\. Review of Approximability Results

In this section, we review results for TSP variants known as the the
"standard" TSP, Path TSP, Bottleneck TSP, Maximum Scatter TSP, Generalized
TSP, Clustered TSP, Traveling Purchaser Problem, Profitable Tour Problem,
Quota TSP, Prize-Collecting TSP, Orienteering Problem, Time-dependent TSP, TSP
with Time Windows, and the Orienteering Problem with Time Windows. After a
brief informal description of the problem variant, we present an overview of
approximability and inapproximability results where we limit ourselves to only
peer reviewed results and focus on the best currently known bounds. We
selected a paper for inclusion in the review if the paper either uses the name
of the problem variant or provides a definition that is very close to other
publications using the name. For hybrid TSP variants, we only included the
Orienteering Problem with Time Windows due to the extensive body of results.
Further approximability results exist for other hybrid variants. For each
reference from the literature, we provide a TSP-T3CO definition using the
shorthand notation. The definition makes it possible to very compactly and
clearly summarize the results in table form and it clarifies the restrictions
under which a result holds.

In the presentation of the approximability results, we use an asymptotic
notation for upper and lower bounds. This typically includes big-O and
little-o for upper bounds, whereas big-$\Omega$ and little-$\omega$ is used in
lower bounds. Informally speaking, the difference between big-O and little-o
is similar to the difference between $\leq$ and $<$, whereas the difference
between big-$\Omega$ and little-$\omega$ is similar to the difference between
$\geq$ and $>$.

More formally, for a function $f:\mathbb{Z}_{\geq 0}\to\mathbb{R}$ we define:

  * •

$O(f(n)):=\\{g:\mathbb{Z}_{\geq 0}\to\mathbb{R}\,:\exists c,n_{0}>0,\forall
n\geq n_{0}:|g(n)|\leq c\cdot|f(n)|\\}$

is the set of functions that grow at most as fast as $f$.

  * •

$\Omega(f(n)):=\\{g:\mathbb{Z}_{\geq 0}\to\mathbb{R}\,:\exists
c,n_{0}>0,\forall n\geq n_{0}:|f(n)|\leq c\cdot|g(n)|\\}$

is the set of functions that grow at least as fast as $f$.

  * •

$o(f(n)):=\\{g:\mathbb{Z}_{\geq 0}\to\mathbb{R}\,:\forall c>0,\exists
n_{0}>0,\forall n\geq n_{0}:|g(n)|\leq c\cdot|f(n)|\\}$

is the set of functions that grow strictly slower than $f$.

  * •

$\omega(f(n)):=\\{g:\mathbb{Z}_{\geq 0}\to\mathbb{R}\,:\forall c>0,\exists
n_{0}>0,\forall n\geq n_{0}:|f(n)|\leq c\cdot|g(n)|\\}$

is the set of functions that grow strictly faster than $f$.

In general, we use $\epsilon$ to denote any arbitrarily small positive real
number. Though the asymptotic notation defines sets, we also use it in
mathematical expressions and equations. The former case describes a
transformed set by means of composition, whereas a statement is considered
true if it holds for at least one function in the corresponding set.
Furthermore, when a result holds for non-negative edge costs, it can be
generalized to also include negative edge costs unless there is a directed
cycle with negative costs. This is due to the fact that there exist node
potentials, see (schrijver2003combinatorial, ). In such a case, the node
potentials yield non-negative reduced costs by adding the potential difference
between the endpoints to the edge costs, which does not change the costs of
any cycle. Such node potentials can be found in polynomial time using the
Bellman-Ford algorithm.

From a complexity point of view, the encoding of the numbers in the input
matters. However, reals can be approximated by rationals to any desired degree
of accuracy such that the influence on approximation factors becomes
insignificant. We therefore use $\mathbb{R}$ for the domain of cost functions
unless further restrictions apply.

###  6.1. The ``standard'' TSP

We consider the ``standard'' TSP to be the problem of finding a shortest walk
through a graph traversing all cities and returning to the origin city at the
end. The edge costs may be assumed to be asymmetric (syslo1980generalizations,
) or some restrictions may be placed on the edge costs, for example that they
are euclidean (arora1996polynomial, ). Additionally, the underlying graph may
be considered to be complete (syslo1980generalizations, ) or incomplete
(bellmore1974transformation, ).

$\begin{array}[]{lr}\textbf{Variant}&\textbf{Reference}\\\
\hline\cr\hline\cr\langle=1\,|\,\geq 1\,|\,\mbox{circuit; complete;
directed}\,|\,c:E\mapsto\,\mathbb{R}\,|\,\min
c(\mathcal{S})\rangle&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{syslo1980generalizations}{\@@citephrase{,
}}{})}}\\\ \hline\cr\langle=1\,|\,=1\,|\,\mbox{circuit;
directed}\,|\,c:E\mapsto\mathbb{R}\,|\,\min
c(\mathcal{S})\rangle&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{bellmore1974transformation}{\@@citephrase{,
}}{})}}\\\ \hline\cr\hline\cr\end{array}$ Figure 4. Variants of the
``standard'' TSP.

It is a well-known fact that no polynomial time $\rho$-approximation algorithm
exists for the ``standard'' TSP in which each city is to be traversed exactly
once, where $\rho$ is any polynomial time computable function, unless P=NP. We
indicate this with $\infty$ as lower bound (see the first row of Figure 5). As
most variants of the TSP can be reduced to a ``standard'' TSP, this
inapproximability result generalizes to most of the variants presented in this
section. Furthermore, this result means that approximability results can only
exist for subvariants of the ``standard'' TSP, which simplify the problem by
applying further restrictions on the cost function, or by relaxing
restrictions on the tour.

An overview of approximability and inapproximability results is given in
Figure 5. Most importantly, the ``standard'' TSP with metric edge costs and on
a complete graph can at best be approximated with a ratio of $123/122$
(KLS2015, ). The first algorithm giving an upper bound better than $3/2$ for
the same variant was presented (karlin2021slightly, ), which is considered a
major breakthrough. If more restrictions are imposed on the values of the edge
costs, so required to be euclidean or given by a graphic metric of a planar
graph, then the ``standard'' TSP can be approximated arbitrarily closely i.e.,
with a ratio of $1+\epsilon$ in polynomial time.

Finally, note that

$\langle=1\,|\,=1\,|\,\text{circuit; complete;
undirected}\,|\,c:E\mapsto\mathbb{R}_{\geq 0},\text{ (triangle)}\,|\,\min
c(\mathcal{S})\rangle$

and

$\langle=1\,|\,\geq 1\,|\,\text{circuit;
undirected}\,|\,c:E\mapsto\mathbb{R}_{\geq 0}\,|\,\min c(\mathcal{S})\rangle$

are equivalent and thus any results that apply to one, also transfer to the
other.

$\begin{array}[]{lclcl}\textbf{Variant}&\textbf{Lower Bound}&&\textbf{Upper
Bound}&\\\ \hline\cr\hline\cr\langle=1\,|\,=1\,|\,\text{circuit;
undirected}\,|&\infty&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{Karp1972}{\@@citephrase{,
}}{})}}&&\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}\,|\,\min
c(\mathcal{S})\rangle\\\ \hline\cr\langle=1\,|\,\geq 1\,|\,\text{circuit;
bidirected}\,|&\frac{75}{74}&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{KLS2015}{\@@citephrase{,
}}{})}}&22+\varepsilon&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{TV2020}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq 0}\,|\,\min
c(\mathcal{S})\rangle\\\ \hline\cr\langle=1\,|\,=1\,|\,\text{circuit;
complete;
undirected}\,|&\frac{123}{122}&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{KLS2015}{\@@citephrase{,
}}{})}}&\frac{3}{2}-10^{-36}&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{karlin2021slightly}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq
0},\text{metric}\,|\,\min c(\mathcal{S})\rangle&&&&\\\
\hline\cr\langle=1\,|\,=1\,|\,\text{circuit; complete;
undirected}\,|&&&\frac{7}{5}&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{seboe2014}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq
0},\text{graphic}\,|\,\min c(\mathcal{S})\rangle&&&&\\\
\hline\cr\langle=1\,|\,=1\,|\,\text{circuit; complete;
undirected}\,|&&&1+\varepsilon&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{arora1996polynomial,Mit1999}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq
0},\text{euclid}\,|\,\min c(\mathcal{S})\rangle&&&&\\\
\hline\cr\langle=1\,|\,=1\,|\,\text{circuit; complete;
undirected}\,|&&&1+\varepsilon&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{Kle2005}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq
0},\text{planar}\,|\,\min c(\mathcal{S})\rangle&&&&\\\
\hline\cr\hline\cr\end{array}$ Figure 5. Approximability and inapproximability
results for the ``standard'' TSP.

###  6.2. Path TSP

In the Path TSP, also denoted as the $s-t$ Path TSP, the goal is to find the
shortest Hamiltonian path between two nodes $s$ and $t$ in the graph rather
than a cycle traversing all cities.

$\begin{array}[]{lr}\textbf{Variant}&\textbf{Reference}\\\
\hline\cr\hline\cr\langle=1\,|\,=1\,|\,\mbox{start; end; complete;
undirected}\,|\,c:E\mapsto\mathbb{R}_{>0},\mbox{metric}\,|\,\min
c(\mathcal{S})\rangle&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{an2015improving}{\@@citephrase{,
}}{})}}\\\ \hline\cr\langle=1\,|\,=1\,|\,\mbox{start; end; complete;
directed}\,|\,c:E\mapsto\mathbb{R}_{\geq 0},\mbox{metric}\,|\,\min
c(\mathcal{S})\rangle&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{seboe2013,seboeVanZuylen2016,zenklusen2019}{\@@citephrase{,
}}{})}}\\\ \hline\cr\langle=1\,|\,=1\,|\,\mbox{start; end;
undirected}\,|\,c:E\mapsto\mathbb{R}_{\geq 0}\,|\,\min
c(\mathcal{S})\rangle&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{traub2020beating}{\@@citephrase{,
}}{})}}\\\ \hline\cr\langle=1\,|\,\geq 1\,|\,\mbox{start; end;
undirected}\,|\,c:E\mapsto\mathbb{R}_{\geq 0}\,|\,\min
c(\mathcal{S})\rangle&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{traub2020reducing}{\@@citephrase{,
}}{})}}\\\ \hline\cr\hline\cr\end{array}$ Figure 6. Variants of the Path TSP.

For a long time, there was a gap between the best known approximation bounds
for the circuit version of the TSP compared to the path version of the TSP.
However, in 2020, it was shown that any $\alpha$-approximation for a standard
TSP can be converted into an $(\alpha+\epsilon)$-approximation for the
corresponding path variant (traub2020reducing, ). That is, for any standard
TSP with non-negative symmetric edge costs having some some property
$\mathbf{p}$

$\langle=1\,|\,\geq 1\,|\,\text{circuit; complete;
undirected}\,|\,c:E\mapsto\mathbb{R}_{\geq 0},\mathbf{p}\,|\,\min
c(\mathcal{S})\rangle$

that admits an $\alpha$-approximation, we have an
$(\alpha+\epsilon)$-approximation for the Path TSP where the non-negative
symmetric edge costs also have property $\mathbf{p}$

$\langle=1\,|\,\geq 1\,|\,\mbox{start; end; complete;
undirected}\,|\,c:E\mapsto\mathbb{R}_{\geq 0},\mathbf{p}\,|\,\min
c(\mathcal{S})\rangle$

for any arbitrarily small constant $\varepsilon>0$.The currently best known
upper approximation bounds for the Path TSP can thus be obtained from the
upper approximation bounds for the standard TSP by setting the circuit
attribute to False, the start and end attributes to True and by adding
$+\epsilon$ to the approximation bound.

Various hybrid variants of the Path TSP are also studied in the literature. An
example is the Metric Many-visit Path TSP (rothkopf1966traveling, ), in which
each city needs to be traversed a pre-specified number of times. It can be
defined in TSP-T3CO as

$\langle=1\,|\,d_{v}\,|\,\mbox{start; end; complete;
undirected}\,|\,c:E\mapsto\mathbb{R}_{\geq 0},\mbox{metric}\,|\,\min
c(\mathcal{S})\rangle$

A polynomial time approximation algorithm with an approximation ratio of 1.5
for this problem was devised in (berczi2020, ).

The Path TSP is also denoted in the literature as the Messenger Problem
(gutin2006traveling, ; menger1932botenproblem, ), the Wandering Salesman
Problem (djang1993wandering, ; papadimitriou1984two, ), or the Minimum
Hamiltonian Path problem (MHP) (hammar1999approximation, ).

###  6.3. Bottleneck TSP

The Bottleneck TSP differs from the ``standard'' TSP only in the objective
function (garfinkel1978bottleneck, ). Unlike in the ``standard'' TSP, where
the objective is to minimize the sum of edge costs along the solution path,
the objective of the bottleneck TSP is to minimize the maximum edge cost along
the path. Furthermore, the tour has to traverse all nodes, but is not required
to be a circuit.

$\begin{array}[]{lclcl}\textbf{Variant}&\textbf{Lower Bound}&&\textbf{Upper
Bound}&\\\ \hline\cr\hline\cr\langle=1\,|\,=1\,|\,\text{circuit; complete;
undirected}\,|&\omega(1)&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{PR1984}{\@@citephrase{,
}}{})}}&&\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}\,|\,\min\max\\{c(e):e\in
E_{\mathcal{S}}\\}\rangle\\\ \hline\cr\langle=1\,|\,=1\,|\,\text{circuit;
complete;
undirected}\,|&2&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{PR1984}{\@@citephrase{,
}}{})}}&2&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{PR1984}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq
0},\text{(triangle)}\,|&&&&\\\ \hskip 14.22636pt\min\max\\{c(e):e\in
E_{\mathcal{S}}\\}\rangle\\\ \hline\cr\langle=1\,|\,=1\,|\,\text{circuit;
complete; directed}\,|&&&\lceil
n/2\rceil&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{larusic2014asymmetric}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq
0},\text{(triangle)}\,|&&&&\\\ \hskip 14.22636pt\min\max\\{c(e):e\in
E_{\mathcal{S}}\\}\rangle\\\ \hline\cr\langle=1\,|\,=1\,|\,\text{circuit;
complete; bidirected}\,|&&&\tfrac{\tau}{\tau-1}(2\tau^{\lceil
n/2\rceil-1}-\tau^{\lceil
n/2\rceil-2}-1&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{larusic2014asymmetric}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq
0},\text{($\tau$-triangle)}\,|&&&&\\\ \hskip 14.22636pt\min\max\\{c(e):e\in
E_{\mathcal{S}}\\}\rangle\\\ \hline\cr\langle=1\,|\,=1\,|\,\text{circuit;
complete; bidirected}\,|&&&\tfrac{\lambda}{\lambda-1}(\lambda^{\lceil
n/2\rceil-1}+\lambda-2)&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{larusic2014asymmetric}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq
0},\text{($\lambda$-triangle)}\,|&&&&\\\ \hskip 14.22636pt\min\max\\{c(e):e\in
E_{\mathcal{S}}\\}\rangle\\\ \hline\cr\langle=1\,|\,=1\,|\,\text{circuit;
directed}\,|&2&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{AKS2021}{\@@citephrase{,
}}{})}}&O(\log n/\log\log
n)&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{AKS2021}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq
0},\text{(triangle)}\,|&&&&\\\ \hskip 14.22636pt\min\max\\{c(e):e\in
E_{\mathcal{S}}\\}\rangle\\\ \hline\cr\langle=1\,|\,=1\,|\,\text{complete;
bidirected}\,|&&&2+\gamma&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{kao2009approximation}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq 0}\,|&&&&\\\ \hskip
14.22636pt\min\max\\{c(e):e\in E_{\mathcal{S}}\\}\rangle^{\oplus 1}\\\
\hline\cr\hline\cr\end{array}$

$\oplus 1$::

  * –:

Each node $n_{i}$ is specified by a pair of numbers $(\alpha_{i},\beta_{i})$.

  * –:

The cost function is then given by:

(1)
$c(n_{i},n_{j})=d(\alpha_{i},\beta_{j})=\begin{cases}\int_{\alpha_{i}}^{\beta_{j}}f(x)dx&\text{if
}\beta_{j}\geq\alpha_{i}\\\ \int_{\beta_{j}}^{\alpha_{i}}g(x)dx&\text{if
}\beta_{j}<\alpha_{i}\\\ \end{cases}$

where the functions $f(x)$ and $g(x)$ are integrable and satisfy
$f(x),g(x)\geq 0$ for all $x$.

  * –:

The constant $\gamma$ satisfies
$\gamma\geq\tfrac{f(x)}{g(x)}\geq\tfrac{1}{\gamma}$ for all $x$.

Figure 7. Approximability and inapproximability results for the Bottleneck
TSP. The constant $\tau$ satisfies $\tau>1$, the constant $\lambda$ satisfies
$\lambda<1$, and $\gamma$ is a measure of the asymmetry of the problem, see
$\oplus 1$ for details.

The Bottleneck TSP is sometimes also called the MinMax TSP (kozma2015ptas, ).
A closely related variant is the Maximum Scatter TSP, where the objective is
to maximize the minimum cost of an edge on the tour, see Section 6.4.

###  6.4. Maximum Scatter TSP

The Maximum Scatter TSP (arkin99, ), similarly to the previously discussed
Bottleneck TSP, differs from the ``standard'' TSP in the objective function.
The objective here is to maximize the minimum edge cost along the path.
Furthermore, the tour has to traverse all nodes, but is not required to be a
circuit.

$\begin{array}[]{lclcl}\textbf{Variant}&\textbf{Lower Bound}&&\textbf{Upper
Bound}&\\\ \hline\cr\hline\cr\langle=1\,|\,=1\,|\,\text{circuit; complete;
undirected}\,|&\omega(1)&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{arkin99}{\@@citephrase{,
}}{})}}&&\\\ \hskip
14.22636ptc:E\mapsto\mathbb{R}_{>0}\,|\,\max\min\\{c(e):e\in
E_{\mathcal{S}}\\}\rangle\\\ \hline\cr\langle=1\,|\,=1\,|\,\text{circuit;
complete;
undirected}\,|&2&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{arkin99}{\@@citephrase{,
}}{})}}&2&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{arkin99}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq
0},\text{(triangle)}\,|\,\max\min\\{c(e):e\in E_{\mathcal{S}}\\}\rangle\\\
\hline\cr\langle=1\,|\,=1\,|\,\text{complete;
undirected}\,|&2&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{arkin99}{\@@citephrase{,
}}{})}}&2&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{arkin99}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq
0},\text{(triangle)}\,|\,\max\min\\{c(e):e\in E_{\mathcal{S}}\\}\rangle\\\
\hline\cr\langle=1\,|\,=1\,|\,\text{undirected;
cycle}\,|&&&1+o(1)&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{hoffmann2017maximum}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq 0},\text{euclidean
plane}\,|\,\max\min\\{c(e):e\in E_{\mathcal{S}}\\}\rangle^{\oplus 1}&&&&\\\
\hline\cr\hline\cr\end{array}$

$\oplus 1$::

All nodes are located on a rectangular equidistant grid with $m$ rows and $n$
columns.

Figure 8. Approximability and inapproximability results for the Maximum
Scatter TSP. When $m=n$ or $m=2$, the upper bound in (hoffmann2017maximum, )
is 1.

The Maximum Scatter TSP is, in general, NP-hard and no constant-factor
approximation algorithm for it exists, unless P=NP. Due to the restrictions on
the cost functions, the approximability results for the Bottleneck TSP can not
directly be translated to approximability results for the Maximum Scatter TSP.
As for the Bottleneck TSP, a best-possible polynomial time approximation
algorithm exists for the Maximum Scatter TSP achieving an approximability
ratio of 2. When the nodes lie on a line or a circle in the euclidean plane,
and the cost function is given by the euclidean distance between the nodes, an
exact linear time algorithm exists (arkin99, ). For the extension of the
Maximum Scatter TSP from direct neighbors to $m$-neighbors, further
approximability results exist (arkin99, ; chiang2005new, ). The Maximum
Scatter TSP is sometimes also called the MaxMin TSP (kozma2015ptas, ).

###  6.5. Generalized TSP

In the Generalized TSP, the nodes of $G$ are grouped into subsets and either
exactly one of the nodes or at least one node from each subset has to be
traversed. The subsets of nodes may be disjoint and form a partition of $V$,
see e.g., (snyder2006random, ), or they may overlap and form a cover of $V$,
see e.g., (noon1993efficient, ; noon1988generalized, ). In the variants
studied in (fischetti1997branch, ; noon1993efficient, ; noon1988generalized, ;
snyder2006random, ), the shortest circuit must be found that traverses exactly
one node in each subset once. In (laporte2002some, ), each subset must be
traversed exactly once, whereas in (noon1993efficient, ; noon1988generalized,
), each subset must be traversed at least once. Some variants of the
Generalized TSP are given in Figure 9.

$\begin{array}[]{lr}\textbf{Variant}&\textbf{Reference}\\\
\hline\cr\hline\cr\langle=1\,|\,\mbox{$\leq 1$; partition($\geq$
once)}\,|\,\mbox{circuit; complete;
undirected}\,|\,c:E\mapsto\,\mathbb{R}\,|\,\min
c(\mathcal{S})\rangle&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{fischetti1997branch}{\@@citephrase{,
}}{})}}\\\ \hline\cr\langle=1\,|\,\mbox{$\leq 1$, cover($\geq$
once)}\,|\,\mbox{circuit; complete;
directed}\,|\,c:E\mapsto\mathbb{R},\mbox{(triangle)}\,|\,\min
c(\mathcal{S})\rangle&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{lien1993transformation}{\@@citephrase{,
}}{})}}\\\ \hline\cr\langle=1\,|\,\mbox{$\leq 1$;
partition(once)}\,|\,\mbox{circuit; complete;
undirected}\,|\,c:E\mapsto\mathbb{R}\,|\,\min
c(\mathcal{S})\rangle&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{laporte2002some}{\@@citephrase{,
}}{})}}\\\ \hline\cr\langle=1\,|\,\mbox{$\leq 1$;
partition(once)}\,|\,\mbox{circuit; complete;
directed}\,|\,c:E\mapsto\mathbb{R}\,|\,\min
c(\mathcal{S})\rangle&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{laporte2002some}{\@@citephrase{,
}}{})}}\\\ \hline\cr\hline\cr\end{array}$ Figure 9. Variants of the
Generalized TSP.

In (tsiligirides1984heuristic, ), the following problem is also referred to as
the Generalized TSP, however, it would usually be classified as an
Orienteering Problem, cf. Section 6.11.

$\displaystyle\langle$ $\displaystyle=1\,|$ $\displaystyle\,\leq
1;\mbox{always}\,|\,\mbox{start; end; complete;
undirected}\,|\,c:E\mapsto\mathbb{R},\mbox{(triangle)};q:V\mapsto\mathbb{R}_{\geq
0}\,|\,c\leq b;\,\max q(\mathcal{S})\rangle$

When no assumptions are made about the compositions of the subsets, no
algorithm giving a constant factor approximation in polynomial time is known.
Figure 10 gives an overview of the three most general polynomial time
approximation bounds currently known. Some further polynomial time constant
factor approximation results for neighborhoods with specific properties can be
found in (dumitrescu2003approximation, ) where the subsets correspond to nodes
within neighborhoods in the plane and are either connected regions of the same
or similar diameter or are disjoint unit disks in the plane. Due to their
specificity, we have not included these in the overview here.

$\begin{array}[]{lclcl}\textbf{Variant}&\textbf{Upper Bound}&\\\
\hline\cr\hline\cr\langle=1\,|\,\mbox{$\leq 1$; $k$-partition($\geq$
once)}\,|\mbox{circuit; undirected}\,|&O(\log^{2}n\log\log n\log
k)&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{garg2000polylogarithmic}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636pt\,c:E\mapsto\mathbb{R}_{\geq
0},\mbox{(triangle)}\,|\,\min c(\mathcal{S})\rangle&&\\\
\hline\cr\langle=1\,|\,\mbox{$\leq 1$; $k$-partition (once, $k=O(\log
n)$)}\,|&1+\epsilon&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{khachay2020complexity}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636pt\mbox{circuit; complete;
undirected}\,|\,c:E\mapsto\mathbb{R}_{>0},\mbox{euclidean}\,|\,\min
c(\mathcal{S})\rangle^{\oplus 1}&&\\\ \hline\cr\langle=1\,|\,\mbox{$\leq 1$;
$k$-partition (once, $k=n-O(\log
n)$)}\,|&1+\epsilon&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{khachay2020complexity}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636pt\mbox{circuit; complete;
undirected}\,|\,c:E\mapsto\mathbb{R}_{>0},\mbox{euclidean}\,|\,\min
c(\mathcal{S})\rangle^{\oplus 1}&&\\\ \hline\cr\hline\cr\end{array}$

$\oplus 1$::

The nodes in the problem correspond to a set of points in the planar integer
grid and every non-empty cell of the grid forms a cluster $P_{i}$.

Figure 10. Approximability results for the Generalized TSP.

The Generalized TSP is also referred to as Set TSP or One-of-a-Set TSP, or
Group TSP in the literature, see for example (noon1993efficient, ;
fischetti1997branch, ; guha1998approximation, ).

###  6.6. Clustered TSP

In the Clustered TSP, the nodes of $G$ are grouped into subsets. All nodes in
$G$ must be traversed such that all nodes of one subset are traversed before
the nodes in another subset. Usually, the subsets $P_{1},\dots,P_{m}$ form a
partition of the set of nodes $N$ (laporte2002some, ; ding2007two, ).
Infrequently, this restriction is not made (guttmann2018approximation, ).
Sometimes, further restrictions on the subsets are made such as fixing a start
and end node (laporte1997tabu, ).

Most polynomial time approximability results for the Clustered TSP focus on
the case when the clusters are disjoint. When there is additionally an order
given in which the clusters should be traversed, a $5/3$ approximation is
possible in polynomial time, whether the solution is to be a path or cycle or
the start and end nodes are given or not. When the order of the clusters is
not given, only less good approximation ratios are currently known. Several
cases are covered in the literature depending on whether start and end nodes
in each cluster are given or not. An overview of the polynomial time constant
factor approximation results can be found in Figure 11.

$\begin{array}[]{lclcl}\textbf{Variant}&\textbf{Upper Bound}&\\\
\hline\cr\hline\cr\langle=1\,|\,=1\,|\,\mbox{start; end; circuit; complete;
undirected;
partition(ordered)}\,|&\frac{5}{3}&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{anily199953}{\@@citephrase{,
}}{})}}\\\ \hskip
14.22636ptc:E\mapsto\mathbb{R}_{>0},\mbox{(triangle)}\,|\,\min
c(\mathcal{S})\rangle&&\\\ \hline\cr\langle=1\,|\,=1\,|\,\mbox{start; end;
complete; undirected;
partition(ordered)}\,|&\frac{5}{3}&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{anily199953}{\@@citephrase{,
}}{})}}\\\ \hskip
14.22636ptc:E\mapsto\mathbb{R}_{>0},\mbox{(triangle)}\,|\,\min
c(\mathcal{S})\rangle&&\\\ \hline\cr\langle=1\,|\,=1\,|\,\mbox{circuit;
complete; undirected;
partition(ordered)}\,|&\frac{5}{3}&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{anily199953}{\@@citephrase{,
}}{})}}\\\ \hskip
14.22636ptc:E\mapsto\mathbb{R}_{>0},\mbox{(triangle)}\,|\,\min
c(\mathcal{S})\rangle&&\\\ \hline\cr\langle=1\,|\,=1\,|\,\mbox{circuit;
complete; undirected;
partition(startend)}\,|&1.875&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{kawasaki2020improving}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\,\mathbb{R}_{\geq 0},\mbox{(symmetric,
triangle)}\,|\,\min c(\mathcal{S})\rangle&&\\\
\hline\cr\langle=1\,|\,=1\,|\,\mbox{circuit; complete; undirected;
partition(start)}\,|&\frac{5}{2}&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{bao2017note}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\,\mathbb{R}_{\geq
0},\mbox{(triangle)}\,|\,\min c(\mathcal{S})\rangle&&\\\
\hline\cr\langle=1\,|\,=1\,|\,\mbox{circuit; complete; undirected;
partition(terminals)}\,|&1.714&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{kawasaki2020improving}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\,\mathbb{R}_{\geq
0},\mbox{(triangle)}\,|\,\min c(\mathcal{S})\rangle&&\\\
\hline\cr\langle=1\,|\,=1\,|\,\mbox{circuit; complete; undirected;
partition}\,|&1.9&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{bao2017note}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\,\mathbb{R}_{\geq
0},\mbox{(triangle)}\,|\,\min c(\mathcal{S})\rangle&&\\\
\hline\cr\langle=1\,|\,=1\,|\,\mbox{circuit; complete; undirected;
cover(startend)}\,|&4&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{guttmann2018approximation}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\,\mathbb{R}_{\geq
0},\mbox{(triangle)}\,|\,\min c(\mathcal{S})\rangle&&\\\
\hline\cr\hline\cr\end{array}$ Figure 11. Approximability results for the
Clustered TSP.

###  6.7. Traveling Purchaser Problem

In the Traveling Purchaser Problem, a set of $m$ products is to be purchased
at some nodes, which usually represent cities. Cities may offer the products
at different prices and only a limited number of products may be available at
each city. For each product, a demand $d_{i}$ is specified. For each city, the
product availability specifies how many units of this product are available
and the price for a unit of this product in this city is given. The aim is for
the traveler to visit a subset of the cities and purchase at least the
required demand of each product while minimizing the sum of purchasing and
traveling costs. At each visited node $v$, a certain amount
$\text{share}_{i}(v)$ of the available product is purchased. Figure 12 shows
variants of the Traveling Purchaser Problem.

$\begin{array}[]{ll}\textbf{Variant}&\textbf{Reference}\\\
\hline\cr\hline\cr\langle=1\,|\,\leq 1;\mbox{always}\,|\,\mbox{start; end;
circuit; complete;
directed}\,|&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{bontoux2008ant}{\@@citephrase{,
}}{})}}\\\ \hskip
14.22636ptc:E\mapsto\mathbb{R}_{>0};\\{\text{avail}_{i}\\}_{i=1}^{m}:V\mapsto\mathbb{Z}_{\geq
0},\mbox{partial;}\,\\{\text{price}_{i}\\}_{i=1}^{m}:V\mapsto\mathbb{R}_{\geq
0}\,|&\\\ \hskip 14.22636pt\forall
i\in\\{1,\dots,m\\}\,\,\text{share}_{i}(\mathcal{S}_{V})\geq d_{i};\forall
i\in\\{1,\dots,m\\}\,\forall v\in
V\,\text{share}_{i}(v)\leq\text{avail}_{i}(v)\,;&\\\ \hskip 14.22636pt\min
c(\mathcal{S})+\sum_{i=1}^{m}\sum_{v\in\mathcal{S}_{V}}\text{price}_{i}(v)\cdot\text{share}_{i}(v)\rangle&\\\
\hline\cr\langle=1\,|\,\leq 1;\mbox{always}\,|\,\mbox{start; end; circuit;
complete;
directed}\,|&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{manerba2017traveling}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\,\mathbb{R}_{\geq
0};\\{\text{avail}_{i}\\}_{i=1}^{m}:V\mapsto\mathbb{Z}_{>0},\mbox{partial;}\,\\{\text{price}_{i}\\}_{i=1}^{m}:V\mapsto\mathbb{R}_{>0}\,|&\\\
\hskip 14.22636pt\forall
i\in\\{1,\dots,m\\}\,\,\,\text{share}_{i}(\mathcal{S}_{V})\geq d_{i};\,\forall
i\in\\{1,\dots,m\\}\,\forall v\in
V\,\text{share}_{i}(v)\leq\text{avail}_{i}(v)\,;&\\\ \hskip 14.22636pt\min
c(\mathcal{S})+\sum_{i=1}^{m}\sum_{v\in\mathcal{S}_{V}}\text{price}_{i}(v)\cdot\text{share}_{i}(v)\rangle&\\\
\hline\cr\hline\cr\end{array}$ Figure 12. Variants of the Traveling Purchaser
Problem. The cost function $c$ denotes the edge costs, the cost function
$\text{avail}_{i}$ gives the availability of product $i$ at each node, and the
cost function $\text{price}_{i}$ gives the cost of product $i$ at each node.

The Traveling Purchaser Problem is polynomial-time solvable when the number of
products $k$ is $O(\log n)$, where $n$ denotes the number of cities, or when
the number of cities $n$ is $O(\log k)$ (xiao2020parameterized, ). Due to the
hardness of the general problem (manerba2017traveling, ), few algorithms with
performance guarantees are known. To our knowledge, there exists only a single
polynomial time approximation algorithm for the Traveling Purchaser Problem
with a performance guarantee, which we present in Figure 13. Fixed-parameter
tractable algorithms and complexity results for the Traveling Purchaser
Problem are given in (xiao2020parameterized, ).

$\begin{array}[]{lllll}\textbf{Variant}&\textbf{Upper Bound}&\\\
\hline\cr\hline\cr\langle=1\,|\,\leq 1;\text{always};\,|\,\mbox{start; end;
circuit; complete; undirected}\,|&\max\big{\\{}(1+\epsilon),&\\\ \hskip
14.22636ptc:E\mapsto\mathbb{R}_{\geq 0},\mbox{metric;
}\\{\text{avail}_{i}\\}_{i=1}^{m}:V\mapsto\\{0,1\\};\\{\text{price}_{i}\\}_{i=1}^{m}:V\mapsto\mathbb{R}_{\geq
0}\,|&\,\,\,\left(1+1/\epsilon\right)O(\log^{3}n\log\log
n)\big{\\}}&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{ravi1999approximation}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636pt\forall
i\in\\{1,\dots,m\\}\,\,\,\text{share}_{i}(\mathcal{S}_{V})\geq 1;&&\\\ \hskip
14.22636pt\forall i\in\\{1,\dots,m\\}\,\forall v\in
V\,\text{share}_{i}(v)\leq\text{avail}_{i}(v)\,;&\\\ \hskip 14.22636pt\min
c(\mathcal{S})+\sum_{i=1}^{m}\sum_{v\in\mathcal{S}_{V}}\text{price}_{i}(v)\cdot\text{share}_{i}(v)\rangle&&\\\
\hline\cr\hline\cr\end{array}$ Figure 13. Approximability result for the
Traveling Purchaser Problem.

###  6.8. The Profitable Tour Problem

In the Profitable Tour Problem, the traveler receives a penalty when not
visiting a city. The objective is to find the cheapest tour, when considering
travel costs $c$ and penalties $p$.999The profitable tour problem considered
in (dell1995prize, ) has as objective to minimize the sum of all edge costs
along the tour minus the sum of all profits along the tour. For complete
graphs, this problem is at least as hard to approximate as the corresponding
plain TSP variant, e.g., by setting the penalties to twice the maximum edge
cost. In the metric case, i.e., for a given complete undirected graph with
non-negative edge costs that satisfy the triangle inequality, Goemans and
Williamson (goemans1995general, ) have presented a framework that yields a
2-approximation. This was later slightly improved to roughly 1.98 by
(archer2011improved, ). In the directed case, there is a logarithmic upper
bound on the approximation factor (nguyen2012approximating, ). These results
are specified precisely in Figure 14.

$\begin{array}[]{lcl}\textbf{Variant}&\textbf{Upper Bound}&\\\
\hline\cr\hline\cr\langle=1\,|\,\leq 1;\mbox{always}\,|\,\text{circuit;
undirected;
complete}\,|&2-\frac{1}{n-1}&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{goemans1995general}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq
0},(\text{triangle});p:V\mapsto\mathbb{R}_{\geq 0}\,|\,\min
c(\mathcal{S})+\overline{p}(\mathcal{S})\rangle&&\\\
\hline\cr\langle=1\,|\,\leq 1;\mbox{always}\,|\,\text{circuit;
complete}\,|&\lceil\log_{2}(n)\rceil&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{nguyen2012approximating}{\@@citephrase{,
}}{})}}\\\ \hskip
14.22636ptc:E\mapsto\mathbb{R},(\text{triangle});p:V\mapsto\mathbb{R}_{\geq
0}\,|\,\min c(\mathcal{S})+\overline{p}(\mathcal{S})\rangle&&\\\
\hline\cr\langle=1\,|\,\leq 1;\mbox{always}\,|\,\text{start; circuit;
undirected;
complete}\,|&1.774&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{BlauthN2023}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq
0},(\text{triangle});p:V\mapsto\mathbb{R}_{\geq 0}\,|\,\min
c(\mathcal{S})+\overline{p}(\mathcal{S})\rangle&\\\
\hline\cr\langle=1\,|\,\leq 1;\mbox{always}\,|\,\text{start; end; undirected;
complete}\,|&\frac{241}{141}&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{archer2011improved}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq
0},(\text{triangle});p:V\mapsto\mathbb{R}_{\geq 0}\,|\,\min
c(\mathcal{S})+\overline{p}(\mathcal{S})\rangle&&\\\
\hline\cr\langle=1\,|\,\geq 0;\leq\mbox{once}\,|\,\text{circuit; undirected;
planar}\,|&1+\epsilon&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{BateniCEHKM2011}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq
0};p:V\mapsto\mathbb{R}_{\geq 0}\,|\,\min
c(\mathcal{S})+\overline{p}(\mathcal{S})\rangle&\\\
\hline\cr\hline\cr\end{array}$
Figure 14. Approximability results for the Profitable Tour Problem.

###  6.9. Quota TSP

In the Quota TSP, each node is associated with a profit $q$. The aim is for
the traveler to find a tour which visits each node at most once to collect the
corresponding profit so that the total profit exceeds a given _quota_ $b$
while minimizing the travel cost. Known approximability results are given in
Figure 15.

$\begin{array}[]{lclcl}\textbf{Variant}&\textbf{Upper Bound}&\\\
\hline\cr\hline\cr\langle=1\,|\,\leq 1;\mbox{always}\,|\,\text{circuit;
undirected;
complete}\,|\,c:E\mapsto\mathbb{R}_{>0},\text{(triangle)};q:V\mapsto\mathbb{Z}_{\geq
0}\,|&5&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{AusielloBLM18}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptq(\mathcal{S})\geq b;\min c(\mathcal{S})\rangle\\\
\hline\cr\langle=1\,|\,\leq 1;\mbox{always}\,|\,\text{circuit; undirected;
complete}\,|\,c:E\mapsto\mathbb{R}_{>0},\text{(triangle)}\,|&2&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{garg2005saving}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636pt|V_{\mathcal{S}}|\geq b;\min
c(\mathcal{S})\rangle\\\ \hline\cr\hline\cr\end{array}$ Figure 15.
Approximability results for the Quota TSP.

In the literature, the Quota TSP is sometimes also referred to as TSP with
Profits. When the task is to visit at least $k$ cities at minimum travel
costs, this problem is also called $k$-TSP. However, the usage of names varies
across publications. For example in (feillet2005traveling, ), TSP with Profits
is used as an umbrella term for the Profitable Tour problem, the Orienteering
problem, and the Prize-Collecting TSP.

###  6.10. Prize-collecting TSP

The Prize-collecting TSP is a combination of the Profitable Tour Problem
(Section 6.10) and the Quota TSP (Section 6.9). As in the Profitable Tour
Problem, the traveler receives a penalty $p$ when not visiting a city.
Furthermore, as in the Quota TSP, each node may be associated with a profit
$q$ (bienstock1993note, ), which the traveler receives if the node is visited.
The aim of the traveler is to minimize the sum of all edge costs and penalties
along the tour, while collecting a total profit, which is the sum of profits
of visited nodes, of at least $b$ \- where $b$ is also called the _quota_
(AusielloBLM18, ). If $b=0$, the Prize-collecting TSP reduces to the
Profitable Tour Problem. If $p(v)=0$ for all nodes $v$, the Prize-collecting
TSP reduces to the Quota TSP with. Figure 16 shows these variants in entries
(a) and (b), resp.

$\begin{array}[]{clr}&\textbf{Variant}&\textbf{Reference}\\\
\hline\cr\hline\cr(a)&\langle=1\,|\,\leq 1;\mbox{always}\,|\,\mbox{circuit;
complete;
undirected}\,|&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{marques2019quota}{\@@citephrase{,
}}{})}}\\\ &c:E\mapsto\mathbb{R};p:V\mapsto\mathbb{R}_{\geq 0}\,|\,\min
c(\mathcal{S})+\overline{p}(\mathcal{S})\rangle\\\
\hline\cr(b)&\langle=1\,|\,\leq 1;\mbox{always}\,|\,\mbox{circuit; complete;
undirected}\,|&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{berube2009branch}{\@@citephrase{,
}}{})}}\\\ &c:E\mapsto\mathbb{R}_{\geq 0}\mbox{,
(triangle)};\,q:V\mapsto\mathbb{R}_{\geq 0}\,|\,q(\mathcal{S})\geq b\,;\,\min
c(\mathcal{S})\,\rangle&\\\ \hline\cr(c)&\langle=1\,|\,\leq
1;\mbox{always}\,|\,\mbox{circuit; complete;
undirected}\,|&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{balas1989prize}{\@@citephrase{,
}}{})}}\\\ &c:E\mapsto\mathbb{R};\,q:V\mapsto\mathbb{R}_{\geq
0}\,;\,p:V\mapsto\mathbb{R}_{\geq 0}\,|\,q(\mathcal{S})\geq b\,;\,\min
c(\mathcal{S})+\overline{p}(\mathcal{S})\,\rangle\\\
\hline\cr\hline\cr\end{array}$ Figure 16. Variants of the Prize-Collecting
TSP.

Given an $\alpha$-approximation for (a) and a $\beta$-approximation for (b),
we obtain an $(\alpha+\beta)$-approximation for (c) by _concatenating_ both
solutions, i.e., the traveler first visits all cities according to the tour
for the Quota TSP, and before returning to the starting point, the traveler
visits all cities of the Profitable Tour that have not been visited yet
(AusielloBLM18, ). This yields a constant factor approximation for the Prize-
collecting TSP using the known constant factor approximations from the
previous two subsections.

Similarly to the name TSP with profits, the name Prize-collecting TSP is also
often used as an umbrella term to denote all variants of the TSP where the
traveler collects some profit or a prize when visiting a node such as the
Quota TSP, the Profitable Tour Problem, and the Orienteering Problem, see for
example (balas1989prize, ). Even if all penalties are equal to zero this name
is frequently used.

###  6.11. Orienteering Problem

In the Orienteering Problem (golden1987orienteering, ;
vansteenwegen2011orienteering, ), the traveler maximizes the profit $q$
without exceeding a given a budget $b$ for the total travel cost. An
$\alpha$-approximation algorithm for the Orienteering Problem with unit
profits, i.e., all node costs are equal to 1, yields an
$\alpha\cdot(1+o(1))$-approximation algorithm for the Orienteering Problem
with profits in $\mathbb{R}_{\geq 0}$ (korula2010approximation, , Lemma 2.6).
The Orienteering Problem occurs in the literature in various variants as shown
in Figure 17.

$\begin{array}[]{lr}\textbf{Variant}&\textbf{Reference}\\\
\hline\cr\hline\cr\langle=1\,|\,\leq 1;\mbox{always}\,|\,\mbox{start; end;
complete;
undirected}\,|&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{vansteenwegen2011orienteering}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R};\,q:V\mapsto\mathbb{R}_{\geq
0}\,|\,c(\mathcal{S})\leq b;\max q(\mathcal{S})\rangle\\\
\hline\cr\langle=1\,|\,\leq 1;\mbox{always}\,|\,\mbox{start; end;
undirected}\,|&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{kara2016new}{\@@citephrase{,
}}{})}}\\\ \hskip
14.22636ptc:E\mapsto\mathbb{R};q:V\mapsto\mathbb{R}\,|\,c(\mathcal{S})\leq
b;\max q(\mathcal{S})\rangle&\\\ \hline\cr\langle=1\,|\,\leq
1;\mbox{always}\,|\,\mbox{circuit; complete;
undirected}\,|&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{leifer1994strong}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}\mbox{,
(triangle)};\,q:V\mapsto\mathbb{R}_{>0}\,|\,c(\mathcal{S})\leq b;\max
q(\mathcal{S})\rangle\\\ \hline\cr\langle=1\,|\,\geq
0;\mbox{once}\,|\,\mbox{circuit;
undirected}\,|&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{kataoka1988algorithm}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq
0};\,q:V\mapsto\mathbb{R}_{\geq 0}\,|\,c(\mathcal{S})\leq b;\max
q(\mathcal{S})\rangle&\\\ \hline\cr\langle=1\,|\,\leq
1;\mbox{always}\,|\,\mbox{circuit; complete;
undirected}\,|&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{awerbuch1998new}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq
0};\,q:V\mapsto\mathbb{R}_{\geq 0}\,|\,c(\mathcal{S})\leq b;\max
q(\mathcal{S})\rangle&\\\ \hline\cr\hline\cr\end{array}$
Figure 17. Variants of the Orienteering Problem.

Approximability results for the Orienteering Problem are shown in Figure 18.

$\begin{array}[]{lclcl}\textbf{Variant}&\textbf{Lower Bound}&&\textbf{Upper
Bound}&\\\ \hline\cr\hline\cr\langle=1\,|\,\geq
0;\mbox{once}\,|\,\text{circuit;
undirected}\,|&&&2&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{paul2017prize,paul2020budgeted}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq
0}\,|\,c(\mathcal{S})\leq b;\max|V_{\mathcal{S}}|\rangle\\\
\hline\cr\langle=1\,|\,\geq 0;\mbox{once}\,|\,\text{start; end;
undirected}\,|&&&2+\epsilon&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{chekuri2012improved}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq
0}\,|\,c(\mathcal{S})\leq b;\max|V_{\mathcal{S}}|\rangle&&&\\\
\hline\cr\langle=1\,|\,\geq 0;\mbox{once}\,|\,\text{start; directed;
circuit}\,|&&&O(\log^{2}(OPT))&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{chekuri2012improved}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq
0},(\text{triangle})\,|\,c(\mathcal{S})\leq
b;\max|V_{\mathcal{S}}|\rangle&&&\\\ \hline\cr\langle=1\,|\,\geq
0;\mbox{once};\,|\,\text{start; undirected;
complete}\,|&\frac{1481}{1480}&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{blum2007approximation}{\@@citephrase{,
}}{})}}&2+\epsilon&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{chekuri2012improved}{\@@citephrase{,
}}{})}}\\\ \hskip
14.22636ptc:E\mapsto\\{1,2\\},\text{metric}\,|\,c(\mathcal{S})\leq
b;\max|V_{\mathcal{S}}|\rangle\\\ \hline\cr\langle=1\,|\,\leq
1;\mbox{always}\,|\,\text{start; undirected;
complete}\,|&&&1+\varepsilon&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{ChenHar-
Peled2008}{\@@citephrase{, }}{})}}\\\ \hskip
14.22636ptc:E\mapsto\mathbb{R}_{\geq 0},\text{euclidean fixed
dim}\,|\,c(\mathcal{S})\leq b;\max|V_{\mathcal{S}}|\rangle\\\
\hline\cr\hline\cr\end{array}$ Figure 18. Approximability results for the
Orienteering Problem.

Papers introducing the Orienteering Problem frequently remark that this
variant of the TSP is also called the Selective TSP (kara2016new, ), and vice
versa (laporte1990selective, ). When taking a closer look at the definitions,
one notices a subtle difference though. Most papers that use the name
Selective TSP, usually assume that the traveler returns to the starting node,
whereas most papers that use the term Orienteering Problem assume that a fixed
start and end node are given, which are distinct from one another. The
Selective TSP is also sometimes denoted as the Maximum Collection Problem, see
for example (kataoka1988algorithm, ). The literature also mentions Bank Robber
Problem as another name for the Orienteering Problem (arkin1998resource, ;
awerbuch1998new, ). Historically, the Orienteering Problem was sometimes
referred to as the Generalized TSP, see (golden1987orienteering, ).

###  6.12. Time-dependent TSP

In the Time-dependent TSP, the edge costs or node costs change over time. For
example in (gouveia1995classification, ; picard1978time, ; bigras2008time, ),
the costs of an edge or node usually depend on its position in the solution
sequence. In (hansknecht2021dynamic, ), the costs of an edge depend on the
actual time at which the edge starts being traversed. In the moving-target or
kinetic variant of the time-dependent TSP, targets move with a fixed constant
speed in a fixed direction (hammar1999approximation, ; helvig2003, ). A
flexible timing scheme where traveling times depend on the time of the day is
considered in (malandraki1996restricted, ). A good overview over the timing
models used in variants of time-dependent TSP and VRP problems is given in
(gendreau2015time, ).

$\begin{array}[]{lclcl}\textbf{Variant}&\textbf{Lower Bound}&&\textbf{Upper
Bound}&\\\ \hline\cr\hline\cr\langle=1\,|\,=1\,|\,\mbox{circuit; complete;
undirected}\,|&2^{\Omega(\sqrt{n})}&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{hammar1999approximation}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq
0},\mbox{kinetic}\,|\,\min c(\mathcal{S})\rangle^{\oplus 1}&&&&\\\
\hline\cr\langle=1\,|\,=1\,|\,\mbox{circuit; complete;
undirected}\,|&2&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{hammar1999approximation}{\@@citephrase{,
}}{})}}&2+\epsilon&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{helvig1998moving,helvig2003}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq
0},\mbox{kinetic}\,|\,\min c(\mathcal{S})\rangle^{\oplus 2}&&&&\\\
\hline\cr\langle=1\,|\,=1\,|\,\mbox{circuit; complete;
undirected}\,|&&&1+\epsilon&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{hammar1999approximation}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq
0},\mbox{kinetic}\,|\,\min c(\mathcal{S})\rangle^{\oplus 3}&&&&\\\
\hline\cr\langle=1\,|\,=1\,|\,\mbox{circuit; complete;
undirected}\,|&&&2-\frac{2}{3k}&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{broden2004online}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\\{1,2\\},\mbox{poszone}(k)\,|\,\min
c(\mathcal{S})\rangle&&&&\\\ \hline\cr\langle=1\,|\,=1\,|\,\mbox{circuit;
complete;
undirected}\,|&\omega(1)&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{broden2004online}{\@@citephrase{,
}}{})}}&&\\\ \hskip
14.22636ptc:E\mapsto\mathbb{R}_{>0},\mbox{euclidean},\mbox{costzone(2)}\,|\,\min
c(\mathcal{S})\rangle&&&&\\\ \hline\cr\langle=1\,|\,=1\,|\,\mbox{circuit;
complete;
undirected}\,|&&&\frac{5}{3}&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{broden2004online}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\\{1,2\\},\mbox{costzone(2)}\,|\,\min
c(\mathcal{S})\rangle&&&&\\\ \hline\cr\langle=1\,|\,=1\,|\,\mbox{start;
circuit; complete;
bidirected}\,|&\infty&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{hansknecht2021dynamic}{\@@citephrase{,
}}{})}}&&\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq
0},\mbox{(triangle)},\mbox{time}\,|\,\min c(\mathcal{S})\rangle\\\
\hline\cr\hline\cr\end{array}$

$\oplus 1$::

  * –:

An instance consists of $n$ moving points in the euclidean plane that are
described by their respective starting points at time $0$ and their two-
dimensional velocity vectors in polar coordinates.

  * –:

The traveler starts at time $0$ at the origin of the coordinate system. The
speed of the traveler is strictly larger than the speed of any moving target.
It is often normalized to $1$.

$\oplus 2$::

  * –:

The statements for $\oplus 1$ hold.

  * –:

The lower bound for the approximability result holds when there are at least
two moving targets or when the speed of each moving target is exactly half of
the speed of the traveler.

  * –:

The upper bound for the approximability result holds when there are at most
$O\Big{(}\frac{\log n}{\log\log n}\Big{)}$ moving targets. The other targets
have speed 0 and are stationary.

$\oplus 3$::

The statements for $\oplus 1$ hold. All $n$ targets move with the same fixed
constant speed in a fixed direction.

Figure 19. Approximability results for the Time-dependent TSP.

When all $n$ targets and the traveler move on the same line (restriction to
one dimension, acyclic graph) and traveler and targets move with constant
speed, an exact optimal algorithm of complexity $O(n^{2})$ exists
(helvig1998moving, ; helvig2003, ). The inapproximability result for the
metric Time-dependent TSP (hansknecht2021dynamic, ), see last line of Figure
19, demonstrates that approximability results for the metric "standard" TSP do
not carry over to the Time-dependent TSP. Any $\alpha$-approximation of the
asymmetric "standard "TSP yields an ($\alpha\lambda$)-approximation for the
Time-dependent TSP when the time-dependent cost functions are of low variance,
i.e., bounded by a product of a static cost underestimator with a constant
$\lambda\geq 1$ (hansknecht2021dynamic, ).

The Time-dependent Orienteering Problem requires the traveler to visit a
maximum number of targets within a given deadline. Under the assumption that
the ratio between the maximum and minimum traveling times between any two
targets is constant, a $2+\epsilon$-approximation algorithm exists
(fomin2002approximation, ). The kinetic variant of the Time-dependent TSP is
also denoted as the Moving-Target TSP (helvig2003, ) or the Kinetic TSP
(hammar1999approximation, ). In the Moving-Target TSP with Resupply variant
(helvig2003, ), a single traveler must always return to the origin after
visiting each target.

###  6.13. TSP with Time Windows

In the TSP with Time Windows, each node $v$ is associated with a time window
$[r(v),d(v)]$ during which the node must be visited (christofides1981state, ;
savelsbergh1985local, ). Travelers may arrive at the node $v$ before the
_release time_ $r(v)$, in which case they need to wait until $r(v)$ and
usually incur a wait cost $w$ that extends the traveling time. Only seldomly,
the waiting time is not increasing the costs of a tour, e.g.,
(ascheuer2001solving, ). In most variants, visiting the node $v$ after the
_deadline_ $d(v)$ would not be considered a valid solution. Moreover, it is
often permitted that some of the nodes may have infinite deadlines. It is
commonly assumed that there is no preemption of a job when a traveler visits a
node. This means, if a traveler visits a node, the job at this node is
completed once and for all leading to node costs $h(v)$, representing the
_handling time_ at node $v$. TSP-T3CO definitions for typical variants of the
TSP with Time Windows are summarized in Figure 20.

$\begin{array}[]{lr}\textbf{Variant}&\textbf{Reference}\\\
\hline\cr\hline\cr\langle=1\,|\,\geq 1;\mbox{once}\,|\,\mbox{circuit;
undirected}\,|\,c:E\mapsto\mathbb{R}_{\geq 0};\,w:E\mapsto\mathbb{R}_{\geq
0},\mbox{waiting};h:V\mapsto\mathbb{R}_{\geq
0}\,|&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{christofides1981state}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636pt\forall\,i\in\\{0,\dots,k\\}:\,r(v_{i})\leq
c(\mathcal{S}_{<i})+w(\mathcal{S}_{\leq i})+h(\mathcal{S}_{<i})\leq
d(v_{i})-h(\mathcal{S}_{i});\min
c(\mathcal{S})+w(\mathcal{S})+h(\mathcal{S})\rangle\\\
\hline\cr\langle=1\,|\,=1;\mbox{always}\,|\,\mbox{circuit; complete;
undirected}\,|\,c:E\mapsto\mathbb{R}_{\geq
0},\mbox{(triangle)};\,w:E\mapsto\mathbb{R}_{\geq
0},\mbox{waiting}\,|&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{savelsbergh1985local}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636pt\forall\,i\in\\{0,\dots,k\\}:\,r(v_{i})\leq
c(\mathcal{S}_{<i})+w(\mathcal{S}_{\leq i})\leq d(v_{i});\min
c(\mathcal{S})+w(\mathcal{S})\rangle\\\
\hline\cr\langle=1\,|\,=1;\mbox{always}\,|\,\mbox{start; end; complete;
bidirected}\,|\,c:E\mapsto\mathbb{R}_{\geq 0};w:E\mapsto\mathbb{R}_{\geq
0},\mbox{waiting}\,|&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{gendreau1998generalized}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636pt\forall\,i\in\\{0,\dots,k\\}:\,r(v_{i})\leq
c(\mathcal{S}_{<i})+w(\mathcal{S}_{\leq i})\leq d(v_{i});\min
c(\mathcal{S})\rangle\\\ \hline\cr\langle=1\,|\,\geq
1;\mbox{once}\,|\,\mbox{circuit; directed}\,|\,c:E\mapsto\mathbb{R}_{\geq
0},\mbox{(triangle)};\,w:E\mapsto\mathbb{R}_{\geq
0},\mbox{waiting};h:V\mapsto\mathbb{R}_{\geq
0}\,|&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{ascheuer2001solving}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636pt\forall\,i\in\\{0,\dots,k\\}:\,r(v_{i})\leq
c(\mathcal{S}_{<i})+w(\mathcal{S}_{\leq i})+h(\mathcal{S}_{<i})\leq
d(v_{i})-h(\mathcal{S}_{i});\min c(\mathcal{S})+h(\mathcal{S})\rangle\\\
\hline\cr\hline\cr\end{array}$ Figure 20. Variants of the TSP with Time
Windows.

$\begin{array}[]{lcl}\textbf{Variant}&\textbf{Upper Bound}&\\\
\hline\cr\hline\cr\langle=1\,|\,=1;\mbox{always}\,|\,\mbox{circuit; complete;
undirected}\,|&2S/(S+L)&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{psaraftis1990routing}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq
0},\mbox{shoreline};\,w:E\mapsto\mathbb{R}_{\geq 0},\mbox{waiting}\,|&&\\\
\hskip 14.22636pt\forall\,i\in\\{0,\dots,k\\}:\,r(v_{i})\leq
c(\mathcal{S}_{<i})+w(\mathcal{S}_{\leq i});\min
c(\mathcal{S})+w(\mathcal{S})\,\rangle&&\\\
\hline\cr\langle=1\,|\,=1;\mbox{always}\,|\,\mbox{start; end; complete;
undirected}\,|&\min\\{2(L+S)/3L,&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{psaraftis1990routing}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq
0},\mbox{shoreline};\,w:E\mapsto\mathbb{R}_{\geq
0},\mbox{waiting}\,|&4(S-L)/2S\\}&\\\ \hskip
14.22636pt\forall\,i\in\\{0,\dots,k\\}:\,r(v_{i})\leq
c(\mathcal{S}_{<i})+w(\mathcal{S}_{\leq i});\min
c(\mathcal{S})+w(\mathcal{S})\,\rangle&&\\\ \hline\cr\langle=1\,|\,\geq
1;\mbox{once}\,|\,\mbox{circuit; undirected;
path}\,|&\frac{3}{2}&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{karuno1998,karuno2002better}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq
0});\,w:E\mapsto\mathbb{R}_{\geq
0},\mbox{waiting};\,h:V\mapsto\mathbb{R}_{\geq 0}\,|&&\\\ \hskip
14.22636pt\forall\,i\in\\{0,\dots,k\\}:\,r(v_{i})\leq
c(\mathcal{S}_{<i})+w(\mathcal{S}_{\leq i})+h(\mathcal{S}_{<i});\\\ \hskip
14.22636pt\min c(\mathcal{S})+w(\mathcal{S})+h(\mathcal{S})\,\rangle^{\oplus
1}&&\\\ \hline\cr\langle=1\,|\,\geq 1;\mbox{once}\,|\,\mbox{circuit;
undirected; path}\,|\,c:E\mapsto\mathbb{R}_{\geq
0};\,h:V\mapsto\mathbb{R}_{\geq
0}\,|&\frac{3}{2}&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{karuno2002better}{\@@citephrase{,
}}{})}}\\\ \hskip
14.22636pt\forall\,i\in\\{0,\dots,k\\}:\,c(\mathcal{S}_{<i})+h(\mathcal{S}_{<i})\leq
d(v_{i})-h(\mathcal{S}_{i});&&\\\ \hskip
14.22636pt\min\max_{i}\max\\{0,c(\mathcal{S}_{<i})+h(\mathcal{S}_{<i})-d(v_{i})\\}\,\rangle&&\\\
\hline\cr\langle=1\,|\,\geq 1;\mbox{once}\,|\,\mbox{circuit; undirected;
path}\,|\,c:E\mapsto\mathbb{R}_{\geq
0};\,|&O(n^{2})&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{chan1995single,young1999single}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636pt\forall\,i\in\\{0,\dots,k\\}:\,r\leq
c(\mathcal{S}_{<i})\leq d(v_{i});\min c(\mathcal{S})\,\rangle&&\\\
\hline\cr\hline\cr\end{array}$

$\oplus 1$::

The solution is a so-called simple schedule. The traveler moves from the first
node on the line to the last node and back and only chooses to visit a node
and do the job at this node on the first move or on the second.

Figure 21. Approximability results for the TSP with Time Windows on lines. The
parameters $S$ and $L$ denote the length of the shoreline where
$S=\sum_{i=1}^{n-1}c(v_{i},v_{i+1})$ and $L=c(v_{1},v_{n})$ is the distance
between node $1$ and node $n$. According to the authors of
(psaraftis1990routing, ), their result also applies to the case of a global
deadline $D$ for all nodes or non-overlapping time windows. The result in
(karuno1998, ; karuno2002better, ) also holds when the maximum lateness at
nodes is minimized.

Various approximability results exist for the TSP with Time Windows, which are
summarized in different figures based on the structure of the underlying
graph. Figure 21 summarizes approximation results for variants where the graph
is a straight line, only release times are considered, and no deadlines are
allowed. Figure 22 summarizes results for variants over trees or general
graphs. The shoreline metric considered in (psaraftis1990routing, ) is defined
as follows:

###### Definition 6.1 (Shoreline Metric (psaraftis1990routing, )).

Let $1\leq v_{i}\leq v_{k}\leq v_{j}\leq n$ be nodes in the graph. Let
$c(v_{i},v_{j})$ denote the costs of the edge from node $v_{i}$ to node
$v_{j}$ as defined in Section 2. The shoreline metric satisfies the following
conditions:

  1. (1)

$c(v_{i},v_{i})=0$

  2. (2)

$c(v_{i},v_{j})=c(v_{j},v_{i})$

  3. (3)

$c(v_{i},v_{j})\geq c(v_{i},v_{k})$

  4. (4)

$c(v_{i},v_{j})\geq c(v_{k},v_{j})$

  5. (5)

$c(v_{i},v_{j})\geq c(v_{i},v_{k})+c(v_{k},v_{j})$

$\begin{array}[]{lclcl}\textbf{Variant}&\textbf{Lower Bound}&&\textbf{Upper
Bound}&\\\ \hline\cr\hline\cr\langle=1\,|\,\geq
1;\mbox{once}\,|\,\mbox{circuit; bidirected;
tree}\,|&&&1+\alpha&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{karuno1997}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq
0};\,w:E\mapsto\mathbb{R}_{\geq 0},\mbox{waiting};\\\ \hskip
14.22636pth:V\mapsto\mathbb{R}_{\geq 0}\,|&&\\\ \hskip
14.22636pt\forall\,i\in\\{0,\dots,k\\}:\,r(v_{i})\leq
c(\mathcal{S}_{<i})+w(\mathcal{S}_{\leq i})+h(\mathcal{S}_{<i});\\\ \hskip
14.22636pt\min c(\mathcal{S})+w(\mathcal{S})+h(\mathcal{S})\,\rangle^{\oplus
2}&&\\\ \hline\cr\langle=1\,|\,\geq 1;\mbox{once}\,|\,\mbox{start; undirected;
tree(b)}\,|&&&1+\epsilon&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{augustine2004linear}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq
0},\mbox{metric};w:E\mapsto\mathbb{R}_{\geq 0},\mbox{waiting};\\\ \hskip
14.22636pth:V\mapsto\mathbb{R}_{\geq 0}\,|&&\\\ \hskip
14.22636pt\forall\,i\in\\{0,\dots,k\\}:\,r(v_{i})\leq
c(\mathcal{S}_{<i})+w(\mathcal{S}_{\leq i})+h(\mathcal{S}_{<i});\\\ \hskip
14.22636pt\min c(\mathcal{S})+w(\mathcal{S})+h(\mathcal{S})\,\rangle^{\oplus
3}&&\\\ \hline\cr\langle=1\,|\,=1;\mbox{always}\,|\,\mbox{circuit; complete;
undirected;}\,|&&&\frac{5}{2}&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{nagamochi1997}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq
0}(\mbox{triangle});\,w:E\mapsto\mathbb{R}_{\geq 0},\mbox{waiting};\\\ \hskip
14.22636pth:V\mapsto\mathbb{R}_{\geq 0}\,|&&\\\ \hskip
14.22636pt\forall\,i\in\\{0,\dots,k\\}:r(v_{i})\leq
c(\mathcal{S}_{<i})+w(\mathcal{S}_{\leq i})+h(\mathcal{S}_{<i});\\\ \hskip
14.22636pt\min c(\mathcal{S})+w(\mathcal{S})+h(\mathcal{S})\,\rangle&&\\\
\hline\cr\langle=1\,|\,=1;\mbox{always}\,|\,\mbox{circuit; complete;
undirected}\,|&2-\epsilon&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{bockenhauer2007}{\@@citephrase{,
}}{})}}&\frac{5}{2}&\text{\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{bockenhauer2007}{\@@citephrase{,
}}{})}}\\\ \hskip 14.22636ptc:E\mapsto\mathbb{R}_{\geq 0},\mbox{metric}\,|\\\
\hskip 14.22636pt\forall\,i\in\\{0,\dots,n\\}:\,c(\mathcal{S}_{<i})\leq
d(v_{i});\min c(\mathcal{S})\,\rangle^{\oplus 4}&&&\\\
\hline\cr\hline\cr\end{array}$

$\oplus 2$::

The traveler starts at the root of the tree.

$\oplus 3$::

There is a constant number of leaves $b$ in the tree.

$\oplus 4$::

The number of nodes $v_{i}$ with a finite deadline $d(v_{i})$ is bounded by a
constant $k$.

Figure 22. Approximability and inapproximability result for the TSP with Time
Windows on trees or general graphs. The value of $\alpha$ is instance-
dependent and depends on the maximum release time $r_{max}$, the sum of all
traveling times, and the sum of all handling times. It always satisfies
$0<\alpha\leq 1$, i.e., the bound is at most 2. The lower approximation bound
in(bockenhauer2007, ) applies even if the number of deadlines is at most 2.
According to the authors of (augustine2004linear, ), their result also applies
to other tour variants where either start and end nodes are defined or the
traveler travels a circuit. The paper only considers the case where the start
of the traveler is given.

The TSP with Time Windows is also denoted as TSP with Time Constraints
(christofides1981state, ; savelsbergh1985local, ), Shore Line Problem
(psaraftis1990routing, ), Traveling Repairman Problem (tsitsiklis1992special,
; frederickson2012approximation, ), Time-constrained TSP (karuno1997, ), Time-
Window TSP (gao2020approximation, ), or Single VRP with release and handling
times (karuno1997, ). VRP variants with Time Windows occur in many practical
applications, see for example (solomon1987algorithms, ; desrochers1988vehicle,
; desrochers1992new, ). Approximability results for those VRP variants have
for example been published in (khachay2018improved, ; guo2022online, ).

###  6.14. Orienteering Problem with Time Windows

In the Orienteering Problem with Time Windows as many nodes as possible are
visited within their time windows. The deadline $d(v)$ is usually a "soft"
deadline where a profit $p$ is collected if and only if a node is visited
before its deadline. Profits usually replace the handling times that are
considered in the TSP with Time Windows. In some variants, deadlines can also
be exceeded by a constant factor, see for example (bansal2004approximation, ;
farbstein2019deadline, ).

Figures 23, 24 and 25 summarize approximability results for the Orienteering
Problem with Time Windows. Figure 23 summarizes results for the Orienteering
Problem with Time Windows under general profits. Figure 24 summarizes results
that consider only release times or only deadlines. Figure 25 summarizes
results that consider release times and deadlines under unit profits.