On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment
Alonso-Mora Javier et al. — 2017
Résumé (FR)
Cet article présente un algorithme optimal et hautement évolutif pour affecter dynamiquement des groupes de passagers à des véhicules partagés en temps réel. Validé sur les données de taxi de New York, l’algorithme montre que 2 000 véhicules de capacité 10 peuvent servir 98 % de la demande avec un temps d’attente moyen de 2,8 minutes. Le cadre mathématique repose sur une décomposition du problème en graphes de partage et en assignation de véhicules. La méthode intègre les contraintes de capacité, de fenêtres temporelles et de détours maximaux des passagers. Ce travail démontre que le covoiturage à haute capacité peut remplacer significativement la flotte traditionnelle de taxis. Les résultats ont des implications directes pour la conception de services de mobilité partagée à la demande.
Summary (EN)
This paper presents a highly scalable anytime optimal algorithm for dynamically assigning groups of passengers to shared vehicles in real time. Validated on New York City taxi data, the algorithm shows that 2,000 vehicles of capacity 10 can serve 98% of demand with a mean waiting time of 2.8 minutes. The mathematical framework decomposes the problem into shareability graphs and vehicle assignment. The method integrates capacity constraints, time windows, and maximum passenger detours. This work demonstrates that high-capacity ride-sharing can significantly replace traditional taxi fleets. The results have direct implications for the design of mobility-on-demand services.
Points clés
| Aspect | Détail |
|---|---|
| Algorithme | Affectation dynamique en temps réel via graphes de partageabilité (shareability graphs) et assignation optimale véhicule-trajet |
| Validation empirique | Données de taxi de New York City ; 2 000 véhicules de capacité 10 couvrent 98 % de la demande |
| Performance | Temps d’attente moyen de 2,8 minutes ; réduction significative du nombre de véhicules nécessaires par rapport à la flotte taxi classique |
| Contraintes modélisées | Capacité des véhicules, fenêtres temporelles d’acceptabilité, détour maximal par passager |
| Passage à l’échelle | Approche anytime : fournit une solution admissible à tout moment et l’améliore tant que du temps de calcul est disponible |
Lien avec mes recherches
Ce travail constitue une référence fondatrice pour l’étude du covoiturage à la demande à haute capacité et de l’optimisation de flotte en temps réel, deux dimensions centrales de ma thèse sur l’émergence de propriétés dans les systèmes de mobilité partagée multi-agents. La décomposition en graphes de partageabilité offre un cadre formel pour analyser comment des comportements collectifs efficaces (fort taux de service, faible temps d’attente) émergent d’interactions locales entre agents-passagers et agents-véhicules. Les résultats empiriques sur le remplacement de la flotte taxi constituent également un point de comparaison de référence pour évaluer les gains systémiques produits par des mécanismes d’appariement dynamique dans mes simulations multi-agents.