The Network Design Problem (NDP), known to be NP-complete, arises in many application contexts. Transportation NDP involves optimizing the network performance under a budget constraint. Due to its non-convex and discontinuous solution space, a majority of the research efforts have been focused on tackling this problem using metaheuristics. Quantum computing is an active research area in which numerous advances have been made since the early 1990s. Quantum algorithms, such as Shor's factorization algorithm and Grover's database search algorithm, have opened up the possibility of solving NP-hard/NP-complete problems in polynomial time with quantum computers. Quantum-inspired genetic algorithms (QGA), as one of the novel meta-heuristics, seek to use insights gained through quantum computing to improve upon the performance of traditional genetic algorithms. By using the qubit as the basic unit of information in QGA, complex search space can be probabilistically characterized by superposition of states. With a suitable QGA updating mechanism, the qubit chromosome gradually converges to a single state as each qubit in the chromosome reaches the stable state of either 0 or 1. Therefore, without an exhaustive search of the qubit states combination, the solution spaces can be effectively explored and a better quality solution can be obtained with the same level of population, generation, and overall computational effort. In this research, we present a floating-point encoded quantum-inspired genetic algorithm to solve the dynamic transportation network design problem. The proposed algorithm is empirically applied to the Sioux-Falls and Monticello networks to test its effectiveness and applicability. Through numerical experiments, the QGA outperforms the conventional genetic algorithm, even with a smaller population size. Technical, computational and practical issues involved in developing and calibrating quantum-inspired genetic algorithm are discussed.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    A quantum-inspired genetic algorithm for dynamic continuous network design problem


    Contributors:
    Lin, Dung-Ying (author) / Waller, S. (author)

    Published in:

    Transportation Letters ; 1 , 1 ; 81-93


    Publication date :

    2009-01-01


    Size :

    13 pages




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    A dual approximation-based quantum-inspired genetic algorithm for the dynamic network design problem

    Lin, Dung-Ying / Lin, Peng-Hsueh / Ng, ManWo | Taylor & Francis Verlag | 2019


    Dynamic Continuous Network Design Problem

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


    Robust Dynamic Continuous Network Design Problem

    Karoonsoontawong, Ampol | Online Contents | 2007


    Robust Dynamic Continuous Network Design Problem

    Karoonsoontawong, Ampol / Waller, S. Travis | Transportation Research Record | 2007


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

    Lin, Dung-Ying / Unnikrishnan, Avinash / Waller, S. | Taylor & Francis Verlag | 2009