TL;DR
This paper tackles the challenge of efficiently rebalancing dockless bike-sharing systems by proposing a novel approach that combines station community discovery with a spatio-temporal mixed-integer programming (STMIP) model. By decomposing the system into smaller, manageable communities and considering truck movement dynamics, their method significantly improves service level, profit, and computational efficiency compared to existing methods.
What Problem Does This Paper Address?
The rapid growth of dockless bike-sharing systems (Dockless BSS) has led to a persistent problem: the imbalance between bike supply and demand. Users' travel patterns, often concentrated around commuting hubs during peak hours, result in an oversupply of bikes in some areas and a severe shortage in others. This imbalance directly impacts customer satisfaction (e.g., inability to find a bike when needed) and the operator's profitability. Traditional rebalancing methods, whether truck-based or user-based, have limitations. User-based incentives are unreliable due to unpredictable user behavior. Truck-based rebalancing, while more stable, often simplifies the problem by ignoring crucial factors like truck travel time, routing, and velocity, leading to inefficient or infeasible rebalancing plans. Furthermore, centralized rebalancing for large-scale systems becomes computationally intractable.
Methods
The paper introduces a two-pronged approach:
- Flow-graphed Community Discovery (FCD): This algorithm addresses the complexity of centralized rebalancing.
- Station Definition: It first defines abstract "stations" by clustering historical trip start/end locations using a k-means algorithm. This moves beyond simple grid-based partitioning to capture actual user behavior hotspots.
- Community Discovery: It then constructs a weighted graph of "flow" between these stations (based on trip frequency) and applies an improved fast unfolding algorithm to detect station communities. The goal is to create communities with dense "inner flow" (trips within the community) and minimal "inter-net flow" (trips crossing community boundaries). This decomposition transforms a single, complex problem into multiple smaller, independent rebalancing problems.
- Spatio-Temporal Mixed Integer Program (STMIP): This model is designed to generate a flexible and efficient rebalancing policy for each identified community.
- Key Innovations: Unlike previous models, STMIP explicitly considers:
- Truck Routing and Velocity: It accounts for the time it takes trucks to travel between stations, ensuring that rebalancing plans are feasible within a given time slot.
- Episode-based Simulation: A time slot is divided into smaller "episodes" to model truck movement and bike pickup/drop-off sequentially.
- Objective Function: The model aims to maximize total profit, balancing order revenue (from serviceable trips) against the cost of moving bikes.
Datasets
The experiments were conducted on real-world data from DiDi Chuxing, covering the core area of Beijing from August 1st to August 31st, 2020. Each record included bike ID, start/end times, and start/end locations (longitude and latitude).
Key Insights and Ideas
- Community-based decomposition is key: Breaking down a large, complex rebalancing problem into smaller, localized community problems drastically reduces computational complexity and allows for more efficient, distributed rebalancing.
- Spatio-temporal dynamics matter: Ignoring truck travel time and velocity leads to unrealistic rebalancing plans. Incorporating these factors ensures feasibility and improves the effectiveness of repositioning.
- Profit maximization is a nuanced objective: The model balances the revenue from fulfilling user demand with the operational costs of moving bikes, providing a more realistic optimization goal.
- Trade-offs exist: The paper highlights how increasing the number of rebalancing "episodes" (R) can improve profit and reduce lost demand, but at the cost of increased computational complexity.
Key Results
The proposed STMIP with FCD approach consistently outperformed baseline methods (No Rebalancing, MIP, and MIP with FCD) across several metrics:
- Lost Demand: Reduced by an average of 19.11% (STMIP with FCD) and 22.48% (STMIP) compared to NR.
- Additional Profit: Achieved nearly double the additional profit compared to baselines. For instance, with a fleet size of 3500 and R=4, STMIP achieved a profit of 14939.0 RMB, significantly higher than other methods.
- Computational Complexity: The STMIP with FCD approach demonstrated the lowest complexity, with integer variables reduced by up to 93.26% compared to other methods. The average running time was a mere 2 seconds, making it highly practical for real-time application.
Limitations and Future Work
- Assumptions: The paper makes several assumptions, including impatient customers (they leave if no bike is available), equivalent bikes within a station, and bikes being unavailable while being transported. These simplifications might not hold true in all scenarios.
- Truck Capacity and Number: The allocation of trucks to communities is described as "approximately linear," suggesting potential for further optimization in truck distribution.
- Future Work: The authors suggest that increasing the number of trucks can lead to further improvements in profit for large-scale systems, implying that exploring optimal fleet size and distribution remains an avenue for future research. The paper also implicitly points to the need for robust demand prediction as a critical input for the STMIP model.
Summary updated