This paper presents an exact solution approach for the problem of the simultaneous dispatching and conflict-free routing of automated guided vehicles. The vehicles carry out material handling tasks in a flexible manufacturing system (FMS). The objective is to minimize the costs related to the production delays. The approach is based on a set partitioning formulation. The proposed model is solved to optimality by a column generation method, which is embedded in a branch-and-cut exploration tree. The proposed model and solution methodology are tested on several scenarios with up to four vehicles in the manufacturing system. The results show that most of these scenarios can be solved to optimality in less than three minutes of computational time.