[pgrouting-users] Question on using TSP

[Anton Patrushev]

Steve,

I forgot to mention that I'm using genetic algorithm to solve TSP.
It is also not exact solution, but it is guarantied that you get a
solution after certain number of iterations.

Anton.

On 10/29/08, Stephen Woodbridge <woodbri at swoodbridge.com> wrote:
> 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
>  _______________________________________________
>  Pgrouting-users mailing list
>  Pgrouting-users at lists.postlbs.org
>  http://lists.postlbs.org/mailman/listinfo/pgrouting-users
>