Trip-Vehicle Assignment Algorithms for Ride-Sharing

The trip-vehicle assignment problem is a central issue in most peer-to-peer ride-sharing systems. Given a set of n available vehicles with respective locations and a set of m trip requests with respective origins and destinations, the objective is to assign requests to vehicles with the minimum overall cost (which is the sum of the moving distances of the vehicles). Since the assignment constraints are well captured by edges matched in graphs, we investigate the problem from a matching algorithm point of view. Suppose there are at most two requests sharing a vehicle at any time, we answer an open question by Bei and Zhang (AAAI, 2018), that asks for a constant-approximation algorithm for the setting where the number (m) of requests is no more than twice the number (n) of vehicles, i.e., m≤ 2 n. We propose an O(n⁴) -time 2.5-approximation algorithm, which is built upon a solution of the Minimum-weight Fixed-size Matching problem with unmatched vertex Penalty (MFMP), in which the cost is the sum of the weights of both matched edges and unmatched vertices. Then, we study a more general setting that also allows m> 2 n. We propose a dynamic assignment algorithm that is built upon a solution of the Minimum Weight Matching problem with unmatched vertex Penalty (MWMP). Further, we extend the dynamic assignment algorithm to an online setting where on-demand trip requests appear over time. Experiments are conducted on a real-world data set of trip records showing that our algorithms actually achieve good performances.