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.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

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


    Beteiligte:
    Lin, Dung-Ying (Autor:in) / Waller, S. (Autor:in)

    Erschienen in:

    Transportation Letters ; 1 , 1 ; 81-93


    Erscheinungsdatum :

    2009-01-01


    Format / Umfang :

    13 pages




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    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