Top

Journal of Combinatorial Optimization

Published in:

01-08-2016

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

Authors: Xinyun Wu, Shengfeng Yan, Xin Wan, Zhipeng Lü

Published in: Journal of Combinatorial Optimization | Issue 2/2016

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

previous article A quasi-human algorithm for the two dimensional rectangular strip packing problem: in memory of Prof. Wenqi Huang

next article A three-phased local search approach for the clique partitioning problem

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Which are available on the web site: http://mauricio.resende.info/data/rwa.tar.gz.

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–908CrossRef

Chlamtac I, Ganz A, Karmi G (1992) Lightpath communications: an approach to high bandwidth optical wan’s. IEEE Trans Commun 40(7):1171–1182CrossRef

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–243MathSciNetCrossRefMATH

Glover F (1989) Tabu search part i. ORSA J Comput 1(3):190–206CrossRefMATH

Glover F (1990) Tabu search part ii. ORSA J Comput 2(1):4–32CrossRefMATH

Glover F (1996) Ejection chains, reference structures and alternating path methods for traveling salesman problems. Discret Appl Math 67(1–3):223–253MathSciNetCrossRefMATH

Gonzalez-Velárde J, Laguna M (2002) Tabu search with simple ejection chains for coloring graphs. Ann Oper Res 117(1–4):165–174MathSciNetCrossRefMATH

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–481MathSciNetCrossRefMATH

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–172CrossRef

Jaumard B, Meyer C, Thiongane B (2009) On column generation formulations for the RWA problem. Discret Appl Math 157(6):1291–1308MathSciNetCrossRefMATH

Krishnaswamy RM, Sivarajan KN (2001) Algorithms for routing and wavelength assignment based on solutions of lp-relaxations. IEEE Commun Lett 5(10):435–437CrossRef

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–141CrossRef

Lü Z, Huang W (2009) Iterated tabu search for identifying community structure in complex networks. Phys Rev E 80:026130CrossRef

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–213CrossRef

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–2141MathSciNetCrossRefMATH

Noronha TF, Ribeiro CC (2006) Routing and wavelength assignment by partition colouring. Eur J Oper Rese 171(3):797–810MathSciNetCrossRefMATH

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–518CrossRef

Ramaswami R, Sivarajan KN (1995) Routing and wavelength assignment in all-optical networks. IEEE/ACM Trans Netw (TON) 3(5):489–500CrossRef

Skorin-kapov N (2007) Routing and wavelength assignment in optical networks using bin packing based algorithms. Eur J Oper Res 177:1167–1179CrossRefMATH

Wang L, Huang W (2005) A new local search algorithm for job shop scheduling problem. Chin J Comput 28(5):60–67MathSciNet

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–453MathSciNetCrossRefMATH

Wu Q, Hao JK, Glover F (2012) Multi-neighborhood tabu search for the maximum weight clique problem. Ann Oper Res 196(1):611–634MathSciNetCrossRefMATH

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–577CrossRef

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

Title: Multi-neighborhood based iterated tabu search for routing and wavelength assignment problem
Authors: Xinyun Wu
Shengfeng Yan
Xin Wan
Zhipeng Lü
Publication date: 01-08-2016
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 2/2016
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-015-9962-y

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 2/2016

A note on the duality between matchings and vertex covers in balanced hypergraphs

Solving the maximum vertex weight clique problem via binary quadratic programming

Optimal space coverage with white convex polygons

An effective discrete dynamic convexized method for solving the winner determination problem

A three-phased local search approach for the clique partitioning problem

The expected values of Hosoya index and Merrifield–Simmons index in a random polyphenylene chain

Premium Partner