BOUNDS AND APPROXIMATIONS FOR THE TRANSPORTATION PROBLEM OF LINEAR PROGRAMMING AND OTHER SCALABLE NETWORK PROBLEMS

Bounds and approximate formulae are developed for the average optimum distance of the transportation linear programming 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.