Dynamic Ridehailing with Electric Vehicles

Nicholas D Kullman (1) , Martin Cousineau (2) , Justin C Goodson (3) , Jorge E. Mendoza

1 LIFAT - Laboratoire d'Informatique Fondamentale et Appliquée de Tours
2 HEC Montréal - HEC Montréal
3 Saint Louis University

We consider the problem of an operator controlling a fleet of electric vehicles for use in a ridehailing service. The operator, seeking to maximize revenue, must assign vehicles to requests as they arise and recharge and reposition vehicles in anticipation of future requests. To solve this problem, we employ deep reinforcement learning, developing policies whose decision making uses Q-value approximations learned by deep neural networks. We compare these policies against a common taxi dispatching heuristic and against dual bounds on the value of an optimal policy, including the value of an optimal policy with perfect information which we establish using a Benders-based decomposition. We assess performance on instances derived from real data for the island of Manhattan in New York City. We find that, across instances of varying size, our best policy trained with deep reinforcement learning outperforms the taxi dispatching heuristic. We also provide evidence that this policy may be effectively scaled and deployed on larger instances without retraining.

Domains: Operations Research [math.OC]

Nicholas D Kullman, Martin Cousineau, Justin C Goodson, Jorge E. Mendoza. Dynamic Ridehailing with Electric Vehicles. Transportation Science, 2021. ⟨hal-02463422v2⟩