DISTRIBUTED COORDINATED IN-VEHICLE ONLINE ROUTING USING A MIXED-STRATEGY CONGESTION GAME

Among a number of approaches for in-vehicle routing, there are two groups that are rather accessible to both academia and practitioners. One is independent routing, which simply disseminates the information of instantaneous traffic conditions of an interested network to equipped vehicles, and expects each driver to independently make his/her own route choice. The second is systemic routing, which collects all drivers’ origin-destination information for a centralized decision unit to systemically make an overall route decision for all involved vehicles. It is well known that independent routing leads to selfish routing and results in oscillating traffic conditions in the network, while systemic routing is for the best interest of the whole network, but not necessarily individual vehicles. Moreover, the computational load in the second approach is too high to be feasible for a real application. To address the dilemma between the above two groups of approaches, this study proposes a novel coordinated online in-vehicle routing mechanism (CRM), assuming that smart vehicles are equipped with wireless communication and local computation facilities.

The proposed CRM models the routing decision process of a group of smart vehicles as a mixed strategy routing game, in which smart vehicles decide their own online route choice priorities by a negotiation and coordination process with other smart vehicles. A discrete choice model is employed to counter for drivers’ behaviors. This study shows the existence of an equilibrium coordinated routing decision for the mixed-strategy routing game. Furthermore, a simultaneously updating distributed algorithm is proposed to implement the CRM. The convergence of the distributed algorithm to the equilibrium routing decision is proved, assuming that individual smart vehicles are selfish players seeking to minimize their own travel times. Numerical experiments conducted based on the Sioux Falls city network indicate that the proposed distributed algorithm converges quickly under different smart vehicle penetration levels; thus it possesses great potential for online applications. Moreover, the proposed coordinated routing mechanism outperforms the traditional independent selfish-routing mechanism; it reduces the travel times for both the overall system and individual vehicles, which represents the core idea of Intelligent Transportation Systems.

Dr. Du is an assistant professor in the Department of Civil, Architectural and Environmental Engineering at the Illinois Institute of Technology (IIT). Before joining IIT, she worked as a Post-doctoral Research Associate for NEXTRANS, the USDOT Region V Regional University Transportation Center at Purdue University, from 2008 to 2012. She received her Ph.D. degree in Decision Sciences and Engineering Systems with a minor in Operations Research and Statistics from Rensselaer Polytechnic Institute in 2008. Dr. Du’s research is characterized by applying operations research, network modeling and statistical methods into transportation system analysis and network modeling. Dr. Du’s current research covers several interdisciplinary research areas in Transportation Engineering, such as Connected and Autonomous Vehicle Systems, Interdependent Infrastructure Network Modeling, Sustainable Multimodal Transportation Systems, Optimization and Data fusion Applications in Traffic Flow Analysis, and so on. Dr. Du’s research articles have appeared in several major transportation journals, including Transportation Research Part B, Transportation Research Part C, IEEE Transactions on ITS, Networks and Spatial Economics, etc . Dr. Du’s research has been funded by the National Science Foundation (including a CAREER award), Illinois Department of Transportation, and the University Transportation Research Center. Her recent project “Driverless City” won the First Nayar Prize at IIT. Dr. Du is currently a member of the Transportation Research Board Committee on Transportation Network Modeling (ADB30) and serves on the editorial board for this committee. She is also on the editorial board of the International Journal of Business Analytics.