TY - GEN
T1 - On efficient passenger assignment for group transportation
AU - Xu, Jiajie
AU - Liu, Guanfeng
AU - Zheng, Kai
AU - Liu, Chengfei
AU - Guo, Haoming
AU - Ding, Zhiming
PY - 2015
Y1 - 2015
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84942569256&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-18120-2_14
DO - 10.1007/978-3-319-18120-2_14
M3 - Conference proceeding contribution
AN - SCOPUS:84942569256
SN - 9783319181196
VL - 9049
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 226
EP - 243
BT - Database Systems for Advanced Applications
A2 - Renz, Matthias
A2 - Shahabi, Cyrus
A2 - Zhou, Xiaofang
A2 - Cheema, Muhammad Aamir
PB - Springer, Springer Nature
CY - Cham
T2 - 20th International Conference on Database Systems for Advanced Applications, DASFAA 2015
Y2 - 20 April 2015 through 23 April 2015
ER -