With the ever-rising data volume that is demanded by the market, network planning in order to minimize the nec-essary investment while meeting the demands is constantly an important task for the network providers. Synchronous digi-tal hierarchy (SDH) and wavelength division multiplex (WDM) form the core of many current backbone networks. In order to solve the provisioning and routing problem in such WDM networks, we develop a variable neighborhood search (VNS) metaheuristic. VNS is a metaheuristic that combines series of random and improving local searches based on systemati-cally changed neighborhoods. An integer flow formulation is modeled in AMPL and solved by CPLEX in order to obtain optimal solutions as a reference for the heuristic.