Bounds and approximations for the transportation problem of linear programming and other scalable network problems

Carlos F. Daganzo*, Karen R. Smilowitz

*Corresponding author for this work

Research output: Contribution to journalArticle

12 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)343-356
Number of pages14
JournalTransportation Science
Volume38
Issue number3
DOIs
StatePublished - Aug 2004

Keywords

  • Linear programming
  • Logistics
  • Networks
  • Scalable optimization problems

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Transportation

Fingerprint Dive into the research topics of 'Bounds and approximations for the transportation problem of linear programming and other scalable network problems'. Together they form a unique fingerprint.

  • Cite this