Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2016-08-16T20:15:31Z No. of bitstreams: 1 GuilhermeFernandesDeAraujo_DISSERT.pdf: 1848505 bytes, checksum: eaa10d2add37ab0c93d005b148c492ee (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2016-08-17T22:17:58Z (GMT) No. of bitstreams: 1 GuilhermeFernandesDeAraujo_DISSERT.pdf: 1848505 bytes, checksum: eaa10d2add37ab0c93d005b148c492ee (MD5) / Made available in DSpace on 2016-08-17T22:17:58Z (GMT). No. of bitstreams: 1 GuilhermeFernandesDeAraujo_DISSERT.pdf: 1848505 bytes, checksum: eaa10d2add37ab0c93d005b148c492ee (MD5) Previous issue date: 2016-02-12 / O Problema do Caixeiro Viajante com Caronas M?ltiplas (PCV-MCa) ? uma classe do Caixeiro Viajante Capacitado que apresenta a possibilidade de compartilhamento de assentos para passageiros aproveitando os deslocamentos do caixeiro entre as localidades do ciclo. O caixeiro divide o custo do trajeto com os passageiros embarcados. O modelo pode representar uma situa??o real em que, por exemplo, motoristas est?o dispostos a compartilhas trechos de sua viagem com turistas que pretendem se deslocar entre duas localidades visitadas pela rota do motorista, aceitando compartilhar o ve?culo com outros indiv?duos e visitando outras localidades do ciclo. / The Traveling Salesman with Multiple Ridesharing (TSP-MR) is a type of the Capacitated Traveling Salesman, which presents the possibility of sharing seats with passengers taking advantage of the paths the salesman travels through his cycle. The salesman shares the cost of a path with the boarded passengers. This model can portray a real situation in which, for example, drivers are willing to share parts of a trip with tourists that wish to move between two locations visited by the driver?s route, accepting to share the vehicle with other individuals visiting other locations within the cycle. This work proposes a mathematical formulation for the problem, and an exact and metaheuristics algorithms for its solution, comparing them.

Made available in DSpace on 2014-12-17T14:52:47Z (GMT). No. of bitstreams: 1 ThalesLS.pdf: 825402 bytes, checksum: 8e0d2b64fc7287a7921fa605343a8bb6 (MD5) Previous issue date: 2008-12-23 / Particle Swarm Optimization is a metaheuristic that arose in order to simulate the behavior of a number of birds in flight, with its random movement locally, but globally determined. This technique has been widely used to address non-liner continuous problems and yet little explored in discrete problems. This paper presents the operation of this metaheuristic, and propose strategies for implementation of optimization discret problems as form of execution parallel as sequential. The computational experiments were performed to instances of the TSP, selected in the library TSPLIB contenct to 3038 nodes, showing the improvement of performance of parallel methods for their sequential versions, in executation time and results / Otimiza??o por Enxame de Part?culas ou Particle Swarm Optimization (PSO) ? uma metaheur?stica que surgiu na inten??o de simular o comportamento de um conjunto de p?ssaros em v?o, com seu movimento localmente aleat?rio, mas globalmente determinado. Esta t?cnica tem sido muito utilizada na resolu??o de problemas cont?nuos n?o-lineares e ainda pouco explorada em problemas discretos. Este trabalho apresenta o funcionamento desta metaheur?stica, al?m de propor estrat?gias para sua aplica??o em problemas de otimiza??o discreta tanto na sua forma de execu??o seq?encial quanto paralela. Os experimentos computacionais foram realizados para inst?ncias do problema do caixeiro viajante, selecionados na biblioteca TSPLIB contendo at? 1002 n?s, mostrando a melhoria de desempenho dos m?todos paralelos em rela??o as suas vers?es seq?enciais, em tempo de execu??o e resultados

Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2017-06-02T19:19:17Z No. of bitstreams: 1 RanmsesEmanuelMartinsBastos_DISSERT.pdf: 3544164 bytes, checksum: 0be0a21709a7526cbbea13cf73f55d8e (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2017-06-05T19:52:50Z (GMT) No. of bitstreams: 1 RanmsesEmanuelMartinsBastos_DISSERT.pdf: 3544164 bytes, checksum: 0be0a21709a7526cbbea13cf73f55d8e (MD5) / Made available in DSpace on 2017-06-05T19:52:51Z (GMT). No. of bitstreams: 1 RanmsesEmanuelMartinsBastos_DISSERT.pdf: 3544164 bytes, checksum: 0be0a21709a7526cbbea13cf73f55d8e (MD5) Previous issue date: 2017-02-17 / O Problema do Caixeiro Viajante com Passageiros e Lota??o ? uma vers?o do PCV cl?ssico onde o caixeiro ? o motorista de um ve?culo que compartilha os custos de viagem com passageiros. Al?m de dividir os custos do percurso, o caixeiro pode se valer, tamb?m, dos descontos das high-occupancy vehicle lanes, que s?o faixas de tr?nsito que isentam ve?culos lotados do pagamento de ped?gio. A adi??o de passageiros ao PCV, um problema restrito ao roteamento, cria um vi?s colaborativo que ? intensificado pela considera??o das faixas especiais. Tal cen?rio confere ao problema estudado um aspecto ecol?gico, uma vez que seu estudo tem consequ?ncias diretas sobre o uso eficiente do espa?o urbano e a diminui??o da emiss?o de gases poluentes, contribuindo sobremaneira para o incremento da qualidade de vida. A pesquisa compreendeu desde a correla??o entre esse novo problema e outros constantes na literatura at? a concep??o de um conjunto de seiscentas inst?ncias artificiais e a cria??o de diversos m?todos de solu??o. Para a determina??o de ?timos, ? proposto um modelo matem?tico que suportou as solu??es por Programa??o Matem?tica e por Restri??es. Adicionalmente, ? apresentado um algoritmo branch-and-bound especificamente desenvolvido para o problema. Visando a busca por solu??es de qualidade em curto espa?o de tempo, s?o expostos cinco algoritmos experimentais com base nas abordagens heur?sticas Simulated Annealing, Variable Neighborhood Search, Coloniza??o de Abelhas e Algoritmos Gen?ticos. Diversos procedimentos auxiliares para constru??o de solu??es e execu??o de buscas locais s?o tamb?m expostos. Um experimento computacional ? realizado para compara??o entre os m?todos de solu??o. Uma amostra de cem casos teste ? utilizada para o processo estat?stico de ajuste de par?metros dos algoritmos heur?sticos, enquanto o restante das inst?ncias ? extensivamente abordado pelos m?todos. S?o determinados os ?timos para cento e cinquenta e cinco casos com tamanhos 10 e 20 cidades. Dentre os m?todos experimentais, cabe destacar a superioridade do algoritmo heur?stico que une as meta-heur?sticas Simulated Annealing e Variable Neighborhood Search. / The Traveling Salesman with Passengers and High Occupancy Problem is a version of the classic TSP where the salesman is the driver of a vehicle who shares travels? expenses with passengers. Besides shared expenses, the driver also benefits from discounts of the highoccupancy vehicle lanes, i.e. traffic lanes in which high occupancy vehicles are exempted from tolls. The addition of passengers to the TSP, a routing-only problem, creates a sharing view which is intensified by the consideration of special lanes. This scenario grants to the problem an ecological feature, since its study have direct consequences for the efficient use of urban space and the greenhouse gas emissions reduction, greatly contributing for quality of life improvement. This work addresses the study of this novel combinatorial optimization problem, going from the relationship it draws with other ones in the literature until the conception of a six hundred set of artificial test cases and the creation of many solution methods. To find optimal solutions, a mathematical model is proposed. This model supported the search for exact solutions by Mathematical and Constraint Programming. Additionally, is presented a branchand- bound algorithm specifically developed for the problem. Aiming the search for good quality solutions in short time period, five experimental algorithms based on the heuristics approaches Simulated Annealing, Variable Neighborhood Search, Bees Colony and Genetic Algorithms are introduced. Several auxiliary procedures for solutions generations and local search execution are revealed as well. A computational experiment is fulfilled to comparison between the solution methods. A sample of a hundred test cases is used for the heuristics algorithms? parameter tuning statistical process, while the rest of them are extensively addressed by the methods. The optimal solution for a hundred and fifty five test cases with sizes of 10 and 20 cities are determined. Among the experimental methods, one has to highlight the advantage of the heuristic algorithm that unites the metaheuristics Simulated Annealing and Variable Neighborhood Search.

Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2017-11-01T21:17:49Z No. of bitstreams: 1 ZailtonSachasAmorimCalheiros_DISSERT.pdf: 970322 bytes, checksum: b3f4c21bcb05d3c25bba593777a5b94a (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2017-11-07T21:20:44Z (GMT) No. of bitstreams: 1 ZailtonSachasAmorimCalheiros_DISSERT.pdf: 970322 bytes, checksum: b3f4c21bcb05d3c25bba593777a5b94a (MD5) / Made available in DSpace on 2017-11-07T21:20:44Z (GMT). No. of bitstreams: 1 ZailtonSachasAmorimCalheiros_DISSERT.pdf: 970322 bytes, checksum: b3f4c21bcb05d3c25bba593777a5b94a (MD5) Previous issue date: 2017-07-31 / Este trabalho apresenta um modelo de compartilhamento de assentos veicular de modo a reduzir os custos de viagem de motoristas e passageiros, contribuindo de maneira significativa ao meio ambiente e ? sociedade. O problema tamb?m ? descrito atrav?s de um modelo de programa??o linear e s?o discutidas algumas variantes de um subproblema importante para resolu??o do modelo proposto. Al?m disso, algumas abordagens computacionais s?o implementadas, compostas de algoritmos evolucion?rios (gen?tico e mem?tico) e construtivos (formigas e GRASP). Al?m da adapta??o de algoritmos j? existes para o problema do caixeiro viajante tradicional como o algoritmo de Lin-Kernighan. Ap?s a realiza??o de experimentos, o algoritmo baseado em formiga revela-se promissor para inst?ncias assim?tricas enquanto que o algoritmo de Lin-Kernighan leva vantagem pela sua robustez atrav?s da implementa??o de Helsgaun que desempenha bons resultados para inst?ncias sim?tricas. / This thesis presents a vehicle seat sharing model in order to reduce travel costs for drivers and passengers, contributing significantly to the environment and society. The problem is also described by a linear programming model and it is discussed in some variants of an important subproblem for solving the main problem. Besides, some computational approaches are implemented, composed by evolutionary (genetic and memetic) e constructive (ant optimization) algorithms. In addition to the adaptation of already existing algorithms for the travaling salesman problem as the Lin-Kernighan algorithm. After performing experiments, ant-based algorithms prove itself promising for asymmetric instances while the Lin-Kernighan algorithm takes advantage of its robustness through the implementation of Helsgaun and has a good performance for symmetric instances.

Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2017-11-01T21:17:50Z No. of bitstreams: 1 JeanGleisonDeSantanaSilva_DISSERT.pdf: 1141115 bytes, checksum: 891de7a8a9407e8af54f241f1a174785 (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2017-11-07T22:09:47Z (GMT) No. of bitstreams: 1 JeanGleisonDeSantanaSilva_DISSERT.pdf: 1141115 bytes, checksum: 891de7a8a9407e8af54f241f1a174785 (MD5) / Made available in DSpace on 2017-11-07T22:09:47Z (GMT). No. of bitstreams: 1 JeanGleisonDeSantanaSilva_DISSERT.pdf: 1141115 bytes, checksum: 891de7a8a9407e8af54f241f1a174785 (MD5) Previous issue date: 2017-07-31 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior (CAPES) / O Problema do Caixeiro Viajante com Passageiros e Quota pertence ? classe de Problemas do Caixeiro Viajante com Quota. Neste problema, considera-se uma vantagem econ?mica quando o caixeiro, viajando em um ve?culo privado, embarca passageiros que passam a dividir as despesas da viagem com ele. O modelo pode representar situa??es reais onde o motorista tem uma rota de visita de cidade predefinida, na qual a cada cidade est? associado um b?nus, sendo demandada a coleta de um valor m?nimo desses b?nus, na fun??o objetivo da variante investigada leva-se em conta a possibilidade da redu??o dos custos do caixeiro embarcando pessoas em seu ve?culo. Um modelo matem?tico, seis algoritmos evolucion?rios, um GRASP e um heur?stico s?o apresentados para o problema. O comportamento dos algoritmos propostos ? analisado em um experimento computacional com 48 inst?ncias. / The Traveling Salesman Problem with Ridesharing and Quota belongs to the class of Quota Traveling Salesman problems. In this problem, it is considered the economic advantage achieved when the salesman, traveling in a private vehicle, gives ride to passengers who share travel expenses with him. The model can represent real situations where a driver programs a route to visit cities, each of which associated with a bonus, with the requirement of collecting a minimum sum of bonuses and taking into account the possibility of reducing costs due to people embarked in his vehicle. A math model, six evolutionary algorithms, a GRASP and one heuristic are presented for the problem addressed. The behavior of the proposed algorithms is analyzed on a computational experiment with 48 instances.

Orientador: Akebo Yamakami / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-08T23:52:00Z (GMT). No. of bitstreams: 1 Carvalho_MarciaBragade_M.pdf: 2154346 bytes, checksum: caafd847980349294a73d2ad38d6414c (MD5) Previous issue date: 2007 / Resumo: Dentre as várias técnicas heurísticas e exatas existentes para a resolução de problemas combinatórios, os algoritmos populacionais de otimização por colônia de formigas e genéticos têm se destacado devido à sua boa performance. Em especial os algoritmos de colônia de formigas são considerados atualmente como uma das técnicas mais bem sucedidas para a resolução de vários problemas combinatórios, dentre eles o problema do caixeiro viajante. Neste trabalho é apresentado um algoritmo híbrido que trabalha com as meta-heurísticas de sistema de colônia de formigas e genético conjuntamente aplicados no problema do caixeiro viajante simétrico. Além disso, apresentamos uma proposta para o algoritmo de formigas quando temos incertezas associadas aos parâmetros do problema. Os resultados obtidos com as metodologias propostas apresentam resultados satisfatórios para todas as instâncias utilizadas / Abstract: Amongst the several existing heuristical and accurate techniques for the resolution of combinatorial problems, the population algorithms ant colony optimization and genetic have been detached due to their good performance. In special the ant colony algorithms are considered currently as one of the techniques most succeeded for the resolution of some combinatorial problems, amongst them the travelling salesman problem. In this work is presented a hybrid algorithm which works with the ant colony system and genetic metaheuristics jointly applied in the symmetric travelling salesman problem. Moreover, we presented a proposal for the ant algorithm when we have uncertainties associated to problem parameters. The results gotten with the methodology proposals present resulted satisfactory for all the used instances / Mestrado / Automação / Mestre em Engenharia Elétrica

A Roteirização de Veículos desempenha papel fundamental nos processos modernos de distribuição de produtos e realização de serviços. A atual disseminação de recursos de tecnologia de informação e comunicação, de forma confiável e economicamente acessível, permite trabalhar com informações em tempo real e melhoram os padrões de nível de serviço associados. O presente trabalho apresenta uma solução para roteirização de veículos cujas equipes de bordo realizam serviços que justificam seu deslocamento, uma vez que as demandas estão geograficamente dispersas. Tais demandas são, em parte, conhecidas antes do despacho (permitem programação antecipada) dos veículos e suas equipes; outra parte surge durante a jornada de trabalho. Como exemplos podem-se citar os casos de serviços de montagem e manutenção de instalações, equipamentos, engenharia e inspeção de tráfego, policiamento etc. Trata-se da aplicação da roteirização parcialmente dinâmica, conforme Larsen (2000), cujas bases foram definidas por Psaraftis (1988,1995), Bertsimas et al (1993) no problema DTRP (Dynamic Travelling Repairman Problem). A função objetivo apresenta uma combinação de minimização dos custos de deslocamento, para os pedidos de serviços conhecidos antes da saída dos veículos e de minimização do tempo de resposta (chegada no local do cliente ou da ocorrência) para os casos de pedidos imediatos ou emergenciais. A solução do problema envolve um modelo computacional de testes e avaliação, heurística de Clarke e Wright (1964) para formação das rotas estáticas, no Método Húngaro (Kuhn, 1955) para designar o veículo que resulta no menor tempo de resposta no atendimento a um pedido emergencial e a heurística de Clarke e Wright modificada na otimização do restante dos pedidos quando o veículo voltar a sua rota original. O modelo computacional foi testado em uma empresa de manutenção de elevadores na cidade de São Paulo, Brasil, onde demonstrou resultados comparativamente melhores em relação ao sistema de roteirização utilizado atualmente pela empresa. / The Vehicle Routing Problem plays a critical role on modern processes related to physical distribution of goods and services. The present expansion of information and communication technology in a reliable, economic and accessible way allows real time information and requires the utilization of appropriate tools for real time decisions resulting in significant improvements in quality and service level related to dynamic vehicle routing. A dynamic routing problem is presented, in which vehicles serve geographic dispersed service demands that justify their movement in a fixed area. Such service demands are partially known before vehicles dispatching (allowing prior programming) whilst others are known during the work journey. As examples, one can mention cases concerning installation and maintenance of utilities, equipment, engineering and surveillance services that refer to applications of Partially Dynamic Routing according to Larsen (2000), the groundings of which were defined by Psaraftis (1988,1995), Bertsimas et al (1993) in the Dynamic Travelling Repairman Problem (DTRP). The objective function is a combination of the minimization of movement costs to serve the prior demands and the minimization of time to reach (time to response) Dynamic-or-emergency-demand sites. The proposed solution involves a computational model for testing and evaluating a set of heuristics and methods comprising the Clarke and Wright (1964) Heuristic to compose the static routes, the Hungarian Method (Kuhn, 1955) to assign vehicles to the dynamic demands that produces the lowest response time and, finally, a Clarke and Wright Modified Heuristic used to optimize the remainder of the route when each diverted vehicle returns to its static route. The Computational Model was applied to a lift maintenance company located in the city of São Paulo (Brazil) demonstrating better results as compared to the present routing system.

Submitted by Angela Maria de Oliveira (amolivei@uepg.br) on 2017-12-01T13:39:21Z No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) Jose Wander de Paula.pdf: 846750 bytes, checksum: 4b196f858fbc02cabdfbc08b6cee6553 (MD5) / Made available in DSpace on 2017-12-01T13:39:21Z (GMT). No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) Jose Wander de Paula.pdf: 846750 bytes, checksum: 4b196f858fbc02cabdfbc08b6cee6553 (MD5) Previous issue date: 2017-09-25 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Esta dissertação trata de uma leitura do livro Se um viajante numa noite de inverno de Italo Calvino (1979) e o objetivo é analisar três categorias trazidas pelo livro como personagens: o autor, o editor e o leitor e a “voz narrativa” que fala no romance. Para o escritor “a relação de quem narra com a matéria narrada e com o leitor” é a “problemática mais árdua da narrativa contemporânea” (CALVINO, 2009, p. 199). Como fundamentação teórica para esta temática utilizamos alguns textos fomentadores destas discussões: Roger Chartier (1998) e seu estudo sobre autor e editor, Compagnon sobre estilo, autor e leitor (2001), Michel Foucault (2009) sobre o que é um autor, a “morte do autor” prenunciada por Roland Barthes (2004), Umberto Eco (1994) e a questão do leitor, entre outros. A respeito da categoria “autor”, entendemos ser este uma figura que Umberto Eco renomeou em “autor-modelo”, “autor-empírico”, entendemos que a “voz narrativa” criada por Italo Calvino no romance e as estratégias narrativas utilizadas pelo escritor ecoam este viés. Destas duas categorias, “autor” e “voz narrativa”, relacionamos à teoria que fala a respeito de “estilo”, reconhecendo as estratégias de Italo Calvino como um “tom” que dificilmente poderíamos desvincular da figura histórica do autor ao compararmos com seu experimentalismo em outros livros como Cidades Invisíveis (CALVINO, 2003). Este estudo nos possibilitou compreender, também, que o “Editor” faz parte da autoria no sentido de que a Casa Editorial é o local em que são aceitos para publicação textos que passam pelo crivo de estéticas estabelecidas por um Editor que circunscreve, delimita e corrige o que será publicado. Por último, estudar a morte do autor anuncia que o Leitor deve ser enfatizado em sua atividade de leitura. A conclusão a que chegamos é que em Se um viajante numa noite de inverno Italo Calvino criou um romance armadilha, tanto do leitor-médio, como dos demais leitores. / This paper is about our reading of If on a traveler on a winter’s night, book was wrote by Italo Calvino (1979), and the aim is to analyze three characters from the book: the editor, the author and the reader, as well as we study the book “narrative voice”. To the writer “a relação de quem narra com a matéria narrada e com o leitor” is the “problemática mais árdua da narrativa contemporânea” (CALVINO, 2009, p. 199). This discussions in this text is based on Roger Chartier about author and editor (1998), Antoine Compagnon (2001) about author, reader and style, the “author’s dead” by Roland Barthes (2004), Michel Foucault and what is an author? (2009), Umberto Eco (1994) and the reader, among others. We understand the author is a figure divided by Umberto Eco in autor-modelo and autor-empírico and the narrative strategies used by the writer talks with these categories – and these categories are very hard to separate on historical author figure. The Editor is part of the authorship in the sense that the Editorial House is the place where texts that pass through the aesthetic list established by an Editor are accepted for publication. Studying the death of the author announces that the reader should be emphasized in his reading activity. The conclusion we reach is that in If a traveler on a winter's night Italo Calvino created a trappings romance, be it the average reader or the other readers.

O problema do caixeiro viajante (PCV) é um problema clássico de otimização que possui diversas variações, aplicações e instâncias. Encontrar a solução ótima para muitas instâncias desse problema é geralmente muito difícil devido o alto custo computacional. Vários métodos de otimização, conhecidos como meta-heurísticas (MHs), são capazes de encontrar boas soluções para o PCV. Muitos algoritmos baseados em diversas MHs têm sido propostos e investigados para diferentes variações do PCV. Como não existe um algoritmo universal que encontre a melhor solução para todas as instâncias de um problema, diferentes MHs podem prover a melhor solução para diferentes instâncias do PCV. Desse modo, a seleção a priori da MH que produza a melhor solução para uma dada instância é uma tarefa difícil. A pesquisa desenvolvida nesta tese investiga o uso de abordagens de meta-aprendizado para selecionar as MHs mais promissoras para novas instâncias de PCV. Essas abordagens induzem meta-modelos preditivos a partir do treinamento das técnicas de aprendizado de máquina em um conjunto de meta-dados. Cada meta-exemplo, em nosso conjunto de meta-dados, representa uma instância de PCV descrita por características (meta-atributos) do PCV e pelo desempenho das MHs (meta-atributo alvo) para essa instância. Os meta-modelos induzidos são usados para indicar os valores do meta-atributo alvo para novas instâncias do PCV. Vários experimentos foram realizados durante a investigação desta pesquisa e resultados importantes foram obtidos / The traveling salesman problem (TSP) is a classical optimization problem that has several variations, applications and instances. To find the optimal solution for many instances of this problem is usually a very hard task due to high computational cost. Various optimization methods, known as metaheuristics (MHs), are capable to generate good solutions for the TSP. Many algorithms based on different MHs have been proposed and investigated for different variations of the TSP. Different MHs can provide the best optimization solution for different TSP instances, since there is no a universal algorithm able to find the best solution for all instances. Thus, a priori selection of the MH that produces the best solution for a given instance is a hard task. The research developed in this thesis investigates the use of meta-learning approaches to select the most promising MHs for new TSP instances. These approaches induce predictive meta-models from the training of machine learning techniques on a set of meta-data. In our meta-data, each meta-example is a TSP instance described by problem characteristics (meta-features) and performance of MHs (target meta-features) for this instance. The induced meta-models are used to indicate the values of the target meta-feature for new TSP instances. During the investigation of this research, several experiments were performed and important results were obtained

Made available in DSpace on 2014-12-17T15:47:44Z (GMT). No. of bitstreams: 1 AlvaroNP.pdf: 769620 bytes, checksum: a6a391c5417e2fcb7b544cc7f3b2140f (MD5) Previous issue date: 2006-07-27 / Due to great difficulty of accurate solution of Combinatorial Optimization Problems, some heuristic methods have been developed and during many years, the analysis of performance of these approaches was not carried through in a systematic way. The proposal of this work is to make a statistical analysis of heuristic approaches to the Traveling Salesman Problem (TSP). The focus of the analysis is to evaluate the performance of each approach in relation to the necessary computational time until the attainment of the optimal solution for one determined instance of the TSP. Survival Analysis, assisted by methods for the hypothesis test of the equality between survival functions was used. The evaluated approaches were divided in three classes: Lin-Kernighan Algorithms, Evolutionary Algorithms and Particle Swarm Optimization. Beyond those approaches, it was enclosed in the analysis, a memetic algorithm (for symmetric and asymmetric TSP instances) that utilizes the Lin-Kernighan heuristics as its local search procedure / Devido ? grande dificuldade de solu??o exata dos Problemas de Otimiza??o Combinat?ria, v?rios m?todos heur?sticos t?m sido desenvolvidos e durante muitos anos, a an?lise de desempenho dessas abordagens n?o foi realizada de maneira sistem?tica. A proposta deste trabalho ? fazer uma an?lise estat?stica de abordagens heur?sticas aplicadas ao Problema do Caixeiro Viajante. O foco da an?lise ? avaliar o desempenho de cada abordagem em rela??o ao tempo computacional necess?rio at? a obten??o da solu??o ?tima para uma determinada inst?ncia do PCV. Para essa an?lise, foi utilizada uma metodologia estat?stica chamada An?lise de Sobreviv?ncia, auxiliada por m?todos para o teste da hip?tese de igualdade entre fun??es. Para uma melhor compreens?o, as abordagens avaliadas foram divididas em tr?s classes: Algoritmos Lin-Kernighan, Algoritmos Evolucion?rios e Algoritmos de Otimiza??o por Nuvem de Part?culas. Al?m das abordagens j? existentes, foi inclu?do na an?lise, um algoritmo mem?tico (para inst?ncias sim?tricas e assim?tricas do PCV) que utiliza o algoritmo de Lin e Kernighan como procedimento de busca local