@inproceedings{676d36441f324ea08324b2cd6978ccef, title = "Trip-Vehicle Assignment Algorithms for Ride-Sharing", abstract = "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 ≤ 2n. We propose an O(n4)-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 > 2n. 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.", keywords = "Matching algorithm, Ride-sharing system, Trip-vehicle assignment", author = "Songhua Li and Minming Li and Lee, {Victor C. S.}", note = "Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).; 14th International Conference on Combinatorial Optimization and Applications, COCOA 2020 ; Conference date: 11-12-2020 Through 13-12-2020", year = "2020", month = dec, doi = "10.1007/978-3-030-64843-5_46", language = "English", isbn = "978-3-030-64842-8", series = "Lecture Notes in Computer Science (including subseries Theoretical Computer Science and General Issues)", publisher = "Springer Nature", pages = "681--696", editor = "Weili Wu and Zhongnan Zhang", booktitle = "Combinatorial Optimization and Applications", url = "https://theory.utdallas.edu/COCOA2020/index.html", }