摘要
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. © 2009 J. Ross Publishing, Inc.