Improved Algorithms for Trip-Vehicle Assignment in Ride-Sharing

Abstract 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