Paper Info
Title
High-capacity ride-sharing via shortest path clustering on large road networks
Abstract
Ride-sharing has been widely studied in academia and applied in mobility-on-demand systems as a means of reducing the number of cars, congestion, and pollution by sharing empty seats. Solving this problem is challenging on large-scale road networks for the following two reasons: Distance calculation on large-scale road networks is time-consuming, and multi-request allocation and route planning have been proved to be NP-hard problems. In this paper, we propose a clustering-based request matching and route planning algorithm $${Roo}$$ whose basic operations are merging requested trips on road networks. Several requested trips can be merged and served by a vehicle if their shortest paths from origins to destinations are close to each other based on spatiotemporal road network distances. The resultant routes are further refined by introducing meeting points, which can shorten the total traveling distance while keeping matched ride requests satisfied. The $${Roo}$$ algorithm has been evaluated with two real-world taxi trajectory datasets and road networks from New York City and Beijing. The results show that $${Roo}$$ can save up to 50% of mileage by 1000 vehicles serving around 7000 trip requests in New York City between 7:40 and 8:00 am with an average waiting time of 4 minutes.
Year
DOI
Venue
2021
10.1007/s11227-020-03424-6
The Journal of Supercomputing
Keywords
DocType
Volume
Spatial data mining, Trajectory mining, Ride-sharing, Route planning
Journal
77
Issue
ISSN
Citations 
4
0920-8542
0
PageRank 
References 
Authors
0.34
19
6
Name
Order
Citations
PageRank
Haojia Zuo100.34
Bo Cao212.06
Ying Zhao390249.19
Bilong Shen492.23
Weimin Zheng51889182.48
Yan Huang61736108.45