////
Licensed to the Apache Software Foundation (ASF) under one
or more contributor license agreements.  See the NOTICE file
distributed with this work for additional information
regarding copyright ownership.  The ASF licenses this file
to you under the Apache License, Version 2.0 (the
"License"); you may not use this file except in compliance
with the License.  You may obtain a copy of the License at

  http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing,
software distributed under the License is distributed on an
"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
KIND, either express or implied.  See the License for the
specific language governing permissions and limitations
under the License.
////

[[tsp]]
= Traveling salesman (TSP - traveling salesman problem)
:imagesdir: ../..


[[tspProblemDescription]]
== Problem description

Given a list of cities, find the shortest tour for a salesman that visits each city exactly once.

The problem is defined by https://en.wikipedia.org/wiki/Travelling_salesman_problem[Wikipedia].
It is http://www.math.uwaterloo.ca/tsp/[one of the most intensively studied problems] in computational mathematics.
Yet, in the real world, it is often only part of a planning problem, along with other constraints, such as employee shift rostering constraints.


[[tspProblemSize]]
== Problem size

[source,options="nowrap"]
----
dj38     has  38 cities with a search space of   10^43.
europe40 has  40 cities with a search space of   10^46.
st70     has  70 cities with a search space of   10^98.
pcb442   has 442 cities with a search space of  10^976.
lu980    has 980 cities with a search space of 10^2504.
----


[[tspProblemDifficulty]]
== Problem difficulty

Despite TSP's simple definition, the problem is surprisingly hard to solve.
Because it is an NP-hard problem (like most planning problems), the optimal solution for a specific problem dataset can change a lot when that problem dataset is slightly altered:

image::use-cases-and-examples/travelling-salesman/tspOptimalSolutionVolatility.png[align="center"]
