In the literature, this design problem has been referred to as the routing and wavelength assignment problem. Our proposal involves a three-step process that results in a low cost design to satisfy a set of static point-to-point demands. Our strategy simultaneously addresses the problem of routing working traffic, determining backup paths for single-node or single-link failures, and assigning wavelengths to both working and restoration paths.
An integer linear program is presented that formally defines the routing and wavelength assignment problem (RWA) being solved along with a simple heuristic procedure. In an empirical analysis, the heuristic procedure successfully solved realistically-sized test cases in under thirty seconds on a Compaq AlphaStation. CPLEX 6.6.0 using default settings required over 1000 times longer to obtain only slightly better solutions than those obtained by our new heuristic procedure.
Data files and AMPL code for the test cases presented in the paper:
Optimization Model AMPL code for the KO Heuristic Problem Instance AMPL data file A01 A01dat A02 A02dat A03 A03dat J01 J01dat J02 J02dat J03 J03dat J04 J04dat J05 J05dat J06 J06dat J07 J07dat ATT01 ATT01dat ATT02 ATT02dat ATT03 ATT03dat ATT04 ATT04dat ATT05 ATT05dat EUR01 EUR01dat EUR02 EUR02dat EUR03 EUR03dat EUR04 EUR04dat EUR05 EUR05dat