A note on asymptotic formulae for one-dimensional network flow problems

Carlos F. Daganzo, Karen R. Smilowitz*

*Corresponding author for this work

Research output: Contribution to journalArticle

Abstract

This note develops asymptotic formulae for single-commodity network flow problems with random inputs. The transportation linear programming problem (TLP) where N points lie in a region of R1 is one example. It is found that the average distance traveled by an item in the TLP increases with N 1/2; i.e., the unit cost is unbounded when N and the length of the region are increased in a fixed ratio. Further, the optimum distance does not converge in probability to the average value. These one-dimensional results are a useful stepping stone toward a network theory for two and higher dimensions.

Original languageEnglish (US)
Pages (from-to)153-160
Number of pages8
JournalAnnals of Operations Research
Volume144
Issue number1
DOIs
StatePublished - Apr 1 2006

    Fingerprint

Keywords

  • Distance approximations
  • Transportation problem

ASJC Scopus subject areas

  • Decision Sciences(all)
  • Management Science and Operations Research

Cite this