Near-Optimal Emission-Aware Online Ride Assignment Algorithm for Peak Demand Hours
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916936500117504 |
|---|---|
| author | Zeynali, Ali Sahebdel, Mahsa Bashir, Noman Sitaraman, Ramesh K. Hajiesmaili, Mohammad |
| author_facet | Zeynali, Ali Sahebdel, Mahsa Bashir, Noman Sitaraman, Ramesh K. Hajiesmaili, Mohammad |
| contents | Ridesharing has experienced significant global growth over the past decade and is becoming an integral component of modern transportation systems. However, despite their benefits, ridesharing platforms face fundamental inefficiencies that contribute to negative environmental impacts. A prominent source of such inefficiency is the deadhead miles. This issue becomes especially severe during high-demand periods, when the volume of ride requests exceeds the available driver supply, leading to suboptimal rider-to-driver assignments, longer deadhead trips, and increased emissions. Although limiting these unproductive miles can reduce emissions, doing so may increase passenger wait times due to limited driver availability, thereby degrading the overall service experience. In this paper, we introduce LARA, an online rider-to-driver assignment algorithm that dynamically adjusts the maximum allowable distance between rider and drivers and assigns ride requests accordingly. While LARA is applicable in general settings, it is particularly effective during peak demand periods, achieving reductions in both emissions and wait times. We provide theoretical guarantees showing that LARA achieves near-optimal performance in online environments, with respect to an optimal offline benchmark. Beside our theoretical analysis, our empirical evaluations on both synthetic and real-world datasets show that LARA achieves up to a 34% reduction in carbon emissions and up to a 50% decrease in rider wait times, compared to state-of-the-art baselines. While prior work has explored emission-aware ride assignment, LARA is, to our knowledge, the first algorithm to offer both rigorous theoretical guarantees and strong empirical performance. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_01412 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Near-Optimal Emission-Aware Online Ride Assignment Algorithm for Peak Demand Hours Zeynali, Ali Sahebdel, Mahsa Bashir, Noman Sitaraman, Ramesh K. Hajiesmaili, Mohammad Systems and Control Ridesharing has experienced significant global growth over the past decade and is becoming an integral component of modern transportation systems. However, despite their benefits, ridesharing platforms face fundamental inefficiencies that contribute to negative environmental impacts. A prominent source of such inefficiency is the deadhead miles. This issue becomes especially severe during high-demand periods, when the volume of ride requests exceeds the available driver supply, leading to suboptimal rider-to-driver assignments, longer deadhead trips, and increased emissions. Although limiting these unproductive miles can reduce emissions, doing so may increase passenger wait times due to limited driver availability, thereby degrading the overall service experience. In this paper, we introduce LARA, an online rider-to-driver assignment algorithm that dynamically adjusts the maximum allowable distance between rider and drivers and assigns ride requests accordingly. While LARA is applicable in general settings, it is particularly effective during peak demand periods, achieving reductions in both emissions and wait times. We provide theoretical guarantees showing that LARA achieves near-optimal performance in online environments, with respect to an optimal offline benchmark. Beside our theoretical analysis, our empirical evaluations on both synthetic and real-world datasets show that LARA achieves up to a 34% reduction in carbon emissions and up to a 50% decrease in rider wait times, compared to state-of-the-art baselines. While prior work has explored emission-aware ride assignment, LARA is, to our knowledge, the first algorithm to offer both rigorous theoretical guarantees and strong empirical performance. |
| title | Near-Optimal Emission-Aware Online Ride Assignment Algorithm for Peak Demand Hours |
| topic | Systems and Control |
| url | https://arxiv.org/abs/2411.01412 |