Optimization: principles and algorithms, by Michel Bierlaire
subtourLength.m
Go to the documentation of this file.
1 %> \file
2 %> Calculate the length of a subtour of the TSP
3 %>
4 %> @note Called by \ref tspInsertion
5 %> @note Called by \ref bestInsert
6 %>
7 %> @author Michel Bierlaire
8 %> @date Tue Apr 14 11:39:05 2015
9 %> @ingroup Algorithms
10 %> @ingroup chap27
11
12 %> Calculate the length of a tour
13 %> @param next for each node, provides the next node in the tour
14 %> @param dist the distance matrix
15 %> @return l the length of the tour
16 %> @return m the number of nodes in the tour
17 function [l,m] = subtourLength(next,dist)
18  currentnode = 1 ;
19  l = 0 ;
20  m = 1 ;
21  while (currentnode != 0)
22  na = currentnode ;
23  if (next(currentnode) == 0)
24  nb = 1 ;
25  else
26  nb = next(currentnode) ;
27  endif
28  l += dist(na,nb) ;
29  m += 1 ;
30  currentnode = next(currentnode) ;
31  endwhile
32 endfunction
function bestInsert(in next, in dist, in i)
Inserts city i in the best place.
function subtourLength(in next, in dist)
Calculate the length of a tour.
function tspInsertion(in dist, in initialTour)
Compute an halmitonian path using the insertion heuristic.