Non-Convex Traffic Assignment on a Rectangular Grid Network

We consider here an idealized infinite rectangular grid of roads with a translationally symmetric O-D distribution. The total cost of travel on all links approaching each junction is approximated by a quadratic function of the four flows N, S, E, and W at that junction. If any of the four eigenvalues of this quadratic form is negative, the system optimal assignment problem is non-convex. If there are economies of scale (due possibly to construction costs) then all eigenvalues could be negative and the optimal assignment will lead to a hierarchical type of flow distribution (city streets, arterials, freeways, etc.). If costs arise only from congestion, however, it is possible that one or more of the eigenvalues is negative particularly if the cost of travel N, for example, is more sensitive to the flows E and/or W than to the flow N, or is more sensitive to the flow S than N. If it is more sensitive to the flow E-W an efficient assignment would seem to be one in which the space is divided into subregions such that in certain subregions traffic will be predominantly N or S and in other subregions it is predominately E or W. The optimal assignment is expected to be highly unstable to changes in the O-D distribution. If it is more sensitive to the flow S, a user optimal assignment may be stable and translationally symmetric but not the system optimal. The conclusion is that a non-convex assignment problem is not only a computational nightmare, but may be inconsistent with social objective or impractical to implement.