Optimization: principles and algorithms, by Michel Bierlaire
tspVns.m
Go to the documentation of this file.
1 %> \file
2 %> Implements the VNS to solve the TSP, as described in Section 27.3.2 of \cite Bier15-book
3 %>
4 %> @note Tested with \ref run2703vns.m
5 %> @note Calls \ref tspTourLength
6 %> @note Calls \ref getTourList
7 %> @note Calls \ref tspInsertionLocalSearch
8 %>
9 %> @author Michel Bierlaire
10 %> @date Wed Apr 15 11:38:36 2015
11 %> @ingroup Algorithms
12 %> @ingroup chap27
13
14 %> Runs the VNS heuristic on the TSP
15 %> @param tour Initial tour
16 %> @param dist matrix
17 %> @return best Best tour found by the heuristic
18 %> @return bestLength length of the best tour found.
19 %> @return The file \c ksIters.dat is also created, containing the details of the iterations.
20 function [best,bestLength] = tspVns(tour,dist)
21  n = rows(dist) ;
22  if (columns(dist) != n)
23  error("Distance matrix must be square") ;
24  endif
25  [fff,msg] = fopen("tspIters.dat","w") ;
26  fprintf(fff,"Iter\tNeighborhood\tCandidate\tBest\n") ;
27  printf("Iter\tNeighborhood\tCandidate\tBest\n") ;
28  best = tour ;
29  bestLength = tspTourLength(best,dist) ;
30  s = 2 ;
31  iter = 1 ;
32  while (s <= n)
33  subtourlist = getTourList(best(1:s),n) ;
34  [candidate,length] = tspInsertionLocalSearch(dist,subtourlist) ;
35  fprintf(fff,"%d\t%d\t%f\t%f\n",iter,s,length,bestLength) ;
36  printf("%d\t%d\t%f\t%f\n",iter,s,length,bestLength) ;
37  iter += 1 ;
38  if (length < bestLength)
39  best = candidate ;
40  bestLength = length ;
41  s = 2 ;
42  else
43  s += 1 ;
44  endif
45  endwhile
46  fclose(fff) ;
47 endfunction
function tspInsertionLocalSearch(in dist, in subtourList)
function tspTourLength(in tour, in dist)
Calculate the length of a tour for the TSP.
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.