Exact Set Packing in Multimodal Transportation with Ridesharing System for First/Last Mile
Preprint
Abstract
We propose a centralized transportation system that integrates public transit with ridesharing to provide multimodal transportation. At each time interval, the system receives a set of personal drivers, designated drivers, and public transit riders. It then assigns all riders to drivers, ensuring that pick-ups and drop-offs occur at designated transit stations. This effectively replaces first-mile/last-mile (FM/LM) segments with a ridesharing alternative, reducing overall commuting time. We study two optimization problems: (1) minimizing the total travel distances of drivers and (2) minimizing the number of designated drivers required to serve all riders. We show the optimization problems are NP-hard and give hypergraph-based integer linear programming exact algorithm and approximation algorithms. To enhance computational efficiency, we introduce a clustering heuristic that utilizes both spatial and temporal aspects of the input data to accelerate rider-to-driver assignments. Finally, we conduct an extensive computational study using real-world datasets and surveys from Chicago to evaluate our model and algorithms at a city-wide scale.Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- Beyond the last mile: different spatial strategies to integrate on-demand services into public transport in a simplified cityPublic Transport, 2024
- Algorithms and computational study on a transportation system integrating public transit and ridesharing of personal vehiclesComputers & Operations Research, 2024
- An analysis of the mobility hub concept in the Netherlands: Historical lessons for its implementationJournal of Transport Geography, 2022
- A methodology to determine suitable locations for regional shared mobility hubsCase Studies on Transport Policy, 2022
- Shared automated vehicle fleet operations for first-mile last-mile transit connections with dynamic poolingComputers, Environment and Urban Systems, 2022
- Combustion-Based Transportation in a Carbon-Constrained World—A Review2018
- Is Uber a substitute or complement for public transit?Journal of Urban Economics, 2018
- Integrating shared autonomous vehicle in public transportation system: A supply-side simulation of the first-mile service in SingaporeTransportation Research Part A: Policy and Practice, 2018
- Enhancing urban mobility: Integrating ride-sharing and public transitComputers & Operations Research, 2018
- Greedy Local Improvement and Weighted Set Packing ApproximationJournal of Algorithms, 2001