Algoritmos heurísticos para equilibrio de carga en anillos bidireccionales

Résumé

Internet applications need a substantial amount of bandwidth in order to guarantee access to different applications with minimal delays. Ring networks are suited to deliver a large amount of bandwidth in a reliable and inexpensive way. An optimal load balancing is of paramount importance because it increases the system capacity and improves the overall ring performance. In this context an important optimisation problem is the Weighted Ring Loading Problem (WRLP). That is the design of a direct path for each request, in a communication network, in a way that high load on the arcs/edges will be avoided, where an arc is an edge endowed with a direction. The load of an arc is defined as the total weight of those requests routed through the Arc in its direction (WRALP), and the load of an edge as the number of routes traversing the Edge in either direction (WRELP). WRALP/WRELP ask for a routing scheme such that the maximum load on arcs/edges will be minimum. In this Thesis, we study these two problems without demand splitting. The work presented in this Thesis is also focused in other two problems that arise in the design of optical telecommunication networks, namely the Synchronous optical network Ring Assignment Problem (SRAP) and the Intraring synchronous optical network Design Problem (IDP). In SRAP, the objective is to minimise the number of rings and in IDP, the objective is to minimise the number of Add-Drop Multiplexers (ADMs). Both problems are subject to a ring capacity constraint. To solve these four NP-hard (Non-deterministic Polynomial-time hard) problems, are proposed several metaheuristic algorithms including bio-inspired randomised search heuristics such as Evolutionary Algorithms (EAs), Swarm Intelligence (SI) algorithms, and hybridisations with Local Search (LS). The foremost objectives of this work were those of defining/applying new algorithms for solving the four problems addressed in this Thesis, capable of producing better results in smaller times comparing with the results already obtained in literature. Were performed several modifications to the basic form of the algorithms in order to improve their efficiency. Simulation results verify the effectiveness of the proposed algorithms.