A real-time algorithm to solve the peer-to-peer ride-matching problem in a flexible ridesharing system
Masoud Neda et al. — 2017
Résumé (FR)
Cet article présente un algorithme en temps réel pour résoudre de manière optimale le problème de correspondance peer-to-peer dans un système de covoiturage flexible. Les auteurs introduisent la méthode ESTAM (ellipsoid spatio-temporal accessibility method) pour réduire l’espace de recherche et construire le réseau de faisabilité temporel de chaque passager. Le problème est résolu par programmation dynamique, maximisant le nombre de passagers servis tout en minimisant les transferts et les temps d’attente. La conception est entièrement centrée sur la demande des usagers (passenger-centric), permettant à chaque passager de déclarer ses contraintes de voyage individuellement. Les résultats de simulation montrent que l’algorithme peut traiter des milliers de requêtes par minute avec un taux d’appariement élevé. Ce travail démontre que les approches demand-driven permettent de concevoir des systèmes de mobilité partagée flexibles et efficaces.
Summary (EN)
This paper presents a real-time algorithm to optimally solve the peer-to-peer ride-matching problem in a flexible ridesharing system. The authors introduce the ESTAM (ellipsoid spatio-temporal accessibility method) to reduce the search space and construct each passenger’s temporally feasible network. The problem is solved via dynamic programming, maximizing the number of served passengers while minimizing transfers and waiting times. The design is fully passenger-centric, allowing each traveler to declare individual trip constraints. Simulation results show that the algorithm can process thousands of requests per minute with a high matching rate. This work demonstrates that demand-driven approaches enable the design of flexible and efficient shared mobility systems.
Points clés
| Aspect | Détail |
|---|---|
| Méthode | ESTAM (ellipsoid spatio-temporal accessibility method) + programmation dynamique pour la construction et résolution du réseau de faisabilité temporelle |
| Données | Simulations synthétiques de requêtes de covoiturage avec contraintes spatio-temporelles individuelles par passager |
| Résultat principal | L’algorithme traite des milliers de requêtes par minute avec un taux d’appariement élevé, tout en minimisant transferts et temps d’attente |
| Lien demand/offer-driven | Système entièrement passenger-centric (demand-driven) : chaque usager déclare ses propres contraintes, sans offre prédéfinie de lignes ou d’horaires |
| Lien réseau/flux | La méthode ESTAM concentre la recherche dans un ellipsoïde spatio-temporel, structurant implicitement les flux vers des zones de rencontre faisables analogues à des hubs |
Lien avec la problématique
Cet article illustre paradigmatiquement l’approche demand-driven pure : l’offre de transport émerge entièrement des contraintes individuelles des usagers, sans réseau prédéfini, ce qui le place à l’opposé des systèmes offer-driven classiques et permet d’explorer la complémentarité entre ces deux logiques. La méthode ESTAM, en délimitant un ellipsoïde spatio-temporel de faisabilité, introduit implicitement une concentration des flux dans l’espace-temps, rejoignant la problématique de la structuration par hubs, PUDO et lignes qui concentrent les flux pour maximiser l’efficacité du partage. Ce travail fournit ainsi une base algorithmique pour comprendre comment un système demand-driven peut, par optimisation, faire émerger des structures de réseau proches de celles conçues a priori dans les systèmes hybrides.