Abstract

In this study, an approach is proposed to address a variant of the Pollution Traveling Salesman Problem (PTSP), which focuses on fuel consumption and pollutant emissions. Since PTSP generalizes the Traveling Salesman Problem (TSP), it is classified as NP-Hard. This problem involves visiting all customers by a vehicle, minimizing an objective function that considers various factors such as speed, truck load, and distance traveled. Computational experiments were conducted to evaluate the performance of several integer linear programming solvers. Additionally, a metaheuristic was developed that combines mathematical models and metaheuristic techniques to find near-optimal solutions in reduced times. The implementation was carried out in Julia 1.7, using the JuMP 1.0 library for both the metaheuristic and mathematical models. In the first phase of the metaheuristic, the PTSP model with the minimum distance objective function was executed to quickly find a solution, followed by the application of various metaheuristics to improve it. In the second phase, previous solutions were used in the PTSP model, which yielded promising results in terms of solution quality and computation time. Among the evaluated solvers, it is highlighted that Gurobi outperformed others in terms of execution time and solution quality.