Fast Many-to-Many Routing for Ridesharing with Multiple Pickup and Dropoff Locations
Laupichler Moritz et al. — 2023
Résumé (FR)
Cet article introduit KaRRi, un algorithme optimisé pour la planification de flottes de véhicules partagés permettant de gérer de nombreux points de prise en charge et de dépose. L’approche accélère l’insertion de nouveaux clients dans des routes existantes et généralise les fonctions objectif pour mieux refléter les préférences opérationnelles. Les auteurs démontrent que KaRRi surpasse significativement les méthodes précédentes en termes de vitesse d’exécution. L’intégration de points de rencontre flexibles permet de réduire les coûts opérationnels des flottes de jusqu’à 15 %, tout en diminuant les temps d’attente et de trajet des passagers. L’algorithme est validé sur des données réelles de transport à la demande. Ces résultats montrent que la multiplicité des options PUDO est un levier majeur d’efficacité pour les systèmes de covoiturage à grande échelle.
Summary (EN)
This paper introduces KaRRi, an optimized algorithm for shared vehicle fleet scheduling that handles numerous pick-up and drop-off locations. The approach accelerates the insertion of new customers into existing routes and generalizes objective functions to better reflect operational preferences. The authors demonstrate that KaRRi significantly outperforms previous methods in terms of execution speed. Integrating flexible meeting points reduces vehicle fleet operating costs by up to 15% while also reducing passenger wait and trip times. The algorithm is validated on real on-demand transportation data. These results show that multiple PUDO options are a major efficiency lever for large-scale ridesharing systems.
Points clés
| Aspect | Détail |
|---|---|
| Thème | pudo-optimization-2020 |
| Venue | European Symposium on Algorithms (ESA 2023) |
| Mots-clés | ridesharing routing, multiple PUDO, fleet scheduling, meeting points, algorithm |
| DOI | 10.48550/arXiv.2305.05417 |
Lien avec la problématique
Cet article contribue à la compréhension de la complémentarité offre↔demande dans les systèmes de covoiturage urbain/périurbain, en lien avec l’utilisation d’un réseau structurant (PUDO, hubs, lignes) pour concentrer les flux.