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 journalArticle

Abstract

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
Volume11
Issue number3
DOIs
Publication statusPublished - 2019 May 4

Fingerprint

Genetic algorithms
policy of expansion
Function evaluation
road user
road network
heuristics
Profitability
urban area
profit
traffic
infrastructure
paradigm
evaluation
resources
Values

All Science Journal Classification (ASJC) codes

  • Transportation

Cite this

Lin, Dung-Ying ; Lin, Peng Hsueh ; Ng, Man Wo. / A dual approximation-based quantum-inspired genetic algorithm for the dynamic network design problem. In: Transportation Letters. 2019 ; Vol. 11, No. 3. pp. 158-173.
@article{5ea54afbd7c44ad89cbd7e6be21341eb,
title = "A dual approximation-based quantum-inspired genetic algorithm for the dynamic network design problem",
abstract = "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.",
author = "Dung-Ying Lin and Lin, {Peng Hsueh} and Ng, {Man Wo}",
year = "2019",
month = "5",
day = "4",
doi = "10.1080/19427867.2017.1299395",
language = "English",
volume = "11",
pages = "158--173",
journal = "Transportation Letters",
issn = "1942-7867",
publisher = "Maney Publishing",
number = "3",

}

A dual approximation-based quantum-inspired genetic algorithm for the dynamic network design problem. / Lin, Dung-Ying; Lin, Peng Hsueh; Ng, Man Wo.

In: Transportation Letters, Vol. 11, No. 3, 04.05.2019, p. 158-173.

Research output: Contribution to journalArticle

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

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 -