Optimization: principles and algorithms, by Michel Bierlaire
tspInsertionLocalSearch.m
Go to the documentation of this file.
1 %> \file
2 %> Local search method for the TSP based on the insertion heuristic, as described in Section 27.3.2 of \cite Bier15-book
3 %>
4 %> @note Called by \ref tspVns
5 %> @note Calls \ref tspInsertion
6 %> @note Calls \ref tspTourLength
7 %> @note Calls \ref twoOptNeighborhood
8 %> @note Calls \ref getTourList
9 %> @note Calls \ref getTourSequence
10 %>
11 %> @author Michel Bierlaire
12 %> @date Wed Apr 15 11:59:07 2015
13 %> @ingroup Algorithms
14 %> @ingroup chap27
15 %>
16 %> @param dist the distance matrix
17 %> @param subtour initial subtour stored as a succesor list
18 %> @return betterTour local optimum
19 function [bestTourSeq,bestLength] = tspInsertionLocalSearch(dist,subtourList)
20  n = rows(dist) ;
21  if (columns(dist) != n)
22  error("Distance matrix must be square") ;
23  endif
24  betterTourList = subtourList ;
25  currentList = subtourList ;
26  bestTourSeq = tspInsertion(dist,subtourList) ;
27  bestLength = tspTourLength(bestTourSeq,dist) ;
28  iter = 0 ;
29  contin = 1 ;
30  while (contin)
31  contin = 0 ;
32  iter += 1 ;
33  [neighborhood, city1, city2] = twoOptNeighborhood(getTourSequence(currentList)) ;
34  for i = 1:columns(neighborhood)
35  tourSeq = tspInsertion(dist,getTourList(neighborhood(:,i),n)) ;
36  l = tspTourLength(tourSeq,dist) ;
37 % printf("Best length: %f, Candidate length: %f\n",bestLength,l);
38  if (l < bestLength)
39  betterTourList = getTourList(neighborhood(:,i),n) ;
40  bestLength = l ;
41  bestTourSeq = tourSeq ;
42  bestindex = i ;
43  contin = 1 ;
44  endif
45  endfor
46  if (contin)
47  currentList = betterTourList ;
48  endif
49  endwhile
50 endfunction
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.