PasLoin/RunEveryStreet

Solves the Chinese Postman Problem by finding the shortest route that covers all roads on a map.

The live website can be accessed here: https://pasloin.github.io/RunEveryStreet/

Run Every Street

This is an attempt at solving the Chinese Postman Problem by calculating the shortest route that covers all possible roads at least once within a selected town. This is a common problem faced by rubbish collectors cleaning every street while using the least amount of fuel, or a postman delivering letters to every house on foot. In my case, I wanted to run down every street in my town in the laziest manner possible.

The tool pulls map data from OpenStreetMap, converts it into a mathematical model (a Graph Database) consisting of nodes and edges, then applies an algorithm that produces a route. The algorithm calculates a large number of routes stochastically and selects the best one. The final route can be downloaded as a GPX file to a Garmin or other GPS.

How it works

1. When the website is loaded, it pulls the background map tileset from OpenStreetMap via the OpenLayers API
2. The user zooms and pans to select the area to analyse
3. The map data is then downloaded in XML via the OpenStreetMap Overpass API
4. Road segments, junctions and intersections are loaded into a data constellation of nodes (intersections) connected by edges (roads).
5. This is then drawn on the screen using the p5.js framework.
6. The user clicks on a node to select the starting point and clicks on roads to remove them from the graph in order to trim the coverage area.
7. Any orphaned nodes or islands that cannot be reached from the starting point are then removed using a Flood Fill algorithm.
8. The route-finding algorithm then calculates a large number of possible routes from the starting node:
   1. Create a list of all connected edges (roads) emanating from the current node
   2. Sort these by the number of times each edge has been traveled and pick the one with least travels
   3. If there is a tie with multiple edges with the same lowest number of travels, pick one randomly.
   4. Travel down the selected edge
   5. Repeat until all edges have been traveled at least once.
   6. At this point the route is complete and is drawn on the map, coloured from red at the start to green at the finish.
9. Keep repeating above to create a large set of possible solutions until the user stops the process.
10. Pick the shortest route of all those created and export it to GPX file for download