A new approach is proposed for relaxing the computational complexity of the user equilibrium discrete network design problem (UE-DNDP), under deterministic traffic conditions, with a solution search procedure based on the selectorecombinative genetic algorithm (SGA). The SGA uses only selection and recombination operators rather than mutation. The UE-DNDP approach proposed in this study has a bilevel structure: the upper-level problem relates to the strategy of the network design authority, and the lower-level problem deals with network user behaviors. To solve the upper-level problem, the SGA is first used to create feasible network design solutions to the UE-DNDP by accounting for a budget constraint. Then the design authority selects the best network design strategy with minimum total system travel time (TSTT). Extensive experimental design and testing on GA operators and parameters are conducted to select the useful GA operators and parameters. For the lower-level problem, the best K-value concept is introduced to reduce the computational effort by allowing only a few best K-design solutions with best fitness values among the feasible network design solutions to the UE network evaluation model. The study uses statistical analysis to validate whether the proposed SGA-based UE-DNDP model is working well. The results of numerical analysis have shown that the proposed solution search procedure could significantly improve computational efficiency without loss of solution quality in terms of TSTT.


    Access

    Download

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Selectorecombinative Genetic Algorithm to Relax Computational Complexity of Discrete Network Design Problem


    Additional title:

    Transportation Research Record


    Contributors:


    Publication date :

    2006-01-01




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    Selectorecombinative Genetic Algorithm to Relax Computational Complexity of Discrete Network Design Problem

    Jeon, Kyunghwi / Lee, Jong / Ukkusuri, Satish et al. | Transportation Research Record | 2006


    Selectorecombinative Genetic Algorithm to Relax Computational Complexity of Discrete Network Design Problem

    Jeon, K. / Lee, J. S. / Ukkusuri, S. et al. | British Library Conference Proceedings | 2006


    Implementation of the RELAX Algorithm

    Liu, Z.-S. | Online Contents | 1998


    Implementation of the RELAX algorithm

    Zheng-She Liu, / Jian Li, | IEEE | 1998