A Computational Study on Ant Colony Optimization for the Traveling Salesman Problem with Dynamic Demands

Abstract 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, MM AS ) 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 MM AS and P-ACO, isolating local search as an experimental factor. While P-ACO proves indeed effective in the absence of local search, MM AS 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, MM AS outperforms P-ACO for a large part of our experimental setup.