Institute of Transportation Studies at UC Berkeley

This paper proves that a class of first order partial differential equations, which include scalar conservation laws with concave (or convex) equations of state as special cases, can be formulated as calculus of variations problems. Every well-posed problem of this type, no matter how complicated, even in multi-dimensions, is reduced to the determination of a tree of shortest paths in a relevant region of space-time where "cost" is predefined. Thus, problems of this type can be practically solved with fast network algorithms. The new formulation automatically identifies the unique, single-valued function, which is stable to perturbations in the input data. Therefore, an auxiliary "entropy" condition does not have to be introduced for the conservation law. In traffic flow applications, where one-dimensional conservation laws are relevant, constraints to flow such as sets of moving bottlenecks can now be modeled as shortcuts in space-time. These shortcuts become an integral part of the network and affect the nature of the solution but not the complexity of the solution process. Boundary conditions can be naturally handled in the new formulation as constraints/shortcuts of this type.