Logic-based modeling and solution of a linear optimal signal control problem for surface street networks

A review of the literature reveals that formulating an optimal signal control problem for surface street networks presents difficulties associated both with its modeling and its solution. The consistent modeling of the traffic flow process as a linear model necessitates the mathematical representation of some type of conditional piece-wise functions that describe the flow at lattice points on the surface street network depending on the prevailing traffic conditions and the signal indication. Representing such complex non-linear functions by a linear model is a non-trivial task. Based on analogies from the theory of mathematical logic we developed two methodologies for transforming such functions into a Mixed Integer Model (MIM) that is an equivalent representation corresponding to a set of linear equations and/or inequalities. The methodologies can be applied either towards the development of MIM representations or for the analysis of the structure of existing representations. Specifically, in this dissertation we develop MIM representations for virtually every possible piece-wise conditional function that can be found when developing a model for a surface street network based on the widely used dispersion-and-store or the cell transmission traffic flow models; further, we analyze and provide an improved MIM for the piece-wise conditional function that describes the flow according to the cell transmission model. The consistent modeling of the control strategy necessitates the consideration of a dual ring, 8-phase, variable cycle controller. For this we develop a model for the control strategy based on the aforementioned controller type, in contrast to all previous approaches in which a fixed cycle, 2-phase controller is considered. The linear optimal control problem is solved as a large scale Mixed Integer Linear Programming problem. It is known from the theoretical findings of optimal control and optimization theory that this type of problem is particularly difficult to solve. A number of optimal signal control problem variations are solved for an isolated intersection that accommodates eight movements during an optimization horizon of 5 minutes, by a commercial solver that uses a branch-and-cut algorithm. The solution time for all variations of these problems were faster than real time; however, an optimization horizon of 10 minutes required a solution time significantly slower than real time, ostensibly because the system states increased dramatically. We propose a logic-based formulation for the control strategy model that can be used for the development of a specially-tailored branch-and-bound algorithm for the problem of optimal signal control. We believe that a combination of the branch-and-cut with the customized branch-and-bound algorithm could efficiently solve the optimal signal control problem for high order systems. Finally, the solutions prove the effectiveness, adaptability, and versatility of the control strategy that is based on the concept of a dual ring, 8-phase, variable cycle controller, as well as the quality, of the decisions ordered by solving an optimal signal control problem.