Parallel ACO with a Ring Neighborhood for Dynamic TSP

Parallel ACO with a Ring Neighborhood for Dynamic TSP

Camelia M. Pintea (Technical University of Cluj-Napoca, Northern University Centre, Baia Mare, Romania), Gloria Cerasela Crisan (Department of Mathematics, Informatics and Educational Sciences, “Vasile Alecsandri” University of Bacau, Bacau, Romania) and Mihai Manea (“Vasile Alecsandri” University of Bacau, Bacau, Romania)
Copyright: © 2012 |Pages: 13
DOI: 10.4018/jitr.2012100101
OnDemand PDF Download:
$37.50

Abstract

The current paper introduces a new parallel computing technique based on ant colony optimization for a dynamic routing problem. Ant Colony Optimization is a metaheurisitc that is able to solve large scale optimization problems. In the dynamic traveling salesman problem, the distances between cities as travel times are no longer fixed. The new technique uses a parallel model for a problem variant that allows a slight movement of nodes within their neighborhoods. The algorithm is tested with success on several large data sets. The paper concludes with a discussion of the results provided by both the sequential and parallel approaches and calls for further research on the subject.
Article Preview

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 Xi, i = 1,…, n, with values vij∈ Di = {vi1,…, vi|Di|} a variable instantiation, that is, the assignment of a value vij to a variable Xi, is denoted by Xi ← vij.

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.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 10: 4 Issues (2017)
Volume 9: 4 Issues (2016)
Volume 8: 4 Issues (2015)
Volume 7: 4 Issues (2014)
Volume 6: 4 Issues (2013)
Volume 5: 4 Issues (2012)
Volume 4: 4 Issues (2011)
Volume 3: 4 Issues (2010)
Volume 2: 4 Issues (2009)
Volume 1: 4 Issues (2008)
View Complete Journal Contents Listing