With the rapid development of location based services, ride-sharing has become very popular in our daily life. Although the fairness has been considered in existing ride-sharing relevant tasks, they only focus on the overall revenue rather than the individual driver revenue. To fill in this research gap, in this paper, we propose a novel Fairness-aware Ride-sharing Assignment (FRA) model. In this model, we aim to maximize the lowest revenue among all drivers, and simultaneously minimize the total travel distance of the drivers. We theoretically show that it is NP-hard to find the optimal solution for our problem. To solve this problem, we first an approximation algorithm called Routing and Assignment (RA), which strikes a balance between efficiency and optimality. Observing that the efficient task assignment strategy of RA may not consider the drivers revenue adequately. We further propose an algorithm called Grouping, Assignment, and Routing (GAR). Our empirical results show the superior performance of our algorithms in comparison to existing methods focused on optimizing total distance.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Fairness-Aware Ride-Sharing Assignment

  • Leshu Yuan,
  • Ting Wang,
  • Jianye Yang,
  • Dian Ouyang

摘要

With the rapid development of location based services, ride-sharing has become very popular in our daily life. Although the fairness has been considered in existing ride-sharing relevant tasks, they only focus on the overall revenue rather than the individual driver revenue. To fill in this research gap, in this paper, we propose a novel Fairness-aware Ride-sharing Assignment (FRA) model. In this model, we aim to maximize the lowest revenue among all drivers, and simultaneously minimize the total travel distance of the drivers. We theoretically show that it is NP-hard to find the optimal solution for our problem. To solve this problem, we first an approximation algorithm called Routing and Assignment (RA), which strikes a balance between efficiency and optimality. Observing that the efficient task assignment strategy of RA may not consider the drivers revenue adequately. We further propose an algorithm called Grouping, Assignment, and Routing (GAR). Our empirical results show the superior performance of our algorithms in comparison to existing methods focused on optimizing total distance.