Optimization: principles and algorithms, by Michel Bierlaire
tspLocalSearch.m
Go to the documentation of this file.
1 %> \file
2 %> Algorithm 27.3: local search for the TSP. Implementation of algorithm 27.3 of \cite Bier15-book
3 %>
4 %> @note Tested with \ref run2703localSearch.m
5 %> @note Calls \ref twoOptNeighborhood
6 %> @note Calls \ref tspTourLength
7 %>
8 %> @author Michel Bierlaire
9 %> @date Tue Apr 14 15:27:43 2015
10 %> @ingroup Algorithms
11 %> @ingroup chap27
12 %>
13 %> Local search based on the 2-OPT neighborhood.
14 %> @param tour initial solution
15 %> @param dist the distance matrix
16 %> @return betterTour local optimum
17 %> Perform a local search for the TSP with a 2-OPT neighborhood
18 function betterTour = tspLocalSearch(tour,dist)
19  betterTour = tour ;
20  current = tour ;
21  bestLength = tspTourLength(tour,dist) ;
22  printf("%d\t",current) ;
23  printf("|%.2f\n",bestLength) ;
24  iter = 0 ;
25  contin = 1 ;
26  while (contin)
27  contin = 0 ;
28  iter += 1 ;
29  [neighborhood, city1, city2] = twoOptNeighborhood(current) ;
30  for i =1:columns(neighborhood)
31  l = tspTourLength(neighborhood(:,i),dist) ;
32  if (l < bestLength)
33  betterTour = neighborhood(:,i) ;
34  bestLength = l ;
35  bestindex = i ;
36  contin = 1 ;
37  endif
38  endfor
39  if (contin)
40  printf("%d\t",betterTour) ;
41  printf("|%.2f\t%d\t%d\n",bestLength,city1(bestindex),city2(bestindex)) ;
42  current = betterTour ;
43  endif
44  endwhile
45 endfunction
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 tspLocalSearch(in tour, in dist)