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.
