Asymptotic Approximations for the Transportation LP and Other Scalable Network Problems

Carlos F. Daganzo and Karen R. Smilowitz

Institute of Transportation Studies, Research Reports, Working Papers, Proceedings from Institute of Transportation Studies, UC Berkeley

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. It is found that when the objective function is quadratic (as occurs in electric circuits), then the solution is always unbounded.

Keywords: Network analysis (Planning); Mathematical optimization; Transportation problems (Programming); Asymptotes (search for similar items in EconPapers)
Date: 2000-08-01
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/3dn2j66w.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:itsrrp:qt3dn2j66w

Access Statistics for this paper

More papers in Institute of Transportation Studies, Research Reports, Working Papers, Proceedings from Institute of Transportation Studies, UC Berkeley Contact information at EDIRC.
Bibliographic data for series maintained by Lisa Schiff ().