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 scalable pour le covoiturage à haute capacité à la demande, validé sur les données de taxis de New York City. Les auteurs proposent une méthode de graphe shareability qui permet de combiner dynamiquement des trajets compatibles en temps réel. Le système est capable de servir 98 % de la demande avec seulement 15 % des véhicules d’une flotte de taxis traditionnelle. L’algorithme fonctionne en attribuant des groupes de passagers à des véhicules de capacité variable (jusqu’à 10 places). Les résultats montrent un temps d’attente moyen de 2,8 minutes et un délai de trajet de 3,5 minutes pour les passagers. Ce travail démontre que la concentration des flux de demande par groupement dynamique améliore drastiquement l’efficacité du système.
Summary (EN)
This paper presents a highly scalable anytime optimal algorithm for on-demand high-capacity ride-sharing, validated using New York City taxi data. The authors propose a shareability network-based approach that dynamically groups compatible trips in real time. The system can serve 98% of demand with only 15% of a traditional taxi fleet using vehicles of capacity up to 10. The algorithm assigns groups of passengers to vehicles through an integer linear programming formulation solved at each time step. Results show a mean waiting time of 2.8 minutes and a mean trip delay of 3.5 minutes. This work demonstrates that concentrating demand flows through dynamic grouping drastically improves system efficiency.
Points clés
| Aspect | Détail |
|---|---|
| Méthode | Graphe de shareability + programmation linéaire en nombres entiers résolue à chaque pas de temps pour l’affectation dynamique passagers-véhicules |
| Données | Données réelles de taxis de New York City (trajets, origines-destinations, horodatages) |
| Résultat principal | 98 % de la demande servie avec seulement 15 % des véhicules d’une flotte traditionnelle ; attente moyenne 2,8 min, délai moyen 3,5 min |
| Lien demand/offer-driven | Le système est entièrement piloté par la demande : les routes et groupements émergent dynamiquement des requêtes passagers, sans lignes prédéfinies |
| Lien réseau/flux | La concentration des flux par groupement dynamique reproduit l’effet de massification d’un réseau structuré, améliorant l’efficacité sans infrastructure fixe |
Lien avec la problématique
Cet article illustre le paradigme demand-driven poussé à l’extrême : l’offre de transport (véhicules, routes, groupements) est entièrement déterminée en temps réel par l’agrégation des demandes individuelles, sans structure de réseau préétablie. Il constitue ainsi un point de comparaison central pour la complémentarité demand-driven/offer-driven, en montrant jusqu’où la flexibilité pure peut aller mais aussi ses limites en contexte de faible densité de demande. La concentration des flux obtenue algorithmiquement dans ce modèle urban-dense rappelle le rôle que jouent les hubs, points d’arrêt et lignes structurantes dans un réseau offer-driven, suggérant que la massification des flux est une propriété système recherchée indépendamment du paradigme.