Fuel cost contributes to a significant portion of operating cost in cargo transportation. Though classic routing models usually treat fuel cost as input data, fuel consumption heavily depends on the travel speed, which has led to the study of optimizing speeds over a given fixed route. In this paper, we propose a joint routing and speed optimization problem to minimize the total cost, which includes the fuel consumption cost. The only assumption made on the dependence between the fuel cost and travel speed is that it is a strictly convex differentiable function. This problem is very challenging, with medium-sized instances already difficult for a general mixed-integer convex optimization solver. We propose a novel set partitioning formulation and a branch-cut-and-price algorithm to solve this problem. Our algorithm clearly outperforms the off-the-shelf optimization solver, and is able to solve some benchmark instances to optimality for the first time.