Algorithms for the Ridesharing with Profit Constraint Problem
Preprint
Abstract
Mobility-on-demand (MoD) ridesharing is a promising way to improve the occupancy rate of personal vehicles and reduce traffic congestion and emissions. Maximizing the number of passengers served and maximizing a profit target are major optimization goals in MoD ridesharing. We study the ridesharing with profit constraint problem (labeled as RPC) which considers both optimization goals altogether: maximize the total number of passengers subject to an overall drivers' profit target. We give a mathematical formulation for the RPC problem. We present a polynomial-time exact algorithm framework (including two practical implementations of the algorithm) and a (1/2)-approximation algorithm for the case that each vehicle serves at most one passenger. We propose a (2/3*lambda)-approximation algorithm for the case that each vehicle serves at most lambda >= 2 passengers. Our algorithms revolve around the idea of maximum cardinality matching in bipartite graphs and hypergraphs (set packing) with general edge weight. Based on a real-world ridesharing dataset in Chicago City and price schemes of Uber, we conduct an extensive empirical study on our model and algorithms. Experimental results show that practical price schemes can be incorporated into our model, our exact algorithms are efficient, and our approximation algorithms achieve about 90% of optimal solutions, in the number of passengers served.Keywords
All Related Versions
This publication has 42 references indexed in Scilit:
- Optimizing ride-sharing operations in smart sustainable cities: Challenges and the need for agile algorithmsComputers & Industrial Engineering, 2021
- Dynamic pricing and matching in ride‐hailing platformsNaval Research Logistics (NRL), 2019
- The impact of ride-hailing on vehicle miles traveledTransportation, 2018
- Enhancing urban mobility: Integrating ride-sharing and public transitComputers & Operations Research, 2018
- Approximating the $k$-Set Packing Problem by Local Improvements2014
- Large Neighborhood Local Search for the Maximum Set Packing ProblemLecture Notes in Computer Science, 2013
- On the complexity of approximating k-set packingcomputational complexity, 2006
- Greedy Local Improvement and Weighted Set Packing ApproximationJournal of Algorithms, 2001
- A d/2 Approximation for Maximum Weight Independent Set in d-Claw Free GraphsLecture Notes in Computer Science, 2000
- Reducibility among Combinatorial Problems1972