The Stochastic Share-a-Ride Problem with Electric Vehicles and Customer Priorities

We introduce a stochastic share-a-ride problem with electric vehicles, in which passenger and parcel orders can be served in a shared manner by the same vehicle in a ride-hailing system. We assume that customer service requests arrive stochastically in the system. We consider that passenger orders have priorities over parcel orders, while passengers need to be transported directly from their origins to destinations. To maximize the total expected rewards that can be collected by the system, the system operator must determine how to assign the two types of orders to vehicles, in what sequence the vehicles should visit the pickup and drop-off locations of the orders and when to charge the electric vehicles. We formally model the problem as a Markov decision process (MDP). To overcome the computational challenges induced by the large state and action space, we propose a reinforcement learning (RL) approach based on an approximate value iteration (AVI) algorithm to learn the value of the post-decision states. We develop a state space aggregation scheme to reduce the state space, while both the spatial and temporal information on customer orders and vehicles are included in the aggregated states. We demonstrate the capability of our modeling and solution approaches in generating high quality policies via computational experiments based on real-world taxi data for New York City