Travelling salesman problem

2020 Mathematics Subject Classification: Primary: 90C35 Secondary: 90C27 [MSN][ZBL]

A generic name for a number of very different problems. For instance, suppose that a facility (a "machine" ) starting from an "idle" position is assigned to process a finite set of "jobs" (say $n$, $n\geq3$ jobs). If the machine has to be "calibrated" (or "set-up" ) for processing each of these jobs and if the machine's "calibration time" (the distance metric) between processing of a pair of jobs in succession is dependent on the particular pair, then a reasonable objective is to organize this job assignment so it will minimize the total machine calibration time. One might want to assume that after the last job is processed the machine returns to its idle position.

A very similar problem exists when the "machine" corresponds to a computer centre which has $n$ programs to run, and each program requires resources such as a compiler, a certain portion of the main memory, and perhaps some other "devices" . I.e., each program requires a specific configuration of devices. Conversion cost (or time) from one configuration to another, say from the configuration of program $i$ to that of program $j$ is denoted by $c_{ij}$ ($\geq0$). Thus, the question becomes that of determining the cost minimizing order in which all the programs ought to be run.

If at the end of running all the programs by the computer centre the system returns to an "idle" configuration, then the number of possible ways to run these programs one after the other equals $n!$ (for $n+1$ configurations).

This is the same problem as that in the story about the lonely salesman who has to visit $n$ sales outlets (starting from his home) and wishes to travel the shortest total distance in the process. It is the salesman's problem to select a distance-minimizing travel order of outlet visits. Thus, the name travelling salesman problem.

In graph terminology terms, the problem is presented as that of a graph $G=(V,E)$, where$V$ is a finite set of nodes ( "cities" ) and $E\subset V\times V$ is the set of edges connecting the node pairs in $V$. If one associates a real-valued "cost" matrix $(c_{ij})$, $i,j=1,\ldots,\lvert V\rvert$, with the set of edges $E$, the travelling salesman dilemma becomes that of constructing a cost-minimizing circuit on $G$ that visits all the nodes in $V$ exactly once, if such a circuit exists (cf. also Graph circuit).

If the requirement is that all the nodes in $V$ are visited in a cost-minimizing fashion but without necessarily forming a circuit, then the problem is referred to as a travelling salesman path problem, or travelling salesman walk problem. Again, the question of the existence of such a path has to be addressed first.

If the graph $G=(V,A)$, $A\subset V\times V$, assigns a "direction" to each element in $A$ (a subset of arcs), then the corresponding travelling salesman problem is of the "directed" variety. Clearly, there is the option of the mixed problem, where some of the node pairs are connected by arcs and some by edges.

The question of whether a circuit exists in a graph $G$ which visits each node in $V$ exactly once is commonly referred to as that of determining the existence of a Hamiltonian circuit (or path; cf. also Hamiltonian tour). Graphs for which such a circuit (path) is guaranteed to exist are called Hamiltonian graphs.

The difficulty of determining the existence of a Hamiltonian circuit for a graph $G$ and that of constructing a cost-minimizing travelling salesman circuit on a graph $G$ are very much the same when measured by the worst possible order magnitude of the required number of computer operations. This casts these problems (the travelling salesman and the Hamiltonian circuit problems) as being "hard" (cf. also $\mathcal{NP}$). Essentially, for this sort of problems, one does not presently (2000) know of any solution scheme which does not require some sort of enumeration of all possible "configuration" sequences.

See [a1], [a2] for recent overviews of the problem.

References

[a1]	"The traveling salesman problem" E.L. Lawler (ed.) J.K. Lenstra (ed.) A.H.G. Rinnoy Kan (ed.) D.B. Shmoys (ed.) , Wiley (1985)
[a2]	H. Fleishner, "Traversing graphs: The Eulerian and Hamiltonian theme" M. Dror (ed.) , Arc Routing: Theory, Solutions, and Applications , Kluwer Acad. Publ. (2000)