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

Abstract

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.