[Talk-in] Routing challenge: Covery every path optimally

[Nikhil VJ]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/talk-in/attachments/20210511/3e873493/attachment.htm>