An Optimization Model for Rigorously Assessing Efficient Heuristics for Traffic Coordination at Intersections

Large-scale, network-centric control systems can benefit significantly via the use of computer and communication technologies. Given the large size and complexity of such systems, it is often not possible to compute optimal solutions. In many cases, it may be necessary that the control solution can be computed within a short time interval, whereas computing an optimal solution might require a much longer time interval. Thus, heuristic control strategies are often deployed in lieu of fully optimal solutions. However, in order to ensure that a heuristic technique meets the performance requirements reasonably well, it is necessary to compare it with the optimal method. In this paper, we demonstrate this process by using a case study of scheduling vehicles traveling on a grid of intersecting roads. We develop an optimization model for this problem using linear programming and solve it using CPLEX. Moreover, we develop two heuristic algorithms for the same problem, and evaluate them against the optimal approach.