Balancing Fairness and Efficiency in 3D Repeated Matching in Ridesharing

Ride-hailing services' main feature is mediating the assignment and transactions between drivers and passengers. Essentially, they decide on the quality of passengers' experience and the drivers' workload balancing. To boost the company's profit, these services try to maximize the utility for the passengers by optimizing the matching, resulting in shorter waiting times and better service availability. Often, in the process of maximizing revenue, drivers' interests get sidelined. We focus on two objectives: efficiency (minimizing total distance traveled by drivers) and fairness (minimizing the maximum traveled distance by any driver) for shared-mode rides, where the vehicles' capacity is two passengers. We theoretically show the relation between the optimal solutions of both objectives and as the problem is computationally intractable, we propose a heuristic algorithm to achieve an approximately optimal solution. We also propose a re-assignment-based algorithm when the aim is to achieve maximum matching with fairness up to a given threshold, if that is feasible. The experimental analysis for the proposed algorithms on real-world data from Chicago city shows that our approach can significantly improve fairness for drivers without losing much efficiency.