Selectorecombinative genetic algorithm to relax computational complexity of discrete network design problem

Kyunghwi Jeon, Jong Sung Lee, Satish Ukkusuri, S. Travis Waller

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationNetwork Modeling 2006
PublisherNational Research Council
Number of pages13
ISBN (Print)0309099730, 9780309099738
StatePublished - 2006

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Mechanical Engineering


Dive into the research topics of 'Selectorecombinative genetic algorithm to relax computational complexity of discrete network design problem'. Together they form a unique fingerprint.

Cite this