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

Dorabella Santos , Amaro de Sousa , Filipe Alvelos , Michał Pióro


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.
Author Dorabella Santos - [Instituto de Telecomunicacoes]
Dorabella Santos,,
, Amaro de Sousa
Amaro de Sousa,,
, Filipe Alvelos - [Universidade do Minho]
Filipe Alvelos,,
, Michał Pióro (FEIT / IT)
Michał Pióro,,
- The Institute of Telecommunications
Journal seriesTelecommunication Systems, ISSN 1018-4864, [1572-9451 (electronic version)]
Issue year2013
Keywords in EnglishLink load balancing optimization · Column generation based heuristics · Routing · Traffic engineering, Artificial Intelligence (incl. Robotics), Business Information Systems, Column generation based heuristics, Computer Communication Networks, Link load balancing optimization, Probability Theory and Stochastic Processes, Routing, Traffic engineering
ASJC Classification2208 Electrical and Electronic Engineering
URL http://link.springer.com/article/10.1007/s11235-011-9604-3
ProjectThe Develpment of Digital Communicatios. Project leader: Lubacz Józef, , Phone: 22 234 65 31, start date 04-05-2012, planned end date 31-03-2013, end date 31-12-2013, IT/2012/statut, Completed
WEiTI Działalność statutowa
Optimization models and methods for planning of integrated transport network under uncertain, and short-term and long-term variable traffic demand. Project leader: Pióro Michał, , Phone: +48 22 234-7383, start date 08-10-2010, planned end date 08-10-2011, end date 31-03-2012, IT/2008/SPUB/07, Completed
WEiTI Projekty finansowane przez MNiSW
European Network of the Future: Anticipating the Network of the Future - From Theory to Design. Project leader: Pióro Michał, , Phone: +48 22 234-7383, start date 01-01-2008, end date 30-06-2012, IT/2008/7PR/05, Completed
WEiTI 7 Framework Programme (7 FP) [7 Program Ramowy (7 PR)]
Languageen angielski
10.pdf 566.51 KB
Score (nominal)25
Score sourcejournalList
ScoreMinisterial score = 20.0, 17-03-2020, ArticleFromJournal
Ministerial score (2013-2016) = 25.0, 17-03-2020, ArticleFromJournal
Publication indicators WoS Citations = 5; Scopus Citations = 7; GS Citations = 8.0; Scopus SNIP (Source Normalised Impact per Paper): 2014 = 1.174; WoS Impact Factor: 2013 = 1.163 (2) - 2013=1.201 (5)
Citation count*8 (2020-09-15)
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Are you sure?