Dynamic Dropoff and System Optimization do not have the flexibility nor the existing knowledge to be incrementally extended to support more flexible headway service. We propose to gradually deprecate Dynamic Dropoff in favor of building a system that can tree-out a linear route with full stop skipping and the ability to intersperse pickups and dropoffs. This will increase the flexibility of the system while simultaneously increasing the ease of understanding the routing and scheduling limitations.
- Bridj-1.0 -- Bridj before the intellectual property was acquired by Transit Systems
- Dynamic Dropoff -- currently existing service where an algorithm re-assigns traveler's booked stops so that the aggregate walk time is minimized.
- Stop Skipping -- the ability to intersperse pickup and dropoff (and thus both) stops, and to skip any unused stops.
- Late-Binding Bookings -- bookings are made to a time-window and route, and are resolved to a specific vehicle "just in time".
- Headway Service -- Buses no longer operate on fixed schedules. Instead, each bus operates along a route, following the directions of the central system to skip stops and pickup/dropoff passengers as necessary. This requires Stop Skipping and Late-Binding Bookings
Dynamic Dropoff as it currently exists is not extensible. The primary limitation is that it requires a closed problem to solve -- it must have all of the bookings present in order to decide to which stops to allocate passengers and direct the bus. This has two important restrictions:
- All pickup stops must be before all dropoff stops
- No optimization can happen until all pickups are completed
The original vision in Bridj-1.0 was the supplant dynamic dropoff with "Full System Optimization". This is a complex prototype that is currently within the Dynamic Dropoff application. However, it is not well-known or well-understood by any of the current staff, and is not incrementally developable/deployable.
The vision now is to eventually deprecate dynamic dropoff in favor of full headway service with full stop skipping. While this sacrifices the optimization of minimizing the aggregate walk time, it opens the door to drastically improving the overall service by allowing interspersed pickups and dropoffs, and by allowing stop skipping in the pickups.
Promising fixed pickup times for passengers leads to restrictions in the service Bridj can offer. Specifically, it requires that buses not leave any pickup early, so that no passengers are left behind. This restriction makes any attempt at optimization on pickup stops fruitless, becuase the bus will simply have to wait at the next pickup.
Headway service requires major changes to both the booking and scheduling flows.
Bookings will no longer be made to a specific trip at a specific time. Instead, they will be made to a time window along a route. The system will then need to assign the booking to a specific vehicle based on the vehicles progress through the routes in the time frame that the passenger has requested.
For the passenger, they will see that they have confirmed a booking and a time window, but they will not see vehicle information immediately. Instead, the time window will adjust until a certain point when a vehicle is close to the requested pickup and within an acceptable time difference. Then the booking will commit to both a vehicle and a minimum arrival time.
Buses will no longer be scheduled to hit certain stops at specific times. Instead, each bus will be assigned a route and a block of time. The bus will continue to repeat that route (with the actual stops to be decided by the backend application) for the alloted time.
This will require that, in addition to controlling which stop a vehicle travels to next, the backend application can hold vehicles (or potentially express vehicles) to ensure that they do not bunch excessively.
Routes will be simplified into a single list of stops, from a start to an end. Branching will be eliminated entirely, and the restriction that a route be a closed cycle will be removed.
Trips that are actually scheduled and sold already fit this model; the extra freedom was for potential future need.
Initially, the vision of a route was to encompass all of the paths a vehicle may take through a set of stops. Thus, routes were implemented as directed graphs, where each node is a stop and each edge is an allowed transit from a given stop. However, this model does not reflect the current or near-future reality. Stop skipping essentially adds edges to the existing route (which must be linear in its scheduled segments). Adding all the possible edges that can be realized by stop skipping converts the linear route into a tree.
Thus, the new route scheme is a simple linear list of stops, but stop skipping implicitly realizes the route as a tree of possible paths. Because this tree can be fully generated, there is no need to either manually build or to store the tree representation.
- "Where Next" -- full stop skipping on static routes
- Late-Binding Bookings -- travelers assigned to trips at the last minute
- Route entry -- restrict routes to list of stops; transform legs to list of routes
- Aggregate travelers to nearby stops -- replace dynamic dropoff; perhaps naively
- Bunching algorithm -- space the buses out during service
- Scheduling Time Blocks -- actual headway service
A standalone, stateless service will be implemented, operating in parallel with the current application. It will take the known state of a trip - a list of stops and bookings - and return the next stop that the vehicle should use. When first implemented, this service can simply be called and its result logged so that an idea of the real-world behavior can be generated. Once satisfactory, the system can be integrated into the flow of the trip.
The call to the "Where Next" system will be triggered by the trip state machine, either on arrival to or departure from a stop. Before this is deployed to actual service, there will need to be a way to lock-out the skipped stops to prevent a traveler from booking at a pickup that is being skipped. This can be implemented independently from the actual "Where Next" logic.
This service will only apply to "static" trips, but will allow full stop skipping. It does not entirely unlock headway because there is still a need to keep the buses from bunching. Buses will have to wait to start each trip until the scheduled time, and for each chosen pickup stop, buses will have to wait until the scheduled pickup time to depart.
Bookings for travelers will be made to time windows and routes instead of specific trips. This has wide ramifications from the search process to the actual booking and traveler-notification process. It is predicated on successful deployment and refinement of the time windows that are currently under development, as well as accurate reporting for the vehicle position and eta.
For each booking, when there is a vehicle available in the appropriate time window for the designated pickup stop, the booking will be assigned to the specific trip. At this point, a guaranteed pickup time will be determined and the traveler and driver will be notified. The traveler must arrive at the pickup by the guaranteed time, and the driver must not depart the pickup before the guaranteed time.
The existing dynamic dropoff (the application) route-entry interface will be simplified by restricting the routes to linear lists of stops. Legs will be re-designed to be a list of routes. This will break the existing representations of routes, but will significantly simplify the conception of them. It is also possible that there exists an automated migration between legs that are scheduled and independent routes.
Rebuilding legs as a list of routes will be a stopgap measure for continued dynamic service. Headway service will not require this feature because pickups and dropoffs will be freely interspersed, so the legs that are being currently scheduled can simply be concatonated.
A simplified service will be deployed to aggregate travelers who book sufficiently nearby stops that they are considered "interchangable". The purpose is not a minimization of aggregate walking time, though that should be taken into account, but an effort to allow a large number of stops without having multiple, very-close-together stops being booked on the same trip.
A service will be deployed to direct buses to hold or to run express to keep the proper spacing between buses. This will likely be observe-only until late-binding bookings are available; until that point, the buses are committed to certain minimum times for their pickup stops, and so any bunching will be secondary to those timings. However, this is required for smooth operation once scheduling ceases to be concerned with specific stop arrival times.
At this point, scheduling as it is currently known will be deprecated. Instead, a vehicle will be assigned a specific route to traverse over a specific period of time. The Bunching Algorithm and Where Next service will be responsible for directing the vehicle to its next stop, and the Bunching Algorithm and Late Binding Bookings will determine when each bus should leave each stop.