Source-linked AI summary
A Deep Reinforcement Learning Framework for Rebalancing Dockless Bike Sharing Systems
Ling Pan, Qingpeng Cai, Zhixuan Fang, Pingzhong Tang, Longbo Huang
TL;DR
Dockless bike sharing needs efficient rebalancing because similar travel patterns create spatial and temporal bike shortages and surpluses. This paper models rebalancing as an MDP and develops HRP, a hierarchical deep reinforcement learning method with localized spatial modeling. HRP outperforms state-of-the-art methods, while the authors identify real-world deployment and shifting environments as future challenges.
Problem
Dockless bike-sharing systems experience costly bike imbalance, while rebalancing must handle limited budgets, computational complexity, dynamic demand, and unknown user costs.
Method
The paper models user incentivization as an MDP and develops HRP, which uses hierarchical Q-value decomposition and a localized module to capture temporal and spatial dependencies.
Results
HRP outperforms state-of-the-art methods in experiments using Mobike data and demonstrates generalization across different areas.
Takeaways & Limitations
User incentives combined with spatial-temporal deep reinforcement learning provide a framework for rebalancing dockless bike-sharing systems.
Takeaways & Limitations
Real-world deployment and adaptation to shifting environments remain future work, requiring updated simulators and periodic offline retraining.
Abstract
from arXiv · showhide
Bike sharing provides an environment-friendly way for traveling and is booming all over the world. Yet, due to the high similarity of user travel patterns, the bike imbalance problem constantly occurs, especially for dockless bike sharing systems, causing significant impact on service quality and company revenue. Thus, it has become a critical task for bike sharing systems to resolve such imbalance efficiently. In this paper, we propose a novel deep reinforcement learning framework for incentivizing users to rebalance such systems. We model the problem as a Markov decision process and take both spatial and temporal features into consideration. We develop a novel deep reinforcement learning algorithm called Hierarchical Reinforcement Pricing (HRP), which builds upon the Deep Deterministic Policy Gradient algorithm. Different from existing methods that often ignore spatial information and rely heavily on accurate prediction, HRP captures both spatial and temporal dependencies using a divide-and-conquer structure with an embedded localized module. We conduct extensive experiments to evaluate HRP, based on a dataset from Mobike, a major Chinese dockless bike sharing company. Results show that HRP performs close to the 24-timeslot look-ahead optimization, and outperforms state-of-the-art methods in both service level and bike distribution. It also transfers well when applied to unseen areas.
Introduction
Dockless bike sharing suffers spatial and temporal imbalance, motivating a user-incentive framework that models rebalancing as sequential decision-making. The proposed HRP algorithm combines hierarchical decomposition with localized spatial modeling and outperforms state-of-the-art methods in reported experiments.
- Introduction: Dockless bike sharing faces imbalance from similar travel patterns, creating shortages, surpluses, and service problems across regions.The challenge is especially severe during rush hours because users’ parking locations are unrestricted.
- Introduction: Prior work includes vehicle-based and user-based rebalancing, with truck-based methods affected by prediction and operating costs.User-based methods are more economical and flexible but often omit spatial information and require unknown user-cost information.
- Introduction: The paper formulates rebalancing as an MDP whose actions are regional incentives and whose objective is to maximize long-term satisfied requests.States include supply, demand, arrivals, and related operational information.
- Introduction: HRP decomposes the overall Q-value into regional sub-Q-values and adds a localized module to capture spatial dependencies and reduce estimation bias.The divide-and-conquer structure addresses high-dimensional inputs and temporal dependencies.
- Introduction: HRP uses monetary incentives to encourage users to help rebalance dockless bike-sharing systems.The algorithm decides payments for different users at each time.
- Introduction: HRP outperforms state-of-the-art methods, with experiments also validating its optimality and generalization across different areas.The evaluation uses Mobike data and compares HRP with an offline-optimal algorithm.
Related Work
Bike-rebalancing research has developed truck-based, user-based, and related operational approaches for repositioning bikes. Truck-based methods can be static or dynamic, while other approaches leverage operational data from bike-sharing systems.
- Related Work: Bike-rebalancing approaches are commonly classified into truck-based, user-based, and other operational approaches.The literature surveys operational issues studied with large-scale bike-sharing data.
- Related Work: Truck-based methods reposition bikes with multiple trucks and can operate statically or dynamically in docked systems.The passage identifies static and dynamic truck-based repositioning as distinct approaches.
- Related Work: Recent bike-sharing research increasingly studies operational issues using big data, with rebalancing as a major focus.Rebalancing is presented as one of the most important operational problems.
Problem Definition
The paper formulates user-based bike rebalancing as incentivizing users to obtain bikes from neighboring regions while maximizing satisfied requests under a limited budget.
- System representation: The system is divided into n regions and T timeslots, with supply, demand, arrivals, and origin-destination requests tracked for each region.Supply denotes available bikes at the beginning of a timeslot; demand and arrivals describe requests and bike arrivals during it.
- User response: When no bike is available locally, users may receive price incentives to walk to a neighboring region and select an offered bike.Users choose the option with maximum utility, defined as the incentive minus their private walking cost, and reject all offers yielding negative utility.
- User response: The walking-cost function is zero locally, quadratic in walking distance for neighboring regions, and infinite for non-neighboring regions.The convex cost form is motivated by a prior survey, while the cost itself is private and unknown to the service provider.
- Objective: The objective is to maximize satisfied requests by pricing incentives that redirect users from congested regions to neighboring regions, subject to budget B.The pricing algorithm operates online as users arrive and stops offering incentives when the rebalancing budget is depleted.
Hierarchical Reinforcement Pricing Algorithm
HRP models pricing as an online MDP and combines DDPG with hierarchical Q-value decomposition and spatial bias correction to handle high-dimensional, spatially coupled actions.
- MDP formulation: The pricing problem is formulated as an MDP whose state includes current supply, recent demand, arrivals, expenses, remaining budget, and past un-service rates.The operator’s action is a vector of regional prices, and the immediate reward is the number of satisfied requests across the area.
- Objective: With γ = 0.99, the discounted objective performs very close to the offline optimal service-level objective.The paper treats the discounted objective as a close approximation to service level when the discount factor is near one.
- Hierarchical Reinforcement Pricing: HRP decomposes the whole-area Q-value into regional sub-Q-values and adds a localized correction using neighboring-region states and actions.This divide-and-conquer design addresses high-dimensional policy search while accounting for coupling between neighboring regions.
- Temporal modeling: GRU-based regional estimators capture sequential dependencies while avoiding the more complex architecture and larger parameter count associated with LSTM.The design targets accurate sub-Q-value estimation, which is needed for accurate overall Q-value estimation.
- Actor-critic architecture: The actor maps states to deterministic price actions, while the critic estimates their action values and is trained by minimizing a temporal-difference loss.The implementation uses experience replay, exploratory noise, target networks, and sampled policy gradients.
Dataset
The experiments use a Shanghai Mobike trajectory dataset containing 102,361 orders and exhibiting temporal and spatial demand imbalance.
- Dataset: The Mobike dataset contains user trajectories collected in Shanghai from August 1 to September 1, 2016, totaling 102,361 orders.Each record includes order, bike, and user identifiers; start and end times and locations; and a trace.
- Demand imbalance: The dataset’s thermodynamic diagram visualizes demand levels through circle colors and radii, revealing significant temporal and spatial imbalance.Colors represent demand levels, while circle radius represents the number of demands.
Experimental Setup
The experimental setup draws minute-level requests from Mobike trajectories, initializes bikes in proportion to regional demand, and trains and tests algorithms across daily episodes.
- Demand generation: Requests are served every minute from observed data, while starting locations are sampled uniformly within their corresponding regions.Weekday demand curves show similar daily patterns with bimodal peaks in the dataset.
- Initial supply: Initial bikes in each region are assigned in proportion to that region’s share of total demand, with locations randomly sampled from corresponding observed bike locations.The experiments vary initial supply because it affects the system’s inherent imbalance degree.
- Training and testing: Each reinforcement-learning setting uses 100 training episodes followed by 20 testing episodes, with each episode lasting 24N steps.N denotes the number of days, and the same hyperparameters are used when comparing reinforcement-learning algorithms.
Evaluation Metric
The paper evaluates pricing algorithms using the decreased un-service ratio, which measures improvement over Mobike’s original system in un-served events.
- Decreased un-service ratio measures how much an algorithm reduces un-service events relative to Mobike’s original system.It is defined from the difference between Mobike’s un-service count and the algorithm’s count, divided by Mobike’s count.
Baselines
The evaluation compares HRP with randomized, offline, bandit, and reinforcement-learning pricing methods, plus an offline-optimal upper-bound scheme.
- The comparison includes methods using random incentives, acceptance-rate optimization, multi-armed bandits, DDPG, and reward decomposition.The methods represent randomized pricing, offline optimization, user-based bandit rebalancing, and reinforcement-learning alternatives.
- The baselines include Random, OPT-FIX, DBP-UCB, DDPG, HRA, and Offline-optimal pricing algorithms.Offline-optimal maximizes service level under a budget constraint with known user costs and serves as an upper bound for online pricing algorithms.
- The offline-optimal formulation assumes trips finish within their starting timeslot and uses equal neighboring-region user costs for tractability.The paper states that the model and simulation themselves do not rely on the one-timeslot trip assumption.
Performance Comparison
Across budget, supply, time horizon, optimality, bike distribution, and transfer tests, HRP consistently outperforms comparison methods and approaches offline optimization.
- Convergence: HRP converges while DDPG and HRA diverge during training, with HRA’s divergence attributed to biased Q-value estimation from assuming independent sub-MDPs.The training-loss comparison evaluates HRP, HRA, and DDPG.
- Effect of varying budget constraints: HRP decreases the un-service ratio by 43%−63% across budget levels and outperforms other algorithms under every budget constraint.DDPG fails to use the budget efficiently, while OPT-FIX and DBP-UCB do not consider spatial information.
- Achieving better bike distribution: HRP obtains a KL divergence of 0.548, lower than Mobike’s 0.554, indicating improved end-of-day bike distribution.OPT-FIX produces the distribution most different from the initial distribution among the compared methods.
- Effect of varying supply: HRP achieves a 47%−60% decrease in un-service ratio across supply levels, demonstrating robustness when total bike supply varies.The supply experiments find Random and DBP-UCB perform poorly, while HRP performs significantly better than the other methods.
- Long-term performance: HRP outperforms HRA and OPT-FIX over one to five days, with the performance gap increasing as the number of days grows.The long-term comparison uses decreased un-service number and attributes the gap to better bike distribution and long-term reward maximization.
- Optimality: HRP performs close to 24-timeslot offline optimization, whereas HRA performs close to 4-timeslot optimization.The comparison averages results over 400 independent runs on a smaller 3 × 3-region area.
- Generalization: HRP achieves a 40%−80% un-service ratio decrement over 80% of tested areas, demonstrating transfer to unseen areas.The transfer experiment trains HRP and HRA in one area and tests them across other 3 × 3-region areas.
Conclusion
HRP combines divide-and-conquer temporal handling with a localized module for spatial dependencies, and experiments show it outperforms state-of-the-art methods on real Mobike data. Deployment in a real-world bike sharing system remains future work.
- Conclusion: HRP combines divide-and-conquer temporal handling with a localized module that captures spatial dependencies.The algorithm builds on deep reinforcement learning and is evaluated on a real Mobike dataset.
- Conclusion: HRP outperforms state-of-the-art methods in experiments based on a real Mobike dataset.
- Conclusion: Deploying HRP in a real-world bike sharing system remains an open extension.The authors also suggest updating the simulator with recent data and retraining offline to adapt across the year.