Plenary lecture 2: a heuristic algorithm for the network design problem
Milan Tuba · 2010
The network design problem (NDP) is a well known problem which can be applied to many different types of networks. It was well investigated applied to computer communications networks during the time of Internet development. Today it is again very actual applied mostly to the dynamic wireless networks (MANET - mobile ad hoc networks). The network design problem is an NP-hard problem which involves topology selection (subset of possible links) and routing determination (paths for the offered traffic). Capacity assignment is usually treated as a 0-1 problem and as such included it in the topology problem. This does not make the network design problem easier, just the opposite, it moves optimization from continuous to integer. The goal is to minimize the cost which can be a combination of the link costs and delay penalties, under possible additional constraints. Such hard combinatorial graph problems are often treated by evolutionary metaheuristics. In many cases better results and faster convergence are achieved by hybrid algorithms where some local searcher that utilizes particular knowledge about the corresponding problem is included. Here we propose and analyze a computationally feasible heuristic algorithm which excludes underutilized links by a version of flow-deviation method. A simplified queuing model is developed for cost function estimate. Some theoretical results are also established that direct initial approximation. Proposed algorithm can dynamically be adjusted for faster or better results. It is implemented and computes a good solution that is robust with respect to often required dynamic changes of the cost function.