Source-linked AI summary
Dynamic vehicle redistribution and online price incentives in shared mobility systems
Julius Pfrommer, Joseph Warrington, Georg Schildbach, Manfred Morari
TL;DR
Public bicycle-sharing schemes face costly station imbalances requiring staffed bicycle redistribution. This paper combines model-based receding-horizon truck routing with dynamic customer incentives and evaluates the approach in a simulated London Cycle Hire scheme. The results indicate that price incentives are viable, including service levels above 87% on weekends using incentives alone, while trade-offs remain between payouts and truck deployment.
Problem
Public bicycle-sharing schemes often cannot cover operating costs, and staffed trucks are needed to prevent station imbalances that reduce customer service levels.
Method
The paper computes truck routes and customer price incentives with model-based receding-horizon optimization that accounts for expected future customer behavior.
Results
Price incentives are viable for repositioning bicycles, and incentives alone keep simulated weekend service levels above 87%.
Takeaways & Limitations
Repositioning can combine customer payments with operator truck effort to pursue a desired service level.
Takeaways & Limitations
A field trial is needed to improve the accuracy of the customer decision model underlying the price-control algorithm.
Abstract
from arXiv · showhide
This paper considers a combination of intelligent repositioning decisions and dynamic pricing for the improved operation of shared mobility systems. The approach is applied to London's Barclays Cycle Hire scheme, which the authors have simulated based on historical data. Using model-based predictive control principles, dynamically varying rewards are computed and offered to customers carrying out journeys. The aim is to encourage them to park bicycles at nearby under-used stations, thereby reducing the expected cost of repositioning them using dedicated staff. In parallel, the routes that repositioning staff should take are periodically recomputed using a model-based heuristic. It is shown that a trade-off between reward payouts to customers and the cost of hiring repositioning staff could be made, in order to minimize operating costs for a given desired service level.
1 Introduction
The paper addresses costly bicycle imbalances in public bicycle-sharing schemes by combining dynamic truck routing with customer price incentives. Both interventions are recomputed online using predictive models and evaluated in a historical-data simulation of London's Cycle Hire scheme.
- 1 Introduction: Staffed trucks are needed to rebalance station supply and demand, because otherwise stations may become full or empty and service rates may fall below acceptable levels.This redistribution creates an operating-cost trade-off against the desired service level.
- 1 Introduction: The paper combines dynamic multi-truck route planning with incentives that encourage users to change journey endpoints toward nearby stations with available space.The incentives are based on current and predicted system states and are separate from usual rental fees.
- 1 Introduction: The truck heuristic plans dynamic redistribution actions for multiple vehicles with the aim of enabling as many additional journeys as possible.Customers are assumed to accept or reject incentives according to the payment offered and the value of their time.
- 1 Introduction: Both truck routes and user payments are recomputed periodically over a finite receding horizon using predictions of near-future system evolution.The optimization uses updated system-state information and accounts for resources, payouts, and repositioning costs.
- 1 Introduction: The approaches are evaluated with a Monte Carlo model of London's Cycle Hire scheme constructed from detailed historical usage information.The study varies the number of repositioning trucks and the level of price incentives.
- 1 Introduction: Price incentives alone may improve service levels, while increasing customer payouts or repositioning trucks produces diminishing service-level returns; weekends permit higher service levels than weekdays.The reported findings concern the simulated London scheme.
2 System model
The system model represents London’s Barclays Cycle Hire scheme using historical station, ride, and fill-level data, with weekday/weekend demand patterns and station-level flows. It simulates customer departures, arrivals, travel, and incentive responses under explicit behavioral and modeling assumptions.
- Historical data: The model uses 1.42 million rides over 97 days, data for 354 active stations, and an initial nighttime fill level.The modeled system is estimated to contain 3708 bikes.
- Historical data: Historical journeys show regular daily flows, including morning commutes toward central London and late-afternoon rides toward outer districts.These commuting patterns produce two daily rental-activity spikes and differ substantially between weekdays and weekends.
- Demand model: Demand is indexed by weekday or weekend and 20-minute timeslices, with departure and arrival events recorded in station-to-station matrices.The matrices contain D_i,j(k,w) for departures and A_i,j(k,w) for arrivals.
- Demand model: Average historical event counts determine time-varying departure and arrival parameters, while destination probabilities follow historical relative frequencies.Customer departures are modeled as exponentially distributed with time-varying parameter M_i,j(t).
- Customer behavior: The simulation assumes empty-station customers leave without riding, fixed average travel times, and rerouting to neighboring stations when destinations are full.Customers do not wait or walk to another station after an empty departure station, and they do not revisit stations during overflow rerouting.
3 Utility of changes in station fill level
The paper defines station-fill utility as the expected change in customers served over a finite horizon after repositioning bikes. This utility supports truck-routing and incentive decisions while using tractable approximations and lookup tables.
- Model assumptions: The model assumes deterministic arrivals and departures represented by expected net change η_s(t), producing a coarser but tractable system model.The authors explicitly contrast this with probabilistic modeling.
- Utility definition: Utility measures the difference in customers expected to be served after adding or removing bikes at a station.It is evaluated over a finite look-ahead horizon using expected station-fill dynamics.
- Computation: The utility can be computed for each station using three calls to the repositioning-utility algorithm, then reused by routing and pricing procedures.Because online computation is costly, the implementation uses a lower-dimensional lookup-table parameterization.
- Utility structure: Capacity constraints create a plateau of constant maximum utility between the fill levels at which a station first becomes empty or full.Outside this interval, utility changes monotonically as additional bikes alter future service opportunities.
- Utility structure: For a station that becomes full, utility decreases with slope -1 when additional bikes cause expected returns to be rejected.The analogous empty-station case decreases utility when more bikes are removed.
4 A dynamic truck-routing algorithm
The dynamic routing method periodically replans truck movements during operation, selecting routes and bike loads that maximize utility gained per available truck time.
- Dynamic repositioning: Dynamic repositioning replans truck routes online so actions can respond to unexpected changes in system state.The paper considers this dynamic case because nighttime redistribution is restricted in key London areas.
- Route heuristic: A greedy heuristic builds promising route candidates using utility added per travel time, then optimizes bike quantities after each complete route is known.The route with the highest utility improvement is selected and extended to multiple trucks.
- Network model: Truck routing is modeled on a time-expanded network with vertices for station-time pairs and arcs for feasible truck journeys.Time is discretized into 5-minute intervals, with a 40-minute planning horizon and 30-minute implementation horizon.
- Objective: The dynamic objective is to invest limited truck operating hours where they provide the greatest utility improvement rather than attain a predefined system state.The single-truck procedure maximizes added utility per invested truck time.
5 Dynamic price incentives for users
The paper uses model predictive control to compute real-time payments that encourage customers to change destinations toward nearby stations, trading expected payouts against service-level improvement.
- Incentive scheme: The incentive scheme pays customers who change their journey endpoint to a nearby station in ways that improve overall service level.Changes in journey length may be inconvenient for customers.
- MPC controller: MPC optimizes price offers over a finite horizon using predicted customer responses, expected payouts, and expected service-level improvement.Only the first planned input is applied before the problem is solved again using a new state measurement.
- MPC controller: The controller treats station fill levels as system states and price incentives as control inputs, while enforcing bounds on both.The state evolves through customer behavior and manual truck repositioning.
- Behavior model: Customer responses are nonlinear and discontinuous in prices, so the model is linearized using samples of reactions to random incentive offers and least-squares fitting.The approximation uses a fixed set of nearby neighboring stations for each station.
- System dynamics: The station-fill dynamics combine expected net arrivals, incentive-driven customer changes, and truck-induced changes.The resulting equation determines how incentives enter the MPC system model.
6 Simulation
Monte Carlo simulations based on historical demand compare truck repositioning and customer incentives across weekday and weekend demand patterns. Both interventions improve service, but their marginal efficiency declines as service level rises.
- Simulation design: The simulations use simplified models for decisions but the full historical-data model for customer behavior, with separate weekday and weekend runs.Each run includes a 24-hour burn-in followed by three simulated days.
- Results: Adding trucks or increasing incentive payouts raises service level, while the marginal efficiency of both interventions declines at higher service levels.The trade-off is explored by varying truck numbers and the controller’s incentive-cost weight.
- Results: Commuter usage peaks account for most service shortfalls in the weekday and weekend simulations.Most unserved-customer events are concentrated in a small portion of the network or demand pattern.
- Failure modes: Empty-station events substantially outnumber full-station events, suggesting that adding bikes could improve service rate.Empty events involve failed rentals, whereas full events involve failed returns.
7 Conclusions
The paper combines intelligently routed repositioning trucks with customer redistribution incentives, computed through model-based receding-horizon optimization. Results indicate diminishing gains from additional trucks and incentive payouts, while incentives can reduce service shortfalls, especially with few trucks.
- Approach: The scheme combines repositioning trucks with customer incentives computed using model-based receding-horizon optimization that accounts for expected future customer behavior.Truck routes and price incentives are computed as part of the combined management approach.
- Results: Diminishing service-level gains were reported as the number of repositioning trucks and customer incentive payouts increased.
- Results: Customer payments reduced service shortfalls, particularly when few repositioning trucks were available.
- Results: For the London PBS, price incentives were viable when the commuting rush hour was less prominent.Price incentives alone kept weekend service above 87%, whereas they were insufficient to lift weekday service substantially.
- Limitations and future work: A field trial could improve the customer decision model by measuring price elasticities and the extent of irrational responses to prices.The paper also identifies deterministic arrivals and linearized customer reactions as simplifying assumptions that could be replaced by more detailed models.
- Limitations and future work: More detailed customer-response models may increase computational complexity enough to require a considerably shorter optimization prediction horizon.