The routing-and-driving problem for plug-in hybrid electric vehicles (PHEVs) is an extension of the vehicle routing problem with time windows, where routing involves determining optimal routes and recharging decisions for a fleet of PHEVs, while driving involves choosing the speed and operating mode on each road segment traveled by a vehicle. Specifically, four driving modes are considered: fuel-only, electricity-only, a combination of fuel and electricity, and energy recuperation, which returns energy to the battery. We consider two variants of the problem where the speed variables are either continuous, which results in a non-linear model, or discrete, which represents the case when speeds are chosen from a predetermined set. To solve these two models, we propose a set of valid inequalities to strengthen the continuous linear programming relaxation and we use a tailored branch-and-cut algorithm. Extensive computational experiments demonstrate the efficiency of the proposed solution methods, which can optimally solve instances with a realistic number of customers and recharging stations. In addition, we show that incorporating speed optimization can significantly reduce the energy consumption costs of a PHEV fleet compared to using fixed speeds.