Autor: |
Rodrigo Linfati, Paolo Toth, Luis Miguel Escobar-Falcón, Carlos Contreras-Bolton, Valentina Cacchiani, John Willmer Escobar |
Přispěvatelé: |
Valentina Cacchiani, Carlos Contreras-Bolton, John W. Escobar, Luis M. Escobar-Falcon, Rodrigo Linfati, Paolo Toth |
Jazyk: |
angličtina |
Rok vydání: |
2018 |
Předmět: |
|
Zdroj: |
AIRO Springer Series ISBN: 9783030004729 |
Popis: |
Motivated by recent works on the Pollution Routing Problem (PRP), introduced in Bektas and Laporte (Transp Res Part B: Methodol 45(8):1232–1250, 2011) [1], we study the Pollution Traveling Salesman Problem (PTSP). It is 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 travelled, vehicle speed and load) and driver costs. We present a Mixed Integer Linear Programming (MILP) model for the PTSP, enhanced with sub-tour elimination constraints, and propose an Iterated Local Search (ILS) algorithm. It 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 results obtained by the ILS 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 results show the effectiveness of the ILS algorithm, which can find the best solution for about \(99\%\) of the instances within short computing times. |
Databáze: |
OpenAIRE |
Externí odkaz: |
|