On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment
Alonso-Mora, J., Samaranayake, S., Wallar, A., Frazzoli, E., Rus, D. et al. — 2017
Résumé (FR)
Cet article présente un algorithme scalable pour le covoiturage à haute capacité en temps réel, capable de traiter des milliers de requêtes simultanément dans des environnements urbains denses. Les auteurs formalisent le problème d’affectation trajets-véhicules (trip-vehicle assignment) et proposent une approche anytime optimale fondée sur un graphe de partageabilité. La méthode est validée sur des données réelles de New York City avec une flotte de 3000 véhicules pouvant desservir 98 % de la demande. Les résultats montrent que le covoiturage à haute capacité peut réduire le nombre de véhicules nécessaires de 40 % par rapport aux courses individuelles. L’algorithme se décompose en deux étapes : la génération de groupes de voyageurs compatibles, puis l’optimisation de l’affectation à la flotte par programmation en nombres entiers. Ce travail est devenu une référence fondatrice dans le domaine de la mobilité à la demande et du ridesharing computationnel.
Summary (EN)
This paper presents a highly scalable anytime optimal algorithm for high-capacity real-time ride-sharing that scales to large numbers of passengers and trips in dense urban environments. The authors formalize the dynamic trip-vehicle assignment problem and propose an approach based on shareability graphs to generate optimal shared routes. The method is validated on real New York City taxi data, demonstrating that a fleet of 3000 vehicles can serve 98% of demand with high-capacity sharing. Results show that high-capacity ride-sharing reduces the number of vehicles required by roughly 40% compared to private rides. The algorithm proceeds in two stages: generating feasible groups of compatible travelers, then solving an integer program to optimally assign groups to vehicles. This work has become a foundational reference in the computational ride-sharing and mobility-on-demand literature.
Points clés
| Aspect | Détail |
|---|---|
| Thème | ridesharing-dynamic |
| Venue | Proceedings of the National Academy of Sciences (PNAS) |
| Mots-clés | ride-sharing, trip-vehicle assignment, real-time matching, high-capacity, on-demand mobility |
| DOI | 10.1073/pnas.1611675114 |