Dynamic Ridesharing With Minimal Regret: Towards an Enhanced Engagement Among Three Stakeholders

Authors:
Publisher website
Google Scholar
Abstract
In dynamic ridesharing, the platform serves as the mediator by tailoring the assignment result between workers and riders with a focus on a certain objective. In this paper, we for the rst time study how to incorporate the willingness of all stakeholders (i.e., the platform, workers and riders). Given a set of workers and a set of rider requests, we aim to return the matchable worker-rider pairs in order to minimize the regret. Specically, two types of regret are dened: (i) the served rate regret, which refers to the rate of unserved requests, catering for the reputation and prot of the platform and workers; (ii) the revenue regret, which considers the portion of revenue loss from unserved riders, catering for the focus of workers and riders in the trip schedule. We prove the NP-hardness of this problem. To tackle this problem, we rst propose a dynamic programming insertion algorithm to improve the efciency of inserting a rider request into a trip schedule of a worker. Furthermore, two heuristic algorithms are devised to match rider requests with workers effectively. Comprehensive experiments on two real-world datasets verify the effectiveness, efciency and scalability of our solutions in dealing with different supply-demand relationships.
Funding Information
  • ARC (DP200102611, DP220101434)
  • National Natural Science Foundation of China (61972268)

This publication has 29 references indexed in Scilit: