×

Variable neighborhood descent with iterated local search for routing and wavelength assignment. (English) Zbl 1251.90069

Summary: In this work we treat the Routing and Wavelength Assignment (RWA) with focus on minimizing the number of wavelengths to route demand requests. Lightpaths are used to carry the traffic optically between origin-destination pairs. The RWA is subjected to wavelength continuity constraints, and a particular wavelength cannot be assigned to two different lightpaths sharing a common physical link. We develop a Variable Neighborhood Descent (VND) with Iterated Local Search (ILS) for the problem. In a VND phase we try to rearrange requests between subgraphs associated to subsets of a partition of the set of lightpath requests. In a feasible solution, lightpaths belonging to a subset can be routed with the same wavelength. Thus, the purpose is to eliminate one subset of the partition. When VND fails, we perform a ILS phase to disturb the requests distribution among the subsets of the partition. An iteration of the algorithm alternates between a VND phase and a ILS phase. We report computational experiments that show VND-ILS was able to improve results upon powerful methods proposed in the literature.

MSC:

90B10 Deterministic network models in operations research
90B80 Discrete location and assignment

Software:

PERL; TTTPLOTS
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[1] Aiex, R. M.; Resende, M. G.C.; Ribeiro, C. C., Probability distribution of solution time in GRASP: an experimental investigation, Journal of Heuristics, 8, 343-373 (2002) · Zbl 1012.68795
[2] Aiex, R. M.; Resende, M. G.C.; Ribeiro, C. C., TTT plots: a perl program to create time-to-target plots, Optimization Letters, 1, 355-366 (2007) · Zbl 1220.90102
[3] Banerjee, D.; Mukherjee, B., A practical approach for routing and wavelength assignment in large wavelength-routed optical networks, IEEE Journal on Selected Areas in Communications, 14, 903-908 (1996)
[4] Chlamtac, I.; Ganz, A.; Karmi, G., Lightpath communications: an approach to high bandwidth optical WAN’s, IEEE Transactions on Communications, 40, 1171-1182 (1992)
[5] Dutta, R.; Rouskas, G. N., A survey of virtual topology design algorithms for wavelength routed optical networks, Optical Networks Magazine, 1, 73-89 (2000)
[6] Hansen, P.; Mladenović, N., Variable neighborhood search, (Glover, F.; Kochenberger, G., Handbook of metaheuristics (2003), Kluwer), 145-184 · Zbl 1102.90371
[7] Hansen, P.; Mladenović, N.; Moreno Pérez, J. A., Variable neighborhood search: methods and applications, 4OR A Quarterly Journal of Operations Research, 6, 319-360 (2008) · Zbl 1179.90332
[8] Hansen, P.; Mladenović, N.; Moreno Pérez, J. A., Variable neighbourhood search: methods and applications, Annals of Operations Research, 175, 367-407 (2010) · Zbl 1185.90211
[9] Jaumard, B.; Meyer, C.; Thiongane, B., ILP formulations for the RWA problem for symmetrical systems, (Pardalos, P.; Resende, M., Handbook for optimization in telecommunications (2006), Kluwer), 637-678
[10] Jaumard, B.; Meyer, C.; Thiongane, B., Comparison of ILP formulations for the RWA problem, Optical Switching and Networking, 4, 157-172 (2007)
[11] Jaumard, B.; Meyer, C.; Thiongane, B., On column generation formulations for the RWA problem, Discrete Applied Mathematics, 157, 1291-1308 (2009) · Zbl 1162.90355
[12] Kennington, J.; Olinick, E.; Ortynski, A.; Spiride, G., Wavelength routing and assignment in a survivable WDM mesh network, Operations Research, 51, 67-79 (2003) · Zbl 1163.90772
[13] Krishnaswamy, R. M.; Sivarajan, K. N., Algorithms for routing and wavelength assignment based on solutions of LP-relaxations, IEEE Communications Letters, 5, 435-437 (2001)
[14] Krishnaswamy, R. M.; Sivarajan, K. N., Design of logical topologies: a linear formulation for wavelength-routed optical networks with no wavelength changers, IEEE/ACM Transactions on Networking, 9, 186-198 (2001)
[15] Lee, K.; Kang, K. C.; Lee, T.; Park, S., An optimization approach to routing and wavelength assignment in WDM all-optical mesh networks without wavelength conversion, ETRI Journal, 24, 131-141 (2002)
[16] Lourenço, H. R.; Martin, O. C.; Stützle, T., Iterated local search, (Glover, P.; Kochenberger, G., Handbook of metaheuristics (2003), Springer), 321-353 · Zbl 1116.90412
[17] Manohar, P.; Manjunath, D.; Shevgaonkar, R. K., Routing and wavelengths assignment in optical networks from edge disjoint path algorithms, IEEE Communication Letters, 6, 211-213 (2002)
[18] Mladenović, N.; Hansen, P., Variable neighbourhood search, Computers & Operations Research, 24, 1097-1100 (1997) · Zbl 0889.90119
[19] Mukherjee, B.; Banerjee, D.; Ramamurthy, S.; Mukherjee, A., Some principles for designing a wide-area WDM optical network, IEEE/ACM Transactions on Networking, 4, 684-696 (1996)
[20] Noronha, T.; Resende, M. G.C.; Ribeiro, C. C., Efficient implementations of heuristics for routing and wavelength assignment, (McGeoch, C. C., Proceedings of the seventh international workshop on experimental algorithms. Lecture notes in computer science, vol. 5038 (2008)), 169-180
[21] Noronha, T.; Resende, M. G.C.; Ribeiro, C. C., A biased random-key genetic algorithm for routing and wavelength assignment, Journal of Global Optimization, 50, 3, 503-518 (2011), doi:10.1007/s10898-010-9608-7
[22] Noronha, T.; Ribeiro, C. C., Routing and wavelength assignment by partition colouring, European Journal of Operational Research, 171, 797-810 (2006) · Zbl 1116.90073
[23] Ramaswami, R.; Sivarajan, K. N., Routing and wavelength assignment in all-optical networks, IEEE/ACM Transactions on Networking, 3, 489-500 (1995)
[24] Ramaswami, R.; Sivarajan, K. N., Design of logical topologies for wavelength-routed optical networks, IEEE Journal on Selected Areas in Communications, 14, 840-851 (1996)
[25] Skorin-Kapov, N., Routing and wavelength assignment in optical networks using bin packing based algorithms, European Journal of Operational Research, 177, 1167-1179 (2007) · Zbl 1109.90015
[26] Zang, H.; Jue, J. P.; Mukherjee, B., A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks, Optical Networks Magazine, 1, 47-60 (2000)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.