TY - JOUR
T1 - A dual approximation-based quantum-inspired genetic algorithm for the dynamic network design problem
AU - Lin, Dung Ying
AU - Lin, Peng Hsueh
AU - Ng, Man Wo
N1 - Funding Information:
This work was supported by Ministry of Science and Technology, Taiwan [grant number 103-2410-H-006-079-MY3].
Publisher Copyright:
© 2017, © 2017 Informa UK Limited, trading as Taylor & Francis Group.
PY - 2019/5/4
Y1 - 2019/5/4
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85016179600&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85016179600&partnerID=8YFLogxK
U2 - 10.1080/19427867.2017.1299395
DO - 10.1080/19427867.2017.1299395
M3 - Article
AN - SCOPUS:85016179600
VL - 11
SP - 158
EP - 173
JO - Transportation Letters
JF - Transportation Letters
SN - 1942-7867
IS - 3
ER -