README ¶
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/ -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
Documentation ¶
Index ¶
- Constants
- Variables
- func Distance(lat1 float64, lng1 float64, lat2 float64, lng2 float64, unit ...string) float64
- func GetTripFromTransfer(r *RoutingData, round map[uint64]StopArrival, destination uint64, ...) (*fptf.Trip, uint64)
- func GetTripFromTrip(r *RoutingData, round map[uint64]StopArrival, arrival StopArrival) (*fptf.Trip, uint64)
- type Arc
- type Bifrost
- func (b *Bifrost) AddBifrostData(fileName string)
- func (b *Bifrost) AddGtfs(zipFile string) error
- func (b *Bifrost) AddOSM(path string) error
- func (b *Bifrost) ConnectStopsToVertices()
- func (b *Bifrost) DistanceMs(from kdtree.Point, to kdtree.Point, vehicleType VehicleType) uint32
- func (b *Bifrost) GetMinAvgSpeed(vehicleType VehicleType) float64
- func (b *Bifrost) HeuristicMs(from, to *Vertex, vehicle VehicleType) uint64
- func (b *Bifrost) LoadData(load *LoadOptions) error
- func (b *Bifrost) MergeData(other *RoutingData)
- func (b *Bifrost) NewRounds() *Rounds
- func (b *Bifrost) ReconstructJourney(destKey uint64, lastRound int, rounds *Rounds) *fptf.Journey
- func (b *Bifrost) Route(rounds *Rounds, origins []SourceLocation, dest *fptf.Location, ...) (*fptf.Journey, error)
- func (b *Bifrost) RouteOnlyTimeIndependent(rounds *Rounds, origins []SourceKey, destKey uint64, vehicle VehicleType, ...) (*fptf.Journey, error)
- func (b *Bifrost) RouteTransit(rounds *Rounds, origins []SourceKey, destKey uint64, debug bool) (*fptf.Journey, error)
- func (b *Bifrost) WriteBifrostData(fileName string)
- type GeoPoint
- type LoadOptions
- type NoRouteError
- type Progress
- type Rounds
- type Route
- type RouteInformation
- type RoutingData
- type Service
- type SourceKey
- type SourceLocation
- type StopArrival
- type StopContext
- type StopRoutePair
- type Stopover
- type Trip
- type TripInformation
- type VehicleType
- type Vertex
Constants ¶
const ( TripIdWalk uint32 = 0xffffffff TripIdCycle uint32 = 0xfffffffe TripIdCar uint32 = 0xfffffffd TripIdNoChange uint32 = 0xfffffffc TripIdOrigin uint32 = 0xfffffffb ArrivalTimeNotReached uint64 = 0xffffffffffffffff )
const DayInMs uint32 = 24 * 60 * 60 * 1000
Variables ¶
var DefaultBifrost = &Bifrost{
TransferLimit: 4,
TransferPaddingMs: 3 * 60 * 1000,
WalkingSpeed: 0.8 * 0.001,
CycleSpeed: 4.0 * 0.001,
CarMaxSpeed: 36.0 * 0.001,
CarMinAvgSpeed: 8.0 * 0.001,
MaxWalkingMs: 60 * 1000 * 15,
MaxCyclingMs: 60 * 1000 * 30,
MaxStopsConnectionSeconds: 60 * 1000 * 5,
}
Functions ¶
func GetTripFromTransfer ¶
func GetTripFromTransfer(r *RoutingData, round map[uint64]StopArrival, destination uint64, tripType uint32) (*fptf.Trip, uint64)
func GetTripFromTrip ¶
func GetTripFromTrip(r *RoutingData, round map[uint64]StopArrival, arrival StopArrival) (*fptf.Trip, uint64)
Types ¶
type Bifrost ¶
type Bifrost struct { TransferLimit int TransferPaddingMs uint64 // only search for trips, padded a bit after transitioning WalkingSpeed float64 // in meters per ms CycleSpeed float64 // in meters per ms CarMaxSpeed float64 // in meters per ms CarMinAvgSpeed float64 // in meters per ms MaxWalkingMs uint32 // duration of walks not allowed to be higher than this per transfer MaxCyclingMs uint32 // duration of cycles not allowed to be higher than this per transfer MaxStopsConnectionSeconds uint32 // max length of added arcs between stops and street graph in deciseconds Data *RoutingData }
func (*Bifrost) AddBifrostData ¶
AddBifrostData Adds cached bifrost data file to the Bifrost data. Used by LoadOptions, generated by WriteBifrostData
func (*Bifrost) ConnectStopsToVertices ¶
func (b *Bifrost) ConnectStopsToVertices()
ConnectStopsToVertices connects stops to street graph using knn and the Bifrost parameters.
func (*Bifrost) DistanceMs ¶
func (*Bifrost) GetMinAvgSpeed ¶ added in v1.0.1
func (b *Bifrost) GetMinAvgSpeed(vehicleType VehicleType) float64
func (*Bifrost) HeuristicMs ¶ added in v1.0.1
func (b *Bifrost) HeuristicMs(from, to *Vertex, vehicle VehicleType) uint64
func (*Bifrost) LoadData ¶
func (b *Bifrost) LoadData(load *LoadOptions) error
LoadData loads the data from a given bifrost cache if it exists. Otherwise it will generate the data from given GTFS and street CSV files. After generating the data it will write the data to a bifrost cache.
func (*Bifrost) MergeData ¶
func (b *Bifrost) MergeData(other *RoutingData)
func (*Bifrost) ReconstructJourney ¶
func (*Bifrost) RouteOnlyTimeIndependent ¶ added in v1.0.1
func (*Bifrost) RouteTransit ¶ added in v1.0.1
func (*Bifrost) WriteBifrostData ¶
type GeoPoint ¶
type GeoPoint struct { Latitude float64 Longitude float64 VertKey uint64 CanBeStartedBy uint8 // bitmask of vehicles that can start at this point CanBeReachedBy uint8 // bitmask of vehicles that can reach this point }
func (*GeoPoint) Dimensions ¶
type LoadOptions ¶
type NoRouteError ¶ added in v1.0.6
type NoRouteError bool
func (NoRouteError) Error ¶ added in v1.0.6
func (e NoRouteError) Error() string
type Progress ¶
type Rounds ¶
type Rounds struct { Rounds []map[uint64]StopArrival MarkedStops map[uint64]bool MarkedStopsForTransfer map[uint64]bool EarliestArrivals map[uint64]uint64 Queue map[uint32]uint32 }
func (*Rounds) NewSession ¶
func (r *Rounds) NewSession()
func (*Rounds) ResetRounds ¶
func (r *Rounds) ResetRounds()
type RouteInformation ¶
type RoutingData ¶
type RoutingData struct { MaxTripDayLength uint32 `json:"maxTripDayLength"` // number of days to go backwards in time (for trips that end after midnight or multiple days later than the start) Services []*Service `json:"services"` Routes []*Route `json:"routes"` StopToRoutes [][]StopRoutePair `json:"stopToRoutes"` Trips []*Trip `json:"trips"` StreetGraph [][]Arc `json:"streetGraph"` Reorders map[uint64][]uint32 `json:"reorders"` // for reconstructing journeys after routing Vertices []Vertex `json:"vertices"` StopsIndex map[string]uint64 `json:"stopsIndex"` // gtfs stop id -> vertex index NodesIndex map[int64]uint64 `json:"nodesIndex"` // csv vertex id -> vertex index GtfsRouteIndex []uint32 `json:"gtfsRouteIndex"` // route index -> gtfs route index RouteInformation []*RouteInformation `json:"routeInformation"` TripInformation []*TripInformation `json:"tripInformation"` TripToRoute []uint32 `json:"tripToRoute"` // trip index -> route index // for finding vertices by location. points are GeoPoint WalkableVertexTree *kdtree.KDTree `json:"-"` CycleableVertexTree *kdtree.KDTree `json:"-"` CarableVertexTree *kdtree.KDTree `json:"-"` }
func MergeData ¶
func MergeData(a *RoutingData, b *RoutingData) *RoutingData
MergeData merges two RoutingData structs. It only concatenates the vertices and edges. Use ConnectStopsToVertices to connect stops to the street graph. IMPORTANT: This algorithm may change and re-use the data from both structs. Also note, that using multiple transit feeds may break things like the stops index due to duplicate stop ids. Multiple street graphs are not supported as there is no way of connecting them. todo: fix stops index for multiple transit feeds todo: add support for multiple street graphs
func (*RoutingData) EnsureSliceLengths ¶
func (r *RoutingData) EnsureSliceLengths()
func (*RoutingData) GetFptfStop ¶
func (r *RoutingData) GetFptfStop(stop uint64) *fptf.StopStation
func (*RoutingData) GetTime ¶
func (r *RoutingData) GetTime(ms uint64) fptf.TimeNullable
func (*RoutingData) PrintStats ¶
func (r *RoutingData) PrintStats()
func (*RoutingData) RebuildVertexTree ¶
func (r *RoutingData) RebuildVertexTree()
type StopArrival ¶
type StopArrival struct { Arrival uint64 // arrival time in unix ms Trip uint32 // trip id, special TripId are defined (for example TripIdWalk) EnterKey uint64 // stop sequence key in route for trips, vertex key for transfers Departure uint64 // departure day for trips, departure time in unix ms for transfers TransferTime uint32 // time in ms to walk or cycle to this stop from the previous stop Vehicles uint8 // bitmask of vehicles available at this stop }
type StopContext ¶
type StopRoutePair ¶
type Stopover ¶
type Stopover struct { Arrival uint32 // ms time since start of day Departure uint32 // ms time since start of day }
func (Stopover) ArrivalAtDay ¶
func (Stopover) DepartureAtDay ¶
type TripInformation ¶
type VehicleType ¶ added in v1.0.1
type VehicleType uint32
const ( VehicleTypeCar VehicleType = iota VehicleTypeBicycle VehicleTypeWalking )