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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Combinatorial programming, statistical optimization and the optimal transportation network problem


    Contributors:

    Published in:

    Publication date :

    1981-02-09


    Size :

    36 pages




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English