Dynamic network simplex method for designing emergency evacuation plans

The cell-based system optimal dynamic traffic assignment (SO-DTA) model has recently been applied to study emergency evacuation by a handful of authors. It is recognized that an optimal solution to this model may contain a phenomenon called traffic holding, which discharges flow at a lower rate than what can be achieved under the given traffic conditions. Mathematically, this is caused by the relaxation of traffic flow propagation constraints. In this paper, an optimal traffic pattern that contains no holding is always proved to exist in the context of evacuation planning. An optimal traffic pattern without holding is much easier and less costly to implement in emergency response. A dynamic network simplex method for solving the simplified SO-DTA model that represents traffic flow propagation by a point-queue model is proposed. By making full use of the network structure, the algorithm is able to identify an optimal solution without holding. For the original cell-based SO-DTA, an iterative procedure is suggested that can effectively eliminate holding in a solution obtained from a conventional linear programming algorithm.