Multi-neighborhood based iterated tabu search for routing and wavelength assignment problem

Xinyun Wu, Shengfeng Yan, Xin Wan and Zhipeng Lü ()
Additional contact information
Xinyun Wu: Huazhong University of Science and Technology
Shengfeng Yan: Huazhong University of Science and Technology
Xin Wan: Huazhong University of Science and Technology
Zhipeng Lü: Huazhong University of Science and Technology

Journal of Combinatorial Optimization, 2016, vol. 32, issue 2, No 8, 445-468

Abstract: Abstract The routing and wavelength assignment problem (RWA) has shown to be NP-hard if the wavelength continuity constraint and the objective of minimizing the number of wavelengths are considered. This paper introduces a multi-neighborhood based iterated tabu search algorithm (MN-ITS), which consists of three neighborhoods with a unified incremental evaluation method, to solve the min-RWA problem. The proposed MN-ITS algorithm is tested on a set of widely studied real world instances as well as a set of challenging random ones in the literature. Comparison with other reference algorithms shows that the MN-ITS algorithm is able to improve five best upper bounds obtained by other competitive reference algorithms in the literature. This paper also presents an analysis to show the significance of the unified incremental evaluation technique and the combination of multiple neighborhoods.

Keywords: Routing and wavelength assignment; Network design; Multi-neighborhood search; Tabu search; Perturbation operator (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-015-9962-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:32:y:2016:i:2:d:10.1007_s10878-015-9962-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-015-9962-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().