Efficient matching of offers and requests in social-aware ridesharing

Xiaoyi FU*, Ce Zhang, Hua Lu, Jianliang XU

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference contributionpeer-review

3 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 publicationProceedings - 2018 IEEE 19th International Conference on Mobile Data Management, MDM 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages197-206
Number of pages10
ISBN (Electronic)9781538641330
DOIs
Publication statusPublished - 13 Jul 2018
Event19th IEEE International Conference on Mobile Data Management, MDM 2018 - Aalborg, Denmark
Duration: 26 Jun 201828 Jun 2018

Publication series

NameProceedings - IEEE International Conference on Mobile Data Management
Volume2018-June
ISSN (Print)1551-6245

Conference

Conference19th IEEE International Conference on Mobile Data Management, MDM 2018
Country/TerritoryDenmark
CityAalborg
Period26/06/1828/06/18

Scopus Subject Areas

  • Engineering(all)

User-Defined Keywords

  • LBS services
  • ride sharing
  • spatio-temporal databases

Fingerprint

Dive into the research topics of 'Efficient matching of offers and requests in social-aware ridesharing'. Together they form a unique fingerprint.

Cite this