As urban populations continue to grow, cities around the world are increasingly relying on sustainable transportation solutions like bike-sharing systems. But as bike stations across the city experience fluctuating demand, rebalancing bikes between stations has become a significant challenge. This is known as the Bike Rebalancing Problem (BRP).
In this blog post, we explore how this challenge was addressed using advanced optimization techniques and the new FICO® Xpress C++ API.
Understanding the Bike Rebalancing Problem (BRP)
A typical bike-sharing system consists of a network of docking stations where users can rent and return bikes. Over the course of the day, some stations become empty (no bikes available to rent), while others become full (no space to return bikes). This imbalance is inconvenient for users and can result in operational inefficiencies. The plot below shows how in London, out of the 800 bike stations, more than 40% regularly experience a net flow of more than 5 bikes in or out of the station, thus signifying the need for rebalancing.
The Bike Rebalancing Problem (BRP) involves determining how best to redistribute bikes across these stations, ensuring that bikes are available where they are needed and that docking stations have enough space for returns. There are various ways to formulate the problem, but usually the goal is to meet demand as effectively as possible, while minimizing operational costs related to moving the bikes. With the scale of Bike-Sharing Systems increasing around the world, solving the BRP presents a significant logistical challenge.
The Mathematical Framework Behind the BRP
The main complexity of the BRP arises from the unpredictability of user demand. To account for the stochastic demand for bikes across stations, this study formulated the problem as a two-stage stochastic mixed-integer problem. This involves decision-making under uncertainty in the following way:
So, taking into account the random bike demand, the objective was to minimize the total cost, which included both the cost of moving bikes between stations and a penalty cost for unmet demand due to overfull bike stations or empty bike stations,
How to Solve the BRP?
Now that we have a formal formulation for the BRP, how do we go about solving this two-stage stochastic mixed-integer problem? First, the stochastic demand was captured by a finite set of scenarios as is standard practice in stochastic programming, resulting in the Deterministic Equivalent Problem (DEP). This is essentially one large mixed-integer problem, which can be solved by your favourite mathematical solver.
Scaling up the BRP
One of the key challenges in solving the BRP is its scale. For example, with 800 bike stations in London and many possible demand scenarios, the problem can quickly become too large to solve directly. To address this, the study applied a technique called Benders Decomposition.
Benders Decomposition works by breaking the problem into a main problem and multiple smaller subproblems. First, the main problem (focusing on the first-stage initial bike allocation decisions) is solved after which the subproblems (handling the second-stage bike redistribution decisions) can be solved. These subproblems then communicate back some information to the main problem (called optimality cuts and feasibility cuts), and with each iteration of solving the main- and subproblems, more information is provided to the main problem until a global optimal solution is found.
By using this decomposition technique, the study was able to handle the complexity of the BRP more efficiently. Additionally, the study implemented several enhancements to improve the performance of the algorithm, including:
C++ Code Examples
The small code example below shows the basic functionality of how to create a problem, add some integer variables, add some constraints, and set the objective function. This is the core of the implementation of the main problem.
Furthermore, below one of the more simple enhancements can be found. Loading the previous iteration’s solution as starting point for the current iteration is straightforward using the API, and improves search time.
Experiments
The study conducted several experiments to test the scalability and performance of the FICO Xpress C++ API on different instances of the BRP. These instances varied in size, with up to 800 stations and 50 demand scenarios.
Three different solution methods were compared:
Key Findings and Results
The results showed that Enhanced Benders Decomposition achieved up to a 100x speedup compared to the regular Benders Decomposition. This demonstrates how the enhancements, facilitated by easy-to-use functions in the API, make the decomposition algorithm effective for large-scale optimization problems like the BRP.
However, it was also noted that the performance of Benders Decomposition can be highly dependent on the formulation of the problem. In this case, one formulation of the DEP scaled better when solved directly, while another formulation performed better when decomposed.
Conclusion
These results not only highlight the effectiveness of the FICO Xpress C++ API but also offer a practical solution for cities looking to optimize their bike-sharing systems. As bike-sharing continues to grow in popularity, the ability to solve the BRP efficiently will become increasingly important.
Resources
The implementation of this example problem is publicly accessible on Github.
Please see the Xpress online documentation for the complete Xpress C++ API reference and Xpress C++ API user guide, and also further C++ API examples.
In this blog post, we explore how this challenge was addressed using advanced optimization techniques and the new FICO® Xpress C++ API.
Understanding the Bike Rebalancing Problem (BRP)
A typical bike-sharing system consists of a network of docking stations where users can rent and return bikes. Over the course of the day, some stations become empty (no bikes available to rent), while others become full (no space to return bikes). This imbalance is inconvenient for users and can result in operational inefficiencies. The plot below shows how in London, out of the 800 bike stations, more than 40% regularly experience a net flow of more than 5 bikes in or out of the station, thus signifying the need for rebalancing.
The Bike Rebalancing Problem (BRP) involves determining how best to redistribute bikes across these stations, ensuring that bikes are available where they are needed and that docking stations have enough space for returns. There are various ways to formulate the problem, but usually the goal is to meet demand as effectively as possible, while minimizing operational costs related to moving the bikes. With the scale of Bike-Sharing Systems increasing around the world, solving the BRP presents a significant logistical challenge.
The Mathematical Framework Behind the BRP
The main complexity of the BRP arises from the unpredictability of user demand. To account for the stochastic demand for bikes across stations, this study formulated the problem as a two-stage stochastic mixed-integer problem. This involves decision-making under uncertainty in the following way:
- Stage 1 - Initial Bike Allocation: The first decision is determining the number of bikes to allocate to each station at the start of the day. This is done without yet knowing the exact demand for the day.
- Random demand realization: The day unfolds and people use the bikes throughout the day. This implies a realization of the random demand.
- Stage 2 - Redistribution at the End of the Day: After the day's demand has been realized, the second decision involves redistributing bikes between stations to prepare for the next day, aiming to rebalance the system back to the initial bike allocation that was determined to be optimal for the start of each day.
So, taking into account the random bike demand, the objective was to minimize the total cost, which included both the cost of moving bikes between stations and a penalty cost for unmet demand due to overfull bike stations or empty bike stations,
How to Solve the BRP?
Now that we have a formal formulation for the BRP, how do we go about solving this two-stage stochastic mixed-integer problem? First, the stochastic demand was captured by a finite set of scenarios as is standard practice in stochastic programming, resulting in the Deterministic Equivalent Problem (DEP). This is essentially one large mixed-integer problem, which can be solved by your favourite mathematical solver.
Scaling up the BRP
One of the key challenges in solving the BRP is its scale. For example, with 800 bike stations in London and many possible demand scenarios, the problem can quickly become too large to solve directly. To address this, the study applied a technique called Benders Decomposition.
Benders Decomposition works by breaking the problem into a main problem and multiple smaller subproblems. First, the main problem (focusing on the first-stage initial bike allocation decisions) is solved after which the subproblems (handling the second-stage bike redistribution decisions) can be solved. These subproblems then communicate back some information to the main problem (called optimality cuts and feasibility cuts), and with each iteration of solving the main- and subproblems, more information is provided to the main problem until a global optimal solution is found.
By using this decomposition technique, the study was able to handle the complexity of the BRP more efficiently. Additionally, the study implemented several enhancements to improve the performance of the algorithm, including:
- Multi-cuts: Generating multiple cuts per iteration to speed up convergence.
- Warm starts: Using solutions from previous iterations as a starting point for the current iteration, reducing the time needed to find optimality.
- Constraint pool and Callbacks: As the solver finds multiple (sub-optimal) integer solutions during an iteration, callback functions generated additional new constraints which were stored in a constraint pool and added to the problem in a batch at the end of the iteration, thereby decreasing the number of iterations required until convergence.
C++ Code Examples
The small code example below shows the basic functionality of how to create a problem, add some integer variables, add some constraints, and set the objective function. This is the core of the implementation of the main problem.
Furthermore, below one of the more simple enhancements can be found. Loading the previous iteration’s solution as starting point for the current iteration is straightforward using the API, and improves search time.
Experiments
The study conducted several experiments to test the scalability and performance of the FICO Xpress C++ API on different instances of the BRP. These instances varied in size, with up to 800 stations and 50 demand scenarios.
Three different solution methods were compared:
- The full Deterministic Equivalent Problem (DEP).
- Benders Decomposition.
- Enhanced Benders Decomposition, with some of the performance enhancements mentioned earlier in this article.
Key Findings and Results
The results showed that Enhanced Benders Decomposition achieved up to a 100x speedup compared to the regular Benders Decomposition. This demonstrates how the enhancements, facilitated by easy-to-use functions in the API, make the decomposition algorithm effective for large-scale optimization problems like the BRP.
However, it was also noted that the performance of Benders Decomposition can be highly dependent on the formulation of the problem. In this case, one formulation of the DEP scaled better when solved directly, while another formulation performed better when decomposed.
Conclusion
These results not only highlight the effectiveness of the FICO Xpress C++ API but also offer a practical solution for cities looking to optimize their bike-sharing systems. As bike-sharing continues to grow in popularity, the ability to solve the BRP efficiently will become increasingly important.
Resources
The implementation of this example problem is publicly accessible on Github.
Please see the Xpress online documentation for the complete Xpress C++ API reference and Xpress C++ API user guide, and also further C++ API examples.
Updated 1 year ago
Version 3.0