A genetic algorithm based approach to route selection and capacity flow assignment

Abstract

In large-scale computer communication networks (e.g. the nowadays Internet), the assignment of link capacity and the selection of routes (or the assignment of flows) are extremely complex network optimization problems. Efficient solutions to these problems are much sought after because such solutions could lead to considerable monetary savings and better utilization of the networks. Unfortunately, as indicated by much prior theoretical research, these problems belong to the class of nonlinear combinatorial optimization problems, which are mostly (if not all) NP-hard problems. Although the traditional Lagrange relaxation and sub-gradient optimization methods can be used for tackling these problems, the results generated by these algorithms are locally optimal instead of globally optimal. In this paper, we propose a genetic algorithm based approach to providing optimized integrated solutions to the route selection and capacity flow assignment problems. With our novel formulation and genetic modeling, the proposed algorithm generates much better solutions than two well known efficient methods in our simulation studies. © 2002 Elsevier Science B.V. All rights reserved.