[OSRM-talk] Routing challenge: Covery every path optimally

[Julien Coupey]

Hi Nikhil

What you're describing is a variant of a problem known in the literature 
as Route Inspection / Chinese Postman problem.

It's essentially different from a TSP (visit-all-the-nodes vs 
visit-all-the-edges).

The fun part is that the simple version (undirected graph) can be solved 
to optimal in polynomial time, while other variants are hard (aka NP 
complete).

For what it's worth, I've pushed a prototype[2] that handles a 
simplified version. This is a first draft mostly coded during a 
Hack-weekend in Karlsruhe back in a time where meeting people was a thing.

It's totally not in a usable state for most situations (see limitations 
in readme). I had ideas on how to improve it but did not find the time / 
right use-cases to push it forward so far.

[1] https://en.wikipedia.org/wiki/Route_inspection_problem
[2] https://github.com/verso-optim/pOSMan

Best
Julien

On 11/05/2021 05:39, Nikhil VJ wrote:
> Hi All,
> 
> Wishing everyone good health, stability and pragmatism in these times.
> I came across a certain technical problem statement pertaining to ground 
> survey planning in a target area:
> 
> Given X ground surveyors,
> Create X routes that start from one location,
> Cover all the existing roads and pedestrian pathways in the target area 
> (obtained from OpenStreetMap data),
> Such that each path is walked over at least once.
> Balance the distance amongst the routes so that no one gets the brunt of 
> the tasks.
> 
> Variant 1: Multiple starting locations allowed.
> 
> Reaching out to check if anyone has experience working this out? It 
> seems like a common/recurring challenge that can use a common solution.
> 
> I'm checking out OSMNX, but not finding a usable example yet over there.
> 
> One idea: Plot a point at say every 50 meters along all the paths. 
> Inspect and adjust manually at intersections etc. Then run a travelling 
> salesman type algorithm on it to ensure that each point has been covered 
> at least once.
> 
> Another idea: Create a user interface to assist a person to work out the 
> solution manually - make selections, plot the routes and see the result, 
> tweak the selections and try again. Less glamorous but possibly more 
> effective than chasing behind exotic algorithms.
> 
> One base dataset required for such problems is: distance matrix. 
> Another: way to map on-road route between any two points, lots of times. 
> I've got those sorted out using OSRM, so no worries on that front.
> 
> Please forward this to colleges / students that might be looking for 
> such problem statements to take up. I can setup an official internship 
> if required.
> 
> --
> Cheers,
> Nikhil VJ
> https://nikhilvj.co.in <https://nikhilvj.co.in>
> 
> _______________________________________________
> OSRM-talk mailing list
> OSRM-talk at openstreetmap.org
> https://lists.openstreetmap.org/listinfo/osrm-talk
>