MADRL-Based Order Dispatching in MoD Systems With Bipartite Graph Splitting

Mobility on-demand (MoD) systems widely use machine learning to estimate matching utilities of order-vehicle pairs to dispatch orders by bipartite matching. However, existing methods suffer from overestimation problems due to the complex interactions among order-vehicle pairs in the global bipartite graph, leading to low overall revenue and order completion rate. To fill this gap, we propose a multi-agent deep reinforcement learning (MADRL) based order dispatching method with bipartite splitting, named SplitMatch. The key idea is to split the global bipartite graph into multiple sub-bipartite graphs to overcome the overestimation problem. First, we propose a bipartite splitting theorem and prove that the optimal solution of global bipartite matching can be achieved by solving multiple sub-bipartite matching problems when certain conditions are met. Second, we design a spatial-temporal padding prediction algorithm to generate sub-bipartite graphs that satisfy this theorem, where the spatial-temporal feature of orders and vehicles is captured. Next, we propose a MADRL framework to learn the matching utility, where multi-objective, e.g., immediate revenue and quality of service (QoS), are taken into account to deal with varying action space. Finally, a series of simulations are conducted to verify the superiority of SplitMatch in terms of overall revenue and order completion rate.