masterThesis
Hibridização de meta-heurísticas com métodos baseados em programação linear para o problema do caixeiro alugador
Fecha
2018-02-02Registro en:
RIOS, Brenner Humberto Ojeda. Hibridização de meta-heurísticas com métodos baseados em programação linear para o problema do caixeiro alugador. 2018. 100f. Dissertação (Mestrado em Sistemas e Computação) - Centro de Ciências Exatas e da Terra, Universidade Federal do Rio Grande do Norte, Natal, 2018.
Autor
Rios, Brenner Humberto Ojeda
Resumen
The Traveling Car Renter Salesman Problem, or simply Traveling Car Renter Problem
(CaRS), is a generalization of the Traveling Salesman Problem (TSP) where the tour can
be decomposed into contiguous paths that are traveled by different rented cars. The objective
is to construct a minimal cost Hamiltonian circuit, considering the penalty paid for
changing cars in the tour. This penalty is the cost of returning a car to the city where it
was rented. CaRS is classified as an NP-hard problem. This work studies the CaRS version
classified as: complete, total, unrestricted, with no repetition, free and symmetric. This
research is focused on hybrid procedures that combine metaheuristics and methods based
on Linear Programming (LP). The following methods were investigated: scientific algorithms
(ScA), variable neighborhood descent (VND), adaptive local search (ASLP) and a
new variant of ALSP called iterated adaptive local search (IALSP). The following techniques
are proposed to deal with CaRS: ScA+ALSP, ScA+IALSP and ScA+VND+IALSP.
A mixed integer programming model is proposed for CaRS which was used in the ALSP
and IALSP. Non-parametric tests were used to compare the algorithms within a set of
instances from the literature.