Advance reservation services are being used by a range of applications to schedule connection bandwidth resources at future time intervals. To date many different algorithms have been developed to support various point-to-point reservation models. However, with expanding data distribution needs there is a need to schedule more complex service types to provide connectivity between multiple sites/locations. In particular, these offerings can help improve network resource utilization and help expand carrier service portfolios. Along these lines, this paper presents a novel, scalable optimization solution to schedule (virtual) overlay networks with fixed end-point nodes. An improved re-routing heuristic scheme is also proposed and analyzed for comparison purposes.