A matheuristic algorithm for the pollution and energy minimization traveling salesman problems
Abstract
The pollution traveling salesman problem (PTSP) and the energy minimization traveling salesman problem (EMTSP) generalize the well‐known asymmetric traveling salesman problem by including environmental issues and the goal of reducing carbon emissions. Both problems call for determining a Hamiltonian tour that, in the PTSP, minimizes a function of fuel consumption and driver cost (where the fuel consumption depends on the distance traveled, the vehicle speed, and the vehicle load), while, in the EMTSP, minimizes a function depending on the vehicle load and the traveled distances. For both PTSP and EMTSP, we propose a matheuristic algorithm that uses the solution of the linear programming relaxation of a mixed integer linear programming model for the considered problem to determine good initial feasible solutions, applies a multioperator genetic algorithm to improve these solutions, and refines the best solution found through an iterated local search procedure. In order to evaluate the performance of the proposed matheuristics, we compare them with exact and heuristic algorithms from the literature on benchmark instances of both problems.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- May 11, 2021
- Source ID
- 10.1111/itor.12991
Entities
People
- Carlos Contreras-Bolton
- Luis Miguel Escobar‐falcón
- Paolo Toth
- Valentina Cacchiani
Organizations
- Air Force Office of Scientific Research
- Libre University of Colombia
- National Council for Innovation, Science and Technology
- University of Bologna