Return to search

Hibridiza??o de meta-heur?sticas com m?todos baseados em programa??o linear para o problema do caixeiro alugador / Hybridization of metaheuristics with methods based on linear programming for the traveling car renter salesman problem

Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2018-03-02T23:39:14Z
No. of bitstreams: 1
BrennerHumbertoOjedaRios_DISSERT.pdf: 2438215 bytes, checksum: 3e559bfdaf797a4b9164e336ebd13429 (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2018-03-13T18:44:23Z (GMT) No. of bitstreams: 1
BrennerHumbertoOjedaRios_DISSERT.pdf: 2438215 bytes, checksum: 3e559bfdaf797a4b9164e336ebd13429 (MD5) / Made available in DSpace on 2018-03-13T18:44:23Z (GMT). No. of bitstreams: 1
BrennerHumbertoOjedaRios_DISSERT.pdf: 2438215 bytes, checksum: 3e559bfdaf797a4b9164e336ebd13429 (MD5)
Previous issue date: 2018-02-02 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior (CAPES) / O Problema do Caixeiro Viajante com Aluguel de Carros, ou simplesmente Problema do
Caixeiro Alugador (PCA), ? uma generaliza??o do cl?ssico Problema do Caixeiro Viajante
(PCV) onde seu tour de visitas pode ser decomposto em caminhos cont?guos que
podem ser percorridos com diferentes carros alugados. O objetivo ? determinar o circuito
hamiltoniano que resulte em um custo final m?nimo, considerando a penaliza??o paga
em cada troca de ve?culos no tour. A penaliza??o ? o custo de retornar o carro at? a
cidade onde foi alugado. O PCA est? classificado como um problema NP-dif?cil. O presente
trabalho estuda a variante mais usada na literatura do PCA que ?: completo, total,
irrestrito, sem repeti??o, livre e sim?trico. O foco da pesquisa s?o os procedimentos h?bridos
que combinam meta-heur?sticas e m?todos baseados na Programa??o Linear. S?o
hibridizados: algoritmos cient?ficos (ScA), descida em vizinhan?a vari?vel (VND), busca
local adaptativa (ALSP) e uma nova variante do ALSP chamada busca local adaptativa
iterativa (IALSP). As seguintes t?cnicas s?o propostas para lidar com o PCA: ScA+ALSP,
ScA+IALSP e ScA+VND+IALSP. ? proposto um modelo de programa??o inteira mista
para o PCA o qual ? usado no ALSP e no IALSP. Testes n?o param?tricos s?o usados
para comparar os algoritmos em um conjunto de inst?ncias da literatura. / 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.

Identiferoai:union.ndltd.org:IBICT/oai:repositorio.ufrn.br:123456789/24822
Date02 February 2018
CreatorsRios, Brenner Humberto Ojeda
Contributors81652011749, Goldbarg, Marco C?sar, 25841025953, Menezes, Matheus da Silva, 03329300418, Maia, Silvia Maria Diniz Monteiro, 01397968435, Goldbarg, Elizabeth Ferreira Gouvea
PublisherPROGRAMA DE P?S-GRADUA??O EM SISTEMAS E COMPUTA??O, UFRN, Brasil
Source SetsIBICT Brazilian ETDs
LanguagePortuguese
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis
Sourcereponame:Repositório Institucional da UFRN, instname:Universidade Federal do Rio Grande do Norte, instacron:UFRN
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0029 seconds