MAPPING
Calculating the Shortest Path in Tokyo
Which is more important — the journey, or the destination?
Introduction
One of my favorite and most-used apps are Google Maps and Apple Maps. They help me find new restaurants and cafés, scope out new areas to explore, and help me not get lost when exploring Tokyo’s vast urban landscape.
In this post, I will attempt to replicate one of their popular features: generating a route to navigate from one place to another. There are many well-known algorithms to generate an optimal route, including A* (pronounced “A-Star”) and Dijkstra’s algorithm.
I will be using Dijkstra’s algorithm, against road network data collected from OpenStreetMaps.
Data Sources and Tools
I used the following data sources:
- osmnx: osmnx¹ is a Python library used to easily download road networks from OpenStreetMaps and analyze them. I used
osmnxto download road networks in the Tokyo area. - geofabrik.de: geofabrik is a company that offers OpenStreetMap-related consulting and services. They have free extracts of OpenStreetMap to download, among their other services. I used data from their Kanto region to add additional features to my map, such as buildings, railways, and parks.
- Google Maps: Google Maps is a mapping platform and application offered by Google. I used Google Maps to generate routes to compare against my implementation of Dijkstra’s algorithm.
And I used the following tools:
- Python: Python is a popular general purpose programming language! I used Python to implement Dijkstra’s algorithm. I stuck with PyCharm for this project.
- PostgreSQL + PostGIS: PostgreSQL is an open source relational database, and is well-suited to geospatial data when used with the PostGIS extension. I used PostgreSQL and PGAdmin to interact with the road network data from
osmnx. - QGIS: QGIS is an application to visualize, edit, and analyze geospatial data. I used QGIS to visualize the road network data, additional map information, and my generated routes.
First, I used osmnx to download a section of road network data in the Tokyo area. A road network (or street network) is a graph that represents connected roads and intersections, and is necessary for the network analysis I am performing.
osmnx saves the road network into a Geopackage file with two layers: one for nodes and one for edges.
In the spirit of learning, I will be implementing Dijkstra’s algorithm myself. But for those who prefer not to reinvent the wheel, osmnx first downloads the data from OpenStreetMap into a networkx MultiDiGraph. The MultiDiGraph class comes with some useful methods out of the box , such as calculating the shortest path from one node to another using Dijkstra’s algorithm!
With the data in hand, I implemented Dijkstra’s algorithm to calculate the shortest distance between two nodes, with a modification to keep track of the path taken along with the shortest distance.
All Dijkstra’s algorithm needs is an adjacency relationship between nodes, and a cost to traverse each edge. For this implementation, the cost of traversing an edge is the edge’s length. Continue reading to see how other factors can be used to calculate the cost of traversing an edge!
Assumptions
Some assumptions I have made about this include:
- I assume that the downloaded graph is simple. A simple graph is one where there is at most one edge between any two nodes, and that edges do not start and end with the same node (i.e no loops exist in the graph).
- My implementation of Dijkstra’s considers only the edge’s length when calculating cost, and does not take into account any additional attributes such as road type or roads within private properties.
Results
I will start with a straightforward example: calculating the shortest route from Harajuku Station to Blue Bottle near Omotesando Station. This is a route I take when I’m in the area and in the mood for coffee! ☕️
I’ll use QGIS to visualize the underlying road network, with the generated route on top. And I will add some more map elements from geofabrik.de to hopefully make it more recognizable to those familiar with Tokyo’s urban areas.
And for fun, I will compare the results from my implementation with those generated by Google Maps, to see if there are any notable differences.
Using ST_Length, I calculated the route generated from my implementation to be 1.213km. The one Google Maps has generated is also 1.2km. The path from Harajuku Station to Blue Bottle is straightforward, so I didn’t expect much of a difference between the two.
Moving on to something a little more interesting: Harajuku Station to Aoyama-Itchome Station. There are some main roads, but also many smaller roads in between for the algorithm to choose from.
The route from my implementation runs 2.4km. Google Maps suggested a couple that also run about 2.4km, and one of the generated routes bears a close resemblance with my own!
I’ll finish with one last example — this time, the shortest route from Otemachi Station to Hanzomon Station. In between the two stations lies the Imperial Palace grounds. I was curious to see how my implementation would handle this.
The route generated from my implementation cuts through the Imperial Palace for part of the route. This is not surprising, considering that my implementation has no understanding of public or private properties or business hours: to it, all edges are the same and all are available for traversal.
In comparison, the route by Google Maps goes around the Imperial Palace instead. There is a popular jogging course that surrounds the Imperial Palace, so the route by Google Maps makes sense.
Distance-wise, the route generated from my implementation came to 2.6km. In comparison, the route Google Maps has generated is 2.8km. While my route is shorter, Google probably considers other information when generating routes.
Overall, I’m happy with how my implementation turned out! It lays the foundation for more improvements in the future.
Challenges and Limitations
- Getting the data into a set of nodes and edges is usually a challenge. I was lucky that a library like
osmnxexists to simplify this process. - I had assumed that the graph was simple. However, I have found instances where there may be more than one edge between two nodes, which may cause my implementation to not find the shortest path.
- As shown in the first example, additional information such as road types and road availability were not considered. Dijkstra’s algorithm allows one to optimize for more than just the shortest distance. For example, one could tweak the algorithm’s cost function to prefer certain road types, or prefer a route with with less turns.
Conclusions and Next Steps
Implementing the algorithm is usually the first step, but I am excited in taking this project further. Some potential improvements I can look into include:
- Exploring different cost functions. It would be fun to optimize a route on other metrics, such as the path with the most amount of shade or the path with the fewest turns.
- Factoring road types when calculating the optimal path. It would be interesting to see how the algorithm would respond when certain road types are more expensive, or are inaccessible! This probably comes up when calculating a viable path by car versus on foot.
- Including Tokyo’s train network along with the road network when generating the optimal route.
Thank you so much for reading! Stay safe, happy holidays, and see you next time!
👋, 🌏! My name is Miguell. I am interested in the intersection of software and mobility!
Citations
[1] — Boeing, G. 2017. “OSMnx: New Methods for Acquiring, Constructing, Analyzing, and Visualizing Complex Street Networks.” Computers, Environment and Urban Systems. 65, 126–139. doi:10.1016/j.compenvurbsys.2017.05.004
