Extending and solving a multiperiod congested network flow model
Computers & Operations Research, Volume 17, Issue 5, 1990, Pages 495-507
Malachy Carey
Department of Statistics, University of Oxford, 1 South Parks Road, Oxford OX1 3TG, England
Abstract
We consider an existing model for optimizing time-varying flows on a congested network, and extend it so as to improve its accuracy while reducing computation. The model has been developed in a series of articles and has a variety of applications. Solving the model is a significant problem, since it is a non-linear program and can be very large for even small or medium size applications. Hitherto the model has been solved by taking a piecewise linear approximation and solving this as a linear program, perhaps taking advantage of the staircase structure of the constraints. However, this staircase is not available in the extended model. Further, the existing solution methods do not take advantage of the network structure of the problem. Here we show that a piecewise linear version of the model can be stated as a pure processing network (PPN); this allows algorithms for PPNs to be used to solve the model. We also propose a penalty (or barrier) function solution method. This reduces the problem to successively reoptimizing a program equivalent to the well-known static traffic assignment model. The latter is a convex cost, linearly constrained, uncapacitated network flow problem. The above solution methods apply both to the basic model and the extended model.
* Malachy Carey is the British Rail/Fellowship of Engineering Senior Research Fellow at the University of Oxford. Prior to that he was an Associate Professor of Operations Research at Carnegie Mellon University. He has also been Visiting Assistant Professor at the University of Texas at Austin, and a Research Fellow at the University of Birmingham, England. He has a PhD from the University of Birmingham, and has published in various journals of operations research, transportation, econometrics, economics, etc. He has current research interests in operations research, operations management and decision support systems, with a particular interest in transportation, planning and scheduling.