High-capacity ride-sharing via shortest path clustering on large road networks
- PDF / 2,657,823 Bytes
- 26 Pages / 439.37 x 666.142 pts Page_size
- 11 Downloads / 160 Views
High‑capacity ride‑sharing via shortest path clustering on large road networks Haojia Zuo1 · Bo Cao1 · Ying Zhao1 · Bilong Shen1 · Weimin Zheng1 · Yan Huang2 Accepted: 30 August 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Ride-sharing has been widely studied in academia and applied in mobility-ondemand 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 clusteringbased 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. Keywords Spatial data mining · Trajectory mining · Ride-sharing · Route planning
* Ying Zhao [email protected] Yan Huang [email protected] 1
Department of Computer Science and Technology, Tsinghua University, Beijing, China
2
Department of Computer Science, University of North Texas, Denton, TX, USA
13
Vol.:(0123456789)
H. Zuo et al.
1 Introduction Ride-sharing has been widely studied in academia and applied in mobility-ondemand (MoD) systems as a means of reducing the number of cars, congestion, and pollution by sharing empty seats [2, 7, 14, 21, 25, 27]. In particular, the ride-sharing problem with vehicles as dispatching resources has drawn people’s attention lately [3, 5, 13, 23]. In this scenario, ride requests within a time window t are acquired ahead in MoD systems, and spatiotemporally distributed demands must be picked up and delivered, which requires effective request matching and route planning algorithms to dispatch vehicles to serve the demands. Javier et al. [3] termed this problem as the on-demand high-capacity ride-sharing problem, which deals with a large number of online ride requests and vehicles of various capacities, such as taxis, vans, and minibuses. 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 NPhard problems [19]. The existing methods use approximation algorithms to solve
Data Loading...
