Improved Algorithms for Trip-Vehicle Assignment in Ride-Sharing

The RIDE-SHARING ASSIGNMENT PROBLEM (AAAI 2018) is a fundamental problem in intelligent transportation systems, urban mobility, and algorithmic decision-making. Given a set of m vehicles with initial locations and n requests (n ≤ mk), each with a specified origin and destination, the goal is to assign at most k requests to each vehicle and compute corresponding routes that minimize the total travel distance. The algorithmic approach depends on whether n = mk or n < mk. In this paper, we present algorithms with provable approximation guarantees for both cases. When n = mk, we design a minO( √ k), O( n k )-approximation algorithm, whereas previously the ratio O( √ k) was only proved for k being a power of 2. When n < mk, we achieve an approximation ratio of O( √ k log maxn, m), breaking the natural O(k) barrier. We also conduct experiments to evaluate the empirical performance of our algorithms. The results show that our solutions consistently outperform those produced by the previous existing algorithm.