TY - GEN
T1 - Efficient matching of offers and requests in social-aware ridesharing
AU - FU, Xiaoyi
AU - Zhang, Ce
AU - Lu, Hua
AU - XU, Jianliang
N1 - Funding Information:
ACKNOWLEDGMENT This work was supported by the Hong Kong Research Grants Council (RGC) under projects 12200817 and 12201615.
PY - 2018/7/13
Y1 - 2018/7/13
N2 - Ridesharing has been becoming increasingly popular in urban areas worldwide for its low cost and environmental friendliness. Much research attention has been drawn to the optimization of travel costs in shared rides. However, other important factors in ridesharing, such as the social comfort and trust issues, have not been fully considered in the existing works. In this paper, we formulate a new problem, named Assignment of Requests to Offers (ARO), that aims to maximize the number of served riders while satisfying the social comfort constraints as well as spatial-temporal constraints. We prove that the ARO problem is NP-hard. We then propose an exact algorithm for a simplified ARO problem. We further propose three pruning strategies to efficiently narrow down the searching space and speed up the assignment processing. Based on these pruning strategies, we develop two novel heuristic algorithms, the request-oriented approach and offer-oriented approach, to tackle the ARO problem. Through extensive experiments, we demonstrate the efficiency and effectiveness of our proposed approaches on real-world datasets.
AB - Ridesharing has been becoming increasingly popular in urban areas worldwide for its low cost and environmental friendliness. Much research attention has been drawn to the optimization of travel costs in shared rides. However, other important factors in ridesharing, such as the social comfort and trust issues, have not been fully considered in the existing works. In this paper, we formulate a new problem, named Assignment of Requests to Offers (ARO), that aims to maximize the number of served riders while satisfying the social comfort constraints as well as spatial-temporal constraints. We prove that the ARO problem is NP-hard. We then propose an exact algorithm for a simplified ARO problem. We further propose three pruning strategies to efficiently narrow down the searching space and speed up the assignment processing. Based on these pruning strategies, we develop two novel heuristic algorithms, the request-oriented approach and offer-oriented approach, to tackle the ARO problem. Through extensive experiments, we demonstrate the efficiency and effectiveness of our proposed approaches on real-world datasets.
KW - LBS services
KW - ride sharing
KW - spatio-temporal databases
UR - http://www.scopus.com/inward/record.url?scp=85050810567&partnerID=8YFLogxK
U2 - 10.1109/MDM.2018.00037
DO - 10.1109/MDM.2018.00037
M3 - Conference contribution
AN - SCOPUS:85050810567
T3 - Proceedings - IEEE International Conference on Mobile Data Management
SP - 197
EP - 206
BT - Proceedings - 2018 IEEE 19th International Conference on Mobile Data Management, MDM 2018
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 19th IEEE International Conference on Mobile Data Management, MDM 2018
Y2 - 26 June 2018 through 28 June 2018
ER -