Optimization: principles and algorithms, by Michel Bierlaire
bestInsert.m
Go to the documentation of this file.
1 %> \file
2 %> Identifies the best insertion in a tour for the TSP
3 %>
4 %> @note Called by \ref tspInsertion
5 %> @note Calls \ref insertCity
6 %> @note Calls \ref subtourLength
7 %>
8 %> @author Michel Bierlaire
9 %> @date Tue Apr 14 12:50:27 2015
10 %> @ingroup Algorithms
11 %> @ingroup chap27
12
13 %> Inserts city i in the best place
14 %> @param next for each node, provides the next node in the tour
15 %> @param dist distance matrix
16 %> @param i city to be inserted
17 %> @return new tour
18 function [bestnode,bestlength] = bestInsert(next,dist,i)
19  currentnode = 1 ;
20  bestnode = 0 ;
21  bestlength = realmax ;
22  while (currentnode != 0)
23  candidate = next ;
24  candidate = insertCity(candidate,currentnode,i) ;
25  [l,m] = subtourLength(candidate,dist) ;
26  if (l < bestlength)
27  bestnode = currentnode ;
28  bestlength = l ;
29  endif
30  currentnode = next(currentnode) ;
31  endwhile
32 endfunction
33
34
function insertCity(in next, in a, in i)
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.