Made available in DSpace on 2014-12-17T15:48:12Z (GMT). No. of bitstreams: 1 CristineCS.pdf: 714473 bytes, checksum: 61f78bdfcd48bd6e64e25178e846e81b (MD5) Previous issue date: 2007-02-08 / Este trabalho apresenta um algoritmo transgen?tico h?brido para a solu??o de um Problema de Configura??o de uma Rede de Distribui??o de G?s Natural. O problema da configura??o dessas redes requer a defini??o de um tra?ado por onde os dutos devem ser colocados para atender aos clientes. ? estudada neste trabalho uma maneira de conectar os clientes em uma rede com arquitetura em forma de ?rvore. O objetivo ? minimizar o custo de constru??o da rede, mesmo que para isso alguns clientes que n?o proporcionam lucros deixem de ser atendidos. Esse problema pode ser formulado computacionalmente atrav?s do Problema de Steiner com Pr?mios. Este ? um problema de otimiza??o combinat?ria da classe dos NP?rduos. Este trabalho apresenta um algoritmo heur?stico para a solu??o do problema. A abordagem utilizada ? chamada de Algoritmos Transgen?ticos, que se enquadram na categoria dos algoritmos evolucion?rios. Para a gera??o de solu??es inicias ? utilizado um algoritmo primaldual, e pathrelinking ? usado como intensificador

Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2016-07-22T15:02:52Z No. of bitstreams: 1 HudsonGeovaneDeMedeiros_DISSERT.pdf: 1225087 bytes, checksum: 40f3994faacf86961dbe3768775e4f86 (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2016-07-26T23:00:12Z (GMT) No. of bitstreams: 1 HudsonGeovaneDeMedeiros_DISSERT.pdf: 1225087 bytes, checksum: 40f3994faacf86961dbe3768775e4f86 (MD5) / Made available in DSpace on 2016-07-26T23:00:12Z (GMT). No. of bitstreams: 1 HudsonGeovaneDeMedeiros_DISSERT.pdf: 1225087 bytes, checksum: 40f3994faacf86961dbe3768775e4f86 (MD5) Previous issue date: 2016-02-05 / Problemas multiobjetivo, diferentes daqueles com um ?nico objetivo, possuem, em geral, diversas solu??es ?timas, as quais comp?em o conjunto Pareto ?timo. Uma classe de algoritmos heur?sticos para tais problemas, aqui chamados de otimizadores, produz aproxima??es deste conjunto. Devido ao grande n?mero de solu??es geradas durante a otimiza??o, muitas delas ser?o descartadas, pois a manuten??o e compara??o frequente entre todas elas poderia demandar um alto custo de tempo. Como uma alternativa a este problema, muitos otimizadores lidam com arquivos limitados. Um problema que surge nestes casos ? a necessidade do descarte de solu??es n?o-dominadas, isto ?, ?timas at? ent?o. Muitas t?cnicas foram propostas para lidar com o problema do descarte de solu??es n?o-dominadas e as investiga??es mostraram que nenhuma delas ? completamente capaz de prevenir a deteriora??o dos arquivos. Este trabalho investiga uma t?cnica para ser usada em conjunto com as propostas previamente na literatura, a fim de para melhorar a qualidade dos arquivos. A t?cnica consiste em reciclar periodicamente solu??es descartadas. Para verificar se esta ideia pode melhorar o conte?do dos otimizadores durante a otimiza??o, ela foi implementada em tr?s algoritmos da literatura e testada em diversos problemas. Os resultados mostraram que, quando os otimizadores j? conseguem realizar uma boa otimiza??o e resolver os problemas satisfatoriamente, a deteriora??o ? pequena e o m?todo de reciclagem ineficaz. Todavia, em casos em que o otimizador deteriora significativamente, a reciclagem conseguiu evitar esta deteriora??o no conjunto de aproxima??o. / Multi-objective problems may have many optimal solutions, which together form the Pareto optimal set. A class of heuristic algorithms for those problems, in this work called optimizers, produces approximations of this optimal set. The approximation set kept by the optmizer may be limited or unlimited. The benefit of using an unlimited archive is to guarantee that all the nondominated solutions generated in the process will be saved. However, due to the large number of solutions that can be generated, to keep an archive and compare frequently new solutions to the stored ones may demand a high computational cost. The alternative is to use a limited archive. The problem that emerges from this situation is the need of discarding nondominated solutions when the archive is full. Some techniques were proposed to handle this problem, but investigations show that none of them can surely prevent the deterioration of the archives. This work investigates a technique to be used together with the previously proposed ideas in the literature to deal with limited archives. The technique consists on keeping discarded solutions in a secondary archive, and periodically recycle these solutions, bringing them back to the optimization. Three methods of recycling are presented. In order to verify if these ideas are capable to improve the archive content during the optimization, they were implemented together with other techniques from the literature. An computational experiment with NSGA-II, SPEA2, PAES, MOEA/D and NSGA-III algorithms, applied to many classes of problems is presented. The potential and the difficulties of the proposed techniques are evaluated based on statistical tests.

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.