Asymptotic Approximations for the Transportation LP and Other Scalable Network Problems

Carlos F Daganzo and Karen R Smilowitz

University of California Transportation Center, Working Papers from University of California Transportation Center

Abstract: Network optimization problems with a "scalable" structure are examined in this report. Scalable networks are embedded in a normed space and must belong to a closed family under certain transformations of size (number of nodes) and scale (dimension of the norm). The transportation problem of linear programming (TLP) with randomly distributed points and random demands, the earthwork minimization problem of highway design, and the distribution of currents in an electric grid are examples of scalable network problems. Asymptotic formulas for the optimum cost are developed for the case where one holds the scale parameter constant while increasing the size parameter, N. As occurs in some applied probability problems such as the Ising model of statistical mechanics, and the first passage of time of a random walk, the nature of the solution of linear problems depends on the dimensionality of the space. In the linear case, we find that the cost per node is bounded from above in 3+ dimensions (3+-D), but not in 1- and 2-D. Curiously, zone shape has no effect (asymptotically) on the optimum cost per point in 2+-D, but it has an effect in 1-D. Therefore, the 2-D case can be viewed as a transition case that shares some of the properties of 1-D (unbounded cost) and some of the properties of 3-D (shape-independence). A simple formula for the 2-D, Euclidean TLP is given. Asymptotic results are also developed for a class of non-linear network problems with link costs that are a concave power function of flow. It is found that if these functions are strictly concave than the solution in 2+-D is bounded.

Keywords: Social; and; Behavioral; Sciences (search for similar items in EconPapers)
Date: 2000-12-17
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://www.escholarship.org/uc/item/7wb1g4z7.pdf;origin=repeccitec (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cdl:uctcwp:qt7wb1g4z7

Access Statistics for this paper

More papers in University of California Transportation Center, Working Papers from University of California Transportation Center Contact information at EDIRC.
Bibliographic data for series maintained by Lisa Schiff ().