Asymptotic Approximations for the Transportation LP and Other Scalable Network Problems
AbstractNetwork 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.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Institute of Transportation Studies, UC Berkeley in its series Institute of Transportation Studies, Research Reports, Working Papers, Proceedings with number qt3dn2j66w.
Date of creation: 01 Aug 2000
Date of revision:
Contact details of provider:
Postal: 109 McLaughlin Hall, Mail Code 1720, Berkeley, CA 94720-1720
Web page: http://www.escholarship.org/repec/its/
More information through EDIRC
Network analysis (Planning); Mathematical optimization; Transportation problems (Programming); Asymptotes;
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Newell, G. F., 1986. "Design of multiple-vehicle delivery tours--III valuable goods," Transportation Research Part B: Methodological, Elsevier, vol. 20(5), pages 377-390, October.
- Newell, Gordon F. & Daganzo, Carlos F., 1986. "Design of multiple-vehicle delivery tours--I a ring-radial network," Transportation Research Part B: Methodological, Elsevier, vol. 20(5), pages 345-363, October.
- Daganzo, Carlos F., 1984. "The length of tours in zones of different shapes," Transportation Research Part B: Methodological, Elsevier, vol. 18(2), pages 135-145, April.
- Newell, Gordon F. & Daganzo, Carlos F., 1986. "Design of multiple vehicle delivery tours--II other metrics," Transportation Research Part B: Methodological, Elsevier, vol. 20(5), pages 365-376, October.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Lisa Schiff).
If references are entirely missing, you can add them using this form.