hussein-mahfouz / meet-me-halfway Goto Github PK

Some notes on available tools for transit routing. Related to #2 and #3

• The approach in gtfsmulti is interesting. If I understand correctly, it allows you to do multimodal routing without having to do both street network routing and transit network routing. It edits the feed so that you no longer need street network routing for access/egress/transfer trips. From the documentation: 

While trying to understand the internals of R5, I got the following idea. If we are already pre-calculating so many street network travel times, can we not simply include them in the transit network timetable, which can then be utilized by any GTFS-consuming routing engine? In the end, the grid points are fixed locations in space, just like transit stops. When we take the R5 approach a step further and also use the grid points as origins of trips, the access leg of a multi-modal route can be seen as a “transfer” from a grid point to a transit stop, and the egress leg as a “transfer” from a transit stop to a grid point. Using the same thought, a direct trip is a “transfer” from one grid point to another. I formalized this idea as an extension to the standard GTFS format: GTFS-Multi. It takes quite some pre-processing to create such a GTFS-Multi feed, but the benefit is that afterwards only schedule-based routing algorithms (i.e. those that scan a transit timetable) are sufficient to find optimal multi-modal routes between an origin and (multiple) destination(s).

• gtfsrouter
• Worth going through this list by MobllityData
• r5r isochrone function which calculates travel time matrices from a specific point using raptor
• Raptor in python
  • Kuan butts gist and blogpost
  • Link to a faster implementation (check comment at bottom): https://gist.github.com/kuanb/a45b65c3135dce717497643e7f35f0ab?permalink_comment_id=3823400#gistcomment-3823400

This project is a perfect motivator to make progress on a common web app template, https://github.com/alan-turing-institute/uatk-admin/issues/88. Before the hackathon next week, I'll have something ready that'll fit this project.

One thing useful to decide ahead of time is how the backend logic will work. Rust is (always) my first choice, and I've got related work started in https://github.com/a-b-street/15m/tree/main/backend/src, with an eye to refactoring pieces of this before the hackathon. If we want to use Python or something else, we should do some prep work to figure out how to compile it to WASM or run a server. Knowing the Python dependencies we'd use would help there, to know if compiling to WASM will be feasible.

For walking/cycling routing, I have plenty of existing code / cost functions in Rust that could be helpful. Driving is tougher if we want to take turn restrictions into account, but could be done (and can be ignored for the hackathon). PT is the harder part. I would love the opportunity to experiment with a simple GTFS router -- and maybe we'll need the control to do this multi-point routing. Another question there is to find a data source -- https://data.bus-data.dft.gov.uk/ is clean UK-wide GTFS for buses, but I haven't hunted around for the trains equivalent yet.

(Deciding the rough geographic scope of this app would also be handy -- how big / time-wise apart could people live?)

1. The user adds the home location of people in the group
2. Then configures the maximum distance/time, the type of amenity to meet at (pub, cafe, etc)
3. Then submits, getting back isochrones around each starting location. Where the isochrones overlap and amenities are available, show those as possible meeting spots "equidistant" (but for time) from everyone

https://a-b-street.github.io/15m/ is the layout I use often -- left sidebar, right map

Optimal meeting point definitions

• min sum (isn't really a midpoint)
• min max (works better as a midpoint)

Other stats to use in the UI

• travel time difference between the people with the longest and shortest trips
• person inconvenience score
  • how would the travel time change for everyone if you excluded person "x"
• person compromise score
  • how would the travel time change for everyone if person "x" could travel an extra "y" minutes for free

I haven't read any of the papers yet, and before I do, I wanted to write down how it might work. It feels suspiciously simple, and I don't know why yet.

The input: a list of home positions, the preferred mode of travel (could be different for each person), and other travel constraints

For each person, do a "floodfill" on the appropriate graph, starting from the home position, and stopping after the time limit is reached. Every time an edge in the graph is visited, keep track of how long it took that person to reach that edge. For walking, cycling, and driving (*) this is just a simple Dijkstra's algorithm floodfill on a graph built with appropriate edge cost functions (which could take into account elevation, street safety/comfort, etc -- as long as the edge cost is expressed as a logical "time"). (* For driving, it gets complicated to handle turn restrictions properly -- the graph becomes much messier. But we don't need to worry about this to start.)

For PT, this is more complicated, but the same conceptual floodfill approach can still work. There are edges connecting walking edges with stops/stations, and edges connecting stops. Since we're tracking the current time to reach each place in the graph, we know what the next buses/trains arriving will be. The point is, I don't think we need something fancy like RAPTOR, and I don't know if that would help us anyway -- we don't want point-to-point routing, we want the isochrone calculation.

It won't take very much time to floodfill up to 1-2 hours away for each person. The result is a cost for each person to reach each edge. We have a one-time / offline step that snaps POIs to every edge. So once we have the cost per person, we filter for edges containing POIs of the category we want. Those are our candidate meeting points. It'll be a list of (POI info, person 1 time, person 2 time, person 3 time, ...). Then we just sort those by whatever definition of optimalness -- minimize average time, minimize worst-case time, etc.