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.

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.

Publié le :
DOI : 10.5802/roia.86
Mots-clés : Covoiturage, Simulation, Optimisation, Agents
Keywords: Ridesharing, Simulation, Optimization, Agents

Corwin Fèvre 1 ; Philippe Mathieu 1 ; Hayfa Zgaya-Biau 1 ; Slim Hammadi 1

1 Univ. Lille, CNRS, Centrale Lille, UMR 9189, CRIStAL, F-59000 Lille, France
Licence : CC-BY 4.0
Droits d'auteur : Les auteurs conservent leurs droits
@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] Micah Adler; Brent Heeringa 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] Niels Agatz; Alan L. Erera; Martin W.P. Savelsbergh; Xing Wang Dynamic Ride-Sharing : A Simulation Study in Metro Atlanta, Procedia – Social and Behavioral Sciences, Volume 17 (2011), pp. 532-550 | DOI

[3] Flavien Balbo; Suzanne Pinson 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] H. A. N. C. Bandara; Dileeka Dias A Multi-Agent system for dynamic ride sharing, 2009 International Conference on Industrial and Information Systems (ICIIS), IEEE, 2009, pp. 199-203 | DOI

[5] Sondes Ben Cheikh-Graiet; Mariagrazia Dotoli; Slim Hammadi A Tabu Search Based Metaheuristic for Dynamic Carpooling Optimization, Computers & Industrial Engineering, Volume 140 (2020), 106217 | DOI

[6] Geoff Boeing 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] Zhongpu Chen; Bin Yao; Zhi-Jie Wang; Xiaofeng Gao; Shuo Shang; Shuai Ma; Minyi Guo 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] Jean-François Cordeau; Gilbert Laporte The Dial-a-Ride Problem : Models and Algorithms, Ann Oper Res, Volume 153 (2007), pp. 29-46 | DOI | MR | Zbl

[9] Cristián Cortés; Martín Matamala; Claudio Contardo The Pickup and Delivery Problem with Transfers, Eur. J. Oper. Res., Volume 200 (2010) no. 3, pp. 711-724 | DOI | MR | Zbl

[10] Alaa Daoud; Flavien Balbo; Paolo Gianessi; Gauthier Picard 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] A. Di Febbraro; E. Gattorna; N. Sacco Optimization of Dynamic Ridesharing Systems, Transportation Research Record : Journal of the Transportation Research Board, Volume 2359 (2013) no. 1, pp. 44-50 | DOI

[12] Azise Oumar Diallo; Guillaume Lozenguez; Arnaud Doniec; René Mandiau Usage Des Parkings Relais Dans Les Comportements de Déplacements Intermodaux, JFSMA29, June 28-30, 2021, Cépaduès, 2021, pp. 83-92

[13] Jacques Ferber Multi-Agent Systems : An Introduction to Distributed Artificial Intelligence, 1999

[14] Corwin Fevre; Hayfa Zgaya-Biau; Philippe Mathieu; Slim Hammadi 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] Antonin Guttman 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] Wesam Herbawi; Michael Weber Evolutionary Multiobjective Route Planning in Dynamic Multi-hop Ridesharing, Evolutionary Computation in Combinatorial Optimization, Springer, Berlin, Heidelberg, 2011, pp. 84-95 | DOI

[17] Wesam Herbawi; Michael Weber 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] Karama Jeribi; Hinda Mejri; Hayfa Zgaya; Slim Hammadi Distributed Graphs for Solving Co-Modal Transport Problems, 2011 14th International IEEE Conference on Intelligent Transportation Systems (ITSC), 2011, pp. 1150-1155 | DOI

[19] Ece Kamar; Eric Horvitz Collaboration and Shared Plans in the Open World : Studies of Ridesharing, IJCAI International Joint Conference on Artificial Intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2009, pp. 187-194

[20] Jane Lin; Sandeep Sasidharan; Shuo Ma; Ouri Wolfson 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] Shuo Ma; Ouri Wolfson Analysis and Evaluation of the Slugging Form of Ridesharing, SIGSPATIAL’13, ACM Press, Orlando, Florida, 2013, pp. 64-73 | DOI

[22] Shuo Ma Ma; Yu Zheng; O. Wolfson T-Share : A Large-Scale Dynamic Taxi Ridesharing Service, ICDE29’, IEEE, 2013, pp. 410-421 | DOI

[23] Yannis Manolopoulos; Yannis Theodoridis; Vassilis J. Tsotras Spatial Indexing Techniques, Encyclopedia of Database Systems, Springer New York, New York, NY, 2014, pp. 1-7 | DOI

[24] Neda Masoud; R. Jayakrishnan 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] Philippe Mathieu; Antoine Nongaillard 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] Dimitris Papadias; Qiongmao Shen; Yufei Tao; Kyriakos Mouratidis Group nearest neighbor queries, Proceedings. 20th International Conference on Data Engineering, 2004, pp. 301-312 | DOI

[27] Dimitris Papadias; Yufei Tao; Kyriakos Mouratidis; Chun Kit Hui Aggregate Nearest Neighbor Queries in Spatial Databases, ACM Transactions on Database Systems, Volume 30 (2005) no. 2, pp. 529-576 | DOI

[28] Dimitris Papadias; Jun Zhang; Nikos Mamoulis; Yufei Tao Query Processing in Spatial Network Databases, Proceedings 2003 VLDB Conference, Elsevier, 2003, pp. 802-813 | DOI

[29] Vilfredo Pareto Cours d’économie politique, Librairie Droz, 1964 | DOI

[30] Amirmahdi Tafreshian; Neda Masoud Trip-Based Graph Partitioning in Dynamic Ridesharing, Transportation Research Part C : Emerging Technologies, Volume 114 (2020), pp. 532-553 | DOI

[31] Yixin Xu; Lars Kulik; Renata Borovica-Gajic; Abdullah Aldwyish; Jianzhong Qi 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] Man Yiu; Nikos Mamoulis; Dimitris Papadias Aggregate Nearest Neighbor Queries in Road Networks, IEEE Transactions on Knowledge and Data Engineering, Volume 17 (2005), pp. 820-833 | DOI

Cité par Sources :