NONCONVEXITY OF THE DYNAMIC TRAFFIC ASSIGNMENT PROBLEM

We identify and discuss what appears to be a central difficulty for the future development of models of dynamic traffic flows on road networks. This difficulty is due to the fact that road traffic tends to behave in a first-in-first-out (FIFO) manner: that is, traffic which embarks on a road or other facility in period t exits from that facility ("on average") before traffic which enters in any later time periods. The FIFO requirement does not cause a problem in static traffic assignment, but we show that it yields a nonconvex constraint set in dynamic assignment, especially if there are multiple destinations or commodities. We consider various formulations, each of which yields a nonconvex optimization problem which is at present computationally tractable only for relatively small-scale examples. The above FIFO problem arises even if there is no congestion, and even if travel demands are fixed. Further the problem arises whether we are modeling a system optimum or a user equilibrium, and whether we use an optimization formulation or a complementarity or variational inequality formulation. We make some suggestions for dealing with, or avoiding, the problem and for further research.