Optimization: principles and algorithms, by Michel Bierlaire
twoOptNeighborhood.m
Go to the documentation of this file.
1 %> \file
2 %> Generate the 2-opt neightborhood for the TSP
3 %>
4 %> @note Calls \ref twoOpt
5 %> @note Called by \ref tspLocalSearch
6 %> @note Called by \ref tspInsertionLocalSearch
7 %>
8 %> @author Michel Bierlaire
9 %> @date Tue Apr 14 15:29:19 2015
10 %> @ingroup Algorithms
11 %> @ingroup chap27
12
13 %> Generate the 2-opt neightborhood for the TSP
14 %> @param cities current tour
15 %> @return matrix containing all tours neighbor of the current one
16 function [neighborhood,city1, city2] = twoOptNeighborhood(cities)
17  nCities = size(cities,1) ;
18  if (nCities < 3)
19  neighborhood = [] ;
20  city1 = [] ;
21  city2 = [] ;
22  return ;
23  endif
24  first = 1 ;
25  for i=2:nCities-1
26  for j=i+1:nCities
27  next = twoOpt(cities,i,j) ;
28  if (first)
29  neighborhood = next ;
30  first = 0 ;
31  city1 = cities(i) ;
32  city2 = cities(j) ;
33  else
34  neighborhood = [neighborhood next] ;
35  city1 = [city1 cities(i)] ;
36  city2 = [city2 cities(j)] ;
37  endif
38  endfor
39  endfor
40 endfunction
41
function tspInsertionLocalSearch(in dist, in subtourList)
function twoOpt(in cities, in c1, in c2)
Perform a 2-opt operation of a list of cities.
function twoOptNeighborhood(in cities)
Generate the 2-opt neightborhood for the TSP.
function tspLocalSearch(in tour, in dist)