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

Fri May 14 05:55:34 UTC 2021

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

On Wed, May 12, 2021 at 1:21 AM Dilawar Singh <dilawar.s.rajput at gmail.com>
wrote:

> 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 <https://www.linkedin.com/in/dilawar-singh-ph-d-44b81b194/> ORCID
> <https://orcid.org/0000-0002-4645-3211> Github
> <https://github.com/dilawar>
>
>
> On Tue, May 11, 2021 at 6:14 PM Ujaval Gandhi <ujaval at spatialthoughts.com>
> wrote:
>
>> 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
>> <https://openrouteservice.org/dev/#/api-docs/optimization/post> 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!
>> [image: Logo] <https://spatialthoughts.com/>
>> Ujaval Gandhi
>> Spatial Thoughts
>> mobile: +91-8095684687
>> email: ujaval at spatialthoughts.com
>> [image: LinkedIn icon] <https://www.linkedin.com/in/spatialthoughts/>  [image:
>> Twitter icon] <https://twitter.com/spatialthoughts>
>>
>>
>>
>> On Tue, May 11, 2021 at 9:09 AM Nikhil VJ <nikhil.js at gmail.com> 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
>>>
>>> --
>>> 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+unsubscribe at googlegroups.com.
>>> To view this discussion on the web visit
>>> https://groups.google.com/d/msgid/datameet/CAH7jeuPsR63qjLvXzHw6iOkRCotXhw5jX175gKVJcks3sLPN9Q%40mail.gmail.com
>>> <https://groups.google.com/d/msgid/datameet/CAH7jeuPsR63qjLvXzHw6iOkRCotXhw5jX175gKVJcks3sLPN9Q%40mail.gmail.com?utm_medium=email&utm_source=footer>
>>> .
>>>
>> --
>> 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+unsubscribe at googlegroups.com.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msgid/datameet/CALymcQA7QyCstYwo3S37oBqGCbWQ30DvA0FPDjxnqEuvSY-uMw%40mail.gmail.com
>> <https://groups.google.com/d/msgid/datameet/CALymcQA7QyCstYwo3S37oBqGCbWQ30DvA0FPDjxnqEuvSY-uMw%40mail.gmail.com?utm_medium=email&utm_source=footer>
>> .
>>
> --
> 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+unsubscribe at googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/datameet/CAM72-ZuQvmPg0t3Spr8x45e_Xeip4wxTRoPNypW6ytJS%2BrT7VQ%40mail.gmail.com
> <https://groups.google.com/d/msgid/datameet/CAM72-ZuQvmPg0t3Spr8x45e_Xeip4wxTRoPNypW6ytJS%2BrT7VQ%40mail.gmail.com?utm_medium=email&utm_source=footer>
> .
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/talk-in/attachments/20210514/eb39ba27/attachment.htm>