[pgrouting-users] Question on using TSP

[Stephen Woodbridge]

How does the TSP code work?
Does it order the nodes by straight line distance between the nodes? or 
Does it compute the matrix of possible driving distances between the 
nodes and then order that?

I was thinking that if we had N nodes and ran a Dijkstra solution form 
with each node as the start point that we could then extract the drive 
time costs to each of the other nodes in the solution. So 10 nodes, 10 
Dijkstra solutions and we would be able to build the matrix needed for 
the TSP solver. I think in an ideal world it would be nice to be able to 
handle ~30 nodes, but that may be more an issue of hardware and 
parallelism if the software works well.

If the Dijkstra solutions were cached, you could then extract the route 
directly from the cache without having to rerun the final solution once 
you had the TSP solution.

This is obviously a little more complicated if you assume a directed 
graph and turn restrictions.

I built my own TSP solution a while back that orders the node based on 
straight line distances. I also prototyped up the above suggestion based 
on a Dijkstra solver to feed the TSP.

You can demo my TSP using straight line distances here. It should be 
able to handle a fairly large number of nodes:

http://imaptools.com/cgi-bin/tsp.cgi

Just enter a list of cities, you can copy and paste the example is 
and/or add your own in the US.

Thanks,
   -Steve