|
Calling Sequence
|
|
TravelingSalesman(G, opts)
TravelingSalesman(G, M, opts)
|
|
Parameters
|
|
G
|
-
|
a connected graph or digraph
|
M
|
-
|
(optional) a Matrix containing edge weights
|
opts
|
-
|
zero or or more options as specified below
|
|
|
|
|
Options
|
|
•
|
metric = positive number or one of the symbols Euclidean, Manhattan, discrete, geographical, or infinity.
|
|
The parameter metric must be a positive number or one of the symbols listed above. This specifies the metric to be used in computing distances when the option vertexpositions is set to a non-default value.
|
|
When metric=geographical, the vertex positions must be 2-D and are interpreted as geographical positions on the Earth given as latitudes and longitudes in degrees. Entries in the weight matrix correspond to the distance between points in kilometers.
|
|
The default metric is 2, the metric induced by the Euclidean norm.
|
|
Seed for the random number generator.
|
•
|
solver=one of concorde or legacy
|
|
Specifies the solver to use. The default, solver=concorde, uses the Concorde TSP solver, a well-known and highly efficient optimization library for TSP instances. Specifying solver=legacy dispatches to a pure-Maple TSP solver.
|
•
|
startvertex=a valid vertex in G
|
|
Specifies the starting vertex for the Hamiltonian cycle. If provided, the algorithm will only consider cycles or paths beginning at startvertex.
|
•
|
vertexpositions=truefalse, Matrix, Array, or listlist
|
|
When set to true or a list, Array, or Matrix, this specifies that the edge weights used in computing a tour correspond to the geometric distances between the vertex positions in a particular layout. The metric used in computing these distances is controlled by the metric option.
|
|
When a Matrix, Array, or list is provided corresponding to a set of 2-D or 3-D points, this is taken to specify the positions of the vertices in vertex order.
|
|
When vertexpositions=true, any existing vertex positions stored in G are used, if they exist.
|
|
When vertexpositions=false, the edge weights from the graph or from the specified matrix M are used. This is the default.
|
|
|
Description
|
|
•
|
TravelingSalesman(G) finds a traversal of least weight through all the vertices of a graph G, ending at the starting point. This is known as the traveling salesman problem.
|
•
|
If G is not a weighted graph, then all adjacent vertices are considered to have an edge weight of 1.
|
•
|
If a second argument M is specified, it is used for the weights instead of the existing edge weights of G. If an edge from vertex u to v is not in G then, regardless of the specified edge weight in M, its edge weight is considered to be infinity.
|
•
|
Instead of specifying a weight matrix M, the vertexpositions option may be used to indicate the weights should be interpreted as the geometric distance between the positions of the graph vertices.
|
•
|
The command returns two objects, w of type numeric and the second C a list which is a permutation of the vertices. The first output is the total weight of an optimal tour, and the second is a Hamiltonian cycle which achieves this optimum.
|
•
|
The problem of finding an optimal tour for a weighted graph is is NP-complete, meaning that no polynomial-time algorithm is presently known.
|
|
|
Examples
|
|
Perform a tour through 10 cities by using the vertexpositions option
|
|
Compatibility
|
|
•
|
The GraphTheory[TravelingSalesman] command was updated in Maple 2023.
|
•
|
The metric, seed, solver, startvertex and vertexpositions options were introduced in Maple 2023.
|
|
|
|