Parallel ACO with a Ring Neighborhood for Dynamic TSP

Introduction

Ant Colony Optimization (ACO) (Dorigo & Stützle, Ant Colony Optimization, 2004) is nowadays one of the metaheuristics able to solve large scale optimization problems. Ants are social insects with cooperative and adaptive features. The ant-based algorithms simulate and exploit their natural mechanisms. In order to improve the efficiency, the software designers are now using parallelization of algorithms. Ant-based algorithms are in particular well suited for parallel implementations (Manfrin, Birattari, Stützle, & Dorigo, 2006) because the ants are independent and are able to operate in an asynchronous way. An overview of the parallel metaheuristics is in (Cung, Martins, Ribeiro, & Roucairol, 2001; Alba, 2005) and an overview of the ACO parallel approaches is in (Randall & Lewis, 2002).

Usually, the metaheuristics, involving intelligent (Dorigo & Stützle, Ant Colony Optimization, 2004) and complex agent-based systems (Iantovics & Enăchescu, 2009) are successfully applied for static NP-hard problems. Nowadays the focus is on the dynamic variants of difficult optimization problems. Following this trend, a new parallel approach of the ACO for the Dynamic Traveling Salesman Problem (DTSP) is introduced in the current paper.

Dynamism has different meanings when referring to optimization problems. In our paper the dynamism means that from time to time a randomly chosen node is slightly moved in its neighborhood. In real life also sometimes roads are closed, or a customer is not available, forcing the supplier to deliver the goods to a nearby depot. The DTSP problem is about finding a minimum cost tour (Cung, Martins, Ribeiro, & Rouca, 2001) passing exactly once through each available city (Dorigo & Stützle, Ant Colony Optimization, 2004).

The current paper starts with the state-of-art on static and dynamic ant-algorithms for Traveling Salesman Problem (TSP). The new introduced parallel approach for the Dynamic TSP is further described and followed by numerical experiments. The paper concludes by comparatively discussing the results provided by both the sequential and parallel approaches and pointing out some further research.

The Ant Colony Optimization Metaheuristic

Ant colony optimization (ACO) (Dorigo & Di Caro, The ant colony optimization meta-heuristic, 1999) (Dorigo, Di Caro, & Gambardella, Ant algorithms for discrete optimization, 1999) is a sub-domain of Swarm intelligence. Swarm intelligence algorithms are based on the observation of swarm’s behavior, specifically on their cooperation through self-organization. Many Combinatorial Optimization Problems (COPs) are solved today using ACO. In order to use ACO it is important to define an adequate model for a COP. The model of an optimization problem can be defined as in Dorigo & Di Caro (1999) and Dorigo & Socha (2006):

• Definition 1: A model P = (S; Ω; f) of a COP consists of:

  • •

    A search space S defined over a finite set of discrete decision variables,

  • •

    A set Ω of constraints among the variables,

  • •

    An objective function f: S → R⁺ to be minimized.

Given a set of discrete variables X_i, i = 1,…, n, with values v_ij∈ D_i = {v_i1,…, v_i|Di|} a variable instantiation, that is, the assignment of a value v_ij to a variable X_i, is denoted by X_i ← v_ij.

The search space S is the product of all sets of possible instantiations, for all the discrete variables:

A feasible solution s∈ S is a complete assignment in which each decision variable has an assigned value that satisfies all the constraints in the set Ω. If the set Ω is empty, P is called an unconstrained problem model, otherwise it is said to be constrained.