An efficient heuristic for traffic grooming and light-path routing in wavelength division multiplexing ring networks with hop-count constraint

This paper deals with a traffic grooming and light-path routing problem in WDM-ring networks, where the number of light-paths to be used for each traffic demand is restricted. With a network augmentation by adding a dummy node and a set of dummy arcs, we formulate the comprehensive problem as a mixed Integer Programming problem. Owing to the computational complexity, it is hard to find an optimal solution for a large-scale network within a reasonable computation time. Hence, we develop a heuristic algorithm to solve it with ease. Our heuristic generates good feasible solutions within a few seconds in computation time even for large-scale networks. The computational experiments show that the performance of the proposed heuristic is satisfactory in both the speed and the quality of the solutions generated.