Summary form only given. In this paper, we propose an approach to model the fixed cellular network planning problem as a multi-criteria combinatorial optimisation problem. The first step is to affect the BTSs to the BSCs, then the location areas (LAs) are designed and finally the BSCs are assigned to the MSCs. The multiplicity of the constraints and possible configurations, the discrete character of the problem and the non linearity of the cost functions are as much factors that contribute to the complexity of this problem. In this paper, we search for an optimal method for optimising a fixed cellular network. For that purpose, we provide two heuristic algorithms based on simulated annealing and genetic algorithm. The procedure, consists essentially to modify in an iterative way an initial solution, trying to meet all the constraints.