Application of Ant System to network design problem

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.