A graph theoretic modeling framework for generalized transportation systems with congestion phenomena

Dynamic Traffic Assignment (DTA) is the problem of routing vehicles from their origins to their destinations considering the spatio-temporal dynamic phenomena which may appear in the form of congestion. In this research we started by trying to reduce the computational complexity of the DTA problem after performing a theoretical analysis of a mathematical formulation based on the cell transmission model (CTM). It resulted in the graph theoretic CTM (GT-CTM) for the single destination DTA (SDDTA) problem. The GT-TM was proved to be a generalized time expanded graph (GTEG). The FIFO property for the GT-CTM was also developed in graph theoretic terms in order to allow the modeling of the multiple destinations DTA (MD-DTA) problem. The GT-CTM, being a G-TEG, has the capability to capture in theoretical and analytical terms all problems which have utilized in the past dynamic network flows. It directly enriches them with the modeling capabilities of total input/output and congestion phenomena, while it allows concepts and algorithms from one application area to fertilize the other. Such modeling capabilities were exhibited by showing how the GT-CTM can model some supply chain problems. Finally, the GT-CTM was extended to the graph theoretic link transmission model (GT-LTM) to more efficiently compute large-scale network application and incorporate an increased level of detail for backward propagating traffic waves at dissipating queues. The computational efficiency of the GTLTM for the SD-DTA problem was shown for the Borman Expressway network located in northwest Indiana. In total, we claim that the GT-CTM and accordingly its extension for large-scale network applications the GT-LTM form an applicable graph theoretic modeling framework for generalized transportation systems with congestion phenomena.