J Math Model Algor (2007) 6:361–391 DOI 10.1007/s10852-007-9060-y Finding Edge-disjoint Paths in Networks: An Ant Colony Optimization Algorithm

Abstract One of the basic operations in communication networks consists in estab-lishing routes for connection requests between physically separated network nodes. In many situations, either due to technical constraints or to quality-of-service and survivability requirements, it is required that no two routes interfere with each other. These requirements apply in particular to routing and admission control in large-scale, high-speed and optical networks. The same requirements also arise in a multitude of other applications such as real-time communications, vlsi design, scheduling, bin packing, and load balancing. This problem can be modeled as a combinatorial optimization problem as follows. Given a graph G representing a network topology, and a collection T = {(s1, t1)... (sk, tk)} of pairs of vertices in G representing connection request, the maximum edge-disjoint paths problem is an NP-hard problem that consists in determining the maximum number of pairs in T that can be routed in G by mutually edge-disjoint si − ti paths. We propose an ant colony optimization (aco) algorithm to solve this problem. aco algorithms are approximate algorithms that are inspired by the foraging behavior of real ants. Th