pith. sign in

arxiv: 1907.01071 · v1 · pith:DXPFJMYRnew · submitted 2019-07-01 · 📡 eess.SY · cs.MA· cs.SY

Online Charge Scheduling for Electric Vehicles in Autonomous Mobility on Demand Fleets

Nathaniel Tucker , Berkay Turan , Mahnoosh Alizadeh This is my paper

Pith reviewed 2026-05-25 11:26 UTC · model grok-4.3

classification 📡 eess.SY cs.MAcs.SY
keywords electric vehiclesautonomous mobility on demandonline schedulingprimal-dual algorithmcompetitive ratiocharge schedulingrebalancing
0
0 comments X

The pith

An online primal-dual heuristic schedules charging and rebalancing for autonomous electric vehicle fleets and admits a competitive ratio to the offline optimum.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies charge scheduling for fleets of autonomous electric vehicles that serve ride requests and then become available for the next assignment in an online sequence throughout the day. Because future ride requests remain unknown, no offline plan can be computed in advance. The authors develop a welfare-maximizing heuristic that uses primal-dual updates to decide when and where each vehicle should charge and where it should be sent for the next pickup, while enforcing capacity limits at charging stations and pickup points. They establish a competitive-ratio guarantee that bounds the online welfare relative to the best offline schedule that could have been chosen with full knowledge of the day. Numerical experiments illustrate how the method performs on realistic demand patterns.

Core claim

The central claim is that a primal-dual online algorithm can allocate limited charging resources and rebalance autonomous electric vehicles as each vehicle enters its between-ride state, avoiding congestion at facilities while achieving a competitive ratio against the clairvoyant offline solution.

What carries the argument

The primal-dual online welfare-maximization heuristic that incrementally updates dual prices and primal allocations as vehicle availability information arrives.

If this is right

  • The online method can be deployed without advance knowledge of daily ride demand.
  • Charging and rebalancing decisions remain feasible at every step and respect station capacities.
  • Performance is guaranteed to lie within a fixed factor of the best possible offline schedule.
  • Numerical tests confirm that the heuristic produces high welfare on realistic instances.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same online framework could be adapted to other sequentially revealed resources such as parking spots or energy storage in ride-sharing systems.
  • If the competitive ratio is shown to be tight on worst-case sequences, designers would know the method is already near-optimal in the adversarial setting.
  • Coupling the heuristic with short-term demand forecasts could tighten practical performance while preserving the worst-case guarantee.

Load-bearing premise

Vehicle availability information arrives in an online sequence that permits the primal-dual updates to produce feasible allocations without future knowledge and still satisfy the competitive-ratio analysis.

What would settle it

Compare the total welfare obtained by the online heuristic against the welfare of the optimal offline schedule on the identical sequence of ride requests; if the ratio falls below the claimed bound on any instance, the guarantee does not hold.

Figures

Figures reproduced from arXiv: 1907.01071 by Berkay Turan, Mahnoosh Alizadeh, Nathaniel Tucker.

Figure 1
Figure 1. Figure 1: Example between-ride schedules for 3 vehicles. [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 3
Figure 3. Figure 3: Fleet dispatcher welfare across 100 days. [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
read the original abstract

In this paper, we study an online charge scheduling strategy for fleets of autonomous-mobility-on-demand electric vechicles (AMoD EVs). We consider the case where vehicles complete trips and then enter a between-ride state throughout the day, with their information becoming available to the fleet operator in an online fashion. In the between-ride state, the vehicles must be scheduled for charging and then routed to their next passenger pick-up locations. Additionally, due to the unknown daily sequences of ride requests, the problem cannot be solved by any offline approach. As such, we study an online welfare maximization heuristic based on primal-dual methods that allocates limited fleet charging resources and rebalances the vehicles while avoiding congestion at charging facilities and pick-up locations. We discuss a competitive ratio result comparing the performance of our online solution to the clairvoyant offline solution and provide numerical results highlighting the performance of our heuristic.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript proposes an online welfare-maximization heuristic, based on primal-dual methods, for charge scheduling and rebalancing of autonomous mobility-on-demand electric vehicle (AMoD EV) fleets. Vehicles arrive online in a between-ride state; the algorithm allocates scarce charging resources and routes vehicles to pick-up locations while avoiding congestion at both charging facilities and pick-up points. The central theoretical claim is a competitive-ratio guarantee relative to a clairvoyant offline optimum; numerical experiments are also presented to illustrate practical performance.

Significance. If the competitive-ratio result is rigorously established and the numerical study is reproducible, the work would supply a theoretically grounded online algorithm for a practically relevant resource-allocation problem at the intersection of transportation and energy systems. The primal-dual framework is a standard tool for online welfare maximization, and its application to congestion-aware EV rebalancing is a natural extension that could inform fleet operators.

minor comments (2)
  1. [Abstract] Abstract: 'vechicles' is a typographical error and should read 'vehicles'.
  2. [Abstract] The abstract states that a competitive ratio is 'discussed' but does not state the ratio itself or the assumptions under which it holds. A reader cannot assess the strength of the guarantee without the explicit statement.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for reviewing our manuscript on online charge scheduling for AMoD EV fleets. The report provides a concise summary of the contribution but does not enumerate any specific major comments. We therefore have no individual points to address in the responses section below. We remain available to supply further details on the competitive-ratio proof or the numerical experiments if the editor or referee requests them.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper describes an online primal-dual welfare maximization heuristic for EV charge scheduling and rebalancing, with a competitive ratio result framed as a comparison to the clairvoyant offline optimum. This is a standard external benchmark in online algorithm analysis and does not reduce to any self-definitional, fitted-input, or self-citation load-bearing step within the given claims. No equations or derivations are provided that equate a prediction to its own inputs by construction, and the setup relies on independent problem assumptions about online arrivals rather than circular justification.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract provides no information on free parameters, axioms, or invented entities; all such elements remain unidentified.

pith-pipeline@v0.9.0 · 5692 in / 1043 out tokens · 28873 ms · 2026-05-25T11:26:21.479702+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages

  1. [1]

    Autonomous mobility-on-demand systems for future ur- ban mobility,

    M. Pavone, “Autonomous mobility-on-demand systems for future ur- ban mobility,” pp. 399–416, 2015, Publisher: Springer Berlin Heidel- berg, doi=10.1007/978-3-662-45854-9 19

    work page doi:10.1007/978-3-662-45854-9 2015

  2. [2]

    Models, algorithms, and evaluation for autonomous mobility-on-demand systems,

    R. Zhang, K. Spieser, E. Frazzoli, and M. Pavone, “Models, algorithms, and evaluation for autonomous mobility-on-demand systems,” in 2015 American Control Conference (ACC) , July 2015, pp. 2573–2587

    work page 2015

  3. [3]

    Automated vehicles, on-demand mobility, and environmental impacts,

    J. B. Greenblatt and S. Shaheen, “Automated vehicles, on-demand mobility, and environmental impacts,” Current Sustainable/Renewable Energy Reports, vol. 2, no. 3, pp. 74–81, Sep 2015

    work page 2015

  4. [4]

    Optimization for dynamic ride-sharing: A review,

    N. Agatz, A. Erera, M. Savelsbergh, and X. Wang, “Optimization for dynamic ride-sharing: A review,” European Journal of Operational Research, vol. 223, no. 2, pp. 295 – 303, 2012

    work page 2012

  5. [5]

    A matching algorithm for dynamic ridesharing,

    M. Schreieck et al., “A matching algorithm for dynamic ridesharing,” Transportation Research Procedia, vol. 19, pp. 272 – 285, 2016

    work page 2016

  6. [6]

    A mechanism for dynamic ride sharing based on parallel auctions,

    A. Kleiner, B. Nebel, and V . A. Ziparo, “A mechanism for dynamic ride sharing based on parallel auctions,” in Proceedings of the 22 International Joint Conference on Artificial Intelligence, ser. IJCAI’11, 2011, pp. 266–272

    work page 2011

  7. [7]

    On-demand high-capacity ride-sharing via dy- namic trip-vehicle assignment,

    Alonso-Mora et al. , “On-demand high-capacity ride-sharing via dy- namic trip-vehicle assignment,” Proceedings of the National Academy of Sciences, vol. 114, no. 3, pp. 462–467, 2017

    work page 2017

  8. [8]

    A decomposition algorithm to solve the multi-hop peer-to-peer ride-matching problem,

    N. Masoud and R. Jayakrishnan, “A decomposition algorithm to solve the multi-hop peer-to-peer ride-matching problem,” Transportation Research Part B: Methodological , vol. 99, pp. 1 – 29, 2017

    work page 2017

  9. [9]

    Autonomous mobility and energy service management in future smart cities: An overview,

    X. Tan and A. Leon-Garcia, “Autonomous mobility and energy service management in future smart cities: An overview,” 2018 International Conference on Universal Village , Oct 2018

    work page 2018

  10. [10]

    Model predictive control of autonomous mobility-on-demand systems,

    R. Zhang, F. Rossi, and M. Pavone, “Model predictive control of autonomous mobility-on-demand systems,” in 2016 IEEE International Conference on Robotics and Automation (ICRA) , May 2016

    work page 2016

  11. [11]

    Operations of a shared, autonomous, electric vehicle fleet: Implications of vehicle and charging infrastructure decisions,

    T. D. Chen, K. M. Kockelman, and J. P. Hanna, “Operations of a shared, autonomous, electric vehicle fleet: Implications of vehicle and charging infrastructure decisions,” Transportation Research Part A: Policy and Practice, vol. 94, pp. 243 – 254, 2016

    work page 2016

  12. [12]

    Management of a shared au- tonomous electric vehicle fleet: Implications of pricing schemes,

    T. D. Chen and K. M. Kockelman, “Management of a shared au- tonomous electric vehicle fleet: Implications of pricing schemes,” Transportation Research Record, vol. 2572, no. 1, pp. 37–46, 2016

    work page 2016

  13. [13]

    A congestion-aware routing scheme for autonomous mobility-on-demand systems,

    M. Salazar, M. Tsao, I. Aguiar, M. Schiffer, and M. Pavone, “A congestion-aware routing scheme for autonomous mobility-on-demand systems,” in European Control Conference, 2019

    work page 2019

  14. [14]

    Model predictive control of ride-sharing autonomous mobility-on-demand systems

    M. Tsao, D. Milojevic, C. Ruch, M. Salazar Villalon, E. Frazzoli, and M. Pavone, “Model predictive control of ride-sharing autonomous mobility-on-demand systems.” IEEE, 2019-05, 2019 IEEE Interna- tional Conference on Robotics and Automation (ICRA); Conference Location: Montreal, Canada; Conference Date: May 20-24, 2019

    work page 2019

  15. [15]

    On the interac- tion between autonomous mobility-on-demand systems and the power network: models and coordination algorithms,

    F. Rossi, R. Iglesias, M. Alizadeh, and M. Pavone, “On the interac- tion between autonomous mobility-on-demand systems and the power network: models and coordination algorithms,” Robotics: Science and Systems XIV, Jun 2018

    work page 2018

  16. [16]

    On the interaction between autonomous mobility-on-demand and public transportation systems,

    M. Salazar, F. Rossi, M. Schiffer, C. H. Onder, and M. Pavone, “On the interaction between autonomous mobility-on-demand and public transportation systems,” in 2018 21st International Conference on Intelligent Transportation Systems (ITSC) , Nov 2018, pp. 2262–2269

    work page 2018

  17. [17]

    Distribution grid impacts of smart electric vehicle charging from different perspectives,

    E. Veldman and R. A. Verzijlbergh, “Distribution grid impacts of smart electric vehicle charging from different perspectives,” IEEE Transactions on Smart Grid , vol. 6, no. 1, pp. 333–342, Jan 2015

    work page 2015

  18. [18]

    A survey on the electrifica- tion of transportation in a smart grid environment,

    W. Su, H. Eichi, W. Zeng, and M. Chow, “A survey on the electrifica- tion of transportation in a smart grid environment,” IEEE Transactions on Industrial Informatics , vol. 8, no. 1, pp. 1–10, Feb 2012

    work page 2012

  19. [19]

    A review of charge scheduling of electric vehicles in smart grid,

    J. C. Mukherjee and A. Gupta, “A review of charge scheduling of electric vehicles in smart grid,” IEEE Systems Journal , vol. 9, no. 4, pp. 1541–1553, Dec 2015

    work page 2015

  20. [20]

    Optimal planning of workplace electric vehicle charging insfrastructure with smart charging opportunities,

    B. Ferguson, V . Nagaraj, E.C. Kara, and M. Alizadeh, “Optimal planning of workplace electric vehicle charging insfrastructure with smart charging opportunities,” ITSC Hawaii 2018

    work page 2018

  21. [21]

    An online mechanism for multi-unit demand and its application to plug-in hybrid electric vehicle charging,

    V . Robu, E. H. Gerding, S. Stein, D. C. Parkes, A. Rogers, and N. R. Jennings, “An online mechanism for multi-unit demand and its application to plug-in hybrid electric vehicle charging,” J. Artif. Int. Res., vol. 48, no. 1, pp. 175–230, Oct. 2013

    work page 2013

  22. [22]

    Auc2charge: An online auction framework for electric vehicle park- and-charge,

    Q. Xiang, F. Kong, X. Liu, X. Chen, L. Kong, and L. Rao, “Auc2charge: An online auction framework for electric vehicle park- and-charge,” in Proceedings of the 2015 ACM Sixth International Conference on Future Energy Systems , ser. e-Energy ’15

    work page 2015

  23. [23]

    Deadline differentiated pricing of deferrable electric power service,

    E. Bitar and S. Low, “Deadline differentiated pricing of deferrable electric power service,” in IEEE 51st CDC , 2012, pp. 4991–4997

    work page 2012

  24. [24]

    Control of charging of electric vehicles through menu-based pricing,

    A. Ghosh and V . Aggarwal, “Control of charging of electric vehicles through menu-based pricing,” IEEE Transactions on Smart Grid, vol. 9, no. 6, pp. 5918–5929, Nov 2018

    work page 2018

  25. [25]

    Optimal planning of pev charging station with single output multiple cables charging spots,

    H. Zhang, Z. Hu, Z. Xu, and Y . Song, “Optimal planning of pev charging station with single output multiple cables charging spots,” IEEE Transactions on Smart Grid , vol. 8, Sept 2017

    work page 2017

  26. [26]

    Online pricing mechanisms for electric vehicle management at workplace charging facilities,

    N. Tucker and M. Alizadeh, “Online pricing mechanisms for electric vehicle management at workplace charging facilities,” Allerton Con- ference on Communication, Control, and Computing , 2018

    work page 2018

  27. [27]

    An online pricing mecha- nism for electric vehicle parking assignment and charge scheduling,

    N. Tucker, B. Ferguson, and M. Alizadeh, “An online pricing mecha- nism for electric vehicle parking assignment and charge scheduling,” American Control Conference, 2019, To Appear

    work page 2019

  28. [28]

    An online admission control mechanism for electric vehicles at public parking infrastructures,

    N. Tucker and M. Alizadeh, “An online admission control mechanism for electric vehicles at public parking infrastructures,” IEEE Transac- tions on Smart Grid , pp. 1–1, 2019

    work page 2019

  29. [29]

    Primal dual gives almost optimal energy efficient online algorithms,

    N. R. Devanur and Z. Huang, “Primal dual gives almost optimal energy efficient online algorithms,” in Proceedings of the 25th ACM-SIAM SODA, ser. SODA ’14, Philadelphia, PA, USA, 2014

    work page 2014

  30. [30]

    Online auctions in iaas clouds: Welfare and profit maximization with server costs,

    X. Zhang, Z. Huang, C. Wu, Z. Li, and F. C. M. Lau, “Online auctions in iaas clouds: Welfare and profit maximization with server costs,” IEEE/ACM Transactions on Networking , vol. 25, no. 2, April 2017

    work page 2017

  31. [31]

    California ISO OASIS Locational Marginal Prices (LMP), [Online],

    “California ISO OASIS Locational Marginal Prices (LMP), [Online],” http://oasis.caiso.com/mrioasis/logon.do

    work page

  32. [32]

    California ISO Supply and Renewables, [Online],

    “California ISO Supply and Renewables, [Online],” http://www.caiso. com/TodaysOutlook/Pages/supply.aspx

    work page

  33. [33]

    San Jose Heatmap, SherpaShare Rideshare Analysis, [Online],

    “San Jose Heatmap, SherpaShare Rideshare Analysis, [Online],” https: //www.sherpashare.com/heatmap. APPENDIX Definition 1. (From [30]) The Differential Allocation- Payment Relationship for a given parameter α≥ 1 is: ( p(t)−f′(y(t)) ) dy(t)≥ 1 α(t)f∗′ (p(t))dp(t) (26) for all t∈ [0,T ] and for all shared resources where f′(y(t)) is the derivative of an oper...

    work page