Quantifying the benefits of vehicle pooling with shareability networks
Santi Paolo et al. — 2014
Résumé (FR)
Cet article introduit la notion de réseau de partageabilité, un cadre graphe-théorique permettant de modéliser les bénéfices collectifs du covoiturage en fonction de l’inconvénient accepté par les passagers. Les auteurs appliquent ce cadre à un jeu de données massif de courses de taxi à New York, comprenant 150 millions de trajets. Les résultats montrent que 80 % des trajets pourraient être partagés avec seulement 5 minutes de délai supplémentaire, réduisant de moitié le nombre de véhicules nécessaires. Le réseau de partageabilité permet de calculer efficacement les stratégies optimales de partage sur des données à grande échelle. Ce travail constitue une avancée algorithmique majeure en transformant le problème spatio-temporel de covoiturage en un problème de graphe résolu efficacement. Les implications pour la planification de la mobilité urbaine et la réduction des émissions sont considérables.
Summary (EN)
This paper introduces the notion of shareability network, a graph-theoretic framework allowing the modeling of collective benefits of ride-sharing as a function of passenger inconvenience. The method is applied to a dataset of 150 million taxi trips in New York City to quantify sharing potential at urban scale. Results show that 80% of trips could be shared with only 5 minutes of additional delay, halving the number of required vehicles. The shareability network enables efficient computation of optimal sharing strategies on massive datasets. This constitutes a major algorithmic breakthrough by translating spatio-temporal sharing problems into graph-theoretic frameworks. The implications for urban mobility planning and emissions reduction are substantial.
Points clés
| Aspect | Détail |
|---|---|
| Cadre méthodologique | Réseau de partageabilité : graphe où chaque noeud est un trajet et chaque arête indique la compatibilité au partage selon un seuil de délai acceptable |
| Donnée empirique | 150 millions de courses de taxi à New York City — l’une des premières analyses de covoiturage à cette échelle |
| Résultat principal | 80 % des trajets partageables avec un délai maximal de 5 minutes, conduisant à une réduction de 40 % du kilométrage total parcouru |
| Complexité algorithmique | Réduction du problème NP-difficile de matching spatio-temporel en un problème de couplage maximum dans un graphe, résolu efficacement à grande échelle |
| Paramètre clé | Le délai acceptable (inconvenience) comme curseur continu contrôlant le compromis entre taux de partage et qualité de service |
Lien avec mes recherches
Ce travail fonde formellement la notion de partageabilité comme propriété émergente d’un système de demande de mobilité — une perspective directement pertinente pour l’étude de l’émergence dans les systèmes multi-agents de mobilité partagée. Le réseau de partageabilité constitue un outil de modélisation de la demande applicable aux contextes de covoiturage longue distance étudiés dans ma thèse, notamment pour caractériser la structure de la demande latente et les conditions d’émergence de la viabilité d’un service. La formalisation graphe-théorique offre également un cadre de référence pour comparer les approches de simulation multi-agents avec des méthodes analytiques exactes.