The fleet management problem discussed in this paper consists in assigning the best routes to a set of vehicles in an underground mine haulage network. The haulage network that is considered consists of one-lane bi-directional road segments. The solution approach takes into account potential conflicts between vehicles. An enumeration algorithm based on dynamic programming is proposed to solve the problem. Dynamic programming is an optimization approach that transforms a complex problem into a sequence of simpler problems. This global approach permits to obtain the optimal solution. Different strategies are presented in order to reduce the solution time.