On efficient passenger assignment for group transportation

Jiajie Xu*, Guanfeng Liu, Kai Zheng, Chengfei Liu, Haoming Guo, Zhiming Ding

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

Abstract

With the increasing popularity of LBS services, spatial assignment has become an important problem nowadays. Nevertheless most existing works use Euclidean distance as the measurement of spatial proximity. In this paper, we investigate a variant of spatial assignment problem with road networks as the underlying space. Given a set of passengers and a set of vehicles, where each vehicle waits for the arrival of all passengers assigned to it, and then carries them to the same destination, our goal is to find an assignment from passengers to vehicles such that all passengers can arrive at earliest together. Such a passenger assignment problem has various applications in real life. However, finding the optimal assignment efficiently is challenging due to high computational cost in the fastest path search and combinatorial nature of capacity constrained assignment. In this paper, we first propose two exact solutions to find the optimal results, and then an approximate solution to achieve higher efficiency by trading off a little accuracy. Finally, performances of all proposed algorithms are evaluated on a real dataset.

Original languageEnglish
Title of host publicationDatabase Systems for Advanced Applications
Subtitle of host publication20th International Conference, DASFAA 2015, Proceedings, Part I
EditorsMatthias Renz, Cyrus Shahabi, Xiaofang Zhou, Muhammad Aamir Cheema
Place of PublicationCham
PublisherSpringer, Springer Nature
Pages226-243
Number of pages18
Volume9049
ISBN (Electronic)9783319181202
ISBN (Print)9783319181196
DOIs
Publication statusPublished - 2015
Externally publishedYes
Event20th International Conference on Database Systems for Advanced Applications, DASFAA 2015 - Hanoi, Viet Nam
Duration: 20 Apr 201523 Apr 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9049
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other20th International Conference on Database Systems for Advanced Applications, DASFAA 2015
CountryViet Nam
CityHanoi
Period20/04/1523/04/15

Fingerprint Dive into the research topics of 'On efficient passenger assignment for group transportation'. Together they form a unique fingerprint.

Cite this