naginterfaces.library.mip.tsp_​simann

naginterfaces.library.mip.tsp_simann(dm, bound, targc, statecomm)

tsp_simann calculates an approximate solution to a symmetric travelling salesman problem using simulated annealing via a configuration free interface.

For full information please refer to the NAG Library document for h03bb

https://support.nag.com/numeric/nl/nagdoc_30.3/flhtml/h/h03bbf.html

Parameters

dmfloat, array-like, shape $(\text{nc},\text{nc})$

The distance matrix; each $dm[\text{i}-1,\text{j}-1]$ is the effective cost or weight between nodes $\text{i}$ and $\text{j}$. Only the strictly upper half of the matrix is referenced.

boundfloat

A lower bound on the solution. If the optimum is unknown set $bound$ to zero or a negative value; the function will then calculate the minimum spanning tree for $dm$ and use this as a lower bound (returned in $alg\_stats\left[5\right]$). If an optimal value for the cost is known then this should be used for the lower bound. A detailed discussion of relaxations for lower bounds, including the minimal spanning tree, can be found in Reinelt (1994).

targcfloat

A measure of how close an approximation needs to be to the lower bound. The function terminates when a cost is found less than or equal to $bound+targc$. This argument is useful when an optimal value for the cost is known and supplied in $bound$. It may be sufficient to obtain a path that is close enough (in terms of cost) to the optimal path; this allows the algorithm to terminate at that point and avoid further computation in attempting to find a better path.

If $targc<0$, $targc=0$ is assumed.

statecommdict, RNG communication object, modified in place

RNG communication structure.

This argument must have been initialized by a prior call to rand.init_repeat or rand.init_nonrepeat.

Returns

pathint, ndarray, shape $\left(\text{nc}\right)$

The best path discovered by the simulation. That is, $path$ contains the city indices in path order.

costfloat

The cost or weight of $path$.

tmodeint

The termination mode of the function:

$tmode=0$

Optimal solution found, $cost=bound$.

$tmode=1$

System temperature cooled. The algorithm returns a $path$ and associated $cost$ that does not attain, nor lie within $targc$ of, the $bound$. This could be a sufficiently good approximation to the optimal $path$, particularly when $bound+targc$ lies below the optimal $cost$.

$tmode=2$

Halted by $cost$ falling within the desired $targc$ range of the $bound$.

$tmode=3$

System stalled following lack of improvement.

$tmode=4$

Initial search failed to find a single improvement (the solution could be optimal).

alg_statsfloat, ndarray, shape $\left(6\right)$

An array of metrics collected during the initial search. These could be used as a basis for future optimization. If an exception is raised, the elements of $alg\_stats$ are set to zero; the first five elements are also set to zero in the trival cases $\text{nc}=1$, $2$ or $3$.

$alg\_stats\left[0\right]$

Mean delta.

$alg\_stats\left[1\right]$

Standard deviation of deltas.

$alg\_stats\left[2\right]$

Cost at end of initial search phase.

$alg\_stats\left[3\right]$

Best cost encountered during search phase.

$alg\_stats\left[4\right]$

Initial system temperature. At the end of stage 1 of the algorithm, this is a function of the mean and variance of the deltas, and of the distance from best cost to the lower bound. It is a measure of the initial acceptance criteria for stage $2$. The larger this value, the more iterations it will take to geometrically reduce it during stage 2 until the system is cooled (below a threshold value).

$alg\_stats\left[5\right]$

The lower bound used, which will be that computed internally when $bound\le 0$ on input. Subsequent calls with different random states can set $bound$ to the value returned in $alg\_stats\left[5\right]$ to avoid recomputation of the minimal spanning tree.

Raises

NagValueError

(errno $1$)

On entry, $\text{nc}=⟨value⟩$.

Constraint: $\text{nc}\ge 1$.

(errno $2$)

On entry, the strictly upper triangle of $dm$ had a negative element.

(errno $9$)

On entry, $statecomm$[‘state’] vector has been corrupted or not initialized.

Notes

tsp_simann provides a probabilistic strategy for the calculation of a near optimal path through a symmetric and fully connected distance matrix; that is, a matrix for which element $(i,j)$ is the pairwise distance (also called the cost, or weight) between nodes (cities) $i$ and $j$. This problem is better known as the Travelling Salesman Problem (TSP), and symmetric means that the distance to travel between two cities is independent of which is the destination city.

In the classical TSP, which this function addresses, a salesman wishes to visit a given set of cities once only by starting and finishing in a home city and travelling the minimum total distance possible. It is one of the most intensively studied problems in computational mathematics and, as a result, has developed some fairly sophisticated techniques for getting near-optimal solutions for large numbers of cities. tsp_simann adopts a very simple approach to try to find a reasonable solution, for moderately large problems. The function uses simulated annealing: a stochastic mechanical process in which the heating and controlled cooling of a material is used to optimally refine its molecular structure.

The material in the TSP is the distance matrix and a given state is represented by the order in which each city is visited—the path. This system can move from one state to a neighbouring state by selecting two cities on the current path at random and switching their places; the order of the cities in the path between the switched cities is then reversed. The cost of a state is the total cost of traversing its path; the resulting difference in cost between the current state and this new proposed state is called the delta; a negative delta indicates the proposal creates a more optimal path and a positive delta a less optimal path. The random selection of cities to switch uses random number generators (RNGs) from submodule rand; it is thus necessary to initialize a state array for the RNG of choice (by a call to rand.init_repeat or rand.init_nonrepeat) prior to calling tsp_simann.

The simulation itself is executed in two stages. In the first stage, a series of sample searches through the distance matrix is conducted where each proposed new state is accepted, regardless of the change in cost (delta) incurred by applying the switches, and statistics on the set of deltas are recorded. These metrics are updated after each such sample search; the number of these searches and the number of switches applied in each search is dependent on the number of cities. The final collated set of metrics for the deltas obtained by the first stage are used as control parameters for the second stage. If no single improvement in cost is found during the first stage, the algorithm is terminated.

In the second stage, as before, neighbouring states are proposed. If the resulting delta is negative or causes no change the proposal is accepted and the path updated; otherwise moves are accepted based on a probabilistic criterion, a modified version of the Metropolis–Hastings algorithm.

The acceptance of some positive deltas (increased cost) reduces the probability of a solution getting trapped at a non-optimal solution where any single switch causes an increase in cost. Initially the acceptance criteria allow for relatively large positive deltas, but as the number of proposed changes increases, the criteria become more stringent, allowing fewer positive deltas of smaller size to be accepted; this process is, within the realm of the simulated annealing algorithm, referred to as ‘cooling’. Further exploration of the system is initially encouraged by accepting non-optimal routes, but is increasingly discouraged as the process continues.

The second stage will terminate when:

• a solution is obtained that is deemed acceptable (as defined by supplied values);

• the algorithm will accept no further positive deltas and a set of proposed changes have resulted in no improvements (has cooled);

• a number of consecutive sets of proposed changes has resulted in no improvement.

References

Applegate, D L, Bixby, R E, Chvátal, V and Cook, W J, 2006, The Traveling Salesman Problem: A Computational Study, Princeton University Press

Cook, W J, 2012, In Pursuit of the Traveling Salesman, Princeton University Press

Johnson, D S and McGeoch, L A, The traveling salesman problem: A case study in local optimization, Local search in combinatorial optimization, 1997, 215–310

Press, W H, Teukolsky, S A, Vetterling, W T and Flannery, B P, 2007, Numerical Recipes, The Art of Scientific Computing ((3rd Edition))

Rego, C, Gamboa, D, Glover, F and Osterman, C, 2011, Traveling salesman problem heuristics: leading methods, implementations and latest advances, European Journal of Operational Research (211 (3)), 427–441

Reinelt, G, 1994, The Travelling Salesman. Computational Solutions for TSP Applications, Volume 840 of Lecture Notes in Computer Science, Springer–Verlag, Berlin Heidelberg New York