Solving the Bi-level Linear Programming Network Design Problem (BLPNDP), which is typically regarded as a strongly NP-complete problem, with traditional mathematical programming algorithms is computationally intractable. A majority of the research efforts have been focused on tackling this problem using meta-heuristics. However, the evaluation functions in most meta-heuristic approaches involve dynamic traffic simulation when evaluating feasible capacity expansion policies. This commonly used evaluation function becomes a major bottleneck constraining the applicability of meta-heuristics as it is computationally expensive and analytically complicated. To address this issue, we present a modified Genetic Algorithm (GA) to solve the BLPNDP with a novel evaluation function which reduces the number of dynamic traffic simulations needed. The heuristic exploits the underlying linear programming structure of the BLPNDP and employs dual variable approximation techniques to estimate the evaluation function instead of dynamic traffic simulation. Empirical analyses are conducted on three networks of varying sizes to examine the performance of the GA based heuristic. From the experiments conducted, the proposed GA based heuristic outperforms the traditional GA. Also the proposed method of estimating the evaluation function is flexible and can be used within the framework of many meta-heuristic approaches.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    A genetic algorithm for bi-level linear programming dynamic network design problem


    Contributors:

    Published in:

    Transportation Letters ; 1 , 4 ; 281-294


    Publication date :

    2009-10-01


    Size :

    14 pages




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    Dynamic Continuous Network Design Problem: Linear Bilevel Programming and Metaheuristic Approaches

    Karoonsoontawong, Ampol / Waller, S. | Transportation Research Record | 2006


    Dynamic Continuous Network Design Problem: Linear Bilevel Programming and Metaheuristic Approaches

    Karoonsoontawong, A. / Waller, S. T. / National Research Council (U.S.) | British Library Conference Proceedings | 2006



    Bi-Level Programming Model in Road Network Programming and Its Genetic Algorithm

    Lu, Xiaoli / Xie, Xinlian / Zhou, Wanzhi et al. | ASCE | 2007


    Bi-Level Programming Model in Road Network Programming and Its Genetic Algorithm

    Lu, X. / Xie, X. / Zhou, W. et al. | British Library Conference Proceedings | 2007