  This paper deals with the Pollution-Routing Problem (PRP), a Vehicle Routing
Problem (VRP) with environmental considerations, recently introduced in the
literature by [Bektas and Laporte (2011), Transport. Res. B-Meth. 45 (8),
1232-1250]. The objective is to minimize operational and environmental costs
while respecting capacity constraints and service time windows. Costs are based
on driver wages and fuel consumption, which depends on many factors, such as
travel distance and vehicle load. The vehicle speeds are considered as decision
variables. They complement routing decisions, impacting the total cost, the
travel time between locations, and thus the set of feasible routes. We propose
a method which combines a local search-based metaheuristic with an integer
programming approach over a set covering formulation and a recursive
speed-optimization algorithm. This hybridization enables to integrate more
tightly route and speed decisions. Moreover, two other "green" VRP variants,
the Fuel Consumption VRP (FCVRP) and the Energy Minimizing VRP (EMVRP), are
addressed. The proposed method compares very favorably with previous algorithms
from the literature and many new improved solutions are reported.
