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 (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 poin...

Full description

Saved in:
Bibliographic Details
Published in:Transportation science 2004-08, Vol.38 (3), p.343-356
Main Authors: Daganzo, Carlos F, Smilowitz, Karen R
Format: Article
Language:English
Subjects:
Applied sciences
Approximation
Computer simulation
Cost estimates
Cost functions
Cubes
Economic costs
Exact sciences and technology
Ground, air and sea transportation, marine construction
Linear programming
Logistics
Networks
Probability theory
scalable optimization problems
Statistical variance
Studies
Transport
Transportation
Transportation planning, management and economics
Vehicles
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0041-1655
1526-5447
DOI:10.1287/trsc.1030.0037