[pgrouting-users] Is this a known problem with tools for solving it or am I on my own?

[Stephen Woodbridge]

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