TL;DR
This paper introduces a novel general equilibrium model that captures the complex interactions in multi-passenger ridesharing systems, including driver and passenger decisions, platform operations, and network congestion. By developing a sophisticated "sequence-bush" algorithm, the authors provide a computationally efficient way to find stable matching and route choices, paving the way for better urban mobility planning.
What Problem Does This Paper Address?
The rise of ride-sharing services like Uber and Lyft has transformed urban transportation. While ride-hailing has been widely studied, multi-passenger ridesharing (where a single driver picks up multiple passengers) holds immense potential for reducing congestion and emissions. However, modeling these systems is incredibly complex. Existing approaches often struggle to simultaneously account for:
- Multi-passenger dynamics: Drivers picking up and dropping off multiple passengers with different origins and destinations.
- Stable matching: Ensuring that neither drivers nor passengers have an incentive to unilaterally change their matching or route.
- Platform operations: How the ridesharing platform influences matching and pricing.
- Network congestion: How ridesharing traffic impacts travel times for all modes.
- Computational complexity: Finding equilibrium solutions for these interconnected systems is computationally demanding.
This paper aims to bridge this gap by developing a comprehensive model and an efficient algorithm to solve it, enabling a more realistic understanding and optimization of multi-passenger ridesharing.
Methods
The authors propose a general equilibrium model that integrates several key components:
- Hyper-network: They extend traditional transportation networks to a "hyper-network" that explicitly models matching sequences. This allows for transfer-free multi-passenger ridesharing and captures the sequential nature of pickups and drop-offs.
- Stable Matching: They redefine stable matching for multi-passenger ridesharing in terms of matching sequences, considering the detours drivers might take. This stable matching problem is then cast as a route choice problem within the hyper-network.
- Sequence-Bush Algorithm: To tackle the computational challenges, they develop a novel "sequence-bush" assignment algorithm. This algorithm decomposes the complex problem into simpler subproblems (mode choice, ridesharing matching, and network assignment) and uses a bush-based approach to efficiently represent and solve the network assignment for each group of matched drivers and passengers. This method avoids explicit path enumeration, significantly reducing computational burden.
Datasets
The authors evaluate their model and algorithm using the full Sioux-Falls network. This network comprises 24 nodes, 76 links, 529 OD pairs, and a total demand of 360,600 trips. This dataset is noted as being significantly larger than those used in previous studies for similar problems.
Key Insights and Ideas
- Matching Sequence is Key: The paper highlights that the sequence of pickups and drop-offs, not just the group of passengers, is crucial for stable matching and determining ridesharing disutility.
- Hyper-network for Realism: The hyper-network approach effectively models complex multi-passenger ridesharing without transfers, a significant improvement over prior methods.
- Algorithm Efficiency: The sequence-bush algorithm demonstrates a substantial improvement in runtime and number of iterations compared to general-purpose solvers, making large-scale analysis feasible.
- Ridesharing Benefits Depend on Pricing: Sensitivity analysis shows that ridesharing can offer network benefits (like reduced VKT), but these benefits are highly dependent on carefully designed unit prices.
- Value of Time Matters: Travelers with lower values of time are more likely to participate in ridesharing, suggesting targeted strategies might be needed to attract higher-VOT individuals.
Key Results
- The proposed sequence-bush algorithm significantly outperforms GAMS/PATH solvers in terms of runtime and number of iterations on the Sioux-Falls network. For instance, the algorithm achieved convergence in 82 iterations with a runtime of 3.92 seconds, compared to GAMS/PATH's 265,827 iterations and 446.34 seconds.
- Numerical results indicate that ridesharing trips are generally longer than average trip lengths.
- The introduction of ridesharing leads to VKT savings of 2.01% and VHT savings of 2.02% on the Sioux-Falls network.
- Sensitivity analysis shows that ridesharing modal shares and network benefits are strongly influenced by the unit price, with optimal pricing being crucial for realizing benefits.
Limitations and Future Work
- Solution Uniqueness: The authors acknowledge that proving general solution uniqueness for such a complex model is challenging, especially given the asymmetric nature of some constraints and the non-monotone cost functions. Future research could explore restrictive assumptions to establish uniqueness.
- Waiting Times: The model could be extended to accommodate pickup waiting times, which are a significant factor in real-world ridesharing.
- Second-Order Information: For faster convergence, future research could incorporate second-order information or accelerated gradient methods.
- Pricing Strategies: The paper suggests further research is needed to design efficient and effective pricing strategies for transportation systems with shared mobility services.
Summary updated