Addressing the minimum fleet problem in on-demand urban mobility
Vazifeh, M.M., Santi, P., Resta, G., Strogatz, S.H., Ratti, C. et al. — 2018
Résumé (FR)
Cet article résout le problème de la flotte minimale de véhicules nécessaire pour satisfaire toutes les courses d’un service de mobilité à la demande sans induire de délai pour les passagers. Les auteurs proposent un algorithme polynomial optimal basé sur un réseau de partage de véhicules (vehicle-sharing network) représenté sous forme de graphe. La méthode est appliquée à des données réelles de taxis de New York City et démontre qu’une coordination optimale permet de réduire considérablement la taille de la flotte nécessaire. Les résultats indiquent qu’avec une coordination parfaite, environ 40 % des véhicules actuellement utilisés suffiraient à couvrir la demande existante. Ce travail établit un lien entre la théorie des graphes et l’optimisation de flottes de transport à la demande. La publication dans Nature souligne l’importance et la généralité des implications de ces résultats pour la mobilité urbaine.
Summary (EN)
This paper solves the minimum fleet problem — determining the smallest number of vehicles needed to serve all trips in an on-demand mobility service without delaying any passenger. The authors propose an optimal polynomial-time algorithm based on a vehicle-sharing network represented as a graph. The method is applied to real New York City taxi data and demonstrates that optimal coordination can dramatically reduce the required fleet size. Results indicate that with perfect coordination, approximately 40% of currently used vehicles would suffice to cover existing demand. This work establishes a link between graph theory and fleet optimization for on-demand transportation. Publication in Nature underscores the importance and generality of these findings for urban mobility.
Points clés
| Aspect | Détail |
|---|---|
| Thème | ridesharing-dynamic |
| Venue | Nature |
| Mots-clés | minimum fleet, on-demand mobility, vehicle-sharing network, graph theory, urban transportation |
| DOI | 10.1038/s41586-018-0095-1 |