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:
See [tsp_getdistance] and [tsp_getcosts] for examples of how to use this tag with x/y coordinate pairs (longitude/latitude).
Parameters
none
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<br>\n';
iterate($cities, local('i'));
// just to show the original order
loop_count + '. ' + #i->first + '<br>\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);
'<br><br>Tour Order<br>\n';
iterate($tour, local('i'));
// new order
loop_count + '. ' + $cities->get(#i)->first + '<br>\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.
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 <http://students.ceid.upatras.gr/~papagel/project/tspprobl.htm>
// 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;
