Algorithms for the Pollution Traveling Salesman Problem
Valentina Cacchiani  1, *@  , Carlos Contreras Bolton  1@  , Luis Escobar-FalcÓn  2, 3@  , Paolo Toth  1@  
1 : DEI, University of Bologna  (DEI)
Viale Risorgimento 2, 40136, Bologna -  Italy
2 : Universidad Tecnológica de Pereira  (UTP)
3 : Universidad Libre Seccional Pereira
* : Corresponding author

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.


Online user: 1 RSS Feed