An iterated greedy algorithm for the node placement problem in bidirectional Manhattan street networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An iterated greedy algorithm for the node placement problem in bidirectional Manhattan street networks

Full text

Pdf (234 KB)

Source

Genetic And Evolutionary Computation Conference archive
Proceedings of the 10th annual conference on Genetic and evolutionary computation table of contents

Atlanta, GA, USA

SESSION: Evolutionary combinatorial optimization papers table of contents

Pages 579-584

Year of Publication: 2008

ISBN:978-1-60558-130-9

Authors

Fubito Toyama	Faculty of engineering, Utsunomiya University, Utsunomiya, Japan
Kenji Shoji	Faculty of engineering, Utsunomiya University, Utsunomiya, Japan
Juichi Miyamichi	Faculty of engineering, Utsunomiya University, Utsunomiya, Japan

Sponsors

ACM: Association for Computing Machinery
SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 69, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1389095.1389207 What is a DOI?

ABSTRACT

Wavelength Division Multiplexing (WDM) is a technology which

multiplexes optical carrier signals on a single optical fiber by using different wavelengths. Lightwave networks based on WDM are promising ones for high-speed communication. If network nodes are equipped with tunable transmitters and receivers, a logical topology can be changed by reassigning wavelengths to tunable transceivers of nodes. Network performance is influenced by the logical node placements. Therefore, an efficient algorithm to obtain the optimal node placement to achieve the best network performance is necessary. In this paper, an iterated greedy algorithm is proposed for this node placement problem. The proposed iterated greedy algorithm consists of two phases, construction and destruction phases. As a local search algorithm, variable depth search is applied after the construction phase. The computational results showed that this iterated greedy algorithm outperformed the best metaheuristic algorithm for this problem.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	C. Baransel, W. Dobosiewicz, and P. Gburzynski. Routing in multihop packet switching networks: Gb/s challenge. IEEE Network, pages 38--61, May/June 1995.
	2	Mário M. Freire , Henrique J. A. da Silva, Performance Comparison of Wavelength Routing Optical Networks with Chordal Ring and Mesh-Torus Topologies, Proceedings of the First International Conference on Networking-Part 1, p.358-367, July 09-13, 2001
	3	L. Jacobs and M. Brusco. A local search heuristic for large set-covering problems. Naval Research Logistics Quarterly, 42(7):1129--1140, 1995.
	4	Kengo Katayama , Akihiro Hamamoto , Hiroyuki Narihisa, An effective local search for the maximum clique problem, Information Processing Letters, v.95 n.5, p.503-511, 15 September 2005 [doi>10.1016/j.ipl.2005.05.010]
	5	K. Katayama, H. Yamashita, and H. Narihisa. Variable depth search and iterated local search for the node placement problem in multihop wdm lightwave networks. In the 2007 IEEE Congress on Evolutionary Computation (CEC-2007), pages 3508--3515, September 2007.
	6	M. Kato and Y. Oie. Reconfiguration algorithms based on metaheuristics for multihop wdm lightwave networks. In IEEE International Conference on Communications ( ICC ) 2000, pages 1638--1644, June 2000.
	7	T. Kitani, M. Yonedu, N. Funabiki, T. Nakanishi, K. Okayama, and T. Higashino. A two-stage hierarchical algorithm for wavelength assignment in wdm-based bidirectional manhattan street networks. In the 11th IEEE International Conference on Networks, pages 419--424, 2003.
	8	S. Lin and B. Kernighan. An effective heuristic algorithm for the traveling salesman problem. Operations Research, 21:498--516, 1973.
	9	Elena Marchiori , Adri Steenbeek, An Evolutionary Algorithm for Large Scale Set Covering Problems with Application to Airline Crew Scheduling, Real-World Applications of Evolutionary Computing, EvoWorkshops 2000: EvoIASP, EvoSCONDI, EvoTel, EvoSTIM, EvoROB, and EvoFlight, p.367-381, April 17, 2000
	10	M. Marsan, G. Alberengo, A. Francesea, E. Leonardi, and F. Neri. All-optical bidirectional manhattan networks. In IEEE International Conference on Communications (ICC)'92, pages 1461--1467, 1992.
	11	B. Mukherjee. Wdm-based local lightwave networks part i: single-hop systems. IEEE Network, pages 12--27, May 1992.
	12	B. Mukherjee. Wdm-based local lightwave networks part ii: multihop systems. IEEE Network, pages 22--32, July 1992.
	13	K. A. Murthy, Y. Li, and P. M. Pardalos. A local search algorithm for the quadratic assignment problem. Informatica, 3(4):524--538, 1992.
	14	R. Ruiz and T. Stutzle. A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 177:2033--2049, 2007.
	15	S. R. Tiourine, C. A. J. Hurkens, and J. K. Lenstra. Local search algorithms for the radio link frequency assignment problem. Telecommunication Systems, 13(2--4):293--314, 2000.