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

Dung Ying Lin, Peng Hsueh Lin, Man Wo Ng

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


In this paper, we formulate a dynamic transportation network design model in which traffic dynamics are modeled by the cell transmission model. In the formulation, transportation planners decide on the optimal capacity expansion policies of existing transportation network infrastructure with limited resources, while road users react to the capacity changes by selfishly choosing routes to maximize their own profit. Owing to the problem complexity, a majority of the research efforts have focused on tackling this problem using meta-heuristics. In this study, we incorporate a series of dual-variable approximation techniques into the paradigm of a quantum-inspired genetic algorithm (QIGA) and devise an efficient evaluation function based on these techniques. The proposed QIGA contains a series of enhancements compared to conventional genetic algorithms (GAs) and can be considered as a better alternative when solving problems with a complex solution space. The QIGA is applied to a synthetic network, a subnetwork of a real-world road network, and a realistic network to justify its theoretical and practical value. From the numerical results, it is found that in the same computational time, the QIGA outperforms the conventional GA by 3.86–5.63% in terms of the objective value, which can be significant, especially when network expansion of a large urban area is considered. Technical, computational, and practical issues involved in developing the QIGA are investigated and discussed.

Original languageEnglish
Pages (from-to)158-173
Number of pages16
JournalTransportation Letters
Issue number3
Publication statusPublished - 2019 May 4

All Science Journal Classification (ASJC) codes

  • Transportation


Dive into the research topics of 'A dual approximation-based quantum-inspired genetic algorithm for the dynamic network design problem'. Together they form a unique fingerprint.

Cite this