Investigating heuristic algorithms for minimal controller location set problem in transportation networks

Abstract

The locations and types of controllers employed in a transportation network directly impact the level of performance reachable by traffic control policies. In order to guarantee that the highest level of performance is reachable, fully exploiting the available network capacity and reducing negative externalities, we explore methods to identify important locations in networks for controller while minimizing the number of controllers used. Previous work employed an exact method to identify controller locations on complex networks. However, this approach exhibits complications when applied to transportation networks containing bi-directional links. We therefore propose simple heuristic algorithms based on topological information to solve this problem, while avoiding heavy computation, thus being able to determine a solution to the minimal controller location set problem on large networks. Based on the existing framework, we aim to provide an experimental setup, with diverse network sizes and configurations to analyze the different heuristic methods performance, in order to develop an efficient algorithm.