  This paper considers a joint pollution-routing and speed optimization problem
(PRP-SO) where fuel costs and $\textit{CO}_2e$ emissions depend on the vehicle
speed, arc payloads, and road grades. We present two methods, one approximate
and one exact, for solving the PRP-SO. The approximate strategy solves
large-scale instances of the problem with a tabu search-based metaheuristic
coupled with an efficient fixed-sequence speed optimization algorithm. The
second strategy consists of a tailored branch-and-price (BP) algorithm in which
speed optimization is managed within the pricing problem. We test both methods
on modified Solomon benchmarks and newly constructed real-life instance sets.
Our BP algorithm solves most instances with up to 50 customers and many
instances with 75 and 100 customers. The heuristic is able to find near-optimal
solutions to all instances and requires less than one minute of computational
time per instance. Results on real-world instances suggest several managerial
insights. First, fuel savings of up to 53\% are realized when explicitly taking
into account arc payloads and road grades. Second, fuel savings and emissions
reduction are also achieved by scheduling uphill customers later along the
routes. Lastly, we show that ignoring elevation information when planning
routes leads to highly inaccurate fuel consumption estimates.
