[tsp_gettour]

Description

This tag accepts a cost matrix and returns a "next-closest tour" for solving basic TSP problems. The original version of this tag was translated into Lasso by Kyle Jessup, based on pseudo code available here:

http://students.ceid.upatras.gr/~papagel/project/tspprobl.htm

See [tsp_getdistance] and [tsp_getcosts] for examples of how to use this tag with x/y coordinate pairs (longitude/latitude).

Sample Usage

// test data	
var('cities') = array(
	'Location A' = array(-82.521102,37.484227),
	'Location B' = array(-84.622564,37.059857),
	'Location C' = array(-84.622668,37.059893),
	'Location D' = array(-82.642757,38.480449),
	'Location E' = array(-84.600683,37.031884),
	'Location F' = array(-85.062656,36.982708),
	'Location G' = array(-84.623724,37.055167),
	'Location H' = array(-84.622564,37.059857),
	'Location I' = array(-84.072400,37.107600),
	'Location J' = array(-84.335426,36.841322)	
);

// need an array of just the coordinate pairs	
var('points' = array);

'Raw Order
\n';

iterate($cities, local('i'));
	// just to show the original order
	loop_count + '. ' + #i->first + '
\n';

	// Flipping x/y values because my test data is backwards...
	$points->insert(array(#i->second->get(2),#i->second->get(1)));
/iterate;

var('costs') = tsp_getcosts($points);	
var('tour') = tsp_gettour($costs);

'

Tour Order
\n';

iterate($tour, local('i'));
	// new order 
	loop_count + '. ' + $cities->get(#i)->first + '
\n';
/iterate;

Source Code

Click the "Download" button below to retrieve a copy of this tag, including the complete documentation and sample usage shown on this page. Place the downloaded ".inc" file in your LassoStartup folder, restart Lasso, and you can begin using this tag immediately.

Download

define_tag(
	'gettour',
	-namespace='tsp_',
	-priority='replace',
	-required='costs',
	-type='array',
	-description='Generate a simple next-closest tour from a cost matrix.'
);
	// original Lasso version of this tag kindly ported by Kyle Jessup,
	// based on pseudo-code at  

	// assumes starting city is first item in the cost matrix
	local('currentCity' = 1);
	local('out') = array(#currentCity);
  
	// loop until all cities are accounted for
	// we've already added the first one, so 
	// subtract one from the array size
	loop(#costs->size - 1);
		local(
			'min' = 999999,		// must start as a high number
			'minCity' = 0
		);
		
		// set the cost of travelling to the current city
		// from all other cities to -1 to exclude it
		// (vertical axis of the cost matrix)
		iterate(#costs, local('i'));
			#i->get(#currentCity) = -1;
		/iterate;
		
		// compare the cost of travelling to each of the other
		// cities and find the shortest distance
		iterate(#costs->get(#currentCity), local('i'));
			if (#i != -1 && loop_count != #currentCity && #i < #min);
				#min = #i;
				#minCity = loop_count;
			/if;
		/iterate;
					
		// set the cost of travelling from the current city
		// to anywhere else as -1 to exclude it
		// (horizontal axis of the cost matrix)
		iterate(#costs->get(#currentCity), local('i'));
			#i = -1;
		/iterate;
		
		// set the closest city as the current city and 
		// add it to the output
		#currentCity = #minCity;
		#out->insert(#currentCity);
	/loop;

	return(#out);
/define_tag;

Related Tags

• tsp_geocode
• tsp_getcosts
• tsp_getdistance

Comments

No comments

Please log in to comment