SHAREK*: A Scalable Matching Method for Dynamic Ride Sharing
- PDF / 3,794,206 Bytes
- 33 Pages / 439.642 x 666.49 pts Page_size
- 103 Downloads / 190 Views
SHAREK*: A Scalable Matching Method for Dynamic Ride Sharing Bin Cao1 · Chenyu Hou1 · Liwei Zhao1 · Louai Alarabi2 · Jing Fan1 · Mohamed F. Mokbel3 · Anas Basalamah4 Received: 27 February 2018 / Revised: 31 March 2020 / Accepted: 24 April 2020 / © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Due to its significant economic and environmental impact, sharing the ride among a number of drivers (i.e., car pooling) has recently gained significant interest from industry and academia. Hence, a number of ride sharing services have appeared along with various algorithms on how to match a rider request to a driver who can provide the ride sharing service. However, existing techniques have several limitations that affect the quality of the ride sharing service, and hence hinder its wide applicability. This paper proposes SHAREK*; a scalable and efficient ride sharing service that overcomes the limitations of existing approaches. SHAREK* allows riders requesting the ride sharing service to indicate Jing Fan
[email protected] Bin Cao [email protected] Chenyu Hou [email protected] Liwei Zhao otoko [email protected] Louai Alarabi [email protected] Mohamed F. Mokbel [email protected] Anas Basalamah [email protected] 1
Zhejiang University of Technology, HangZhou, China
2
Department of Computer Science, Umm Al-Qura University, Mecca, Kingdom of Saudi Arabia
3
Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN, USA
4
Computer Engineering Department and KACST GIS Technology Innovation Center, Umm Al-Qura University, Makkah, Saudi Arabia
Geoinformatica
the maximum price they are willing to pay for the service, the maximum waiting time before being picked up and the maximum arrival time for arriving the destination. In the mean time, SHAREK* computes the price of the service based on the distance of the rider trip and the detour that the driver will make to offer the service. Then, SHAREK* returns a set of drivers that can make it to the rider within its price and temporal constraints. Since there could be many of such drivers, SHAREK* internally prunes those drivers that are dominated by others, i.e., they provide higher price and higher waiting time (or arrival time) than other drivers. To realize its efficiency and scalability, SHAREK* employs a set of early pruning techniques that minimize the need for any actual shortest path computations. Keywords Ride sharing · Dynamic matching · Skyline
1 Introduction Dynamic ride sharing can be viewed as a form of car pooling system that arranges ad-hoc shared rides with sufficient convenience and flexibility [11]. Since dynamic ride sharing can be enabled by smart mobile phones, GPS and wireless networks, it is viewed as an environmentally and socially sustainable way to solve the world-widely major transportation problems, such as finite oil supplies, high gas prices, and jam-packed traffic. With the increasing number of the vehicles, it is widely believed that dynamic ride sharing will gain more popula
Data Loading...
