OpenStreetMap logo OpenStreetMap

Google Summer of Code Midterm Update: Reintroducing Transit to Valhalla

Posted by ChrisPark on 26 July 2022 in English. Last updated on 27 July 2022.

GitHub Project

The project indicates the milestones and progress required for project completion, although currently it is still under development as issues may be fine-tuned later with more documentation and tests.

https://github.com/orgs/valhalla/projects/1

Abstract

We are on track for the goal to re-introduce transit to Valhalla, the open-source routing engine. So far, we have the ability to convert raw GTFS data into Valhalla’s transit tiles. The transit tiles must now be connected to rest of Valhalla’s graph for routing, which are the next steps.

Updates

I have pushed updates to Valhalla, such that it no longer relies on the Transitland API to get transit data. Instead, it now reads from locally placed raw GTFS data. To achieve this, the following was done:

1) I needed an ability to read and write GTFS data. GTFS comes in a collection of text files that must be parsed into a structure below:

GTFS Connections

To do this, I borrowed a third-party library called “just_gtfs”, which allowed me to create custom GTFS files for testing. Creating custom test data was more effective than using existing transit data, as existing ones can be extremely large, and may not cover edge cases.

2) Sort the parsed GTFS files into tiles.

The entire Valhalla map is divided into tiles, forming layers of grids of different levels of detail. The tiles are spatially unique, so different stations, and routes belong into their respective tiles. I had to create data-structures and functions that sorted the data into their unique tiles, so that they could be computed later.

3) Convert sorted data into protobufs

Protobufs are used as an intermediary data storage before it is converted to tiles, as a way to keep all the extracted relevant information from the raw GTFS data. Protobufs are useful because they can be read and edited in many environments.

4) Parse protobufs into Valhalla’s transit tiles

Currently, this is a work in progress. The old convert_transit files have been modified so that the functions can be called during testing. Modifications may be made to remove any calls to the Transitland API if any remain, and only the protobufs are accessed.

Old Valhalla Transit Implementation

New Valhalla Transit Implementation The above are flowcharts indicating how the transit data parsing process have been and will be modified.

Future Work

1) The Transit tiles must be connected to rest of the Valhalla road network. There exists more references to Transitland’s API to find graph edges, so that must be sorted out. The best method will be chosen after further discussion. We must find a way to find an optimal coordinate to connect the transit tiles.

2) Show proof of work by creating tests that connect points A -> B with functional transit routing.

Acknowledgements

I’d like to thank Nils Nolde (nilsnolde) and Kevin Kreiser (kevinkreiser) for guiding me every step of the way and allowing me to get this far already. I have learned all the tools and techniques needed to complete the project, and learned deeply about contributing to open source. It’s been an exciting past six weeks and I can’t wait for six more to come.

Discussion

Comment from IanVG on 24 August 2022 at 14:07

Very cool! Keep up the good work!

Log in to leave a comment