In this paper, three new methods for the solution of the off-line Traffic Engineering (TE) problem in multi-service networks based on genetic optimisation and simulated annealing optimization techniques are presented and compared. In the first method the off-line TE problem is formulated as an optimisation model with linear constraints and then solved using the Genetic Algorithm for Numerical Optimisation for Constraint Problems (GENOCOP). In the second method the same problem is solved using Simulated Annealing. Besides, a third hybrid method for the solution of the aforementioned problem involving GENOCOP and a heuristic TE algorithm is also provided. The performance of the above methods against a standard LP-based optimisation method is examined in terms of two different network topologies and numerical test results are provided. The contribution of the paper lies on the fact that for the first time Genetic optimization and simulated annealing methods are involved in traffic engineering problems. In addition, a novel hybrid method based on genetic optimization is proposed with performance comparable to that obtained by linear programming techniques (Simplex), which are the optimum solvers in the case of linear cost functions optimization under linear constraints as it takes place in the herein proposed traffic engineering problem formulations. Finally, the contribution of the paper is that for the first time genetic optimization and simulated annealing techniques are used to solve real world problems of thousands of variables achieving, in the case of Genetic Algorithms, near optimal results.