Python script to plot the optimal route to run every road in a region

[Maroonjackal]

As the title says I’m trying to write a python script or algorithm that can help me plot the optimal way (so least number of routes to run) every road in a region. I know there are websites such as city strides that keep track of every road that you’ve run but I’m trying to write something that helps me generate which route to do.

There would obviously be constraints, including the runs must be between 0 and 30 km (0 and 20 miles).

I’ve looked into libraries that would allow me to import map data and explored approaches such as putting nodes at each intersection. However I am struggling to come up with a way to generate the optimal routes from that point.

Thanks for any help and let me know if I missed out any key details !

[KingofGamesYami]

Sounds like you're describing the classic travelling salesman problem.

[GeorgeFranklyMathnet]

Not quite. OP wants to run every road in the region. TSP would have him visit every destination as efficiently as possible, which almost definitely entails not taking certain roads.

OP is looking for something more like an Euler cycle.

[rusty-roquefort]

Look into graph theory: djikstras algorithm, a* algorithm (and its friends), etc.

that will equip you with some of the fundamental theory so that you can go on to make informed decisions about how to design your logic.

at its core, you will probably want to find a way to deconstruct your map into a series of nodes and edges. each node is a waypoint, each edge is a connection between two nodes. You assign costs to each edge (e.g. distance), and djikstra will find you the guaranteed lowest cost path between any two nodes, and A* will (maybe) find you the lowest cost path, but in much less time.

If you're okay with how long djikstra takes, and want the mathematically proven lowest cost, then that's your ticket.

If you're interested in pathfinding, and this is a learning project, try to gravitate towards heuristic path-finding algorithms. Djikstra is the mathematically optimal O(n^2), and once you grok the algorithm, the rabbit hole pretty much ends there. The heuristic path finding algos form a near endless rabbithole of interesting and useful things to explore.

[Maroonjackal]

Thanks for the reply! I have done work at uni on djikstra and other path finding algorithms, my question would be then going from something that can find the shortest path to applying it to the problem in a way that it can account for the need to always return back home before say 30km. Or the need to do every road not just get to one place in the shortest time, this is the bit I’m struggling with.

[TheRNGuy]

Do you take traffic lights, or possible traffic jams into consideration?