A Multi-start Tabu Search Approach for Solving the Information Routing Problem

摘要

In this paper, we propose a new global routing algorithm supporting advance reservation. A set of flows are shared across a communication network. Each flow has a source node, a destination node and a predetermined traffic demand. The design goal of the routing is to minimize the overall network congestion under the constraint that each flow should be sent along a single path without being bifurcated. We model this optimization problem as a single path multicommodity flow problem (SPMFP). As the complexity of the SPMFP is NP-Hard, a Multi-start Tabu Search (MTS) is proposed as a solution approach. The empirical validation is done using a simulation environment called Inform Lab. A comparison to a state-of-the-art ant colony system (ACS) approach is performed based on a real case of maritime surveillance application. The same instances are optimally solved using CPLEX. The experimental results show that the MTS produces considerably better results than the ACS to the detriment of the CPU time.