Project Abstract

The primary aim of this Google Summer of Code project is to re-introduce transit support in Valhalla, the OpenStreetMap based Routing Engine. Initially, Valhalla supported a mode to route transit, but due to a bottleneck from a third-party library, it became unviable to continue support transit routing. Therefore, the aim of the project is to directly parse raw General Transit Feed Specification (GTFS) data and remove the dependency.

The high level overview of the project is visible here:

GitHub Project

Specific details of each pull request will be described below.

What has been done

The first stage of the project was importing GTFS and ensuring that we can parse the data. GTFS is a set of text files, and rather than iterating through them manually, I decided to use a third party library to automize the read-write process. Just_gtfs allows us to read and store transit data in variables rather than manually trying to parse text. Moreover, I can create sample test data without being concerned about creating invalid data.

After parsing GTFS data, the next step was to pre-process them so that they could fit into Valhalla’s existing data format. Firstly, since the map is divided into tiles – square regions of equal area – I sorted the data according to which tile it belongs to. Tiles are beneficial to save computing power because only the information that belong inside the tile need to be processed when routing through small regions.

Parsing GTFS Pull Request

The sorted data then needed to be built into protobufs, which are used as intermediary data storage before they are converted to tiles. Protobufs are much more condense and versatile than raw GTFS data, so we extract the relevant information from GTFS into protobufs and gather the data. This is further useful because instead of iterating through each stop or trip of a tile, the tile could be read as one whole entity, streamlining the reading process.

Creating Protobufs Pull Request

For a detailed process of how the GTFS data is converted into protobufs, check out the Midterm Update.

The final process is parsing the protobuf files to build the Valhalla transit tiles. Although there already exists a method to build the transit map given the tiles, this was the trickiest process because each tile requires very specific data points to be created, even when they are not provided by the raw data. For instance, I had to generate virtual stations with entrances and platforms for each transit stop, when in reality it could have been a bus stop with only a pole to indicate its place.

Building Tiles Pull Request

To check that every step was working properly, unit tests were built with each data conversion using Google Test and Gurka.

What to do next

There is still a little more debugging to do, with the final step being passing the transit routing test where multimodal routing (i.e. walking to a train station, boarding a train, transferring to a bus, and walking to the destination) is possible. There remain a few more bugs to iron out before this feature can be enabled and transit routing is included in the Valhalla library.

What I have learned

Stepping my first foot into the open-source community, I realized the range of possibilities that I can work on and how there are endless projects to be discovered no matter my niche. In OpenStreetMap, I enjoyed discovering the relationships between the project and the data, and how OSM data could be applied with so much versatility in Valhalla.

On the technical side, I learned how to manage large projects in C++, as it was my first time working with a project of this caliber. At first, even setting up the project was troubling, with all the dependencies and conditions for building the project. Then I learned how to utilize the standard library and build custom data structures effectively, to store and access data most efficiently it. Furthermore, because Valhalla is a project that can be used in so many devices, I’ve learned how to thread the data processing depending on the hardware.

Acknowledgements

From building the project environment to optimizing data management, every step of working on this project has been novel and fulfilling. I have only gotten to see a small pie of what Valhalla is capable of, and I wish to continue to contribute to it.

I want to thank both my mentors Kevin Kreiser (kevinkreiser) and Nils Nolde (nilsnolde) for helping me pathfind through this project, where I could have gotten confused or lost. I truly appreciate your help and hope to contribute to Valhalla in the future as well.