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.

For more information on norms, see LinearAlgebra[Norm].

The default metric is 2, the metric induced by the Euclidean norm.

seed = integer or none

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.

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.

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$G≔\mathrm{Graph}\left(\left\{\left[\left\{1\,2\right\}\,2\right]\,\left[\left\{1\,4\right\}\,2\right]\,\left[\left\{2\,3\right\}\,2\right]\,\left[\left\{3\,4\right\}\,2\right]\right\}\right)$

$G≔\mathrm{Graph\; 1:\; an\; undirected\; weighted\; graph\; with\; 4\; vertices\; and\; 4\; edge(s)}$

$\mathrm{TravelingSalesman}\left(G\right)$

$\mathrm{\infty },\left[\right]$

$\mathrm{AddEdge}\left(G\,\left\{\left[\left\{1\,3\right\}\,1\right]\,\left[\left\{2\,4\right\}\,1\right]\right\}\right)$

$\mathrm{Graph\; 1:\; an\; undirected\; weighted\; graph\; with\; 4\; vertices\; and\; 6\; edge(s)}$

$\mathrm{DrawGraph}\left(G\,\mathrm{style}=\mathrm{circle}\right)$

$w,\mathrm{tour}≔\mathrm{TravelingSalesman}\left(G\right)$

$w,\mathrm{tour}≔6,\left[1\,3\,4\,2\,1\right]$

$\mathrm{HighlightTrail}\left(G\,\mathrm{tour}\,\mathrm{red}\right)$

$\mathrm{DrawGraph}\left(G\,\mathrm{style}=\mathrm{circle}\right)$

$G≔\mathrm{CompleteGraph}\left(10\right)\:$

$M≔\mathrm{Matrix}\left(\left[\left[0\,68\,37\,95\,57\,30\,1\,25\,71\,84\right]\,\left[68\,0\,9\,26\,90\,26\,97\,29\,47\,78\right]\,\left[37\,9\,0\,84\,59\,11\,67\,61\,75\,35\right]\,\left[95\,26\,84\,0\,1\,99\,55\,63\,19\,8\right]\,\left[57\,90\,59\,1\,0\,61\,66\,18\,7\,48\right]\,\left[30\,26\,11\,99\,61\,0\,93\,10\,14\,54\right]\,\left[1\,97\,67\,55\,66\,93\,0\,47\,20\,95\right]\,\left[25\,29\,61\,63\,18\,10\,47\,0\,28\,52\right]\,\left[71\,47\,75\,19\,7\,14\,20\,28\,0\,92\right]\,\left[84\,78\,35\,8\,48\,54\,95\,52\,92\,0\right]\right]\right)\:$

$\mathrm{OptimalValue},\mathrm{OptimalPath}≔\mathrm{TravelingSalesman}\left(G\,M\right)$

$\mathrm{OptimalValue},\mathrm{OptimalPath}≔142,\left[1\,8\,6\,2\,3\,10\,4\,5\,9\,7\,1\right]$

$\mathrm{OptimalPath}$

$\left[1\,8\,6\,2\,3\,10\,4\,5\,9\,7\,1\right]$

$\mathrm{BavarianCities}≔\mathrm{Import}\left(''example/bayern10.csv''\,\mathrm{base}=\mathrm{datadir}\,\mathrm{output}=\mathrm{Matrix}\right)$

$\mathrm{BavarianCities}≔\left[\begin{array}{ccc}''München''& 48.137222& 11.575556\\ ''Nürnberg''& 49.455556& 11.078611\\ ''Augsburg''& 48.371667& 10.898333\\ ''Regensburg''& 49.017222& 12.096944\\ ''Ingolstadt''& 48.76415& 11.42434\\ ''Würzburg''& 49.79441& 9.92937\\ ''Fürth''& 49.4774& 10.98844\\ ''Erlangen''& 49.596361& 11.004311\\ ''Bamberg''& 49.891667& 10.891667\\ ''Bayreuth''& 49.9475& 11.5775\end{array}\right]$

$G≔\mathrm{GraphTheory}:-\mathrm{CompleteGraph}\left(\mathrm{convert}\left(\mathrm{BavarianCities}\left[..,1\right]\,\mathrm{list}\right)\right)$

$G≔\mathrm{Graph\; 2:\; an\; undirected\; graph\; with\; 10\; vertices\; and\; 45\; edge(s)}$

$\mathrm{GraphTheory}:-\mathrm{TravelingSalesman}\left(G\,\mathrm{vertexpositions}=\mathrm{BavarianCities}\left[..,2..3\right]\,\mathrm{metric}=\mathrm{geographical}\right)$

$631.542932745210,\left[''München''\,''Augsburg''\,''Ingolstadt''\,''Nürnberg''\,''Fürth''\,''Erlangen''\,''Würzburg''\,''Bamberg''\,''Bayreuth''\,''Regensburg''\,''München''\right]$

The GraphTheory[TravelingSalesman] command was updated in Maple 2023.

The metric, seed, solver, startvertex and vertexpositions options were introduced in Maple 2023.

For more information on Maple 2023 changes, see Updates in Maple 2023.