TY - JOUR
T1 - A Novel Generalized Metaheuristic Framework for Dynamic Capacitated Arc Routing Problems
AU - TONG, Hao
AU - MINKU, Leandro L.
AU - MENZEL, Stefan
AU - SENDHOFF, Bernhard
AU - YAO, Xin
PY - 2022/12
Y1 - 2022/12
N2 - The capacitated arc routing problem (CARP) is a challenging combinatorial optimization problem abstracted from many real-world applications, such as waste collection, road gritting, and mail delivery. However, few studies considered dynamic changes during the vehicles' service, which can cause the original schedule infeasible or obsolete. The few existing studies are limited by the dynamic scenarios considered, and by overly complicated algorithms that are unable to benefit from the wealth of contributions provided by the existing CARP literature. In this article, we first provide a mathematical formulation of dynamic CARP (DCARP) and design a simulation system that is able to consider dynamic events while a routing solution is already partially executed. We then propose a novel framework which can benefit from the existing static CARP optimization algorithms so that they could be used to handle DCARP instances. The framework is very flexible. In response to a dynamic event, it can use either a simple restart strategy or a sequence transfer strategy that benefits from the past optimization experience. Empirical studies have been conducted on a wide range of DCARP instances to evaluate our proposed framework. The results show that the proposed framework significantly improves over state-of-the-art dynamic optimization algorithms. © 1997-2012 IEEE.
AB - The capacitated arc routing problem (CARP) is a challenging combinatorial optimization problem abstracted from many real-world applications, such as waste collection, road gritting, and mail delivery. However, few studies considered dynamic changes during the vehicles' service, which can cause the original schedule infeasible or obsolete. The few existing studies are limited by the dynamic scenarios considered, and by overly complicated algorithms that are unable to benefit from the wealth of contributions provided by the existing CARP literature. In this article, we first provide a mathematical formulation of dynamic CARP (DCARP) and design a simulation system that is able to consider dynamic events while a routing solution is already partially executed. We then propose a novel framework which can benefit from the existing static CARP optimization algorithms so that they could be used to handle DCARP instances. The framework is very flexible. In response to a dynamic event, it can use either a simple restart strategy or a sequence transfer strategy that benefits from the past optimization experience. Empirical studies have been conducted on a wide range of DCARP instances to evaluate our proposed framework. The results show that the proposed framework significantly improves over state-of-the-art dynamic optimization algorithms. © 1997-2012 IEEE.
KW - Dynamic capacitated arc routing problem (DCARP)
KW - experience-based optimization
KW - metaheuristics
KW - restart strategy (RS)
KW - transfer optimization
UR - http://www.scopus.com/inward/record.url?scp=85124229298&partnerID=8YFLogxK
U2 - 10.1109/TEVC.2022.3147509
DO - 10.1109/TEVC.2022.3147509
M3 - Journal Article (refereed)
SN - 1089-778X
VL - 26
SP - 1486
EP - 1500
JO - IEEE Transactions on Evolutionary Computation
JF - IEEE Transactions on Evolutionary Computation
IS - 6
ER -