Issue |
RAIRO-Oper. Res.
Volume 53, Number 5, November-December 2019
Operations Research Applications in Industry
|
|
---|---|---|
Page(s) | 1513 - 1528 | |
DOI | https://doi.org/10.1051/ro/2018072 | |
Published online | 08 October 2019 |
On the problem of minimizing the cost with optical devices in Wavelength Division Multiplexing optical networks: complexity analysis, mathematical formulation and improved heuristics
1
Departamento de Informática, Gestão e Design, Centro Federal de Educação Tecnológica de Minas Gerais (CEFET-MG) – Campus V, Divinópolis, Brazil
2
Departamento de Tecnologia em Engenharia Civil, Computação e Humanidades, Universidade Federal de São João Del Rei (UFSJ), Ouro Branco, Brazil
3
Departamento de Ciência da Computação, Universidade Federal de Minas Gerais (UFMG), Belo Horizonte, Brazil
4
Departamento de Computação, Centro Federal de Educação Tecnológica de Minas Gerais (CEFET-MG) – Campus II, Belo Horizonte, Brazil
* Corresponding author: tfn@dcc.ufmg.br
Received:
28
June
2017
Accepted:
4
September
2018
The Fiber Installation Problem (FIP) in Wavelength Division Multiplexing (WDM) optical networks consists in routing a set of lightpaths (all-optical connections) such that the cost of the optical devices necessary to operate the network is minimized. Each of these devices is worth hundreds of thousands of dollars. In consequence, any improvement in the lightpath routing may save millions of dollars for the network operator. All the works in the literature for solving this problem are based on greedy heuristics and genetic algorithms. No information is known on how good are the solutions provided by these heuristics compared to the optimal solution. Besides, no proof that the problem is NP-Hard can be found. In this paper, we prove that FIP is NP-Hard and also present an Integer Linear Programming (ILP) formulation for the problem. In addition, we propose an implementation of the Iterated Local Search (ILS) metaheuristic to solve large instances of the problem. Computational experiments carried out on 21 realistic instances showed that the CPLEX solver running with our ILP formulation was able to solve 11 out of the 21 instances to optimality in less than two minutes. These results also showed that the ILS heuristic has an average optimality gap of 1% on the instances for which the optimal solution is known. For the other instances, the results showed that the proposed heuristic outperforms the best heuristic in the literature by 7%.
Mathematics Subject Classification: 90C59
Key words: Routing and Wavelength Assignment / optical network optimization / heuristics and metaheuristics / iterated local search
© EDP Sciences, ROADEF, SMAI 2019
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.