Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Journal of Combinatorial Optimization
Erschienen in: Journal of Combinatorial Optimization 2/2016

01.08.2016

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

verfasst von: Xinyun Wu, Shengfeng Yan, Xin Wan, Zhipeng Lü

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 2/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.
Vorheriger Artikel A quasi-human algorithm for the two dimensional rectangular strip packing problem: in memory of Prof. Wenqi Huang
Nächster Artikel A three-phased local search approach for the clique partitioning problem

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Fußnoten
Literatur
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
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, 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
Metadaten
Titel
Multi-neighborhood based iterated tabu search for routing and wavelength assignment problem
verfasst von
Xinyun Wu
Shengfeng Yan
Xin Wan
Zhipeng Lü
Publikationsdatum
01.08.2016
Verlag
Springer US
Erschienen in
Journal of Combinatorial Optimization / Ausgabe 2/2016
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI
https://doi.org/10.1007/s10878-015-9962-y

Weitere Artikel der Ausgabe 2/2016

Journal of Combinatorial Optimization 2/2016 Zur Ausgabe

OriginalPaper

Optimal space coverage with white convex polygons

OriginalPaper

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

OriginalPaper

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

OriginalPaper

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

OriginalPaper

Solving the maximum vertex weight clique problem via binary quadratic programming

OriginalPaper

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

Premium Partner

    Bildnachweise