[pgrouting-users] Question on using TSP

[Anton Patrushev]

hi Steve,
> 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?

It uses straight line (euclidean) distance between nodes.

>  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.

I was thinking so either, but then I read a paper (unfortunately I
don't remember who wrote it), where it was proved that the quality of
TSP with euclidean distance is only slightly worse that one with real
distance in case of normal city layout. In case of very sparse network
or rivers and bridges it becomes mo inaccurate, but still wholly
satisfactory.

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

Exactly! Of course it is nice to have exact solution, but that time it
was a compromise between quality and speed (and development time
also).

>  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

I will try it for sure. Thank you for the link!

Anton.