search

Pipluppp / ebike-ncr

A Dijkstra shortest path application for the Metro Manila road network avoiding the e-bike prohibited roads
0 stars 3 forks source link

readme

E-bike NCR Dijkstra

A Dijkstra shortest path routing application for the Metro Manila road network which avoids the e-bike prohibited roads from MMDA Regulation No. 24-022 series of 2024.

demo

Metro Manila road network graph

The graph of nodes and edges forming the Metro Manila driveable road network is taken from OpenStreetMap. Simplified and manually cleaned to remove the prohibited road edges where e-bike are prohibited through OSMnx.

The graph is a MultiDiGraph and then stored as a .graphml file. It contains 59,055 nodes and 148,676 edges

Interactive map and drawing shortest paths

An interactive map of the Metro Manila region is served using LeafletJS, and from user destination inputs the shortest path is calculated and drawn dynamically on the map.

Dijkstra algorithm

The e-bike routing is a single-source single-target shortest path problem. The specific implementation is a Dijkstra without Decrease-Key operation using binary heaps from the python library heapq. See Lewis (2023) for runtime comparisons with other implementations.