Trip-Vehicle Assignment Algorithms for Ride-Sharing

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review

View graph of relations

Related Research Unit(s)

Detail(s)

Original languageEnglish
Title of host publicationCombinatorial Optimization and Applications
Subtitle of host publication14th International Conference, COCOA 2020, Proceedings
EditorsWeili Wu, Zhongnan Zhang
PublisherSpringer Nature
Pages681-696
ISBN (Electronic)978-3-030-64843-5
ISBN (Print)978-3-030-64842-8
Publication statusPublished - Dec 2020

Publication series

NameLecture Notes in Computer Science (including subseries Theoretical Computer Science and General Issues)
Volume12577
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Title14th International Conference on Combinatorial Optimization and Applications, COCOA 2020
LocationVirtual
PlaceUnited States
CityDallas
Period11 - 13 December 2020

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., ≤ 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.

Research Area(s)

  • Matching algorithm, Ride-sharing system, Trip-vehicle assignment

Bibliographic 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).

Citation Format(s)

Trip-Vehicle Assignment Algorithms for Ride-Sharing. / Li, Songhua; Li, Minming; Lee, Victor C. S.

Combinatorial Optimization and Applications: 14th International Conference, COCOA 2020, Proceedings. ed. / Weili Wu; Zhongnan Zhang. Springer Nature, 2020. p. 681-696 (Lecture Notes in Computer Science (including subseries Theoretical Computer Science and General Issues); Vol. 12577).

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review