Bifrost

A lightweight, blazing fast, multi-modal routing engine in go. It can route on public transport and streets. Its features are still limited compared to other routing engines, but it is already quite fast and easy to use.

Usage

You can use it either as a library or as a command line tool. The cli will start a server that you can query with http requests. You will need to prepare a GTFS and an OSM file. We use the golang binding of the friendly public transport format for journey input and output.

Note, that internally, one of the libraries uses CGO for faster parsing. This can be turned off by setting the environment variable CGO_ENABLED=0 before building.

CLI Usage

Please prepare at least one GTFS and one OSM file. After that, run:

go run server/main.go -gtfs data/mvv/gtfs.zip -osm data/mvv/osm/oberbayern-latest.osm.pbf -bifrost data/mvv/munich.bifrost

This will start a server on port 8090. You can query it with http requests. See here for the api specification.

Library Usage

go get github.com/Vector-Hector/bifrost

Example script:

package main

import (
	"fmt"
	"github.com/Vector-Hector/bifrost"
	"github.com/Vector-Hector/fptf"
	"time"
)

func main() {
	b := bifrost.DefaultBifrost // Create a new router with default parameters
	err := b.LoadData(&bifrost.LoadOptions{
		OsmPaths:    []string{"oberbayern-latest.osm.pbf"},
		GtfsPaths:   []string{"gtfs/"},
		BifrostPath: "munich.bifrost",
	}) // Load cached data or create and cache routing data from source
	if err != nil {
		panic(err)
	}

	r := b.NewRounds() // Reusable rounds object for routing

	// define origin, destination and time
	origin := &fptf.Location{
		Name:      "München Hbf",
		Longitude: 11.5596949,
		Latitude:  48.140262,
	}

	dest := &fptf.Location{
		Name:      "Marienplatz",
		Longitude: 11.5757167,
		Latitude:  48.1378071,
	}

	departureTime, err := time.Parse(time.RFC3339, "2023-12-12T08:30:00Z")
	if err != nil {
		panic(err)
	}

	journey, err := b.Route(r, []bifrost.SourceLocation{{
		Location:  origin,
		Departure: departureTime,
	}}, dest, false, false)
	if err != nil {
		panic(err)
	}

	fmt.Println("Journey from", journey.GetOrigin().GetName(), "to", journey.GetDestination().GetName(), "departs at", journey.GetDeparture(), "and arrives at", journey.GetArrival())
}

How it works internally

The routing algorithm is based on dijkstra and the RAPTOR algorithm. It switches each round between public transport and street routing to find the best multi-modal path.

References

Thanks to all the people who wrote the following articles, algorithms and libraries:

• OpenTripPlanner: Great routing engine that inspired us to write this. It has much more features, but also needs much more resources.
• Raptor Agorithm Paper: The paper that describes the RAPTOR algorithm
• Simple version of RAPTOR in python: Helped us understand the algorithm and implement it
• Dijkstra: For street routing
• GTFS: For public transport data
• OSM: For street data
• osm2ch: For converting OSM to a street graph
• kdtree: For efficient nearest neighbour search
• fptf: For input and output of the routing API