The Pollution Traveling Salesman Problem (PTSP) is a generalization of the well-known Traveling Salesman Problem. It arises when environmental issues become important, as it happens nowadays, since it aims at reducing carbon emissions. More precisely, the PTSP calls for determining a Hamiltonian tour that minimizes a function of fuel consumption and driver costs, where the fuel consumption depends on the distance travelled, the vehicle speed and the vehicle load.

We present a Mixed Integer Linear Programming (MILP) model for the PTSP, and propose an Iterated Local Search algorithm, a Genetic algorithm and a combination of the two algorithms. In order to evaluate the performance of the proposed metaheuristics, we developed a Cut-and-Branch algorithm, in which sub-tour elimination constraints are separated at the root node of the decision tree. The proposed algorithms are tested on instances with up to 200 customers.