Made available in DSpace on 2014-12-17T15:46:59Z (GMT). No. of bitstreams: 1
PauloHAS_TESE.pdf: 9268945 bytes, checksum: 08c0c5f93ed7b964b99c6df2ee26ab1b (MD5)
Previous issue date: 2011-12-19 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / The Car Rental Salesman Problem (CaRS) is a variant of the classical
Traveling Salesman Problem which was not described in the literature where a
tour of visits can be decomposed into contiguous paths that may be performed
in different rental cars. The aim is to determine the Hamiltonian cycle that
results in a final minimum cost, considering the cost of the route added to the
cost of an expected penalty paid for each exchange of vehicles on the route.
This penalty is due to the return of the car dropped to the base. This paper
introduces the general problem and illustrates some examples, also featuring
some of its associated variants. An overview of the complexity of this
combinatorial problem is also outlined, to justify their classification in the NPhard
class. A database of instances for the problem is presented, describing the
methodology of its constitution. The presented problem is also the subject of a
study based on experimental algorithmic implementation of six metaheuristic
solutions, representing adaptations of the best of state-of-the-art heuristic
programming. New neighborhoods, construction procedures, search operators,
evolutionary agents, cooperation by multi-pheromone are created for this
problem. Furtermore, computational experiments and comparative performance
tests are conducted on a sample of 60 instances of the created database,
aiming to offer a algorithm with an efficient solution for this problem. These
results will illustrate the best performance reached by the transgenetic algorithm
in all instances of the dataset / O Problema do Caixeiro Alugador (CaRS) ? uma variante ainda n?o descrita na
literatura do cl?ssico Problema do Caixeiro Viajante onde o tradicional tour de
visitas do caixeiro pode ser decomposto em caminhos cont?guos e que podem
ser realizados em diferentes carros alugados. O problema consiste em
determinar o ciclo hamiltoniano que resulte em um custo final m?nimo,
considerando o custo da rota adicionado ao custo de uma prov?vel penaliza??o
paga em cada troca de ve?culos na rota, penaliza??o devida ao retorno do
carro descartado at? a sua cidade base. Sem perda para a generalidade do
caso, os custos do aluguel do carro podem ser considerados embutidos nos
custos da rota do carro. O presente trabalho introduz o problema geral e o
exemplifica, caracterizando igualmente algumas variantes associadas. Uma
an?lise geral da complexidade desse problema combinat?rio ? descrita,
visando justificar sua classifica??o na classe NP-dif?cil. Um banco de inst?ncias
para o problema ? apresentado, descrevendo-se a metodologia de sua
constitui??o. O problema proposto tamb?m ? objeto de um estudo algor?tmico
experimental baseado na aplica??o de seis metaheur?sticas de solu??o,
representando adapta??es do melhor do estado da arte em programa??o
heur?stica. Novas vizinhan?as, procedimentos construtivos, operadores de
busca, agentes evolucion?rios, coopera??o por multiferom?nios, s?o criados
para o caso. Experimentos computacionais comparativos e testes de
desempenho s?o realizados sobre uma amostra de 60 inst?ncias, visando
oferecer um algoritmo de solu??o competitivo para o problema. Conclui-se pela
vantagem do algoritmo transgen?tico em todos os conjuntos de inst?ncias
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufrn.br:123456789/17945 |
| Date | 19 December 2011 |
| Creators | Silva, Paulo Henrique Asconavieta da |
| Contributors | CPF:25841025953, http://lattes.cnpq.br/1371199678541174, Canuto, Anne Magaly de Paula, CPF:66487099449, http://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4790093J8, Santiago, Regivan Hugo Nunes, CPF:30680581200, http://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4790032Z4, Gouv?a, Elizabeth Ferreira, Goldbarg, Marco C?sar |
| Publisher | Universidade Federal do Rio Grande do Norte, Programa de P?s-Gradua??o em Sistemas e Computa??o, UFRN, BR, Ci?ncia da Computa??o |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | application/pdf |
| Source | reponame:Repositório Institucional da UFRN, instname:Universidade Federal do Rio Grande do Norte, instacron:UFRN |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.015 seconds