Bike Share Toronto

Scheduling and routing bike share trucks in Toronto

This post attempts to answer the following question:

How would Bike Share Toronto schedule and route its trucks to pick up faulty (or defective) bikes from various bike share stations and drop them off at a maintenance depot?

While making these interdependent scheduling and routing decisions, the goal is to minimize the estimated operational cost and respect business rules such as shift hours and loading capacities.

A bike share truck (un-)loading bikes at St. George St & Bloor St.

Using Operations Research (O.R.), the question can be answered by defining three components: decisions to be determined, an objective to be optimized and constraints that the solution must satisfy. In this case,

• Decisions represent the arrival and departure times of each truck at each bike station (i.e., scheduling), and the path that each truck will take among many (i.e., routing).
• Objective can be stated as finding the minimum cost which consists of deploying, and operating the trucks.
• Constraints are restrictions representing shift hours, trucks’ loading capacities as well as making sure that all faulty bikes are loaded and brought to the maintenance depot by the end of the shift.

“Operations Research is a discipline that deals with the application of advanced analytical methods to help make better decisions.”, INFORMS.

The extracted knowledge above in the form of decisions, an objective and constraints can be modelled mathematically. The model could then be solved for various changing parameters accommodating for a wide range of scenarios. One decision optimization model, endless scenarios.

Data

Using Toronto Open Data, we import and wrangle Bike Share Toronto data. Several assumptions are made to generate missing data points in order to provide a complete solution.

For simplicity, and without losing generality, one scenario is examined. Its data parameters consist of 2 depots, 10 bike share stations of 174 dock capacities, 59 faulty bikes to be picked up for reparations, and 10 deployable trucks in total.

The interactive Bike Share Data Dashboard summarizes the selected scenario in three tabs as follows:

• Map tab shows the location of each bike station with a popup window, when clicked upon, summarizing its data points.
• Stations tab provides a tabular summary for bike stations’ ids, names, geolocations, capacities, assumed faulty bikes and estimated loading time. The first and last bike stations in the tables are assumed to be the origin and destination (or maintenance) depots.
• Routes tab provides a tabular summary of all possible paths between stations, the estimated driving distance and cost between each pair of bike stations.

All data manipulations and visualizations are done using Python. Datapane is used to host and add interactivity to the dashboards in this post.

Solution

The Bike Share Solution Dashboard presents the optimal solution found for the examined scenario, with respect to the objective of minimizing the total cost. Out of 10 deployable trucks, 3 are selected, routed and scheduled to pick up all faulty bikes while respecting shift time limit and loading capacities.

The dashboard consists of Map and Itinerary tabs summarizing the solution as follows:

• The Map tab represents the optimal route and schedule of each deployed truck showing its driving direction and the sequence of visiting its bike stations along its optimal route. The arrival and departure time at each station is popped up when clicking on each station’s icon. The top right corner of the Map tab allows to (de-)select a truck or more to highlight each’s itinerary.
• The Itinerary tab shows in a tabular format the detailed itinerary of each deployed truck along with its routing and scheduling information.

The decision optimization model was written in Python and solved using Google OR-Tools.

“OR-Tools is an open source software suite for optimization, tuned for tackling the world’s toughest problems in vehicle routing, flows, integer and linear programming, and constraint programming.”, Google AI.

Acknowledgement

This post is created based on the writer’s opinions, assumptions and knowledge. They do not necessarily represent those of a third party.