Algorithms for trip-vehicle assignment in ride-sharing
Bei, X., Zhang, S. et al. — 2018
Résumé (FR)
Cet article propose des algorithmes d’approximation pour le problème d’affectation trajets-véhicules dans les systèmes de covoiturage, un problème central dans l’optimisation de la mobilité à la demande. Les auteurs formalisent le problème sous forme combinatoire et développent des garanties théoriques sur la qualité des solutions produites. Différents algorithmes sont proposés selon que la demande est connue à l’avance (offline) ou arrive en ligne (online). Les résultats théoriques sont complétés par des expériences numériques validant l’efficacité pratique des approches. L’analyse de complexité démontre les limites fondamentales et les compromis inhérents au problème d’affectation dans le covoiturage. Ce travail fournit des fondements algorithmiques rigoureux pour la conception de systèmes de covoiturage optimisés.
Summary (EN)
This paper proposes approximation algorithms for the trip-vehicle assignment problem in ride-sharing systems, a central problem in on-demand mobility optimization. The authors formalize the problem in combinatorial terms and develop theoretical guarantees on the quality of produced solutions. Different algorithms are proposed depending on whether demand is known in advance (offline) or arrives online. Theoretical results are complemented by numerical experiments validating the practical efficiency of the approaches. Complexity analysis demonstrates the fundamental limits and inherent trade-offs of the assignment problem in ride-sharing. This work provides rigorous algorithmic foundations for the design of optimized ride-sharing systems.
Points clés
| Aspect | Détail |
|---|---|
| Thème | ridesharing-dynamic |
| Venue | Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18) |
| Mots-clés | trip-vehicle assignment, approximation algorithm, ride-sharing, combinatorial optimization, online algorithms |
| DOI | N/A |