Real-time city-scale ridesharing via linear assignment problems
Simonetto, A., Monteil, J., Gambella, C. et al. — 2019
Résumé (FR)
Cet article propose un algorithme dynamique de covoiturage à l’échelle d’une ville, basé sur la reformulation du problème en un problème d’affectation linéaire (linear assignment problem, LAP). L’architecture fédérée d’optimisation permet une distribution des calculs et une grande efficacité computationnelle. L’algorithme résultant est jusqu’à quatre fois plus rapide que l’état de l’art, même exécuté sur du matériel moins spécialisé, tout en atteignant une qualité de service comparable. La méthode est validée sur des scénarios urbains réels et démontre sa capacité à fonctionner en temps réel à grande échelle. Les auteurs discutent des compromis entre optimalité et rapidité d’exécution dans le contexte de déploiements opérationnels. Ce travail représente une avancée significative pour le déploiement pratique d’algorithmes de covoiturage à l’échelle des villes.
Summary (EN)
This paper proposes a dynamic ridesharing algorithm at the city scale, based on reformulating the problem as a linear assignment problem (LAP). A federated optimization architecture enables distributed computation and high computational efficiency. The resulting algorithm is up to four times faster than the state-of-the-art, even on less dedicated hardware, while achieving comparable service quality. The method is validated on real urban scenarios and demonstrates the ability to operate in real-time at large scale. The authors discuss trade-offs between optimality and execution speed in the context of operational deployments. This work represents a significant advance for the practical deployment of city-scale ridesharing algorithms.
Points clés
| Aspect | Détail |
|---|---|
| Thème | ridesharing-dynamic |
| Venue | Transportation Research Part C: Emerging Technologies |
| Mots-clés | linear assignment, ridesharing, real-time, city-scale, computational efficiency |
| DOI | 10.1016/j.trc.2019.01.003 |