Routing multiple vehicles cooperatively: Minimizing road network breakdown probability

• Main Authors: GUO Hongliang, CAO, Zhiguang, SESHADRI Madhavan, ZHANG Jie, NIYATO Dusit, FASTENRATH Ulrich
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2017
• Subjects: Kerner's BM Principle; large scale network; multivehicle routing; matrix manipulation; Newton's method; traffic jam alleviation; Dynamical Systems; Electrical and Computer Engineering; Operations Research, Systems Engineering and Industrial Engineering; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/8184
• Institution: Singapore Management University

Traffic congestion has always been an impending challenge for drivers as well as traffic authorities. It causes frustrations to millions of passengers. The estimated financial cost is $2,200 billion per year in developed countries worldwide. In this paper, we propose an intelligent routing algorithm to minimize the traffic jam occurrence through directing the paths of multiple vehicles cooperatively. According to Kerner's breakdown minimization principle, we can claim that the traffic network optimum has been achieved if the probability for spontaneous traffic jam occurrence over the entire road network during a given observation time period is minimized. The proposed multivehicle routing approach is fully scalable and distributed, which essentially makes it directly applicable to real traffic networks such as that in Singapore. Through numerical studies, the proposed algorithm is much faster in terms of convergence speed than that of state-of-the-art distributed computation approaches. Moreover, our approach always maintains a feasible route guidance solution during the computation process, which is applicable to scenarios with real time decision making requirements, i.e., the reaction time must be within seconds. Simulation results in arbitrarily large road networks with realistic settings show the effectiveness of the proposed algorithm.