IEEE Computational Intelligence Magazine - February 2020 - 53

problem can be seen as a series of different
static problem instances. Hence, a straightforward method to deal with these type of
problems is to consider each dynamic
change as the arrival of a new problem
instance that needs to be solved from
scratch. However, this method is often
impractical when the dynamic change is
relatively small [5]-[7]. A better strategy is
to adapt to dynamic changes by transferring the past experience of the optimization process since the new environment
will be in some sense related to the old
one. ACO is a good choice in adapting to
dynamic changes because it naturally
implements a memory structure (i.e., the
pheromone model), allowing ACO to
remember the past experience. Therefore,
when a dynamic change occurs the past
experience can be transferred via the
pheromone trails of previously optimized
environments [7]. Successful ACO applications to dynamic combinatorial optimization problems include Internet-like
network routing [8], vehicle routing [9],
and train scheduling [10].
In the last decade, studying ACO
algorithms for dynamic environments
attracted a lot of attention because of
their intrinsic features [6], [7]. Several
dynamic strategies have been designed to
enhance the adaptation capabilities of
ACO [11]-[14]. These strategies have
been mainly tested on different dynamic
variations of the traveling salesperson
problem (TSP), which makes the dynamic TSP (DTSP) an ideal subject for a case
study in this article. However, in the
existing DTSPs [15]-[19], important
dynamic optimization settings (e.g., the
type, frequency, and magnitude of the
dynamic change) are not following any
experimentation protocol. This causes
many difficulties for researchers to analyze the strengths and weaknesses of algorithms in DTSPs. Consequently, the
following important questions arise:
Which ACO algorithm performs best under
which dynamic settings and why? Which
ACO features are important when addressing
dynamic environments? We strongly believe
that it would be beneficial to have a unified dynamic benchmark framework to
evaluate algorithms in DTSPs with common dynamic settings [20], [21].

This article aims to provide insights
concerning the behavior of ACO using
the DTSP as a case study. In order to
achieve this aim, we set out the following two objectives. First, the existing
ACO algorithms designed for DTSPs
are classified according to their framework either as evaporation-based or as population-based. Second, a unified dynamic
benchmark framework is proposed to
systematically carry out a critical evaluation of the most important features of
ACO algorithms (i.e., the decision rule
for constructing solutions, the policy for
updating pheromone trails, and the
dynamic strategy for enhancing adaptation capabilities) on different test cases.
In fact, this benchmark framework will
also be able to serve as an initial proving
ground for new algorithmic ideas in
dynamic environments.
The rest of this article is organized as
follows. Section II describes the generation of dynamic test cases utilizing the
unified dynamic benchmark framework
with the TSP as the base problem. Section III classifies the ACO algorithms
from the literature that have been
designed for DTSPs. Section IV outlines the experimental setup of our
study. Next, Section V presents and analyzes the experimental results. Finally,
concluding remarks are presented in
Section VI.
II. Dynamic Travelling Salesperson
Problem

In this section, we describe how dynamic test cases can be generated from a
static problem instance. TSP is used as
the base problem to generate the
dynamic test cases in this article because
it is a problem without too many technicalities (e.g., hard constraints). Hence,
it is more convenient to evaluate algorithms because their behaviors will not
be obscured by the technicalities of the
problem [22]. Additionally, the TSP is an
important N P -hard combinatorial
optimization problem arising in several
applications [23]. Finally, the best ACO
algorithms for the TSP very often perform well when applied to more complex problems. For example, the Ant
Colony System [1], which is one of the

best performing ACO algorithms on the
TSP, is used to solve world-scale instances of vehicle routing problems [24].
A. TSP Formulation

The TSP can be described as follows:
given a collection of cities, the objective
of a salesperson is to find the shortest
Hamiltonian cycle of visiting all of the
cities once before finally returning to the
starting city. More formally, a TSP problem instance is modeled by a complete
directed weighted graph G = (N, A),
where N is a set of n nodes and A is a
set of arcs fully connecting the nodes. For
the classical TSP, nodes and arcs represent
respectively the cities and the links
between the cities. Each arc (i, j ) ! A is
associated with a non-negative value
w ij ! R +, which represents the distance
between nodes i and j. In this article, we
will use symmetric TSP problem instances to generate dynamic test cases and,
hence, these distances are independent of
the direction of traversing the arcs, that is,
w ij = w ji for every pair of nodes.
B. Generating Dynamic
Test Environments

Every TSP problem instance consists of a
weight matrix that contains all the weights
associated with the arcs of the corresponding graph G. In order to generate dynamic test cases the weight matrix of the
problem is subject to changes as follows:
W(T ) = {w ij (T )}n # n,

(1)

where W($) is the weight matrix and T
is the environmental period index
which is synchronized with the algorithm during the optimization process.
Therefore, the environmental period
index is defined as T = ^t /f h, where f
is the frequency of change and t is the
evaluation counter of the algorithm.
A particular TSP solution r =
[r 1, f, r n] is a permutation of node
indices, and for the DTSP it is evaluated
as follows:
z(r, t ) = w r n r 1(T ) +

n-1

(T ). (2)

ri ri + 1

i=1

Mainly, there are two components of the
graph G representing the problem that

FEBRUARY 2020 | IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE

IEEE Computational Intelligence Magazine - February 2020

Table of Contents for the Digital Edition of IEEE Computational Intelligence Magazine - February 2020