Heuristic algorithms in topological design of telecommunication networks

• Autorzy: Karaś P.
• Języki publikacji: EN

Abstrakty

EN

The paper addresses the generic topological network design problem and considers the use of various heuristic algorithms for solving the problem. The target of the optimisation is to determine a network structure and demand allocation pattern that would minimise the cost of the network, which is given by fixed installation costs of nodes and links and variable link capacity costs described bv linear or concave functions. Input data for the optimisation consists of a list of potential node and link locations and their costs and a set of demands defined between the nodes. Since the problem is known to be NP-hard. The use of specialised heuristic algorithms is proposed. The presented approaches encompass original ideas as well as selected methods described in literature and their enhancements. The algorithms are based on the following ideas and methods: shifting of individual flows, local and global restoration of flows from chosen links or nodes, Yaged algorithm for finding local minima, Minoux greedy algorithm, simulated allocation and genetic algorithms. Efficiency of each of the proposed methods is tested on a set of numerical examples.

Słowa kluczowe

EN

topological design; network optimisation; heuristic algorithms; genetic algorithms

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2003
• Tom: nr 3
• Strony: 73--82
• Opis fizyczny: Bibliogr. 7 poz., tab., rys.

Twórcy

autor

Karaś P.

• Institute of Telecommunications, Warsaw University of Technology,

Bibliografia

• [1] M. Pióro, A. Jüttner, J. Harmatos, ́A. Szentesi, P. Gajowniczek, and A. Mysłek, “Topological design of telecommunication networks. Nodes and links localization under demand constraints” in Proc. 17th Int. Teletraf. Congr., 2001.
• [2] M. Minoux, “Network synthesis and optimum network design problems: models, solution methods and application”, Networks, vol. 19, pp. 313–360, 1989.
• [3] B. Yaged Jr., “Minimum cost routing for static network models”, Networks, vol. 1, pp. 139–172, 1972.
• [4] P. Karaś, S. Kozdrowski, and M. Pióro, “Doubly iterative algorithm for multi-layer network design” in 6th PSRT, Oficyna Wydawnicza Politechniki Wrocławskiej, 1999.
• [5] M. Pióro and P. Gajowniczek, “Solving multicommodity integral flow problems by simulated allocation”, Telecommun. Syst., vol. 7, no. 1–3, 1997.
• [6] Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs. 3rd ed., Springer, 1996.
• [7] Network examples can be downloaded from, http://www.tele.pw.edu.pl/networks/TNLLP/