Joint Order Dispatching and Vehicle Repositioning for Dynamic Ridesharing

Dynamic ridesharing has gained significant attention in recent years. However, existing ridesharing studies often focus on optimizing order dispatching and vehicle repositioning separately, leading to short-sighted decisions and underutilization of the ridesharing potential. In this paper, we propose a novel joint optimization framework called <inline-formula><tex-math notation="LaTeX">$\mathtt {JODR}$</tex-math></inline-formula>. By coordinating order dispatching and vehicle repositioning, <inline-formula><tex-math notation="LaTeX">$\mathtt {JODR}$</tex-math></inline-formula> enhances ridesharing efficiency while ensuring high-quality service. The core idea of <inline-formula><tex-math notation="LaTeX">$\mathtt {JODR}$</tex-math></inline-formula> is to dispatch ride orders with high demand in specific mobility directions to vehicles with sufficient available capacity, effectively balancing future supply and demand in those directions. To achieve this, we introduce a novel mobility value function that can predict the long-term mobility value of matching an order with its travel direction. By considering orders’ directional mobility values, service quality assessments, and available vehicle capacities, <inline-formula><tex-math notation="LaTeX">$\mathtt {JODR}$</tex-math></inline-formula> formulates the order dispatching as a minimum-cost maximum-flow problem to derive the optimal order-vehicle assignments. Furthermore, the value function helps the intelligent repositioning of idle vehicles. Extensive experiments conducted on a large real-world dataset demonstrate the superiority of <inline-formula><tex-math notation="LaTeX">$\mathtt {JODR}$</tex-math></inline-formula> over state-of-the-art methods across various performance metrics. These experimental results validate the effectiveness of <inline-formula><tex-math notation="LaTeX">$\mathtt {JODR}$</tex-math></inline-formula> in improving the ridesharing efficiency and experience.