Optimization: principles and algorithms, by Michel Bierlaire
run2703localSearch.m
Go to the documentation of this file.
1 %> \file
2 %> Runs Algorithm 27.3 on example 27.3 of \cite Bier15-book, solving the TSP with local search (Figure 27.11, Table 27.7, Figure 27.12)
3 %>
4 %> @note Calls \ref tspLocalSearch
5 %>
6 %> @ingroup Running
7 %> @author Michel Bierlaire
8 %> @date Tue Apr 14 16:16:28 2015
9 %> @ingroup chap27
10
11 coord = [3.9168352575438883 9.137342270173304;
12 1.1699050319257487 18.455418341069745;
13 9.721881077629464 28.346794704912273;
14 7.390077284252903 39.41399505514082;
15 10.330134350013772 8.872575373705086;
16 17.54844435443345 12.555248083372415;
17 13.973337600200706 27.293670391120408;
18 10.780367650957938 32.30890310240921;
19 27.537494117722936 3.405255742784993;
20 22.109051040277585 13.629868632672725;
21 22.104604981898312 24.4082789143701;
22 22.642443138528456 39.900926037817364;
23 30.483507633842855 3.3699397182036805;
24 39.342134080320214 14.52455206463652;
25 37.63893123807275 21.751973125910553;
26 30.059401007763743 32.48285416836698;
27 ];
28
29 [n two] = size(coord) ;
30 dist = zeros(n,n) ;
31
32 for i=1:n
33  for j=1:n
34  if (i != j)
35  dist(i,j) = sqrt((coord(i,1) - coord(j,1))**2 + (coord(i,2) - coord(j,2))**2) ;
36  endif
37  endfor
38 endfor
39
40 firstSolution = [
41  1
42  7
43  10
44  3
45  16
46  15
47  11
48  4
49  6
50  14
51  8
52  2
53  12
54  13
55  5
56  9] ;
57
58 tour = tspLocalSearch(firstSolution,dist)
59 printf("Tour length: %f\n",tspTourLength(tour,dist)) ;
60
61 firstSolution = [ 1
62  5
63  6
64  10
65  11
66  7
67  3
68  8
69  4
70  12
71  16
72  15
73  14
74  13
75  9
76  2] ;
77
78 tour = tspLocalSearch(firstSolution,dist)
79 printf("Tour length: %f\n",tspTourLength(tour,dist)) ;
function tspTourLength(in tour, in dist)
Calculate the length of a tour for the TSP.
function tspLocalSearch(in tour, in dist)