The Travelling Salesperson Problem (TSP) is a combinatorial optimization problem that was first mentioned in a handbook for Salespersons in Switzerland in 1832, showcasing the practical need for planning (business) trips efficiently. A salesperson has to visit a given list of cities exactly once before returning to the starting point again. The goal is to minimize the aggregate distance (or time, fuel, etc.).
In addition to finding the fastest route, the measure to optimize for can also be changed to most fuel-efficient or least carbon emissions. For modern organizations that try to use resources considerately, finding a schedule that comes as close to the optimal solution is essential. The brute force exact solution of trying all permutations however requires the examination of more than the factorial of the number of cities to be visited (n!) and becomes impractical already if there are more than 20 cities to be visited.
Various heuristics exist that provide very good approximate solutions. For an exact solution, however, no algorithm has been found yet for which the computation time doesn't increase exponentially with the number of cities. This is also true for quantum algorithms. Quantum annealing is however a promising way to speed up the search for approximate solutions, as pointed out in [1].
The TSP is a very popular topic in research due to its wide applicability. Planning the routes of letter carriers and garbage collectors are similar route planning tasks. It is furthermore used in manufacturing, for example in designing machine assembly processes or microchip insertion into circuit boards. With a slight modification, DNA sequencing can also be formulated as a TSP.
[1] Lucas, A. (2014). Ising formulations of many NP problems. Frontiers in Physics, 2. https://doi.org/10.3389/fphy.2014.00005