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

Carlos F. Daganzo; Karen R. Smilowitz

doi:10.1007/s10479-006-0010-2

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

Carlos F. Daganzo, Karen R. Smilowitz^*

^*Corresponding author for this work

Industrial Engineering and Management Sciences

Research output: Contribution to journal › Article › peer-review

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 R¹ 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 language	English (US)
Pages (from-to)	153-160
Number of pages	8
Journal	Annals of Operations Research
Volume	144
Issue number	1
DOIs	https://doi.org/10.1007/s10479-006-0010-2
State	Published - Apr 2006

Funding

Research supported in part by the University of California Transportation Center.

Keywords

Distance approximations
Transportation problem

ASJC Scopus subject areas

General Decision Sciences
Management Science and Operations Research

Access to Document

10.1007/s10479-006-0010-2

Cite this

@article{b1c69e869ba84cac828357a1f63d2f10,

title = "A note on asymptotic formulae for one-dimensional network flow problems",

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.",

keywords = "Distance approximations, Transportation problem",

author = "Daganzo, {Carlos F.} and Smilowitz, {Karen R.}",

note = "Funding Information: Research supported in part by the University of California Transportation Center.",

year = "2006",

month = apr,

doi = "10.1007/s10479-006-0010-2",

language = "English (US)",

volume = "144",

pages = "153--160",

journal = "Annals of Operations Research",

issn = "0254-5330",

publisher = "Springer Netherlands",

number = "1",

}

TY - JOUR

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

AU - Daganzo, Carlos F.

AU - Smilowitz, Karen R.

N1 - Funding Information: Research supported in part by the University of California Transportation Center.

PY - 2006/4

Y1 - 2006/4

N2 - 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.

AB - 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.

KW - Distance approximations

KW - Transportation problem

UR - http://www.scopus.com/inward/record.url?scp=33747838433&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33747838433&partnerID=8YFLogxK

U2 - 10.1007/s10479-006-0010-2

DO - 10.1007/s10479-006-0010-2

M3 - Article

AN - SCOPUS:33747838433

SN - 0254-5330

VL - 144

SP - 153

EP - 160

JO - Annals of Operations Research

JF - Annals of Operations Research

IS - 1

ER -

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

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this