Behind the router: Modeling dockless bikes
Recently, we have released a multimodal router utilizing open source data and software.
To make the open source router work for us, we built a plugin for OpenTripPlanner (OTP). The plugin empowers the router with the live rental bike information. We also extended the original OTP to support dockless rental bikes. Read on to hear more about how we implemented dockless bike-share in OTP.
Background
Routers are graph search algorithms optimized for finding the shortest path between a starting node (origin) and and ending node (destination). The shortest path is the path that has the minimum cost of traversing the graph from the origin to the destination according to a certain cost function. The cost function could be based on traveled distance, traveled time, monetary costs of the trip, or a combination of those.
There are many shortest path algorithms (SPAs) out there. One of the most well known SPAs is the Dijkstra algorithm, which is the foundation of many modern algorithms and used by many of today’s routers. Dijkstra guarantees the optimum path by traversing (almost) the entire graph. Such a guarantee comes with a price: Dijkstra is too slow for large urban networks.
The A* algorithm, a variation of Dijkstra, overcomes the slowness by skipping some nodes, but does not guarantee the optimal path. A* uses heuristics to give higher priority to nodes that are located along the way (in heuristic terms) to the destination and lower priority to the nodes that lead away from the destination. If you have a good heuristic, A* will find a path quickly, which makes it a more suitable algorithm for searching large graphs. Figure 1. compares how the two algorithms traverse the graph.
Despite the variability of how SPAs traverse the edges of a graph to find the shortest path, SPAs all have one thing in common: the way they model the network of streets, intersections, stations, etc. The street networks are usually modeled as a directed graph where nodes represent intersections, and edges represent streets. So, a bi-directional street is modeled with two unidirectional edges. Transit networks, with stations and the links between them, are also modeled as a graph with nodes and edges respectively.
The beauty of modeling transport infrastructure as a graph is that it allows you to combine street network graphs with transit network graphs in one heterogenous (multimodal) graph. This enables the algorithm to find optimum routes that can involve more than one mode of transport.
As Figure 2. depicts, the transit stations are connected to the street edges by an abstract edge — let’s call them links — allowing transfer between the transit mode and other modes of transport. The street-transit links allow a SPA to transfer from streets to transit network and vice versa. The links also carry the cost of transferring between the modes, as well as serving as a trigger for switching the mode of transport.
Shared bikes
Bike-share is a relatively new mode of transport which is becoming more and more popular. Bike-share systems come in two flavors: docked and dockless. Docked bikes must be picked up from and dropped off at specific fixed stations, while dockless bikes are allowed to be dropped off anywhere on the curb side of the streets within the service areas.
Before going deeper into bike-share, let’s take a look at OTP’s support for biking. OTP already supports biking with a personal bike as one of the transport modes. A personal bike can be carried by or can carry a person all the way from the origin to the destination: the router assumes you lock up your bike when you get where you’re going.
This is different in the case of bike-share. Shared bikes are not necessarily right at the origin, meaning the traveler typically has to walk to the bike for pickup. Similarly, shared bikes can’t necessarily be dropped off right at the destination, which results in walking from the drop off point to the destination. So in a sense, the bike-share model should inherit characteristics from both personal bikes and transit models:
- Like personal bikes, they use the street network and allow switching back and forth between biking and walking with the bike;
- Like transit, they pick up and drop off at certain locations.
In contrast with a personal bike which is always in the possession of the traveler, a shared bike can be possessed only between the pickup and the drop off locations. Therefore, a mechanism is needed to trigger pickups and drop offs at certain locations. Similar to traversing transit stations, the SPA should be able to traverse bike stations. Figure 3. describes how this is done by two links connecting the bike-share stations to the street edges and two self-connecting links at the station; one for drop off, and one for pick up.
Dockless shared bikes
Shared bike systems, which allow drop offs at any location in a service area, are referred to as dockless. Each bike reports its location to a central system, so the system knows where each bike is at any moment. An available dockless bike can be modeled as a pickup station with capacity of 1 bike. From this point, a single dockless bike can be connected to the graph the same way a bike stations would be. But, keep in mind, this station does not allow drop off (because it’s not an actual station).
Dockless pick-up
As Figure 4. illustrates, dockless bike is modeled as a bike station. The bike station is represented by a node which is connected to a few nearby streets via abstract links; one link connects a street edge to the bike node enabling the SPA to traverse the bike node, and the other link connects the bike node to the street edge, enabling the SPA to get back to the road network and continue traversing towards the destination using the bike. A self-connecting link at the bike node enables switching from walking to biking modes.
Dockless drop-off
Dockless bikes can be dropped off anywhere within the bike network service area. As such, there are a few use-cases that our model has to support:
- drop off at the destination when it is within the service area,
- drop off right at a transit station allowing immediate transfer to the transit,
- drop off as close as possible to the destination when it is outside the service area,
- cross the “no drop off zones” along the way to the destination.
Drop-off near the destination
Once you have picked them up, dockless bikes are more similar to personal bikes than docked ones. Since you don’t have to park them at a dock, you can drop them off right next to your destination. Therefore, it makes sense to model dockless bikes as personal bikes with a slight difference. The difference is that the pick up location is not necessarily the origin and the traveler has to walk to the bike location.
Once you are using the personal bike model, you are already allowed to take the bike all the way to the destination. Therefore, the near-destination drop off will be satisfied by design (see the example in Figure 5).
Drop-off near the transit stops
Usually, you aren’t allowed to take rental bikes onto transit vehicles. The convenience of a dockless bike system is that it allows you to drop off the bike near a transit stop and transfer to transit. We want the SPA to drop the shared bike off on the street right before boarding. Therefore, when SPA reaches a transit stop with a dockless bike, it checks if the location of the transit stop is inside the bike network’s service area. If so, it creates a transfer to transit option by dropping off the bike at the stop. Otherwise, it continues biking and transfer to transit wouldn’t be an option at this particular stop.
Drop-off in the service area close to the destination
Bike service areas are regions defined by a rental bike operator so that the users can only drop off the bike within those regions. This is a requirement for dockless bikes, while it is a less of an issue for docked bikes. Docked bikes have to be picked up and dropped of at dock stations.
Dockless bike systems explicitly define their service areas. Although service areas are part of the GBFS format (the open source bike data format), bike networks do not include the geometry of their operating regions in their GBFS feeds, so GBFS feeds lack the geometry of their service area. More on this in a future blog post.
A bike service area can be modeled as one polygon, or a multi-polygon. The SPA needs those polygons to avoid generating invalid routes (with bikes being dropped-off outside the regions). These are the cases where the SPA needs to check the service area compatibility:
- When it reaches the destination
- When it switches from bike mode to transit mode.
- When it crosses the boundary of the service area.
Checking if an edge is inside or outside a service area can be done by intersecting the geometry of the region (e.g. a multi-polygon) with the geometry of the edge (a line). This task is CPU intensive, but the good news is that it can be computed and cached once when loading the routing engine, and be used whenever the routing algorithm needs it. In fact, the information about which bike is allowed to park on a street edge is stored in the graph itself. And as the SPA traverses edges, each edge knows which bike networks allow drop offs there. This solves the first and the second cases mentioned above as they are supported by already existing triggers; i.e. arrived at the destination trigger and mode switch trigger.
The third case is more complicated because the drop off at the edge of the service area requires a new trigger. The SPA needs such trigger to be able to generate “a drop off option” in its open set. To generate a drop off possibility at the border of the service area, we can create virtual drop off stations, which allow “unlimited” drop offs with no pickups. This way, when the SPA traverses the drop off node, it creates the option of dropping off the bike right at the border and continues with a walk (or other modes) towards the destination. See Figure 6. for an example.
This model also supports crossing the no-drop-off zone and drops the bike off at the destination (as depicted in Figure 7.).
Conclusion
Implementing dockless bike-share properly in OTP was a challenge, as there are unique scenarios, each of which require special treatment. We encourage you to look at our public repo for a full view of the changes we have made. We are contributing our changes back to the main branch soon. If you are more interested in the final product, you can check out our live demo, which utilizes our Routing API to suggest combined biking and transit routes! We are always making improvements to the router and would love to hear your feedback — please chat with us on coord.co.
