In this paper, a hybrid meta-heuristic is proposed which combines the GRASP with path relinking
method and Column Generation. The key idea of this method is to run a GRASP with path relinking
search on a restricted search space, defined by Column Generation, instead of running the search on the
complete search space of the problem. Moreover, column generation is used not only to compute the
initial restricted search space but also to modify it during the whole algorithm. The proposed heuristic is
used to solve the network load balancing problem: given a capacitated telecommunications network
with single path routing and an estimated traffic demand matrix, the network load balancing problem is
the determination of a routing path for each traffic commodity such that the network load balancing is
optimized, i.e., the worst link load is minimized, among all such solutions, the second worst link load is
minimized, and continuing in this way until all link loads are minimized. The computational results
presented in this paper show that, for the network load balancing problem, the proposed heuristic is
effective in obtaining better quality solutions in shorter running times.