The inventory routing problem (IRP) and the production routing problem (PRP) are two difficult problems arising in the planning of integrated supply chains. These problems are solved in an attempt to jointly optimize production, inventory, distribution and routing decisions. Although several studies have proposed exact algorithms to solve the single-vehicle problems, the multi-vehicle aspect is often neglected due to its complexity. We introduce multi-vehicle PRP and IRP formulations, with and without a vehicle index, to solve the problems under both the maximum level (ML) and order-up-to level (OU) inventory replenishment policies. The vehicle index formulations are further improved using symmetry breaking constraints, while the non-vehicle index formulations are strengthened by several cuts. A heuristic based on an adaptive large neighborhood search technique is also developed to determine initial solutions, and branch-and-cut algorithms are proposed to solve the different formulations. The results show that the vehicle index formulations are superior in finding optimal solutions, while the non-vehicle index formulations are generally better at providing good lower bounds on larger instances. IRP and PRP instances with up to 35 customers, 3 periods and 3 vehicles can be solved to optimality within two hours for the ML policy. By using parallel computing, the algorithms could solve the instances for the same policy with up to 45 and 50 customers, 3 periods and 3 vehicles for the IRP and PRP, respectively. For the more difficult IRP (resp. PRP), under the OU policy, the algorithms could handle instances with up to 30 customers, 3 (resp. 6) periods and 3 vehicles on a single core machine, and up to 45 (resp. 35) customers, 3 (resp. 6) periods and 3 vehicles on a multi-core machine.