2 %> Identifies the best insertion in a tour
for the TSP
8 %> @author Michel Bierlaire
9 %> @date Tue Apr 14 12:50:27 2015
10 %> @ingroup Algorithms
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
18 function [bestnode,bestlength] =
bestInsert(next,dist,i)
21 bestlength = realmax ;
22 while (currentnode != 0)
24 candidate =
insertCity(candidate,currentnode,i) ;
27 bestnode = currentnode ;
30 currentnode = next(currentnode) ;
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.