<div dir="ltr">Thank you Julien, Ujaval, Dilawar for your excellent responses.<div><br></div><div>It's a relief to learn that this is not one of those "will take ages to compute" ones.</div><div>Fascinating, but still hauntingly just beyond my technical reach.</div><div><br></div><div>Dilawar : talk is cheap : Agreed! Here's some sample data:</div><div><a href="https://files.nikhilvj.co.in/routing/pune_peth1.gpkg">https://files.nikhilvj.co.in/routing/pune_peth1.gpkg</a><br></div><div><br></div><div>It's a peth (old city) area in Pune. Screenshot:</div><div><img src="https://files.nikhilvj.co.in/routing/punepeth1.png" width="236" height="210" style="margin-right: 0px;"><br></div><div><br></div><div>Created using HOT Export tool: <a href="https://export.hotosm.org/en/v3/exports/26662965-94cb-4f38-a476-d52ecc159d8d">https://export.hotosm.org/en/v3/exports/26662965-94cb-4f38-a476-d52ecc159d8d</a></div><div><br></div><div>Desired output: .geojson Polyline shape (or equivalent) that traverses the whole area.</div><div><br></div><div>Possible variants:</div><div>- 1 surveyor only </div><div>- N surveyors </div><div><br></div><div>(if N is difficult then ditch it and let's do 1 surveyor only; can make multiple grids as per Ujawal's recco.)</div><div><br></div><div><div><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div>--<br>Cheers,<br>Nikhil VJ<br><a href="https://nikhilvj.co.in" target="_blank">https://nikhilvj.co.in</a></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, May 12, 2021 at 1:21 AM Dilawar Singh <<a href="mailto:dilawar.s.rajput@gmail.com">dilawar.s.rajput@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div>Solutions to such problems can be found in operational research literature.<br></div><div><br></div><div>Have a look at min-flow max-cut problems in graph theory which are suited to solve this kind of optimization problem (<a href="https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.flow.minimum_cut.html" target="_blank">https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.flow.minimum_cut.html</a>). 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).<br></div><div><br></div><div>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. <br></div><div><br></div><div>PS: Talk is cheap! If you show me the data, I can show you the code.<br></div><div><br></div><div><div><div dir="ltr"><div dir="ltr"><div>Dilawar Singh, Ph.D.<br></div><div><a href="https://www.linkedin.com/in/dilawar-singh-ph-d-44b81b194/" target="_blank">LinkedIn</a> <a href="https://orcid.org/0000-0002-4645-3211" target="_blank">ORCID</a> <a href="https://github.com/dilawar" target="_blank">Github</a></div></div></div></div><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, May 11, 2021 at 6:14 PM Ujaval Gandhi <<a href="mailto:ujaval@spatialthoughts.com" target="_blank">ujaval@spatialthoughts.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><div>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 <a href="https://openrouteservice.org/dev/#/api-docs/optimization/post" target="_blank">optimization API</a> for solving optimal routing between the points.</div><div><br></div><div>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'.</div><div><br></div><div>Good luck! <br><table style="border-spacing:0px;border-collapse:collapse;color:rgb(68,68,68);width:480px;font-size:10pt;font-family:Arial,sans-serif;line-height:normal" cellspacing="0" cellpadding="0"><tbody><tr><td style="padding:10px 0px 12px;width:160px;vertical-align:top" valign="top"><a href="https://spatialthoughts.com/" style="background-color:transparent;color:rgb(51,122,183)" target="_blank"><img alt="Logo" src="https://spatialthoughts685850346.files.wordpress.com/2019/12/spatial_thoughts_logo.png" style="border: 0px none; vertical-align: middle; width: 141px; height: auto;" width="141" border="0"></a></td><td style="padding:6px 0px;width:320px"><table style="border-spacing:0px;border-collapse:collapse;background-color:transparent" cellspacing="0" cellpadding="0"><tbody><tr><td style="padding:0px;font-size:12pt;font-family:Arial,sans-serif;font-weight:bold;color:rgb(61,60,63)"><span style="color:rgb(0,175,239)">Ujaval Gandhi</span></td></tr><tr><td style="padding:0px 0px 11px;font-size:10pt;font-family:Arial,sans-serif;color:rgb(61,60,63)"><span style="color:rgb(0,175,239)">Spatial Thoughts</span></td></tr><tr><td style="padding:0px;font-size:10pt;font-family:Arial,sans-serif;color:rgb(155,155,155)"><span>mobile: +91-8095684687</span></td></tr><tr><td style="padding:0px;font-size:10pt;font-family:Arial,sans-serif;color:rgb(155,155,155)"><span>email: </span><span style="color:rgb(23,147,210)"><a href="mailto:ujaval@spatialthoughts.com" target="_blank">ujaval@spatialthoughts.com</a></span></td></tr><tr><td style="padding:6px 0px 0px"><span style="display:inline-block;height:22px"><span><a href="https://www.linkedin.com/in/spatialthoughts/" style="background-color:transparent;color:rgb(51,122,183)" target="_blank"><img alt="LinkedIn icon" src="https://codetwocdn.azureedge.net/images/mail-signatures/generator/elegant-logo/ln.png" style="border: 0px none; vertical-align: middle; height: 20px; width: 20px;" width="23" height="23" border="0"></a> </span><span><a href="https://twitter.com/spatialthoughts" style="background-color:transparent;color:rgb(51,122,183)" target="_blank"><img alt="Twitter icon" src="https://codetwocdn.azureedge.net/images/mail-signatures/generator/elegant-logo/tt.png" style="border: 0px none; vertical-align: middle; height: 20px; width: 20px;" width="23" height="23" border="0"></a> </span></span></td></tr></tbody></table></td></tr><tr><td colspan="2" style="padding:8px 0px 0px;border-top:1px solid rgb(23,147,210);width:480px;font-family:Arial,sans-serif;color:rgb(155,155,155);text-align:justify"></td></tr></tbody></table><br></div></div></div></div></div></div></div></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, May 11, 2021 at 9:09 AM Nikhil VJ <<a href="mailto:nikhil.js@gmail.com" target="_blank">nikhil.js@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">Hi All,<div><br></div><div>Wishing everyone good health, stability and pragmatism in these times.</div><div>I came across a certain technical problem statement pertaining to ground survey planning in a target area:</div><div><br></div><div>Given X ground surveyors, </div><div>Create X routes that start from one location,</div><div>Cover all the existing roads and pedestrian pathways in the target area (obtained from OpenStreetMap data), </div><div>Such that each path is walked over at least once.</div><div>Balance the distance amongst the routes so that no one gets the brunt of the tasks.</div><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div><br></div><div>Variant 1: Multiple starting locations allowed.</div><div><br></div><div>Reaching out to check if anyone has experience working this out? It seems like a common/recurring challenge that can use a common solution.</div><div><br></div><div>I'm checking out OSMNX, but not finding a usable example yet over there.</div><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>--<br>Cheers,<br>Nikhil VJ<br><a href="https://nikhilvj.co.in" target="_blank">https://nikhilvj.co.in</a></div></div></div></div></div></div></div></div></div></div></div></div></div>
<p></p>
-- <br>
Datameet is a community of Data Science enthusiasts in India. Know more about us by visiting <a href="http://datameet.org" target="_blank">http://datameet.org</a><br>
--- <br>
You received this message because you are subscribed to the Google Groups "datameet" group.<br>
To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:datameet+unsubscribe@googlegroups.com" target="_blank">datameet+unsubscribe@googlegroups.com</a>.<br>
To view this discussion on the web visit <a href="https://groups.google.com/d/msgid/datameet/CAH7jeuPsR63qjLvXzHw6iOkRCotXhw5jX175gKVJcks3sLPN9Q%40mail.gmail.com?utm_medium=email&utm_source=footer" target="_blank">https://groups.google.com/d/msgid/datameet/CAH7jeuPsR63qjLvXzHw6iOkRCotXhw5jX175gKVJcks3sLPN9Q%40mail.gmail.com</a>.<br>
</blockquote></div>
<p></p>
-- <br>
Datameet is a community of Data Science enthusiasts in India. Know more about us by visiting <a href="http://datameet.org" target="_blank">http://datameet.org</a><br>
--- <br>
You received this message because you are subscribed to the Google Groups "datameet" group.<br>
To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:datameet+unsubscribe@googlegroups.com" target="_blank">datameet+unsubscribe@googlegroups.com</a>.<br>
To view this discussion on the web visit <a href="https://groups.google.com/d/msgid/datameet/CALymcQA7QyCstYwo3S37oBqGCbWQ30DvA0FPDjxnqEuvSY-uMw%40mail.gmail.com?utm_medium=email&utm_source=footer" target="_blank">https://groups.google.com/d/msgid/datameet/CALymcQA7QyCstYwo3S37oBqGCbWQ30DvA0FPDjxnqEuvSY-uMw%40mail.gmail.com</a>.<br>
</blockquote></div>
<p></p>
-- <br>
Datameet is a community of Data Science enthusiasts in India. Know more about us by visiting <a href="http://datameet.org" target="_blank">http://datameet.org</a><br>
--- <br>
You received this message because you are subscribed to the Google Groups "datameet" group.<br>
To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:datameet+unsubscribe@googlegroups.com" target="_blank">datameet+unsubscribe@googlegroups.com</a>.<br>
To view this discussion on the web visit <a href="https://groups.google.com/d/msgid/datameet/CAM72-ZuQvmPg0t3Spr8x45e_Xeip4wxTRoPNypW6ytJS%2BrT7VQ%40mail.gmail.com?utm_medium=email&utm_source=footer" target="_blank">https://groups.google.com/d/msgid/datameet/CAM72-ZuQvmPg0t3Spr8x45e_Xeip4wxTRoPNypW6ytJS%2BrT7VQ%40mail.gmail.com</a>.<br>
</blockquote></div>