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

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

This work presents a general vision about the main concepts of combinatorial multi-objective optimization, where we present the more used technique for the resolution of problems of this nature. To the speech of the techniques we will also argue important aspects how much to the involved parameters in each technique, swing the main used boardings. Initially we implement and test the Multiple Objective Genetic Algorithm MOGA to generate a set of dominant solutions near to the Pareto optimal set for the biobjective Traveling Salesman Problems. In a second phase, we will go to implement the Strength Pareto Evolutionary Algorithm (SPEA) applied to biobjective Traveling Salesman Problems / Este trabalho apresenta uma visão geral sobre os principais conceitos da otimização combinatória multiobjetivo, onde apresentamos as técnicas mais utilizadas para a resolução de problemas desta natureza. Ao falarmos das técnicas, discutiremos também aspectos importantes quanto aos parâmetros envolvidos em cada técnica, mostrando as principais abordagens utilizadas. Inicialmente, implementamos e testamos o Multiple Objective Genetic Algorithm (MOGA) para gerar um conjunto de soluções dominantes próximo ao conjunto de Pareto ótimo para o problema do caixeiro viajante biobjetivo. Em uma segunda fase, implementamos o Strength Pareto Evolutionary Algorithm (SPEA) aplicado ao caixeiro viajante biobjetivo

Made available in DSpace on 2015-05-08T14:53:38Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 7900350 bytes, checksum: fbca2db827307d8c3ed2a1c15067d0da (MD5) Previous issue date: 2014-02-13 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This research deals with the Close-Enough Traveling Salesman Problem, a variant of the Traveling Salesman Problem wich has several applicatios in logistics. In the Close-Enough Traveling Salesman Problem, rather than visiting the vertex (customer) itself, the salesman must visit a specific region containing such vertex. To solve this problem, we propose a simple yet effective exact algorithm, based on Branch-and-Bound and Second Order Cone Programming. The proposed algorithm was tested in 824 instances suggested in the literature. Optimal solutions are obtained for open problems with up to a thousand vertices. We consider both instances in the two- and three-dimensional space. / Esta pesquisa trata do Problema do Caixeiro Viajante Suficientemente Próximo, uma variante do Problema do Caixeiro Viajante que possui diversas aplicações em logística. No Problema do Caixeiro Viajante Suficientemente Próximo, ao invés de visitar o próprio vértice (cliente), o caixeiro deve visitar uma região especifica contendo este vértice. Para resolver este problema, é proposto um algoritmo exato, simples e efetivo, baseado em branch-and-bound e Programação Cônica de Segunda Ordem. O algoritmo proposto foi testado em 824 instâncias sugeridas na literatura. Soluções ótimas foram obtidas para instâncias com até mil vértices. Foram consideradas instâncias nos espaços bi e tridimensional.