T-share: A large-scale dynamic taxi ridesharing service
Ma Shuo et al. — 2013
Résumé (FR)
Cet article définit formellement le problème de covoiturage dynamique en taxi et propose T-share, un service de partage de taxi à grande échelle basé sur la demande en temps réel. Les auteurs développent un algorithme efficace qui traite les requêtes des passagers dès leur arrivée et génère des itinéraires partagés réduisant significativement la distance totale parcourue. Le système utilise un index spatial et temporel pour associer rapidement des passagers ayant des trajets compatibles, rendant l’approche scalable à l’échelle d’une ville. Les expériences menées sur des données réelles de taxis de Pékin montrent une réduction de 13 % des kilomètres parcourus et un temps de calcul de l’ordre de la seconde. T-share illustre comment un système entièrement guidé par la demande peut concentrer les flux de passagers sans infrastructure fixe. Ce travail est fondateur dans la conception de systèmes MoD basés sur la demande agrégée en temps réel.
Summary (EN)
This paper formally defines the dynamic taxi ridesharing problem and proposes T-share, a large-scale taxi sharing service based on real-time demand. The authors develop an efficient algorithm that processes passenger requests upon arrival and generates shared itineraries that significantly reduce total travel distance. The system uses a spatial and temporal index to rapidly match passengers with compatible trips, making the approach scalable at the city level. Experiments on real Beijing taxi data show a 13% reduction in kilometers traveled with computation times on the order of seconds. T-share illustrates how a fully demand-driven system can concentrate passenger flows without fixed infrastructure. This work is foundational for the design of MoD systems based on real-time aggregated demand.
Points clés
| Aspect | Détail |
|---|---|
| Méthode | Algorithme de matching en temps réel utilisant un index spatio-temporel pour associer des requêtes passagers à des taxis en circulation |
| Données | Traces GPS de taxis réels à Pékin (large dataset empirique) |
| Résultat principal | Réduction de 13 % des kilomètres parcourus, avec un temps de calcul de l’ordre de la seconde à l’échelle d’une ville |
| Lien demand/offer-driven | Système purement demand-driven : aucune ligne fixe ni infrastructure prédéfinie, le service émerge entièrement des requêtes en temps réel |
| Lien réseau/flux | La concentration des flux passagers est obtenue dynamiquement par agrégation des trajets compatibles, sans recours à des hubs ou points de montée/descente fixes |
Lien avec la problématique
T-share constitue une référence fondatrice pour les systèmes MoD entièrement demand-driven, dans lesquels l’absence d’infrastructure fixe est compensée par la densité de la demande et la puissance algorithmique du matching en temps réel. Ce modèle se distingue des approches offer-driven (lignes fixes, hubs, PUDO prédéfinis) qui concentrent les flux par la structure du réseau plutôt que par l’agrégation dynamique des requêtes. La complémentarité entre les deux logiques est directement posée par ce travail : dans des zones ou des plages horaires à faible densité de demande, un système purement demand-driven comme T-share perd en efficacité, ce qui justifie l’introduction de structures réseaux partielles pour concentrer et fiabiliser les flux.