A computational study on ant colony optimization for the traveling salesman problem with dynamic demands

Sabrina M. de Oliveira*, Leonardo C.T. Bezerra, Thomas Stützle, Marco Dorigo, Elizabeth F. Wanner, Sérgio R. de Souza

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    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, 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.

    Original languageEnglish
    Article number105359
    Number of pages19
    JournalComputers and Operations Research
    Volume135
    Early online date14 May 2021
    DOIs
    Publication statusPublished - Nov 2021

    Keywords

    • Ant colony optimization
    • Automatic configuration
    • Dynamic traveling salesman
    • Hypervolume indicator.

    Fingerprint

    Dive into the research topics of 'A computational study on ant colony optimization for the traveling salesman problem with dynamic demands'. Together they form a unique fingerprint.

    Cite this