Multi-task dispatch of shared autonomous electric vehicles for Mobility-on-Demand services – combination of deep reinforcement learning and combinatorial optimization method

The Autonomous Mobility-on-Demand system is an emerging green and sustainable transportation system providing on-demand mobility services for urban residents. To achieve the best recharging, delivering, and repositioning task assignment decision-making process for shared autonomous electric vehicles, this paper formulates the fleet dynamic operating process into a multi-agent multi-task dynamic dispatching problem based on Markov Decision Process. Specifically, the decision-making process at each time step is divided into 3 sub-processes, among which recharging and delivery task assignment processes are transformed into a maximum weight matching problem of bipartite graph respectively, and the repositioning task assignment process is quantified as a maximum flow problem. Kuhn-Munkres Algorithm and Edmond-Karp Algorithm are adopted to solve the above two mathematical problems to achieve the optimal task allocation policy. To further improve the dispatching performance, a new instant reward function balancing order income with trip satisfaction is designed, and a state-value function estimated by Back Propagation-Deep Neural Network is defined as a matching degree between each shared autonomous electric vehicle and each delivery task. The numerical results show that: (i) a reward function focusing on income and satisfaction can increase total revenue by 33.2%, (ii) the introduction of task allocation repositioning increases total revenue by 50.0%, (iii) a re-estimated state value function leads to a 2.8% increase in total revenue, (iv) the combination of charging and task repositioning can reduce user waiting time and significantly improve user satisfaction with the trip.