PaperlayerView exact revision on arXiv

Source-linked AI summary

Approximate Dynamic Programming for Planning a Ride-Sharing System using Autonomous Fleets of Electric Vehicles

Lina Al-Kanj, Juliana Nascimento, Warren B. Powell

arXiv:1810.08124v2cs.AIcs.SYeess.SY

TL;DR

The paper addresses how to operate autonomous electric-vehicle fleets while coordinating rider assignment, charging, and other fleet decisions. It applies approximate dynamic programming and reports dispatch and pricing improvements, while identifying the absence of a formal convergence proof.

  • Problem

    The paper addresses how to operate autonomous electric-vehicle fleets while accounting for rider assignment and vehicle charging decisions.

    Source: §1 · p. 1, §3 · p. 7

  • Method

    An approximate dynamic programming framework coordinates car-rider allocation, relocation, parking, and recharging while accounting for future trip demand.

    Source: §1 · p. 2, §9 · p. 35

  • Results

    The proposed VFA policy outperforms a myopic policy by 17%, and real-world prices that increase with demand show a 13% increase in revenue.

    Source: §9 · p. 35

  • Takeaways & Limitations

    The paper concludes that its policy is asymptotically optimal for modeling a single car.

    Source: §5.7 · p. 24

    The authors report no formal convergence proof, and optimal weights for approximating value functions remain future work.

    Source: §5.7 · p. 23

Abstract

from arXiv · show

Within a decade, almost every major auto company, along with fleet operators such as Uber, have announced plans to put autonomous vehicles on the road. At the same time, electric vehicles are quickly emerging as a next-generation technology that is cost effective, in addition to offering the benefits of reducing the carbon footprint. The combination of a centrally managed fleet of driverless vehicles, along with the operating characteristics of electric vehicles, is creating a transformative new technology that offers significant cost savings with high service levels. This problem involves a dispatch problem for assigning riders to cars, a surge pricing problem for deciding on the price per trip and a planning problem for deciding on the fleet size. We use approximate dynamic programming to develop high-quality operational dispatch strategies to determine which car is best for a particular trip, when a car should be recharged, and when it should be re-positioned to a different zone which offers a higher density of trips. We prove that the value functions are monotone in the battery and time dimensions and use hierarchical aggregation to get better estimates of the value functions with a small number of observations. Then, surge pricing is discussed using an adaptive learning approach to decide on the price for each trip. Finally, we discuss the fleet size problem which depends on the previous two problems.

1. Introduction

The paper models autonomous electric-vehicle fleet operations as coordinated decisions about rider assignment, recharging, repositioning, and parking under uncertain future demand. It uses approximate dynamic programming, monotonicity properties, and hierarchical aggregation, and also considers adaptive surge pricing and fleet sizing.

1. Introduction

  • The model coordinates car-rider allocation, relocation, parking, and recharging while accounting for future trip demand.It optimizes across the fleet both at a point in time and over time.Source: §1 · p. 2
  • The dispatch problem jointly manages assignments, charging, repositioning, and parking to meet trips’ spatial and temporal patterns.These decisions also manage battery use and available vehicle capacity.Source: §1 · p. 2
  • Approximate dynamic programming approximates the operational policy; monotone value functions and hierarchical aggregation improve convergence and estimates from few observations.The value functions are monotone in time and battery charge level.Source: §1 · p. 2
  • The surge-pricing problem uses adaptive learning to set prices in real time and may smooth daily demand peaks.The introduction describes smoothing peaks as the problem’s potential.Source: §1 · p. 3
  • As fleet size increases, the required battery size of the cars decreases.The fleet-size analysis uses the dispatch and surge-pricing results to guide fleet design.Source: §1 · p. 3
  • The paper introduces a scalable simulator for New Jersey that uses real trip data and can vary fleet size, area, trip distribution, and time horizon.The simulator is listed as a separate contribution.Source: §1 · p. 3

2. Literature Review of Autonomous, Electric Vehicles

The review outlines anticipated benefits of autonomous and electric vehicles and the economic case for autonomous EV fleets, including higher utilization and lower costs. It also surveys prior ride-sharing dispatch studies of conventional and autonomous fleets, noting that charging and refueling logistics are largely absent from earlier shared-vehicle studies.

2.1. Autonomous Vehicles

  • Autonomous vehicles sense their surroundings using radar, GPS, odometry, and computer vision (Sivaraman and Trivedi (2013)); anticipated benefits include fewer crashes and greater commuter flexibility.The review also identifies reduced traffic as a potential benefit.Source: §2.1 · p. 3

2.2. Electric Vehicles

  • EVs offer zero tailpipe emissions, with a stated 30% CO2 reduction under the U.S. energy mix (Faiz et al. (1996)), and about three times the energy efficiency of combustion vehicles (Guo et al. (2016)).Source: §2.2 · p. 4
  • Electric motors are mechanically simple and can reach 90% energy-conversion efficiency; the Chevy Volt estimate is under 2 cents per mile on electricity versus 12 cents on gasoline at $3.60 per gallon.The operating-cost comparison is attributed to Valdes-Dapena (2008).Source: §2.2 · p. 4
  • When plugged in, EVs could feed battery power into the grid during peak-use periods, potentially reducing electricity demand (Sortomme and El-Sharkawi (2012), Liu et al. (2013)).Source: §2.2 · p. 5

2.3. Autonomous Fleets of Electric Vehicles

  • Driverless cabs could raise vehicle utilization from 5% to as much as 30% and remove the driver, described as the highest ride-fare cost; sharing also lowers vehicle and operating costs (Litman (2014), Spinoulas et al. (2015)).Source: §2.3 · p. 5
  • Schoettle and Sivak (2015) report that travel per vehicle can increase by up to 75%.Source: §2.3 · p. 6

2.4. Ride Sharing Systems

  • Lin et al. (2012) use simulated annealing for static taxi ride-sharing with multiple cars and time windows, while Stiglic (2017) study itinerary-based rider matching.Stiglic uses a mixed-integer linear program for one driver and multiple riders, and a heuristic for multiple drivers.Source: §2.4 · p. 6
  • Braverman et al. (2016) model empty-car routing, while Banerjee et al. (2018) optimize dispatch assignments to minimize dropped demand.Banerjee et al. assume vehicle assignment is the platform’s exclusive control lever and measure performance by the steady-state proportion of dropped demand.Source: §2.4 · p. 6
  • Charging/refueling was missing from all prior studies mentioned except Fagnant and Kockelman (2014), who assumed fixed-lag refueling anywhere in the grid, and Chen et al. (2016), who heuristically located charging stations.Source: §2.4 · p. 7

3. Problem Description

The section frames fleet operation as three linked decisions: dispatching cars to riders, setting prices to balance supply and demand, and choosing fleet size. Dispatch and pricing account for time-varying trip patterns and inform fleet planning.

3. Problem Description

  • Dispatch chooses a car for each rider while managing charging duration, peak-period availability, and repositioning toward incoming trips.The assignment should account for each car’s charge and trip destination.Source: §3 · p. 7
  • The model jointly considers car assignment, recharging, and empty repositioning, using approximate dynamic programming to account for decisions’ future effects.The policy uses available travel requests, destinations, battery charges, and destination value.Source: §3 · p. 7
  • Surge pricing aims to balance car supply and rider demand, with market response learned dynamically by location and time.The section describes this as a way to maintain a good balance of cars and riders.Source: §3 · p. 8
  • Fleet sizing seeks enough vehicles to cover a target share of trips across a day with morning and afternoon demand peaks.The fleet-size analysis uses marginal car values from dispatch and surge pricing and aims to maximize fleet revenue.Source: §3 · pp. 7–8

4. Problem Formulation

The fleet-management problem is formulated as a discrete-time, discrete-state Markov decision process, specifying the state, decisions, incoming information, transitions, objective, and assumptions. It models vehicle decisions through state transitions and per-action contributions, with a policy selected to maximize expected cumulative contributions.

Problem formulation

  • The model treats cars as resources in a dynamic resource-management framework and represents fleet management as a discrete-time, discrete-state Markov decision process.The model is organized around state variables, decision variables, exogenous information, a transition function, and an objective function.Source: §4 · p. 8

The State Variables

  • The system state combines car and customer physical conditions with a belief state for unknown parameters such as prices; with known fixed prices, only the physical state is needed.Car attributes include availability or arrival time, location, and battery level; trips are represented by time, origin, and destination, and the physical location is divided into 0.5-mile zones.Source: The State Variables · p. 8

The Decision Variables

  • For each available car, the model permits assigning a reachable trip, moving empty to a neighboring zone, recharging in its current zone, or holding there.It assumes a recharging station in every zone, while optimal station placement is left for future work; cars already busy on trips or recharging cannot be reassigned.Source: The State Variables · p. 9, The Decision Variables · p. 9
  • Decision assignments must satisfy car and trip flow conservation, preventing allocation of more cars of a type or more cars to a trip type than are available.The feasible decision set depends on the state and information available at time t, and a decision function selects an allocation from that set.Source: The Decision Variables · p. 10

The Exogenous Information

  • Exogenous information arriving between decision epochs includes changes in car attributes and newly known trip demands.Car changes can reflect service entry or exit, travel delays, or equipment failure; trip requests arrive continuously and are collected between epochs for assignment at the next decision time.Source: The State Variables · p. 9, The Exogenous Information · p. 10

The Transition Function

  • The transition function deterministically maps each chosen action to expected post-decision car attributes before new information arrives, and the next pre-decision state incorporates cars that become available.The formulation uses a post-decision resource vector, which the paper says provides significant computational advantages; it assumes demands are either served or lost, with no backlog.Source: The Transition Function · pp. 11–12

4. Problem Formulation

  • State evolution comprises two consecutive transitions: pre-decision to post-decision, then post-decision to the next pre-decision state.Source: The Transition Function · p. 12
  • A trip earns revenue based on its price per mile and distance, recharging incurs base and energy costs, and staying or moving empty earns zero.The car’s attribute changes according to the selected decision.Source: The Objective Function · p. 12
  • Under the linear-contribution assumption, the optimal policy maximizes expected total contributions across time periods.Source: The Objective Function · p. 12

5. Designing Policies

This section develops approximate dynamic programming policies for fleet decisions, including myopic and lookahead approaches with value-function updates, and uses hierarchical aggregation and monotonicity to estimate value functions from sparse observations. It also examines convergence and limits, noting asymptotic optimality for a single car but not establishing it for larger fleets.

5.1. A Parameterized Myopic Policy

  • The myopic policy combines a car-to-rider assignment linear program with a tuned recharge-threshold rule, but cannot anticipate peak periods.For example, a car at 40% charge during an off-peak period may not reach its threshold until an afternoon peak.Source: §5.1 · pp. 13–14

5.2. Policies Based on Value Function Approximations

  • A lookahead policy uses a post-decision-state value approximation to capture downstream effects while avoiding explicit expectation calculations.The resulting approximation must scale to high-dimensional decision vectors.Source: §5.2 · pp. 14–15
  • The Bellman solution faces state-, outcome-, and action-space dimensionality curses, making traditional discrete dynamic programming intractable at the paper’s network scale.The stated configuration has 22,000 locations, 20 battery levels, and 1,500 cars.Source: §5.2 · p. 14

5.3. An Approximate Dynamic Programming Algorithm

  • The ADP algorithm combines mathematical programming with machine learning and uses sampled paths to update approximations of post-decision-state values.The paper describes its approach as approximate value iteration.Source: §5.3 · p. 15
  • The value approximation is linear in the resource vector and estimates a car’s marginal contribution from its zone, battery level, and remaining horizon.Travel time and the car’s resulting attributes determine its new availability state.Source: §5.3 · p. 16
  • Unlike the myopic policy’s threshold constraint, the ADP policy recharges a car when the optimization finds that recharging’s value exceeds other decisions.The value of a higher battery level motivates recharging.Source: §5.3 · p. 16

5.4. Value Function Updates

  • The value-function update uses classical approximate value iteration, adapted to estimate the marginal value of being in a state.Source: §5.4 · p. 16
  • The fleet-management ADP algorithm makes a single forward pass through a simulated trajectory, choosing trips, repositioning, recharging, or staying using current value-function estimates.Source: §5.4 · pp. 17–18
  • Because real-data trajectories are sparse, only some car attributes receive marginal-value updates, although estimates are needed for zones where cars might be sent.Source: §5.4 · p. 18

5.5. Hierarchical Aggregation for Approximating Value Functions

  • Hierarchical aggregation improves value-function estimates as observations accumulate and is asymptotically unbiased if all zones are sampled infinitely often.Source: §5.5 · p. 18
  • Spatial aggregation shares an observed value across nearby zones at multiple levels, exploiting the assumption that neighboring zones have similar time-and-battery value functions.Source: §5.5 · p. 19
  • Estimates across aggregation levels are combined with weights inversely related to their estimated mean squared deviations, reflecting variance and bias.Source: §5.5 · p. 20
  • Hierarchical aggregation estimates values for visited and unvisited attributes by combining information across aggregation levels.The discussion says it can improve estimates with few observations, while enough observations may make aggregation unnecessary; the authors report no formal convergence proof for this approach in value-function approximation.Source: §5.5 · p. 21, §5.7 · p. 23

5.7. Discussion on Convergence

  • Classical exact dynamic programming is computationally intractable, and basic lookup-table approximations performed poorly, motivating scalable approximations.The authors identify hierarchical aggregation and monotonicity as strategies for learning value functions with fewer observations and improving convergence.Source: §5.7 · p. 23

5.6. Monotonicity of the Value Functions

  • Value functions increase with battery charge and decrease with time, and exploiting these monotonicities accelerates convergence in fleet management.The authors describe this as the first use of ADP with monotone value functions for fleet management and use monotonicity-preserving projections to correct violations.Source: §5.6 · pp. 21–22, §5.7 · p. 23

5.7. Discussion on Convergence

  • The policy is asymptotically optimal for a single car, but this result does not extend to larger fleets; the proposed scalable policy assumes value is linear in the number of cars.The authors note that large fleets may have diminishing marginal value as not all cars operate continuously, and that piecewise-linear alternatives introduce computational challenges.Source: §5.7 · p. 24

6. The Surge Pricing Problem

The section frames surge pricing as a way to balance cars and riders while maximizing revenue, modeling price choice through learned operator and rider acceptance responses. It then describes adaptively using bootstrap aggregation to resample pricing-model candidates and focus probability on more promising values.

6. The Surge Pricing Problem

  • Surge pricing balances car supply and rider demand by offering prices that maximize revenue while remaining acceptable to both riders and the operator.The operator must learn both rider acceptance and whether it will allocate a car at the offered price.Source: §6 · p. 24

6.1. The Mathematical Model

  • A Bayesian learner updates beliefs over zone-specific logistic response curves and chooses the price maximizing expected revenue from operator and rider acceptance.After observing responses, it updates the belief state for subsequent price decisions.Source: §6.1 · pp. 25–27

6.2. Bootstrap Aggregation

  • Treating one randomly drawn logistic curve as the true response is described as naive, though it may approximate reality when the parameter is one- or two-dimensional.The true parameter is unknown and must be estimated from gathered information.Source: §6.2 · p. 27
  • Bootstrap aggregation repeatedly resamples the candidate set to adaptively identify more promising pricing values.The method addresses the possibility that probability mass concentrates on only a small subset of the original candidates.Source: §6.2 · p. 27
  • For each zone, K training sets are sampled uniformly with replacement, and K logistic-regression models are fit; unlike traditional bagging, their outputs are not averaged.Instead, equal probability serves as the initial prior over the models, which remain candidates until the next resampling step; the passage identifies bagging as Breiman (1996).Source: §6.2 · p. 27
  • At the end of each ADP iteration’s time horizon, the method resamples candidates and uses observed data to calculate each model’s likelihood and update posterior probabilities.The passage notes that resampling criteria can vary, but this work resamples at the end of the iteration horizon.Source: §6.2 · p. 28

7. The Fleet Size Problem

The fleet-size problem defines fleet profit from daily revenue and vehicle costs, then uses dispatch and surge-pricing results to guide fleet design. The analysis assumes identical battery capacity across cars and identifies capacity-mix optimization as future work.

7. The Fleet Size Problem

  • Fleet profit is daily revenue over the operating horizon minus per-car purchase, maintenance, insurance, and battery costs.Battery cost increases nonlinearly with battery size.Source: §7 · pp. 28–29
  • Finding the optimal fleet size uses results from the dispatch and surge-pricing problems to guide fleet design.Source: §7 · p. 29
  • The analysis assumes all cars have the same battery capacity; identifying an optimal mix of capacities is left for future research.Source: §7 · p. 29

8. Numerical Results

This section uses simulation to examine the myopic and VFA policies, repositioning and recharging, hierarchical aggregation, surge pricing, and fleet-size and battery-capacity tradeoffs. It also reports how prices vary with demand and available cars, and the fleet sizes and battery range observed for the considered costs and trip data.

8.1. Data and Model Parameters

  • The simulation uses 32,874 New Jersey trips in 15-minute increments and initially tests a 1,500-car fleet that provides 95% trip coverage.Trips are drawn from real trip data.Source: §8.1 · p. 29

8.2. Parameterized Myopic Policy

  • The policy generated $645,584 in revenue, averaging $430 per car; fleet battery levels reached their lowest just before the afternoon peak, forcing recharging, and cars sat in isolated places during peak period.Source: §8.2 · pp. 30–31

8.3. VFA Policy

  • 95% average trip coverage and $505 revenue per car—17.32% higher than with the myopic policy—are reported for VFA with hierarchical aggregation.Figure 11 presents the policy's performance results.Source: §8.3 · pp. 32–33, Figure 11 · p. 33
  • VFA recharges before peak demand, repositions during off-peak periods toward zones with incoming trips, and keeps the fleet fully engaged during peaks by accounting for future demand.The policy also minimizes unnecessary energy in the fleet when no trips are expected near day's end.Source: §8.3 · p. 33

8.4. Surge Pricing

  • Surge pricing increased revenue by 13% over the $1-per-mile baseline, with simulated prices ranging from $0.5 to $2 depending on acceptance-model input ranges and the true response curve.Source: §8.4 · p. 33

8.5. Economics of the Fleet and Battery Sizes

  • The optimal fleet size is 1,900 cars with a 150-mile battery range; good-performing fleets range from 1,500 to 1,900 cars depending on battery range.These results apply to the considered operating costs and trip data set.Source: Figure 13 · p. 34, §8.5 · p. 35

8.4. Surge Pricing

  • Surge pricing reduces trip prices off-peak when available cars outnumber requests and raises prices at peak when demand exceeds available cars, reflecting rider behavior.Riders accept higher prices during peak periods.Source: §8.4 · p. 34

8.5. Economics of the Fleet and Battery Sizes

  • As fleet size increases, the profit-maximizing battery size decreases; medium-sized batteries with 150–250-mile ranges are needed to operate the fleet.Very small fleets or batteries leave some trips uncovered, while large fleets are unprofitable because many high-cost cars are barely needed.Source: §8.5 · p. 35

9. Conclusion

The paper models dispatch, surge pricing, and fleet sizing for autonomous electric-vehicle ride sharing. Its conclusion reports gains for dispatch and pricing, and a decrease in required battery size as fleet size increases.

9. Conclusion

  • Approximate dynamic programming, monotone value functions, and hierarchical aggregation support an accurate simulation of a large-scale fleet.The paper models an autonomous electric-vehicle ride-sharing system.Source: §9 · p. 35
  • The VFA dispatch policy outperforms a myopic policy by 17%.The conclusion presents this as a performance result for the proposed dispatch policy.Source: §9 · p. 35
  • Surge pricing increases revenue by 13% and raises prices with demand, matching the reported real-world pattern.The adaptive learning framework produces the demand-linked price behavior.Source: §9 · p. 35
  • As fleet size increases, the required battery size decreases.The conclusion reports this relationship without specifying its magnitude.Source: §9 · p. 35
  • The logic handles uncertainty including random customer demands, supporting the aim of quantifying autonomous-fleet economics.The conclusion identifies other operational questions for future work, including parking-lot, charging-station, and battery-size distributions.Source: §9 · p. 35

Appendix A: Proof of Proposition 1

The proof establishes that the value function is nondecreasing in battery level for both pre-decision and post-decision states. It uses backward induction and the expansion of feasible decisions with higher battery levels.

Appendix A: Proof of Proposition 1

  • The proof establishes battery-level monotonicity for pre-decision and post-decision value functions.It treats the post-decision value first, then establishes the property for the pre-decision value.Source: Appendix A · pp. 35–36
  • Backward induction carries the post-decision monotonicity property through the conditional expectation and into the pre-decision value function.The proof invokes the proposition’s assumptions when moving between the two value functions.Source: Appendix A · p. 36
  • A higher battery level permits longer trips and yields a larger set of feasible decisions than a lower level.The proof uses this feasible-set inclusion to support monotonicity.Source: Appendix A · p. 36

Appendix B: Proof of Proposition 2

The proof defines a car’s marginal value as its revenue over the remaining horizon from a given zone and battery level. It shows that an earlier operating start can yield greater value under the same trip-request distribution when recharging is disallowed.

Appendix B: Proof of Proposition 2

  • A car’s marginal value is its revenue from operating in a zone with a given battery level through the horizon.The definition considers operation without recharging.Source: Appendix B · p. 37
  • With recharging disallowed, actions have nonnegative rewards because recharging is the only action that incurs a cost.This nonnegative-reward condition is used in the time comparison.Source: Appendix B · p. 37
  • Under the same trip-request distribution, starting earlier in the same zone with the same battery level can yield more revenue by allowing longer operation.The proof attributes the additional return to the opportunity to collect more trips.Source: Appendix B · p. 37
Loading 1810.08124v2…