The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Optimizing network load balancing: an hybridization approach of metaheuristics with column generation

På svenska

Author

  • Dorabella Santos
  • Amaro de Sousa
  • Filipe Alvelos
  • Michal Pioro

Summary, in English

Given a capacitated telecommunications network with single path routing and an estimated traffic demand matrix, we aim to determine the routing path of each traffic commodity such that the whole set of paths provide an optimal network load balancing. In a recent paper, we have proposed a column generation based heuristic where, in the first step, we use column generation to solve a linear programming relaxation of the original problem (obtaining, in this way, a lower bound and a set of paths for each commodity) and, in the second step, we apply a multi-start local search with path relinking heuristic on the solution space defined by the paths of the first step. Here, we propose a hybridization approach of the metaheuristic with column generation that can be seen as an enhanced version of the previous approach: we run column generation not only at the beginning (to define the initial search space) but also during the search. These additional column generation steps consist in solving a perturbed problem defined by the incumbent solution. In the previous paper, we have shown that the first approach is efficient in obtaining near optimal routing solutions within short running times. With the enhanced version, we show through computational results that the additional paths, introduced by the additional column generation steps, either improve the efficiency of the algorithm or show similar efficiency in the cases where the original algorithm is already very efficient.

Publishing year

2013

Language

English

Pages

959-968

Publication/Series

Telecommunication Systems

Volume

52

Issue

2

Document type

Journal article

Publisher

Springer

Topic

  • Electrical Engineering, Electronic Engineering, Information Engineering

Status

Published

ISBN/ISSN/Other

  • ISSN: 1018-4864