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

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.