  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.
