TL;DR
Bike-sharing systems struggle with bikes being in the wrong place at the wrong time, leading to lost demand and revenue. This paper introduces a dynamic repositioning and routing approach that uses optimization, decomposition, and abstraction to efficiently move bikes, significantly reducing lost demand and improving profits compared to existing methods.
What Problem Does This Paper Address?
Bike-sharing systems (BSSs) are popular for their environmental and health benefits, but they face a critical operational challenge: imbalanced bike distribution. At any given time, some stations are "full" (congestion) while others are "empty" (starvation). This imbalance directly leads to lost demand – potential customers can't find a bike when they need one or a place to return it. This not only frustrates users but also results in lost revenue for operators and can even lead to penalties from city governments. Existing solutions often rely on static repositioning (only at the end of the day) or myopic, ad-hoc methods that don't account for future demand. This paper tackles the problem of dynamically repositioning bikes to minimize lost demand and maximize profit by considering future expected demand and optimizing vehicle routes simultaneously.
Methods
The authors propose a Dynamic Repositioning and Routing Problem (DRRP), which they tackle using a combination of advanced techniques:
- Mixed Integer Linear Programming (MILP): They formulate the DRRP as a comprehensive MILP to capture the trade-off between maximizing served demand (profit) and minimizing vehicle operating costs.
- Lagrangian Dual Decomposition (LDD): To handle the computational complexity of the MILP, they decompose it into two subproblems: one for bike repositioning and one for vehicle routing. LDD is used to iteratively solve these subproblems and derive a near-optimal solution for the overall problem.
- Abstraction: To further improve scalability for large BSSs, they employ a geographical proximity-based clustering approach. Nearby stations are grouped into "abstract stations," reducing the problem size. This abstraction is then combined with LDD.
- Simulation: The effectiveness of their approach is evaluated using a simulation model that incorporates real-world customer trip data and Poisson-distributed demand scenarios.
Datasets
The paper uses data from two real-world bike-sharing systems:
- Capital Bikeshare (Washington, DC)
- Hubway (Boston, MA)
Synthetic datasets are also generated from these real-world datasets to test scalability.
Key Insights and Ideas
- Dynamic is Key: Static repositioning is insufficient because it ignores the dynamic nature of bike demand and supply throughout the day. Myopic, ad-hoc approaches also falter by not considering future demand.
- Decomposition is Powerful: Breaking down the complex DRRP into smaller, manageable subproblems (repositioning and routing) via LDD significantly improves computational efficiency.
- Abstraction for Scale: Grouping nearby stations into abstract stations is crucial for making the problem tractable for large-scale BSSs, offering substantial speedups with minimal loss in solution quality.
- Geographical Proximity Matters: The observation that nearby stations often exhibit similar behavior (e.g., becoming empty simultaneously) makes geographical clustering a natural and effective abstraction strategy.
- Trade-offs are Necessary: The problem involves balancing the desire to maximize profit (by serving more demand) with the cost of repositioning bikes. The proposed objective function captures this trade-off effectively.
Key Results
The authors demonstrate significant improvements over benchmark approaches (static and online heuristics):
- Reduced Lost Demand: Their dynamic approach consistently reduces lost demand by substantial margins. For example, on the Hubway dataset, it achieved a 45.80% reduction compared to static repositioning and 41.17% compared to an online heuristic. Similar gains were observed for Capital Bikeshare.
- Increased Profit: The reduction in lost demand translates directly into higher profits. The approach consistently outperforms benchmarks in profit gain, though the difference is often smaller than the lost demand reduction, indicating efficient cost management.
- Scalability: LDD and abstraction significantly improve scalability. LDD alone outperforms the global MILP, and abstraction further enhances performance, allowing solutions for much larger problems within reasonable timeframes. For instance, a 50-station problem was solved in under an hour with LDD, whereas the global MILP failed to finish within 6 hours for problems over 20 stations.
- Robustness: The approach shows robustness to changes in parameters like the number of vehicles and routing costs.
Limitations and Future Work
- Computational Limits: Even with LDD and abstraction, solving very large instances can still be time-consuming.
- Demand Prediction Accuracy: The accuracy of the solution depends on the accuracy of demand prediction. While the paper uses Poisson distributions, more sophisticated demand forecasting could further improve results.
- Real Dynamics: The paper acknowledges that capturing "real dynamics" (e.g., exact customer behavior when stations are empty) would require more complex, potentially quadratic, constraints, which are computationally challenging.
- Future Work: The authors suggest extending the work with robust optimization techniques to account for all possible demand scenarios and exploring the Pareto front of maximizing serviced demand versus minimizing routing cost. They also mention the potential for incorporating operational enhancements like bike-trailers for more granular repositioning.
Summary updated