ALCOMFT-TR-03-105

M. Blesa and C. Blum
Ant Colony Optimization for the maximum disjoint paths problem
Barcelona. Work packages 2, 3 and 5. November 2003.

Abstract: One of the basic operations in communication networks consists in establishing 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 specially 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.

Given a graph G representing a network topology, and a collection T={(s₁,t₁)...(s_k,t_k)} of pairs of vertices in G representing connection request, the maximum 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 disjoint s_i-t_i paths.

We propose an Ant Colony Optimization (ACO) algorithm to solve this problem. ACO algorithms are inspired by the foraging behavior of real ants, whose distributed nature makes them suitable for the applications both in static and dynamic network environments. Our current version is aimed for the application in static graphs. In comparison to a multi-start greedy approach, our algorithm has advantages especially when speed is an issue.

Postscript file: ALCOMFT-TR-03-105.ps.gz (253 kb).