Recently ride-sharing platforms have struggled with a decreased supply of drivers, which has negatively impacted their passengers, by subjecting them to long delays and extremely high surge prices. An approach for mitigating these problems is for service providers to facilitate and coordinate carpooling via the recommendation of individually curated paths, not necessarily the shortest, for drivers towards completing their chosen rides. In this paper, we redesign the Weight Evolving Temporal graph structure to efficiently encode large dynamic road networks with temporal ride availability. Leveraging that graph structure, we efficiently define a polynomial-time optimal route recommendation algorithm that increases carpooling opportunities, taking into consideration the spatio-temporal constraints of both drivers and rides in such a highly-dynamic setting. Finally, we use simulations to demonstrate the effectiveness of these route recommendations, on both the driver and passenger experience.
|Original language||English (US)|
|Title of host publication||Proceedings - 2022 23rd IEEE International Conference on Mobile Data Management, MDM 2022|
|Publisher||Institute of Electrical and Electronics Engineers Inc.|
|Number of pages||6|
|State||Published - 2022|
|Event||23rd IEEE International Conference on Mobile Data Management, MDM 2022 - Virtual, Paphos, Cyprus|
Duration: Jun 6 2022 → Jun 9 2022
|Name||2022 23rd IEEE International Conference on Mobile Data Management (MDM)|
|Conference||23rd IEEE International Conference on Mobile Data Management, MDM 2022|
|Period||6/6/22 → 6/9/22|
Bibliographical noteFunding Information:
This work is supported by the National Science Foundation, USA, under Grants IIS-1907855 and CSR-1755788.
© 2022 IEEE.
- evolving graph
- ride assignment