Dans cet article, nous proposons une approche multi-agent pour résoudre le problème du covoiturage dynamique multi-saut. Dans notre système, les passagers et les conducteurs sont représentés comme des agents autonomes et rationnels en perpétuelle interaction pour satisfaire leurs propres objectifs comme leur temps d’attente ou leur temps de trajet par exemple. Dans la solution proposée, les agents conducteurs et passagers ont une perception modélisée dynamiquement en utilisant des R-Arbres. Nous modélisons leurs préférences en matière de détour et de trajet et montrons l’impact de celles-ci sur la résolution d’une instance de covoiturage dynamique. Les résultats présentés montrent que notre système permet de traiter dynamiquement des requêtes complexes de passagers tout en minimisant l’impact du partage de trajet pour les conducteurs, et ce, pour un large spectre de préférences et de comportements.
In this paper, we propose a multi-agent approach to solve the dynamic multi-hop ridesharing problem. In our system, passengers and drivers are represented as autonomous and rational agents in perpetual interaction to satisfy their own objectives such as their waiting time or their travel time. In the proposed solution, driver and passenger agents have a dynamically modeled perception using R-Trees. We model their detour and route preferences and show the impact of these on the resolution of a dynamic ridesharing instance. The presented results show that our system dynamically handles complex passenger requests while minimizing the impact of ridesharing for drivers across a wide spectrum of preferences and behaviors.
Keywords: Ridesharing, Simulation, Optimization, Agents
Corwin Fèvre 1 ; Philippe Mathieu 1 ; Hayfa Zgaya-Biau 1 ; Slim Hammadi 1

@article{ROIA_2024__5_4_37_0, author = {Corwin F\`evre and Philippe Mathieu and Hayfa Zgaya-Biau and Slim Hammadi}, title = {Covoiturage dynamique multi-saut avec mod\'elisation des pr\'ef\'erences utilisateur}, journal = {Revue Ouverte d'Intelligence Artificielle}, pages = {37--61}, publisher = {Association pour la diffusion de la recherche francophone en intelligence artificielle}, volume = {5}, number = {4}, year = {2024}, doi = {10.5802/roia.86}, language = {fr}, url = {https://roia.centre-mersenne.org/articles/10.5802/roia.86/} }
TY - JOUR AU - Corwin Fèvre AU - Philippe Mathieu AU - Hayfa Zgaya-Biau AU - Slim Hammadi TI - Covoiturage dynamique multi-saut avec modélisation des préférences utilisateur JO - Revue Ouverte d'Intelligence Artificielle PY - 2024 SP - 37 EP - 61 VL - 5 IS - 4 PB - Association pour la diffusion de la recherche francophone en intelligence artificielle UR - https://roia.centre-mersenne.org/articles/10.5802/roia.86/ DO - 10.5802/roia.86 LA - fr ID - ROIA_2024__5_4_37_0 ER -
%0 Journal Article %A Corwin Fèvre %A Philippe Mathieu %A Hayfa Zgaya-Biau %A Slim Hammadi %T Covoiturage dynamique multi-saut avec modélisation des préférences utilisateur %J Revue Ouverte d'Intelligence Artificielle %D 2024 %P 37-61 %V 5 %N 4 %I Association pour la diffusion de la recherche francophone en intelligence artificielle %U https://roia.centre-mersenne.org/articles/10.5802/roia.86/ %R 10.5802/roia.86 %G fr %F ROIA_2024__5_4_37_0
Corwin Fèvre; Philippe Mathieu; Hayfa Zgaya-Biau; Slim Hammadi. Covoiturage dynamique multi-saut avec modélisation des préférences utilisateur. Revue Ouverte d'Intelligence Artificielle, Post-actes des Journées Francophones sur les Systèmes Multi-Agents (JFSMA 2023), Volume 5 (2024) no. 4, pp. 37-61. doi : 10.5802/roia.86. https://roia.centre-mersenne.org/articles/10.5802/roia.86/
[1] Search Space Reductions for Nearest-Neighbor Queries, Theory and Applications of Models of Computation (Manindra Agrawal; Dingzhu Du; Zhenhua Duan; Angsheng Li, eds.), Volume 4978, Springer Berlin Heidelberg, Berlin, Heidelberg, 2008, pp. 554-567 | DOI | Zbl
[2] Dynamic Ride-Sharing : A Simulation Study in Metro Atlanta, Procedia – Social and Behavioral Sciences, Volume 17 (2011), pp. 532-550 | DOI
[3] Dynamic Modeling of a Disturbance in a Multi-Agent System for Traffic Regulation, Decision Support Systems, Volume 41 (2005) no. 1, pp. 131-146 | DOI
[4] A Multi-Agent system for dynamic ride sharing, 2009 International Conference on Industrial and Information Systems (ICIIS), IEEE, 2009, pp. 199-203 | DOI
[5] A Tabu Search Based Metaheuristic for Dynamic Carpooling Optimization, Computers & Industrial Engineering, Volume 140 (2020), 106217 | DOI
[6] OSMnx : New Methods for Acquiring, Constructing, Analyzing, and Visualizing Complex Street Networks, Computers, Environment and Urban Systems, Volume 65 (2017), pp. 126-139 | DOI
[7] Flexible Aggregate Nearest Neighbor Queries and its Keyword-Aware Variant on Road Networks, IEEE Transactions on Knowledge and Data Engineering, Volume 33 (2021) no. 12, pp. 3701-3715 | DOI
[8] The Dial-a-Ride Problem : Models and Algorithms, Ann Oper Res, Volume 153 (2007), pp. 29-46 | DOI | MR | Zbl
[9] The Pickup and Delivery Problem with Transfers, Eur. J. Oper. Res., Volume 200 (2010) no. 3, pp. 711-724 | DOI | MR | Zbl
[10] Un Modèle Agent Générique Pour La Comparaison d’approches d’allocation de Ressources Dans Le Domaine Du Transport à La Demande, JFSMA29, Cépaduès, 2021, pp. 127-136
[11] Optimization of Dynamic Ridesharing Systems, Transportation Research Record : Journal of the Transportation Research Board, Volume 2359 (2013) no. 1, pp. 44-50 | DOI
[12] Usage Des Parkings Relais Dans Les Comportements de Déplacements Intermodaux, JFSMA29, June 28-30, 2021, Cépaduès, 2021, pp. 83-92
[13] Multi-Agent Systems : An Introduction to Distributed Artificial Intelligence, 1999
[14] Multi-Agent Systems and R-Trees for Dynamic and Optimised Ridesharing, 2021 IEEE International Conference on Systems, Man, and Cybernetics (SMC), 2021, pp. 1352-1358 | DOI
[15] R-trees : a dynamic index structure for spatial searching (SIGMOD Rec.), Volume 14, Association for Computing Machinery, New York, NY, USA, 1984 no. 2, pp. 47-57 | DOI
[16] Evolutionary Multiobjective Route Planning in Dynamic Multi-hop Ridesharing, Evolutionary Computation in Combinatorial Optimization, Springer, Berlin, Heidelberg, 2011, pp. 84-95 | DOI
[17] Modeling the Multihop Ridematching Problem with Time Windows and Solving It Using Genetic Algorithms, Proceedings - International Conference on Tools with Artificial Intelligence, ICTAI, Volume 1 (2012), pp. 89-96 | DOI
[18] Distributed Graphs for Solving Co-Modal Transport Problems, 2011 14th International IEEE Conference on Intelligent Transportation Systems (ITSC), 2011, pp. 1150-1155 | DOI
[20] A Model of Multimodal Ridesharing and Its Analysis, 2016 17th IEEE International Conference on Mobile Data Management (MDM), IEEE, 2016, pp. 164-173 | DOI
[21] Analysis and Evaluation of the Slugging Form of Ridesharing, SIGSPATIAL’13, ACM Press, Orlando, Florida, 2013, pp. 64-73 | DOI
[23] Spatial Indexing Techniques, Encyclopedia of Database Systems, Springer New York, New York, NY, 2014, pp. 1-7 | DOI
[24] A Real-Time Algorithm to Solve the Peer-to-Peer Ride-Matching Problem in a Flexible Ridesharing System, Transportation Research Part B : Methodological, Volume 106 (2017), pp. 218-236 | DOI
[25] Effective Evaluation of Autonomous Taxi Fleets, Proceedings of the 10th International Conference on Agents and Artificial Intelligence – Volume 1 : ICAART,, SciTePress, 2018, pp. 297-304 | DOI
[26] Group nearest neighbor queries, Proceedings. 20th International Conference on Data Engineering, 2004, pp. 301-312 | DOI
[27] Aggregate Nearest Neighbor Queries in Spatial Databases, ACM Transactions on Database Systems, Volume 30 (2005) no. 2, pp. 529-576 | DOI
[28] Query Processing in Spatial Network Databases, Proceedings 2003 VLDB Conference, Elsevier, 2003, pp. 802-813 | DOI
[29] Cours d’économie politique, Librairie Droz, 1964 | DOI
[30] Trip-Based Graph Partitioning in Dynamic Ridesharing, Transportation Research Part C : Emerging Technologies, Volume 114 (2020), pp. 532-553 | DOI
[31] Highly Efficient and Scalable Multi-hop Ride-sharing, Proceedings of the 28th International Conference on Advances in Geographic Information Systems, ACM, Seattle WA USA, 2020, pp. 215-226 | DOI
[32] Aggregate Nearest Neighbor Queries in Road Networks, IEEE Transactions on Knowledge and Data Engineering, Volume 17 (2005), pp. 820-833 | DOI
Cité par Sources :