Optimization Models for Assessing the Peak Capacity Utilization of Intelligent Transportation Systems

Due to economic and physical resource constraints, it is not feasible to continually expand transportation infrastructures to adequately support the rapid growth in the usages of these infrastructures. This is especially true for traffic coordination systems where the expansion of the road infrastructure has not been able to keep pace with the increasing number of vehicles, thereby resulting in congestion and delays on the roads as well as in substantial increase in pollution. Hence, in addition to striving for the construction of new roads, it is imperative to develop new intelligent transportation management and coordination systems that can effectively enable the existing infrastructure to be used more efficiently. However, for a deployed solution to be practical and cost-effective, it needs to be provably superior to current methods. The effectiveness of a given technique can be evaluated by comparing it with the optimal capacity utilization. If this comparison indicates that substantial improvements are possible, then the cost of developing and deploying an intelligent traffic system can be justified. Moreover, developing an optimization model can also help in capacity planning. For instance, at a given level of demand, if the optimal solution worsens significantly, this implies that no amount of intelligent strategies can handle this demand, and expanding the infrastructure would be the only alternative. In this paper, we demonstrate these concepts through a case study of scheduling vehicles on a grid of intersecting roads. We develop two optimization models namely, the mixed integer programming model and the space-time network flow model for this problem, and show that the latter model is substantially more effective. Moreover, we prove the strong NP-hard property of this problem and develop two polynomial-time heuristic solutions, which are evaluated and compared with the optimal capacity utilization obtained using the space-time network model. In addition, we also present important implications for the managers