This paper presents a solution approach for routing a fleet of automated vehicles on haulage networks having one-lane bidirectional road segments. The solution method is based upon a shortest path algorithm on a time-window graph. The paper presents various improvements to the solution by offering methods for conflict avoidance over the haulage network and deadlock elimination. The method has been developed in the context of a fleet of load-haul-dump vehicles in underground mines but can be applied also in manufacturing contexts.