TY - JOUR
T1 - A computational study on ant colony optimization for the traveling salesman problem with dynamic demands
AU - de Oliveira, Sabrina M.
AU - Bezerra, Leonardo C.T.
AU - Stützle, Thomas
AU - Dorigo, Marco
AU - Wanner, Elizabeth F.
AU - de Souza, Sérgio R.
PY - 2021/11
Y1 - 2021/11
N2 - Ant colony optimization (ACO) algorithms have originally been designed for static optimization problems, where the input data is known in advance and is not subject to changes over time. Later, the long term memory of ACO proved effective for reoptimization over environment changes when extended to deal with dynamic combinatorial optimization problems (DCOPs). Among the major proposals of this kind, several adaptations of ACO procedures to improve information reuse can be identified, as well as a population-based ACO algorithm (P-ACO) specifically designed for DCOPs. Indeed, P-ACO drew the attention of the research community due to its ability to faster process pheromone information, but the few works assessing the effectiveness of the adapted ACO procedures and also P-ACO are not enough to reach more general conclusions on the current state-of-the-art in ACO for dynamic optimization. In this work, we conduct an extensive experimental campaign to evaluate the most common ACO procedure adaptations identified in the literature, using as underlying algorithms the state-of-the-art in ACO for static optimization (MAX-MIN Ant System, MMAS) and the most relevant ACO algorithm proposed for dynamic optimization (P-ACO). A variant of the traveling salesman problem with dynamic demands (DTSP) is used as test benchmark, similarly to most investigations on ACO for combinatorial optimization. Besides the carefully designed experimental setup we adopt, our work represents a significant contribution for, at least, three reasons. First, our work is the first to acknowledge that DCOPs require custom-configured parameter settings, and also the first to use automatic configuration tools for this task. Concretely, we show how the hypervolume indicator can be used to evaluate and configure the anytime behavior of algorithms for DCOPs. Second, we directly compare MMAS and P-ACO, isolating local search as an experimental factor. While P-ACO proves indeed effective in the absence of local search, MMAS is able to consistently outperform it when local search is adopted. Finally, we conduct an experimental investigation on the DCOP-specific components proposed for ACO, once again isolating local search. Results show that those components contribute very little to performance when algorithms are allowed to use local search, but are remarkably effective in its absence. In fact, coupled with DCOP components, MMAS outperforms P-ACO for a large part of our experimental setup.
AB - Ant colony optimization (ACO) algorithms have originally been designed for static optimization problems, where the input data is known in advance and is not subject to changes over time. Later, the long term memory of ACO proved effective for reoptimization over environment changes when extended to deal with dynamic combinatorial optimization problems (DCOPs). Among the major proposals of this kind, several adaptations of ACO procedures to improve information reuse can be identified, as well as a population-based ACO algorithm (P-ACO) specifically designed for DCOPs. Indeed, P-ACO drew the attention of the research community due to its ability to faster process pheromone information, but the few works assessing the effectiveness of the adapted ACO procedures and also P-ACO are not enough to reach more general conclusions on the current state-of-the-art in ACO for dynamic optimization. In this work, we conduct an extensive experimental campaign to evaluate the most common ACO procedure adaptations identified in the literature, using as underlying algorithms the state-of-the-art in ACO for static optimization (MAX-MIN Ant System, MMAS) and the most relevant ACO algorithm proposed for dynamic optimization (P-ACO). A variant of the traveling salesman problem with dynamic demands (DTSP) is used as test benchmark, similarly to most investigations on ACO for combinatorial optimization. Besides the carefully designed experimental setup we adopt, our work represents a significant contribution for, at least, three reasons. First, our work is the first to acknowledge that DCOPs require custom-configured parameter settings, and also the first to use automatic configuration tools for this task. Concretely, we show how the hypervolume indicator can be used to evaluate and configure the anytime behavior of algorithms for DCOPs. Second, we directly compare MMAS and P-ACO, isolating local search as an experimental factor. While P-ACO proves indeed effective in the absence of local search, MMAS is able to consistently outperform it when local search is adopted. Finally, we conduct an experimental investigation on the DCOP-specific components proposed for ACO, once again isolating local search. Results show that those components contribute very little to performance when algorithms are allowed to use local search, but are remarkably effective in its absence. In fact, coupled with DCOP components, MMAS outperforms P-ACO for a large part of our experimental setup.
KW - Ant colony optimization
KW - Automatic configuration
KW - Dynamic traveling salesman
KW - Hypervolume indicator.
UR - https://www.sciencedirect.com/science/article/pii/S0305054821001362
UR - http://www.scopus.com/inward/record.url?scp=85110296283&partnerID=8YFLogxK
U2 - 10.1016/j.cor.2021.105359
DO - 10.1016/j.cor.2021.105359
M3 - Article
AN - SCOPUS:85110296283
SN - 0305-0548
VL - 135
JO - Computers and Operations Research
JF - Computers and Operations Research
M1 - 105359
ER -