Dynamic Ridesharing Matching and Vehicle Routing Optimization of App-based Taxis

Taxi ridesharing addresses issues such as passenger difficulty in hailing taxis and low seat utilization. However, suboptimal ridesharing matching can increase passenger waiting or in-vehicle travel time, thereby reducing travel satisfaction. Focusing on app-based taxi ridesharing, this paper simultaneously considers travel order matching and taxi route optimization to construct a mathematical model minimizing the sum of all passengers' waiting time costs and travel costs. An optimization algorithm combining multi-agent reinforcement learning QMIX and adaptive large neighborhood search (ALNS) is proposed to solve the model. This algorithm enhances solution speed while maintaining solution quality and generalization capability. Large- and small-scale cases are extracted based on real taxi order data from a district in a major city. Small-scale cases are used to test the model's solvability and the algorithm's effectiveness. Subsequently, large-scale cases are solved to obtain optimized ridesharing matching and routing schemes, which are benchmarked against the actual situation. The results demonstrate average savings of 29.84% in travel cost and 22.40% in the number of taxis utilized after optimization. Tests further indicate significant advantages of the ridesharing system over a non-ridesharing system, achieving average reductions of 20.05%, 15.87%, and 18.96% in waiting time cost, travel cost, and the number of vehicles used, respectively. Finally, the impacts of the rolling horizon period length, clustering scale, and ridesharing fare discount rate on algorithm performance and passenger costs are analyzed.