2 %> Local search method
for the TSP based on the insertion heuristic, as described in Section 27.3.2 of \cite Bier15-book
4 %> @note Called by \ref
tspVns 11 %> @author Michel Bierlaire
12 %> @date Wed Apr 15 11:59:07 2015
13 %> @ingroup Algorithms
16 %> @param dist the distance matrix
17 %> @param subtour initial subtour stored as a succesor list
18 %> @
return betterTour local optimum
21 if (columns(dist) != n)
22 error(
"Distance matrix must be square") ;
24 betterTourList = subtourList ;
25 currentList = subtourList ;
34 for i = 1:columns(neighborhood)
37 % printf(
"Best length: %f, Candidate length: %f\n",bestLength,l);
41 bestTourSeq = tourSeq ;
47 currentList = betterTourList ;
function tspInsertionLocalSearch(in dist, in subtourList)
function tspTourLength(in tour, in dist)
Calculate the length of a tour for the TSP.
function twoOptNeighborhood(in cities)
Generate the 2-opt neightborhood for the TSP.
function getTourSequence(in tour)
Print tour stored as list of successor.
function getTourList(in sequence, in n)
Transforms a tour stored as a sequence of cities into a list of successors.
function tspVns(in tour, in dist)
Runs the VNS heuristic on the TSP.
function tspInsertion(in dist, in initialTour)
Compute an halmitonian path using the insertion heuristic.