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