Utility-Aware Dynamic Ridesharing in Spatial Crowdsourcing

Yafei Li, Huiling Li, Xin Huang, Jianliang Xu*, Yu Han, Mingliang Xu*

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

1 Citation (Scopus)


With smartphones and geo-locating devices widely used around the world, ridesharing, as a main application field of spatial crowdsourcing, has been fast expanding its widespread adoption and potentially brings great benefits to human society and the environment. However, ridesharing has so far not been as popular as expected. A recent survey shows that notable obstacles come from concerns about social comfort and price fairness when riding with strangers. To defeat these obstacles, in this paper, we study a novel problem of utility-aware ride matching (URM) for dynamic ridesharing, where drivers and riders are matched in batches by considering their social comfort and price revenue. While the URM problem is of practical usefulness, we prove that this problem is Nondeterministic Polynomial Hard (NP-hard). To tackle the problem optimally and find exact answers, we present a novel bipartite matching algorithm by integrating an effective Driver-Rider Graph (DR-Graph) index. To balance the effectiveness and efficiency, we propose two efficient algorithms to solve the URM problem with only a small loss of utility. Leveraging a bounded Driver-Rider-group Graph (DRg-Graph) and several useful pruning bounds for matching utility and travel cost, we develop an ϵ -refining algorithm to find an ϵ -approximation matching utility of the optimal answer. Extensive experiments on real datasets showed that our proposed algorithms achieved effective matching results of social-pricing based utilities and the efficient performance of quick matching under various parameter settings.
Original languageEnglish
Pages (from-to)1066-1079
Number of pages14
JournalIEEE Transactions on Mobile Computing
Issue number2
Early online date26 Dec 2022
Publication statusPublished - Feb 2024

Scopus Subject Areas

  • Software
  • Computer Networks and Communications
  • Electrical and Electronic Engineering

User-Defined Keywords

  • Spatial crowdsourcing
  • location-based services
  • optimization
  • ridesharing
  • social network


Dive into the research topics of 'Utility-Aware Dynamic Ridesharing in Spatial Crowdsourcing'. Together they form a unique fingerprint.

Cite this