The pollution routing problem was proposed by Bektas and Laporte (2011) and extends the well-known vehicle routing problem, by minimizing speed- and load-dependent fuel costs on the vehicle routes, rather than the distance travelled. To solve this problem, we present a novel branch-price-and-cut algorithm, where the problem is decomposed into one sub problem generating vehicle routes, and one master problem selecting the optimal subset of these routes. The sub problem may be formulated as an elementary shortest path problem with resource constraints and speed optimization (ESPPRC-SO), and is solved using a labeling algorithm. For the ESPPRC-SO the challenge of applying this approach is to find a valid and efficient dominance step, since both the time and cost resource is dependent on the speed on each arc traversed on a (partial) path. We present a sufficient dominance criteria for the SPPRC-SO by, which handles the time-cost dependencies by approximating the cost function for given points in time, and then uses the relation between the cost values and points to discard dominated paths in the labeling algorithm. Computational results show that our method can solve benchmark instances of up to 50 customers to optimality within one hour.