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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Which are available on the web site: http://mauricio.resende.info/data/rwa.tar.gz.
References
Banerjee D, Mukherjee B (1996a) A practical approach for routing and wavelength assignment in large wavelength-routed optical networks. IEEE J Sel Areas Commun 14(5):903–908
Chlamtac I, Ganz A, Karmi G (1992) Lightpath communications: an approach to high bandwidth optical wan’s. IEEE Trans Commun 40(7):1171–1182
Dutta R, Rouskas GN (2000) A survey of virtual topology design algorithms for wavelength routed optical networks. Opt Netw Mag 1(1):73–89
Dzongang C, Galinier P, Pierre S (2005) A tabu search heuristic for the routing and wavelength assignment problem in optical networks. IEEE Commun Lett 9(5):426–428
Fredman ML, Tarjan R (1984) Fibonacci heaps and their uses in improved network optimization algorithms. In: 25th Annual Symposium on Foundations of Computer Science, 1984, pp. 338–346
Fu Z, Huang W, Lü Z (2013) Iterated tabu search for the circular open dimension problem. Eur J Oper Res 225(2):236–243
Glover F (1989) Tabu search part i. ORSA J Comput 1(3):190–206
Glover F (1990) Tabu search part ii. ORSA J Comput 2(1):4–32
Glover F (1996) Ejection chains, reference structures and alternating path methods for traveling salesman problems. Discret Appl Math 67(1–3):223–253
Gonzalez-Velárde J, Laguna M (2002) Tabu search with simple ejection chains for coloring graphs. Ann Oper Res 117(1–4):165–174
Huang W, Ye T (2011) Global optimization method for finding dense packings of equal circles in a circle. Eur J Oper Res 210(3):474–481
Jaumard B, Meyer C, Thiongane B (2006) ILP formulations for the RWA problem for symmetrical systems. In: Handbook for optimization in telecommunications. Springer, New York, pp 637–677
Jaumard B, Meyer C, Thiongane B (2007) Comparison of ILP formulations for the RWA problem. Opt Switch Netw 4(3):157–172
Jaumard B, Meyer C, Thiongane B (2009) On column generation formulations for the RWA problem. Discret Appl Math 157(6):1291–1308
Krishnaswamy RM, Sivarajan KN (2001) Algorithms for routing and wavelength assignment based on solutions of lp-relaxations. IEEE Commun Lett 5(10):435–437
Lee K, Kang KC, Lee T, Park S (2002) An optimization approach to routing and wavelength assignment in wdm all-optical mesh networks without wavelength conversion. ETRI J 24(2):131–141
Lü Z, Huang W (2009) Iterated tabu search for identifying community structure in complex networks. Phys Rev E 80:026130
Manohar P, Manjunath D, Shevgaonkar R (2002) Routing and wavelength assignment in optical networks from edge disjoint path algorithms. IEEE Commun Lett 6(5):211–213
Martins AX, Duhamel C, Mahey P, Saldanha RR, de Souza MC (2012) Variable neighborhood descent with iterated local search for routing and wavelength assignment. Comput Oper Res 39(9):2133–2141
Noronha TF, Ribeiro CC (2006) Routing and wavelength assignment by partition colouring. Eur J Oper Rese 171(3):797–810
Noronha TF, Resende MG, Ribeiro CC (2008) Efficient implementations of heuristics for routing and wavelength assignment. In: Proceedings of 7th International Workshop on Experimental Algorithms (WEA 2008), C.C. McGeoch (Ed.), LNCS, vol. 5038, pp. 169–180
Noronha TF, Resende MG, Ribeiro CC (2011) A biased random-key genetic algorithm for routing and wavelength assignment. J Global Optim 50(3):503–518
Ramaswami R, Sivarajan KN (1995) Routing and wavelength assignment in all-optical networks. IEEE/ACM Trans Netw (TON) 3(5):489–500
Skorin-kapov N (2007) Routing and wavelength assignment in optical networks using bin packing based algorithms. Eur J Oper Res 177:1167–1179
Wang L, Huang W (2005) A new local search algorithm for job shop scheduling problem. Chin J Comput 28(5):60–67
Wang H, Huang W, Zhang Q, Xu D (2002) An improved algorithm for the packing of unequal circles within a larger containing circle. Eur J Oper Res 141(2):440–453
Wu Q, Hao JK, Glover F (2012) Multi-neighborhood tabu search for the maximum weight clique problem. Ann Oper Res 196(1):611–634
Ye T, Xu R, Huang W (2011) Global optimization of binary lennard-jones clusters using three perturbation operators. J Chem Inf Model 51(3):572–577
Zang H, Jue JP, Mukherjee B et al (2000) A review of routing and wavelength assignment approaches for wavelength-routed optical wdm networks. Opt Netw Mag 1(1):47–60
Acknowledgments
We thank the anonymous referees for their helpful comments to improve our paper significantly. This paper is dedicated to memorizing the authors’ mentor Prof. Wenqi Huang for his lifelong instruction. This research was supported in part by the National Natural Science Foundation of China under Grant Number 61370183 and the program for New Century Excellent Talents in University (NCET 2013).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wu, X., Yan, S., Wan, X. et al. Multi-neighborhood based iterated tabu search for routing and wavelength assignment problem. J Comb Optim 32, 445–468 (2016). https://doi.org/10.1007/s10878-015-9962-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-015-9962-y