Addressing the minimum fleet problem in on-demand urban mobility
Vazifeh Mohammed M. et al. — 2018
Résumé (FR)
Cet article propose une solution réseau pour déterminer le nombre minimal de véhicules nécessaires pour servir l’ensemble des trajets d’une ville sans délai supplémentaire pour les passagers. Les auteurs formulent le problème comme un problème de flux réseau sur un graphe de compatibilité des trajets, basé sur les données réelles de New York City. Les résultats montrent qu’une flotte de seulement 2 800 véhicules pourrait remplacer 14 000 taxis tout en maintenant le même service. La méthode est entièrement guidée par la demande observée et ne nécessite aucune hypothèse sur la distribution spatiale des requêtes. L’article établit une borne inférieure théorique sur la taille de flotte optimale, fondamentale pour la conception de systèmes MoD. Ce travail illustre comment l’exploitation de la structure demand-driven de la demande permet une optimisation radicale des ressources.
Summary (EN)
This paper proposes a network-based solution to determine the minimum number of vehicles needed to serve all trips in a city without any passenger delay. The authors formulate the problem as a network flow problem on a trip-compatibility graph, applied to real New York City taxi data. Results show that a fleet of only 2,800 vehicles could replace 14,000 taxis while maintaining equivalent service. The method is entirely driven by observed demand and requires no assumptions about spatial request distributions. The paper establishes a theoretical lower bound on optimal fleet size, which is fundamental for MoD system design. This work illustrates how exploiting the demand-driven structure of travel requests enables radical resource optimization.
Points clés
| Aspect | Détail |
|---|---|
| Méthode | Formulation du problème de flotte minimale comme un problème de flux réseau sur un graphe de compatibilité des trajets (bipartite matching) |
| Données | Données réelles de taxis de New York City (NYC) — plusieurs millions de courses observées |
| Résultat principal | 2 800 véhicules suffisent pour couvrir le service de 14 000 taxis, soit une réduction de 80 % de la flotte |
| Lien demand/offer-driven | La méthode est entièrement demand-driven : aucune hypothèse sur l’offre, la flotte minimale émerge directement de la structure de la demande observée |
| Lien réseau/flux | La concentration des flux sur un graphe de compatibilité révèle comment la structure spatiotemporelle de la demande détermine l’efficacité du partage de véhicules |
Lien avec la problématique
Cet article illustre directement la logique demand-driven : la taille optimale de la flotte n’est pas fixée a priori par une offre prédéfinie, mais émerge de la structure de la demande réelle, ce qui est au coeur de la complémentarité demand-driven / offer-driven dans les systèmes MoD. La modélisation en graphe de compatibilité des trajets est analogue à la concentration de flux que l’on observe dans les réseaux de transport structurés par des hubs, des points de montée/descente (PUDO) ou des lignes — la connexion entre deux trajets ne devient possible que si les flux se croisent dans le bon espace-temps. Ce résultat établit une borne théorique fondamentale pour la conception de systèmes de covoiturage, et pose la question de savoir dans quelle mesure une infrastructure d’offre (lignes fixes, hubs) peut amplifier ou contraindre cette optimisation demand-driven.