I have a set of points distributed throughout the 32 counties of
Ireland. I want to to plot the quickest route that hits one of the
points for each county.
If I had only one point per county it would just be the traveling
salesperson problem for a fairly trivial problem size. But having more
than one point per county makes it a different problem I think and in
fact that's where the numbers get large. I can pare down the points
per county using other heuristics but the more I pare it down the more
the path may be suboptimal so I don't want to exclude more points than
I have to and there are thousands of points for most of the counties.
Is there an existing tool that would do this or should I try to modify
pg_tsp to handle this or is this a lost cause?
Thanks.
--
greg
Hello,
There is this nice site about TSP
http://www.math.uwaterloo.ca/tsp/index.html
this is interesting about the size of a problem:
http://www.math.uwaterloo.ca/tsp/problem/pcb3cnt.html
I don’t know how your problem, but sound bigger than 3000 nodes
I would break the problem on smaller problems
btw on the next rlease a new version of pgr_tsp will be available
···
On Thu, Aug 18, 2016 at 1:33 PM, Greg Stark <stark@mit.edu> wrote:
I have a set of points distributed throughout the 32 counties of
Ireland. I want to to plot the quickest route that hits one of the
points for each county.
If I had only one point per county it would just be the traveling
salesperson problem for a fairly trivial problem size. But having more
than one point per county makes it a different problem I think and in
fact that’s where the numbers get large. I can pare down the points
per county using other heuristics but the more I pare it down the more
the path may be suboptimal so I don’t want to exclude more points than
I have to and there are thousands of points for most of the counties.
Is there an existing tool that would do this or should I try to modify
pg_tsp to handle this or is this a lost cause?
Thanks.
–
greg
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users
–
Georepublic UG (haftungsbeschränkt)
Salzmannstraße 44,
81739 München, Germany
Vicky Vergara
Operations Research
eMail: vicky@[georepublic.de](http://georepublic.de)
Web: [https://georepublic.info](https://georepublic.info)
Tel: +49 (089) 4161 7698-1
Fax: +49 (089) 4161 7698-9
Commercial register: Amtsgericht München, HRB 181428
CEO: Daniel Kastl
Greg,
Correct this is not a simple TSP problem and I'm not sure if it is a classified problem with a well known algorithm.
You might be able to solve it with a modified TSP code that where you have 32 sets of points and then try to optimize the which point in a set you pick. So you have two goals: 1) to order the sets, and 2) to select the best point in a set for a given order.
I would suggest looking into a simulated annealing solver (which we currently use) and adding code to select the lowest cost point in a set.
But this requires some programming.
-Steve
On 8/18/2016 2:33 PM, Greg Stark wrote:
I have a set of points distributed throughout the 32 counties of
Ireland. I want to to plot the quickest route that hits one of the
points for each county.
If I had only one point per county it would just be the traveling
salesperson problem for a fairly trivial problem size. But having more
than one point per county makes it a different problem I think and in
fact that's where the numbers get large. I can pare down the points
per county using other heuristics but the more I pare it down the more
the path may be suboptimal so I don't want to exclude more points than
I have to and there are thousands of points for most of the counties.
Is there an existing tool that would do this or should I try to modify
pg_tsp to handle this or is this a lost cause?
Thanks.
---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus