The considered problem consists in optimizing the refueling costs of a fleet of locomotives over a railway network. The goal consists in determining the number of trucks contracted for each yard (truck assignment problem) and to determine the refueling plan of each locomotive (fuel distribution problem), while minimizing the costs and satisfying constraints. A two-levels approach is proposed to tackle this NP-hard problem. Three metaheuristics (namely a descent procedure, a tabu search, and an ant local search algorithm) are proposed for the truck assignment level, and a flow model is designed for the fuel distribution level. A post-optimization procedure can be combined with the latter flow model. Six algorithms are proposed for the whole problem, and were tested on a realistic instance proposed by the Railway Applications Section of INFORMS. Competitive results were obtained. A strength of the proposed approach is its flexibility, as it can be easily adapted to non linear cases.