Real-time City-scale Ridesharing via Linear Assignment Problems
Simonetto Andrea et al. — 2019
Résumé (FR)
Cet article propose un algorithme de covoiturage dynamique computationnellement efficace en formulant le problème d’affectation comme une série de problèmes d’affectation linéaire entre véhicules de la flotte et requêtes de trajet. L’architecture fédérée d’optimisation permet une gestion centralisée et évolutive de l’offre de mobilité en temps réel. L’algorithme est jusqu’à quatre fois plus rapide que l’état de l’art tout en atteignant une qualité de service similaire. La méthode s’appuie sur une structure réseau pour concentrer et organiser l’affectation des flux passagers aux véhicules disponibles. Les expériences à l’échelle d’une ville démontrent la faisabilité opérationnelle d’une gestion centralisée de flottes importantes. Ce travail illustre comment des approches offer-driven basées sur l’optimisation peuvent s’appliquer efficacement à la gestion temps réel de la mobilité partagée.
Summary (EN)
This paper proposes a computationally efficient dynamic ridesharing algorithm by formulating the assignment problem as a series of linear assignment problems between fleet vehicles and customer trip requests. The federated optimization architecture enables centralized, scalable supply management of shared mobility in real time. The algorithm is up to four times faster than the state of the art while achieving similar service quality. The method relies on a network structure to concentrate and organize the assignment of passenger flows to available vehicles. City-scale experiments demonstrate the operational feasibility of centralized management of large fleets. This work illustrates how supply-driven optimization approaches can be effectively applied to real-time shared mobility management.
Points clés
| Aspect | Détail |
|---|---|
| Méthode | Série de problèmes d’affectation linéaire (LAP) entre véhicules et requêtes ; architecture fédérée d’optimisation centralisée |
| Données | Expériences simulées à l’échelle d’une ville (city-scale) avec flottes importantes et demandes temps réel |
| Résultat principal | Algorithme jusqu’à 4x plus rapide que l’état de l’art, avec une qualité de service comparable |
| Lien demand/offer-driven | Approche purement offer-driven : l’optimisation pilote l’affectation depuis l’offre (flotte), sans adaptation de la demande |
| Lien réseau/flux | La structure réseau concentre les flux passagers et organise l’affectation aux véhicules disponibles, illustrant le rôle des noeuds de correspondance |
Lien avec la problématique
Cet article illustre la logique offer-driven dans sa forme la plus aboutie : la flotte est gérée de manière centralisée et optimisée pour absorber la demande telle qu’elle se présente, sans chercher à la moduler. Il constitue ainsi un point de comparaison structurant pour explorer la complémentarité demand-driven / offer-driven, où l’on peut questionner ce que gagnerait un tel système à intégrer des mécanismes d’influence sur la demande (hubs, lignes virtuelles, PUDO). La dépendance explicite à une structure réseau pour concentrer les flux passagers rejoint directement la thèse sur le rôle des noeuds et lignes de transport dans l’efficacité de la mobilité partagée.