2 %> Algorithm 27.2: insertion heuristic
for TSP. Implementation of algorithm 27.2 of \cite Bier15-book
4 %> @note Tested with \ref run2703insertion.m
10 %> @author Michel Bierlaire
11 %> @date Tue Apr 14 12:43:17 2015
12 %> @ingroup Algorithms
15 %> Compute an halmitonian path
using the insertion heuristic
16 %> @param dist distance matrix
17 %> @param initialTour description of the initial tour stored as a successors list
18 %> @
return greedyTour permutation of the cities
19 function greedyTour =
tspInsertion(dist,initialTour = zeros(rows(dist),1))
21 if (columns(dist) != n)
22 error("Distance matrix must be square") ;
24 # First city is the depot 26 inserted = zeros(n,1) ;
30 inserted(next(i)) = 1 ;
41 % printf(
"Try to insert city %d\n",i) ;
42 [bestnode,bestlength] =
bestInsert(next,dist,i) ;
43 if (bestlength < thelength)
44 thelength = bestlength ;
50 % printf(
"Decide to insert city %d after city %d\n",thenode,thecity) ;
52 inserted(thenode) = 1 ;
54 % printf(
"%.1f & ",l) ;
56 % printf(
"Length: %f\n",l) ;
62 greedyTour = zeros(n,1) ;
65 greedyTour(pos) = currentnode ;
66 while (next(currentnode) != 0)
68 currentnode = next(currentnode) ;
69 greedyTour(pos) = currentnode ;
function tspInsertionLocalSearch(in dist, in subtourList)
function insertCity(in next, in a, in i)
function bestInsert(in next, in dist, in i)
Inserts city i in the best place.
function subtourLength(in next, in dist)
Calculate the length of a tour.
function tspInsertion(in dist, in initialTour)
Compute an halmitonian path using the insertion heuristic.