The arc-routing problem in many real-life applications has a large search space. For that reasonfinding an optimum solution is often not feasible in reasonable time and different types ofapproximations and heuristics are used. One way of approximating the problem is to partially fix the solution, thus reducing the search space. The partial fixing must be done in an intelligent way in order for the approximation to be close to the optimum value of the original problem. In this thesis, an algorithm that given an arc-routing problem partially fixes a solution in an effective way, is constructed. The algorithm is evaluated against a similar algorithm used currently by BM System on two different real-life applications, the capacitated arc-routing problem and the arc-routing problem with schedules. The new algorithm shows substantial improvement in both the quality of the found solution and the solving time, for large instances,while the performance on small instances is on par with the old algorithm.