Decentralized Right-of-Way Protocol for Connected and Automated Vehicles at Unsignalized Intersections
DOI:
https://doi.org/10.15837/ijccc.2025.6.6677Keywords:
Connected and Automated Vehicles, Unsignalized Intersection, V2X, PCKPAbstract
In urban areas, traffic mainly depends on decisions made by drivers, especially at junctions. The advent of Connected and Automated Vehicles aims to prevent driver error susceptible to causing accidents or congestion. This problem becomes more challenging when the intersection is signal-free. Numerous solutions have addressed this question, also called the conflict-free scheduling problem. However, most of them do not consider handling simultaneously spillbacks, vehicle heterogeneity, and prioritization. Besides, some of these contributions are limited only to pedestrians and ignoring other vulnerable road users such as cyclists and motorcyclists. These shortcomings are detrimental to any real-world efficient implementation. This paper aims to cope with these issues concurrently. To this end, we formulate this question as a Conflict-free and Precedence-Constrained Multiple Knapsack Problem (CPCMKP) solved through a distributed heuristic. Simulation results showed that this solution outperforms related state-of-the-art schemes concerning delay and fairness.
References
Daniela Müller-Eie and Ioannis Kosmidis. Sustainable mobility in smart cities: a document study of mobility initiatives of mid-sized nordic smart cities. European Transport Research Review, 15(1), October 2023. https://doi.org/10.1186/s12544-023-00610-4
Prashant Singh, Maxim A. Dulebenets, Junayed Pasha, Ernesto D. R. Santibanez Gonzalez, Yui- Yip Lau, and Raphael Kampmann. Deployment of autonomous trains in rail transportation: Current trends and existing challenges. IEEE Access, 9:91427-91461, 2021. https://doi.org/10.1109/ACCESS.2021.3091550
Attila Simo, Simona Dzitac, Liviu Ferestyan, Cristian-Dragos Dumitru, and Adrian Gligor. Optimizing electric vehicle performance: Advances in battery management systems for enhanced efficiency and longevity. International Journal of Computers Communications & Control;, 19(5), September 2024. https://doi.org/10.15837/ijccc.2024.5.6794
Liping Zhao, Feng Li, Dongye Sun, and Zihan Zhao. An improved ant colony algorithm based on q-learning for route planning of autonomous vehicle. International Journal of Computers Communications & Control;, 19(3), May 2024. https://doi.org/10.15837/ijccc.2024.3.5382
Faran Awais Butt, Jawwad Nasar Chattha, Jameel Ahmad, Muhammad Umer Zia, Muhammad Rizwan, and Ijaz Haider Naqvi. On the integration of enabling wireless technologies and sensor fusion for next-generation connected and autonomous vehicles. IEEE Access, 10:14643-14668, 2022. https://doi.org/10.1109/ACCESS.2022.3145972
K. Dresner and P. Stone. A multiagent approach to autonomous intersection management. Journal of Artificial Intelligence Research, 31:591-656, March 2008. https://doi.org/10.1613/jair.2502
Biyao Wang, Yi Han, Siyu Wang, Di Tian, Mengjiao Cai, Ming Liu, and Lujia Wang. A review of intelligent connected vehicle cooperative driving development. Mathematics, 10(19):3635, oct 2022. https://doi.org/10.3390/math10193635
Abdeljalil Abbas-Turki, Yazan Mualla, Nicolas Gaud, Davide Calvaresi, Wendan Du, Alexandre Lombard, Mahjoub Dridi, and Abder Koukam. Autonomous intersection management: Optimal trajectories and efficient scheduling. Sensors, 23(3):1509, jan 2023. https://doi.org/10.3390/s23031509
Balázs Varga and Tamás Tettamanti. Jam propagation analysis with mesoscopic traffic simulation. IEEE Transactions on Intelligent Transportation Systems, 24(12):14162-14173, December 2023. https://doi.org/10.1109/TITS.2023.3303680
Ashkan Gholamhosseinian and Jochen Seitz. A comprehensive survey on cooperative intersection management for heterogeneous connected vehicles. IEEE Access, 10:7937-7972, 2022. https://doi.org/10.1109/ACCESS.2022.3142450
Soukaina Laabadi, Mohamed Naimi, Hassan El Amri, and Boujemâa Achchab. The 0/1 multidimensional knapsack problem and its variants: A survey of practical models and heuristic approaches. American Journal of Operations Research, 08(05):395-439, 2018. https://doi.org/10.4236/ajor.2018.85023
Oscar H. Ibarra and Chul E. Kim. Approximation algorithms for certain scheduling problems. Mathematics of Operations Research, 3(3):197-204, 1978. https://doi.org/10.1287/moor.3.3.197
Fayez Alanazi. A systematic literature review of autonomous and connected vehicles in traffic management. Applied Sciences, 13(3):1789, jan 2023. https://doi.org/10.3390/app13031789
Zijia Zhong, Mark Nejad, and Earl E Lee. Autonomous and semiautonomous intersection management: A survey. IEEE Intelligent Transportation Systems Magazine, 13(2):53-70, 2021. https://doi.org/10.1109/MITS.2020.3014074
Michael I.-C. Wang, Jiacheng Wang, Charles H.-P. Wen, and H. Jonathan Chao. Roadrunner: Autonomous intersection management with dynamic lane assignment. In 2020 IEEE 23rd International Conference on Intelligent Transportation Systems (ITSC). IEEE, sep 2020.
Bai Li, Youmin Zhang, Ning Jia, and Xiaoyan Peng. Autonomous intersection management over continuous space: A microscopic and precise solution via computational optimal control. IFAC-PapersOnLine, 53(2):17071-17076, 2020. https://doi.org/10.1016/j.ifacol.2020.12.1611
A. S. M. Bakibillah, Md Abdus Samad Kamal, Chee Pin Tan, Susilawati Susilawati, Tomohisa Hayakawa, and Jun ichi Imura. Bi-level coordinated merging of connected and automated vehicles at roundabouts. Sensors, 21(19):6533, sep 2021. https://doi.org/10.3390/s21196533
Behdad Chalaki and Andreas A. Malikopoulos. Optimal control of connected and automated vehicles at multiple adjacent intersections. IEEE Transactions on Control Systems Technology, 30(3):972-984, may 2022. https://doi.org/10.1109/TCST.2021.3082306
Behdad Chalaki and Andreas A. Malikopoulos. Time-optimal coordination for connected and automated vehicles at adjacent intersections. IEEE Transactions on Intelligent Transportation Systems, 23(8):13330-13345, aug 2022. https://doi.org/10.1109/TITS.2021.3123479
Huaxin Pei, Yuxiao Zhang, Yi Zhang, and Shuo Feng. Optimal cooperative driving at signal-free intersections with polynomial-time complexity. IEEE Transactions on Intelligent Transportation Systems, 23(8):12908-12920, aug 2022. https://doi.org/10.1109/TITS.2021.3118592
Hui Zhang, Rongqing Zhang, Chen Chen, Dongliang Duan, Xiang Cheng, and Liuqing Yang. A priority-based autonomous intersection management (AIM) scheme for connected automated vehicles (CAVs). Vehicles, 3(3):533-544, aug 2021. https://doi.org/10.3390/vehicles3030032
Chaoyi Chen, Qing Xu, Mengchi Cai, JiaweiWang, JianqiangWang, and Keqiang Li. Conflict-free cooperation method for connected and automated vehicles at unsignalized intersections: Graphbased modeling and optimality analysis. IEEE Transactions on Intelligent Transportation Systems, 23(11):21897-21914, nov 2022. https://doi.org/10.1109/TITS.2022.3182403
Zhiyun Deng, Kaidi Yang, Weiming Shen, and Yanjun Shi. Cooperative platoon formation of connected and autonomous vehicles: Toward efficient merging coordination at unsignalized intersections. IEEE Transactions on Intelligent Transportation Systems, 24(5):5625-5639, may 2023. https://doi.org/10.1109/TITS.2023.3235774
Tanja Niels, Klaus Bogenberger, Markos Papageorgiou, and Ioannis Papamichail. Optimizationbased intersection control for connected automated vehicles and pedestrians. Transportation Research Record: Journal of the Transportation Research Board, page 036119812311729, jun 2023. https://doi.org/10.1177/03611981231172956
Ming S. Hung and John C. Fisk. An algorithm for 0-1 multiple-knapsack problems. Naval Research Logistics Quarterly, 25(3):571-579, September 1978. https://doi.org/10.1002/nav.3800250316
Silvano Martello and Paolo Toth. Knapsack problems: algorithms and computer implementations. John Wiley & Sons, Inc., 1990.
Li'ang Zhang and Suyun Geng. The complexity of the 0/1 multi-knapsack problem. Journal of Computer Science and Technology, 1(1):46-50, mar 1986. https://doi.org/10.1007/BF02943300
Vladimir Gorodokin, Irina Alferova, and Elena Shepeleva. Calculating the duration of the traffic light green interval allowing pedestrians entering the traffic way. Transportation Research Procedia, 36:220-224, 2018. https://doi.org/10.1016/j.trpro.2018.12.067
Pablo Alvarez Lopez, Evamarie Wiessner, Michael Behrisch, Laura Bieker-Walz, Jakob Erdmann, Yun-Pang Flotterod, Robert Hilbrich, Leonhard Lucken, Johannes Rummel, and Peter Wagner. Microscopic traffic simulation using SUMO. In 2018 21st International Conference on Intelligent Transportation Systems (ITSC). IEEE, nov 2018.
[omnet++], a public-source, component-based, modular and open-architecture discrete event simulation environment. official homepage: http://www.omnetpp.org/ accessed on May 2024.
Michael I.-C. Wang, Charles H.-P. Wen, and H. Jonathan Chao. Roadrunner+: An autonomous intersection management cooperating with connected autonomous vehicles and pedestrians with spillback considered. ACM Transactions on Cyber-Physical Systems, 6(1):1-29, nov 2021. https://doi.org/10.1145/3488246
Raj Jain, Dah-Ming Chiu, and W. Hawe. A quantitative measure of fairness and discrimination for resource allocation in shared computer systems. CoRR, cs.NI/9809099, 1998.
Jian Wu, Dipak Ghosal, Michael Zhang, and Chen-Nee Chuah. Delay-based traffic signal control for throughput optimality and fairness at an isolated intersection. IEEE Transactions on Vehicular Technology, 67(2):896-909, feb 2018. https://doi.org/10.1109/TVT.2017.2760820
Additional Files
Published
Issue
Section
License
Copyright (c) 2025 Gokou Hervé Fabrice Diédié, Boris Stéphane Zounémé, Tchimou N’Takpé
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
