Combinatorial programming, statistical optimization and the optimal transportation network problem

Marc Los and Christian Lardinois

Transportation Research Part B: Methodological, 1982, vol. 16, issue 2, 89-124

Abstract: This paper presents and evaluates a branch and bound algorithm and two heuristic hill-climbing techniques to solve a discrete formulation of the optimal transportation network design problem. For practical applications it is proposed to combine a hill-climbing algorithm with a uniform random generation of the initial solutions, thereby inducing a statistical distribution of local optima. In order to determine when to stop sampling local optima and in order to provide an estimate of the exact optimum based on the whole distribution of local optima, we follow previous work and fit a Weibull distribution to the empirical distribution of local optima. Several extensions are made over previous work: in particular, a new confidence interval and a new stopping rule are proposed. The numerical application of the statistical optimization methodology to the network design algorithms consolidates the empirical validity of fitting a Weibull distribution to the empirical distribution of local optima. Numerical experiments with hill-climbing techniques of varying power suggest that the method is best applied with heuristics of intermediate quality: such heuristics provide many distinct sample points for statistical estimation while keeping the confidence intervals sufficiently narrow.

Date: 1982
References: Add references at CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/0191-2615(82)90030-3
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:16:y:1982:i:2:p:89-124

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().