A Detour Planning Algorithm for Ride-Pooling Vehicles with Available Seats

Abstract

Ride-pooling services, such as UberPool and Lyft Shared Saver, enable a single vehicle to serve multiple passengers within a shared trip. This work introduces a novel detour planning algorithm designed for ride-pooling vehicles with available capacity. Instead of following the shortest path from the current passenger’s origin to destination, the proposed method aims to design a path, which maximizes the likelihood of matching with additional passengers en route while respecting the time constraint for the current passenger. In contrast to traditional approaches that group passengers and vehicles based on predefined time windows, our algorithm provides immediate responses to passenger requests, dynamically considers real-time passenger demand, and coordinates partially occupied vehicles with other fleets. Approximated as an integer linear programming (ILP) problem, the method is computationally efficient and practical for real-world implementation. The effectiveness of the proposed approach is verified by simulation results built on the road network of Shenzhen, China, demonstrating significant improvements in service quality.