Optimization: principles and algorithms, by Michel Bierlaire
tspNearestNeighbor.m
Go to the documentation of this file.
1 %> \file
2 %> Algorithm 27.1: nearest neighbor heuristic for TSP. Implementation of algorithm 27.1 of \cite Bier15-book
3 %>
4 %> @note Tested with \ref run2703nearestNeighbor.m
5 %>
6 %> @author Michel Bierlaire
7 %> @date Tue Apr 14 11:36:13 2015
8 %> @ingroup Algorithms
9 %> @ingroup chap27
10
11 %> Compute an halmitonian path using the nearest neighbor heuristic
12 %> @param dist distance matrix
13 %> @return permutation of the cities
14 function pi = tspNearestNeighbor(dist)
15  n = rows(dist) ;
16  if (columns(dist) != n)
17  error("Distance matrix must be square") ;
18  endif
19  # First city is the depot
20  currentCity = 1;
21  pi = [ currentCity ] ;
22  while (size(pi) != n)
23  distances = dist(:,currentCity) ;
24  [s,i] = sort(distances) ;
25  for j=1:size(s)
26  if (s(j) != 0.0 && !any(pi==i(j)))
27  currentCity = i(j) ;
28  pi(end+1,1) = currentCity ;
29  break ;
30  endif
31  endfor
32  endwhile
33
34
function tspNearestNeighbor(in dist)
Compute an halmitonian path using the nearest neighbor heuristic.