TY - GEN
T1 - Trip-Vehicle Assignment Algorithms for Ride-Sharing
AU - Li, Songhua
AU - Li, Minming
AU - Lee, Victor C. S.
N1 - 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).
PY - 2020/12
Y1 - 2020/12
N2 - 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.
AB - 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.
KW - Matching algorithm
KW - Ride-sharing system
KW - Trip-vehicle assignment
UR - http://www.scopus.com/inward/record.url?scp=85097821104&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85097821104&origin=recordpage
U2 - 10.1007/978-3-030-64843-5_46
DO - 10.1007/978-3-030-64843-5_46
M3 - 32_Refereed conference paper (with ISBN/ISSN)
SN - 978-3-030-64842-8
T3 - Lecture Notes in Computer Science (including subseries Theoretical Computer Science and General Issues)
SP - 681
EP - 696
BT - Combinatorial Optimization and Applications
A2 - Wu, Weili
A2 - Zhang, Zhongnan
PB - Springer Nature
T2 - 14th International Conference on Combinatorial Optimization and Applications, COCOA 2020
Y2 - 11 December 2020 through 13 December 2020
ER -