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

[Ujaval Gandhi]

A colleague of mine solved a similar problem using the OpenRouteService API. They used k-means clusters to determine the initial distribution of points between surveyors and the optimization API for solving optimal routing between the points.

Another less glamorous but maybe a more practical solution: Overlay a grid and count the length of roads inside each grid. Assign grids to each surveyor. You can add distance from starting point in the calculation as well. I have run field operations before, and a grid-based approach is usually more manageable than a complex 'start here and walk the streets in this order'.

Good luck! 

	Ujaval Gandhi Spatial Thoughts mobile: +91-8095684687 email: uja...@spatialthoughts.com

--
Datameet is a community of Data Science enthusiasts in India. Know more about us by visiting http://datameet.org
---
You received this message because you are subscribed to the Google Groups "datameet" group.
To unsubscribe from this group and stop receiving emails from it, send an email to datameet+u...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/datameet/CAH7jeuPsR63qjLvXzHw6iOkRCotXhw5jX175gKVJcks3sLPN9Q%40mail.gmail.com.

[Dilawar Singh]

Solutions to such problems can be found in operational research literature.

Have a look at min-flow max-cut problems in graph theory which are suited to solve this kind of optimization problem (https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.flow.minimum_cut.html). This problem can be converted into an instance of this problem after suitable transformations. Another approach could be finding a balanced partition of a graph (gomory-hu etc).

I don't see a computational challenge here since the size of the problem is likely to be a few hundred places and thousands on possible routes. Maybe a brute force algo with do the job as well.

PS: Talk is cheap! If you show me the data, I can show you the code.

Dilawar Singh, Ph.D.

LinkedIn ORCID Github

To view this discussion on the web visit https://groups.google.com/d/msgid/datameet/CALymcQA7QyCstYwo3S37oBqGCbWQ30DvA0FPDjxnqEuvSY-uMw%40mail.gmail.com.

[Nikhil VJ]

Thank you Julien, Ujaval, Dilawar for your excellent responses.

It's a relief to learn that this is not one of those "will take ages to compute" ones.

Fascinating, but still hauntingly just beyond my technical reach.

Dilawar : talk is cheap : Agreed! Here's some sample data:

https://files.nikhilvj.co.in/routing/pune_peth1.gpkg

It's a peth (old city) area in Pune. Screenshot:

Created using HOT Export tool: https://export.hotosm.org/en/v3/exports/26662965-94cb-4f38-a476-d52ecc159d8d

Desired output: .geojson Polyline shape (or equivalent) that traverses the whole area.

Possible variants:

- 1 surveyor only 

- N surveyors 

(if N is difficult then ditch it and let's do 1 surveyor only; can make multiple grids as per Ujawal's recco.)

--
Cheers,
Nikhil VJ
https://nikhilvj.co.in

To view this discussion on the web visit https://groups.google.com/d/msgid/datameet/CAM72-ZuQvmPg0t3Spr8x45e_Xeip4wxTRoPNypW6ytJS%2BrT7VQ%40mail.gmail.com.

[Dilawar Singh]

On the left is the raw data. On the right, 5 partitions. The solution is not to my liking but it is promising.

Its performance can be improved further (I might try this month sometimes). This is the quickest solution (in computational terms). It uses the https://arxiv.org/pdf/1703.09307.pdf .

Here are some more snippets

Algo fails when X is large (it is not a fault of algorithm but rather of graph, its not as connected as it likes to be).

A bad solution for k = 4. The black guys gets very little.

On a large graph, it is likely to produce better results. A full-blown solution with guarantees would be a 3-4 month research project! Nonetheless, I'll try one more approach next week which is likely to produce a better result but will take a while to run. This all took ~10 seconds to compute with Python3.7.

You can find the source code: http://github.com/dilawar/algorithms/raw/master/Routing/DATAMEET_ROUTING/main.py

--

Dilawar Singh, Ph.D.

LinkedIn ORCID Github

To view this discussion on the web visit https://groups.google.com/d/msgid/datameet/CAH7jeuOvyV_SCcXPXFnNd-ebfj8V6xrPY02eopYCu06jBqrZUA%40mail.gmail.com.

[Nikhil VJ]

Hi Dilawar,

Great work, thanks! I'll try to wrap this into an api and bring to a webpage as next steps.

--
Cheers,
Nikhil VJ
https://nikhilvj.co.in

To view this discussion on the web visit https://groups.google.com/d/msgid/datameet/CAM72-ZsT9j6vyr_UjQqFsAj3S_VbaRcCvaYeMf%3DjDi%3DybzDXaA%40mail.gmail.com.

[dilawar....@gmail.com]

after the partitions, you can use https://github.com/brooksandrew/postman_problems


best,
    Dilawar

[dilawar....@gmail.com]

https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.euler.eulerize.html


Essentially you need eulerize the subgraph and then find a Euler circuit. The circuit is the route each surveyor needs to take. Both of them are linear time algorithms.

best,
    Dilawar

17 May 2021 02:47:06 data...@googlegroups.com: