This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Daganzo, C. F. Articles by Smilowitz, K. R. Search for Related Content

Bounds and Approximations for the Transportation Problem of Linear Programming and Other Scalable Network Problems

Institute of Transportation Studies, and Department of Civil and Environmental Engineering, University of California, Berkeley, California 94720
Institute of Transportation Studies, and Department of Civil and Environmental Engineering, University of California, Berkeley, California 94720
daganzo{at}ce.berkeley.edu
ksmilowitz{at}iems.nwu.edu

Bounds and approximate formulae are developed for the average optimum distance of the transportation linear programming (TLP) problem with homogeneously, but randomly distributed points and demands in a region of arbitrary shape. It is shown that if the region size grows with a fixed density of points, then the cost per item is bounded from above in 3⁺ dimensions (3⁺-D), but not in 1-D and 2-D. Lower bounds are also developed, based on a mild monotonicity conjecture. Computer simulations confirm the conjecture and yield approximate formulae. These formulae turn out to have the same functional form as the upper bounds. Curiously, the monotonicity conjecture implies that the cost per item does not depend on zone shape asymptotically, as problem size increases, for 2⁺-D problems but it does 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).

The results are then extended to more general network models with subadditive link costs. It is found that if the cost functions have economies of scale, then the cost per item is bounded in 2-D. This explains the prevalence of the "last mile" effect in many logistics applications. The paper also discusses how the results were used to estimate costs under uncertainty for a vehicle repositioning problem.

Key Words: logistics; networks; scalable optimization problems; linear programming
History: Received: October 2001; revised: October 2002; revised: February 2003; accepted: February 2003.