Namespaces
Variants
Actions

Difference between revisions of "Travelling salesman problem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (MSC)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130170/t1301701.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130170/t1301702.png" /> 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.
+
{{TEX|done}}
 +
{{MSC|90C35|90C27}}
  
A very similar problem exists when the "machine"  corresponds to a computer centre which has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130170/t1301703.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130170/t1301704.png" /> to that of program <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130170/t1301705.png" /> is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130170/t1301706.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130170/t1301707.png" />). Thus, the question becomes that of determining the cost minimizing order in which all the programs ought to be run.
+
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.
  
If at the end of running all the programs by the computer centre the system returns to an "idleconfiguration, then the number of possible ways to run these programs one after the other equals <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130170/t1301708.png" /> (for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130170/t1301709.png" /> configurations).
+
A very similar problem exists when the  "machinecorresponds 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.
  
This is the same problem as that in the story about the lonely salesman who has to visit <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130170/t13017010.png" /> 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.
+
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).
  
In graph terminology terms, the problem is presented as that of a [[Graph|graph]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130170/t13017011.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130170/t13017012.png" /> is a finite set of nodes ( "cities" ) and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130170/t13017013.png" /> is the set of edges connecting the node pairs in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130170/t13017014.png" />. If one associates a real-valued  "cost"  matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130170/t13017015.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130170/t13017016.png" />, with the set of edges <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130170/t13017017.png" />, the travelling salesman dilemma becomes that of constructing a cost-minimizing circuit on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130170/t13017018.png" /> that visits all the nodes in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130170/t13017019.png" /> exactly once, if such a circuit exists (cf. also [[Graph circuit|Graph circuit]]).
+
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.
  
If the requirement is that all the nodes in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130170/t13017020.png" /> 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.
+
In graph terminology terms, the problem is presented as that of a [[Graph|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|Graph circuit]]).
  
If the graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130170/t13017021.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130170/t13017022.png" />, assigns a "direction"  to each element in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130170/t13017023.png" /> (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.
+
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.
  
The question of whether a circuit exists in a graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130170/t13017024.png" /> which visits each node in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130170/t13017025.png" /> exactly once is commonly referred to as that of determining the existence of a Hamiltonian circuit (or path; cf. also [[Hamiltonian tour|Hamiltonian tour]]). Graphs for which such a circuit (path) is guaranteed to exist are called Hamiltonian graphs.
+
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 difficulty of determining the existence of a Hamiltonian circuit for a graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130170/t13017026.png" /> and that of constructing a cost-minimizing travelling salesman circuit on a graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130170/t13017027.png" /> 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 [[NP|<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130170/t13017028.png" />]]). 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.
+
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|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 [[NP|$\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 [[#References|[a1]]], [[#References|[a2]]] for recent overviews of the problem.
 
See [[#References|[a1]]], [[#References|[a2]]] for recent overviews of the problem.

Latest revision as of 22:51, 19 April 2012

2010 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)
How to Cite This Entry:
Travelling salesman problem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Travelling_salesman_problem&oldid=12820
This article was adapted from an original article by Moshe Dror (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article