Application of Ant System to network design problem

Authors: Hossain Poorzahedy¹; Farhad Abulghasemi²

Source: Transportation, Volume 32, Number 3, May 2005 , pp. 251-273(23)

Publisher: Springer

Buy & download fulltext article:

Price: $47.00 plus tax (Refund Policy)

Abstract:

Network design problem (NDP) is the problem of choosing from among a set of alternative projects which optimizes an objective (e.g., minimizes total travel time), while keeping consumption of resources (e.g., budget) within their limits. This problem is difficult to solve, because of its combinatorial nature and nonconvexity of the objective function. Many algorithms are presented to solve the problem more efficiently, while trading-off accuracy with computational speed. This increase in speed stems from certain approximations in the formulation of the problem, decomposition, or heuristics. This study adapts a meta – heuristic approach to solve NDP, namely Ant System (AS). The algorithm is first designed, and then calibrated to solve NDP for the Sioux Falls test network. The behavior of the algorithm is then investigated. The result seems encouraging.

Keywords: Ant System; network design

Document Type: Research article

DOI: http://dx.doi.org/10.1007/s11116-004-8246-7

Affiliations: 1: Department of Civil Engineering, P.O. BOX 11365-9313, Tehran, Iran, Email: porzahed@sharif.edu 2: Department of Civil Engineering, P.O. BOX 11365-9313, Tehran, Iran,

Publication date: 2005-05-01