Ant Colony

ISSN 1064 2307, Journal of Computer and Systems Sciences International, 2010, Vol. 49, No. 1, pp. 30–43. © Pleiades Publishing, Ltd., 2010. Original Russian Text © A.A. Kazharov, V.M. Kureichik, 2010, published in Izvestiya Akademii Nauk. Teoriya i Sistemy Upravleniya, 2010, No. 1, pp. 32–45.

COMPUTER METHODS

Ant Colony Optimization Algorithms for Solving Transportation Problems
A. A.Kazharov and V. M. Kureichik
Taganrog Technology Institute, Southern Federal University, Taganrog, ul. Chekhova 22, Taganrog, 347928 Russia
Received May 19, 2009

Abstract—The work is devoted to solving transportation problems with ant colony algorithms. These algo rithms are based on the simulation of the behavior of an ant colony. Several modifications of the ant colony algorithm are developed.DOI: 10.1134/S1064230710010053

INTRODUCTION Today, the vehicle routing problem becomes more and more topical. Under the current economics con dition, it is impossible to meet the customer require ments without using automated solution of transport logistics problems. Here, item prices directly depend on the solution of this problem, and the delivery price is comparable with the item price insome market seg ments [1]. In this work, the possibility of applying ant colony algorithms to various transportation problems and their modifications is considered. This algorithm class was developed in the context of a research field that is called natural computing [2]. Investigations in this field started in the mid 1990s. The author of the idea was Marco Dorigo [3–5], who proposed to simulatethe behavior of an ant colony. The Travelling Salesman Problem (TSP) and the vehicle routing problem with taking into account capacity is considered. For each problem, the mathe matical model of the ant colony behavior is developed. In this work, several modifications of the ant col ony algorithms were implemented and investigated. The results allow us to judge the choice of the optimal parametersfor the solution of transportation problems with various initial data. Experimental comparison with the following methods of the optimal path search is conducted: the branch and bounds algorithm, nearest neighbor algorithm, modified genetic algo rithm, and standard ant colony algorithm. The exper imental investigations have proved the efficiency of the modified ant colony algorithms compared to thestan dard ant colony algorithms and genetic algorithms. To describe the general principles and mathematical model of the ant colony algorithms, consider the TSP. 1. THE TRAVELLING SALESMAN PROBLEM The Travelling Salesman Problem belongs to the class of NP complete problems. It consists in finding
30

the shortest Hamiltonian path in a graph [6]. Without any changes in its definition, the TSPis used to design the configuration of communications, to develop computer network architecture, to route motor and air transport, etc. The informal formulation of the TSP is as follows: a travelling salesman must visit W towns, each of them exactly once, and return to the starting point using the path with the minimum cost. In a more strict formula tion we have: Given a graph G = (X, U), where |X|= n is the set of nodes (towns) and |U| = m is the set of edges (possible paths between towns).; givena matrix D(i, j), where i, j ∈ 1, 2, …, n, represents the costs of the travel from xi to xj. It is necessary to find a permutation ϕ of the ele ments of the set X that minimizes the objective func tion: Fitness ( ϕ ) = D ( ϕ (1),
ϕ ( n )) +

∑ { D (ϕ(i), ϕ(i + 1))} → min.
i

If the graph isnot fully connected, then the entries of matrix D that correspond to the empty edges in the graph are filled with infinity; thus, the passage through these edges is excluded. 2. ANT COLONY OPTIMIZATION ALGORITHM 2.1. General Principles As mentioned above, the basic idea of this algo rithm is the simulation of the ant colony behavior, i.e., collective adaptation. The colony represents a system...