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 <[email protected]> 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 <[email protected]> > 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: [email protected] >> [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 <[email protected]> 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 [email protected]. >>> 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 [email protected]. >> 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 [email protected]. > 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> > . > -- 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 [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/datameet/CAH7jeuOvyV_SCcXPXFnNd-ebfj8V6xrPY02eopYCu06jBqrZUA%40mail.gmail.com.
