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

Research output: Contribution to journalResearch articleContributedpeer-review

Contributors

  • Dung Ying Lin - , University of Texas at Austin (Author)
  • S. Travis Waller - , University of Texas at Austin (Author)

Abstract

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.

Details

Original languageEnglish
Pages (from-to)81-93
Number of pages13
JournalTransportation letters
Volume1
Issue number1
Publication statusPublished - Jan 2009
Peer-reviewedYes
Externally publishedYes

External IDs

ORCID /0000-0002-2939-2090/work/141543843

Keywords

ASJC Scopus subject areas

Keywords

  • Dynamic continuous network design problem, Meta-heuristic, Quantum computing, Quantum-inspired genetic algorithm