Exact Set Packing in Multimodal Transportation with Ridesharing System for First/Last Mile
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913819546091520 |
|---|---|
| author | Gu, Qian-Ping Liang, Jiajian Leo |
| author_facet | Gu, Qian-Ping Liang, Jiajian Leo |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_01989 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Exact Set Packing in Multimodal Transportation with Ridesharing System for First/Last Mile Gu, Qian-Ping Liang, Jiajian Leo Data Structures and Algorithms 68W25, 68Q25 F.2 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. |
| title | Exact Set Packing in Multimodal Transportation with Ridesharing System for First/Last Mile |
| topic | Data Structures and Algorithms 68W25, 68Q25 F.2 |
| url | https://arxiv.org/abs/2505.01989 |