Routing that's sensitive to departure time

[smmaurer]

UrbanAccess currently creates static networks representing aggregate transit service over a given time window. If a transit route runs during the window, it will be available, and the wait time for all agents will be based on the average headway.

How hard would it be to represent each scheduled bus or train, and route agents onto specific vehicles based on their departure time? I think this is a feature request that comes up from time to time, although it's more relevant for travel modeling than for accessibility calculations.

This issue writes up some notes about potential approaches, for future reference. Tagging issue #51 as related to this.

Pandana improvements

First, as of Pandana v0.5 it's now much easier to calculate and inspect point-to-point routings (see Pandana-demo.ipynb). This makes it easier to understand what's happening in UrbanAccess networks: which transit lines are used for which trips, how long the transit and non-transit portions take, etc.

This provides more information than has previously been available, and might actually make departure-time-sensitive routing less important.

Helpful paper

I recently came across this paper about using contraction hierarchies with transit networks, which is helpful for understanding what's feasible using UrbanAccess + Pandana. (This is the algorithm that Pandana uses for fast shortest-path calculations.)

https://i11www.iti.kit.edu/_media/teaching/theses/da-wirth-15.pdf

Earliest arrival queries

Drawing from that paper, one way to place trips onto individual vehicles (which the author calls “earliest arrival queries”) is to put this info into the graph itself — each departure has its own nodes and edges that overlap in physical space but are connected based on the GTFS schedule (section 3).

This gets impractical for large time windows because of graph complexity, but it might work well for travel-modeling use cases. The big catch is that it’s hard to capture incoming connections from the street network without also duplicating the street nodes — because an agent's starting point needs to capture time as well as location (section 5).

Implementing this in UrbanAccess

I think our presumption has been that contraction hierarchies aren't compatible with routing that's sensitive to departure time. It seems like this isn't necessarily true.

It's probably feasible to adapt UrbanAccess to create networks that can route agents onto specific vehicles based on their departure time. But the catch is that we'd have to be strict about delineating catchment areas for trip origins and station transfers -- which may be complex to implement, as well as making the routings themselves less useful.

Before doing this, I think we'd want to explore using Pandana's new route-inspection functionality to generate metrics that might be able to stand in for more detailed trip assignment.