Track: Operations Research

Abstract

We introduce the “Pollution Traveling Salesman Problem” (PTSP), a generalization of  the well-known Traveling Salesman Problem which aims at finding a Hamiltonian tour that minimizes a function of fuel consumption (dependent on distance traveled, vehicle speed and vehicle load) and driver costs. The considered problem is new, and has several real-world applications in transportation and logistics systems. We propose a new Mixed Integer Linear Programming (MILP) model for the PTSP, enhanced with explicit subtour elimination constraints. In addition, we design a new Iterated Local Search (ILS) metaheuristic algorithm that first builds a feasible tour, based on the solution of  the Linear Programming (LP) relaxation of  the MILP model, and then loops between three phases: perturbation, local search and acceptance criterion. The computational  results obtained  by the ILS algorithm on instances with up to 50 customers are compared with those found by a Cut-and-Branch algorithm based on the enhanced MILP model. The computational results show that the proposed  ILS algorithm is effective, since it is able to find the best solution for about 99% of the instances within short computing times. The main contributions of the work are: the introduction of a new routing problem, the definition of a new MILP model for the solution of the considered problem, and the design of a new ILS metaheuristic algorithm whose components are specific for the studied problem.