A Mathematical Model for Pollution Travelling Salesman Problem

Abstract

This paper studies Pollution Travelling Salesman Problem (PTSP). PTSP is a generalization of the well-known Travelling Salesman Problem (PTSP) which aims to find a suitable tour that minimizes fuel consumption in liters. This paper presents a mixed integer linear programming (MILP) for Pollution Travelling Salesman Problem which its objective function considers fuel consumption in term of vehicle engine efficiency, transmission, vehicle load, vehicle speed, road angle, distance and driver wages. The decision variables of the problem include routing of a vehicle, vehicle load and speed level. In this study, the PTSP is solved by the exact algorithm with optimization solver. The experiment uses 15 generated instances with the number of cities varying from 5 to 20 cities. The numerical results obtained by LINGO show that, in small-size instances, optimal solutions are easily found within fast computing time. When the number of cities increases to 15 cities, the model takes 3 to 8 hours to find optimal solutions. Finally, when the number of cities increases to 20 cities, the model cannot find optimal solution within acceptable computing time of 10 hours.