The Pollution-Routing Problem (PRP), which is an extension of the Vehicle Routing Problem with Time Windows, consists of routing a set of vehicles serving a set of customers within their time windows and jointly determining the speeds of the routes. This is a mixed integer non-linear program and very difficult to solve by a standard non-linear solver. We have decomposed the problem into two subproblems and developed a two-stage hybrid algorithm for the PRP. The first stage solves a classical routing problem by means of an accelerated Benders Decomposition method, and the second stage applies a speed optimization algorithm and a non-linear based interior point method. Computational experiments on well-known PRP benchmark instances confirm on the efficiency of the algorithm.