Optimization: principles and algorithms, by Michel Bierlaire
tspInsertion.m
Go to the documentation of this file.
1 %> \file
2 %> Algorithm 27.2: insertion heuristic for TSP. Implementation of algorithm 27.2 of \cite Bier15-book
3 %>
4 %> @note Tested with \ref run2703insertion.m
5 %> @note Called by tspInsertionLocalSearch
6 %> @note Calls \ref subtourLength
7 %> @note Calls \ref bestInsert
8 %> @note Calls \ref insertCity
9 %>
10 %> @author Michel Bierlaire
11 %> @date Tue Apr 14 12:43:17 2015
12 %> @ingroup Algorithms
13 %> @ingroup chap27
14 
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))
20  n = rows(dist) ;
21  if (columns(dist) != n)
22  error("Distance matrix must be square") ;
23  endif
24  # First city is the depot
25  next = initialTour ;
26  inserted = zeros(n,1) ;
27  inserted(1) = 1 ;
28  for i=1:n
29  if (next(i) != 0)
30  inserted(next(i)) = 1 ;
31  endif
32  endfor
33  [l,m] = subtourLength(next,dist);
34 % printf("%f & ",l) ;
35 % printTour(next) ;
36  while (m <= n)
37  thelength = realmax ;
38  thenode = 0 ;
39  for (i = 2:n)
40  if (inserted(i) == 0)
41 % printf("Try to insert city %d\n",i) ;
42  [bestnode,bestlength] = bestInsert(next,dist,i) ;
43  if (bestlength < thelength)
44  thelength = bestlength ;
45  thenode = i ;
46  thecity = bestnode ;
47  endif
48  endif
49  endfor
50 % printf("Decide to insert city %d after city %d\n",thenode,thecity) ;
51  next = insertCity(next,thecity,thenode) ;
52  inserted(thenode) = 1 ;
53  [l,m] = subtourLength(next,dist) ;
54 % printf("%.1f & ",l) ;
55 % printTour(next) ;
56 % printf("Length: %f\n",l) ;
57 
58  endwhile
59  [l,m] = subtourLength(next,dist) ;
60 % printf("%f & ",l) ;
61 % printTour(next)
62  greedyTour = zeros(n,1) ;
63  pos = 1 ;
64  currentnode = 1 ;
65  greedyTour(pos) = currentnode ;
66  while (next(currentnode) != 0)
67  pos += 1 ;
68  currentnode = next(currentnode) ;
69  greedyTour(pos) = currentnode ;
70  endwhile
71 endfunction
72 
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.
Copyright 2015-2016 Michel Bierlaire