The increased popularity of the Internet in recent years, has witnessed an upsurge in the number of traffic types (e.g. Multimedia). This has led to dynamic traffic behaviour that has to be efficiently managed by the Internet Service Providers (ISPs) in coordination with the underlying carrier network. In this paper, we propose a Genetic Algorithm based routing solution for carrier networks that efficiently supports multiple ISP's dynamic traffic demands. The solution is based on the Genetic Algorithm-Local Search Hybrid (GA-LS) algorithm that is executed on a clustered network topology. Performance evaluations have also been presented to demonstrate comparisons with existing evolutionary algorithms.