Efficient Matching of Offers and Requests in Social-Aware Ridesharing

Xiaoyi Fu, Ce Zhang, Hua Lu, Jianliang Xu

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

2 Citations (Scopus)

Abstract

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.
Original languageEnglish
Title of host publication2018 19th IEEE International Conference on Mobile Data Management (MDM)
Number of pages10
Volume2018-June
PublisherIEEE
Publication date13 Jul 2018
Pages197-206
ISBN (Print)978-1-5386-4134-7
ISBN (Electronic) 978-1-5386-4133-0
DOIs
Publication statusPublished - 13 Jul 2018
Event19th IEEE International Conference on Mobile Data Management, MDM 2018 - Aalborg, Denmark
Duration: 25 Jun 201828 Jun 2018

Conference

Conference19th IEEE International Conference on Mobile Data Management, MDM 2018
CountryDenmark
CityAalborg
Period25/06/201828/06/2018
SponsorAalborg University, Center for Data-Intensive Systems (DAISY), Aalborg University, IEEE, IEEE Technical Committee on Data Engineering (TCDE), Otto Monsted Foundation
SeriesIEEE International Conference on Mobile Data Management (MDM)
ISSN2375-0324

Fingerprint

Heuristic algorithms
Costs
Computational complexity
Processing
Experiments

Cite this

Fu, X., Zhang, C., Lu, H., & Xu, J. (2018). Efficient Matching of Offers and Requests in Social-Aware Ridesharing. In 2018 19th IEEE International Conference on Mobile Data Management (MDM) (Vol. 2018-June, pp. 197-206). IEEE. IEEE International Conference on Mobile Data Management (MDM) https://doi.org/10.1109/MDM.2018.00037
Fu, Xiaoyi ; Zhang, Ce ; Lu, Hua ; Xu, Jianliang. / Efficient Matching of Offers and Requests in Social-Aware Ridesharing. 2018 19th IEEE International Conference on Mobile Data Management (MDM). Vol. 2018-June IEEE, 2018. pp. 197-206 (IEEE International Conference on Mobile Data Management (MDM)).
@inproceedings{923588e4901a43518b7429002da799bb,
title = "Efficient Matching of Offers and Requests in Social-Aware Ridesharing",
abstract = "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.",
author = "Xiaoyi Fu and Ce Zhang and Hua Lu and Jianliang Xu",
year = "2018",
month = "7",
day = "13",
doi = "10.1109/MDM.2018.00037",
language = "English",
isbn = "978-1-5386-4134-7",
volume = "2018-June",
series = "IEEE International Conference on Mobile Data Management (MDM)",
publisher = "IEEE",
pages = "197--206",
booktitle = "2018 19th IEEE International Conference on Mobile Data Management (MDM)",
address = "United States",

}

Fu, X, Zhang, C, Lu, H & Xu, J 2018, Efficient Matching of Offers and Requests in Social-Aware Ridesharing. in 2018 19th IEEE International Conference on Mobile Data Management (MDM). vol. 2018-June, IEEE, IEEE International Conference on Mobile Data Management (MDM), pp. 197-206, 19th IEEE International Conference on Mobile Data Management, MDM 2018, Aalborg, Denmark, 25/06/2018. https://doi.org/10.1109/MDM.2018.00037

Efficient Matching of Offers and Requests in Social-Aware Ridesharing. / Fu, Xiaoyi; Zhang, Ce; Lu, Hua; Xu, Jianliang.

2018 19th IEEE International Conference on Mobile Data Management (MDM). Vol. 2018-June IEEE, 2018. p. 197-206 (IEEE International Conference on Mobile Data Management (MDM)).

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

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

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.

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 - Article in proceeding

SN - 978-1-5386-4134-7

VL - 2018-June

T3 - IEEE International Conference on Mobile Data Management (MDM)

SP - 197

EP - 206

BT - 2018 19th IEEE International Conference on Mobile Data Management (MDM)

PB - IEEE

ER -

Fu X, Zhang C, Lu H, Xu J. Efficient Matching of Offers and Requests in Social-Aware Ridesharing. In 2018 19th IEEE International Conference on Mobile Data Management (MDM). Vol. 2018-June. IEEE. 2018. p. 197-206. (IEEE International Conference on Mobile Data Management (MDM)). https://doi.org/10.1109/MDM.2018.00037