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

• Published in: Heliyon 2022-11, Vol.8 (11), p.e11319-e11319, Article e11319
• Main Authors: Wang, Ning, Guo, Jiahui
• Format: Article
• Language: English
• Subjects: Bipartite graph matching; Maximum flow problem; Recharging task assignment; Repositioning task assignment; Sustainable transportation
• ISSN: 2405-8440; 2405-8440
• DOI: 10.1016/j.heliyon.2022.e11319

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. Sustainable transportation; Recharging task assignment; Repositioning task assignment; Bipartite graph matching; Maximum flow problem