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

[pt] Em vários problemas de distribuição e logística, os produtos devem ser coletados em uma origem e entregues em um destino. Exemplos incluem o transporte de pessoas com deficiência, serviços de correio expresso, logística de suprimentos médicos, etc. O problema de roteamento abordado neste trabalho, conhecido como Traveling Salesman Problem with Pickup and Delivery (TSPPD), é da classe de problemas do caixeiro viajante com restrições de precedência. Neste problema, existe um mapeamento um-para-um entre coleta-entrega no qual cada cliente do tipo coleta possui um cliente do tipo entrega associado. Os clientes do tipo entrega somente podem ser visitados posteriormente à coleta associada. O TSPPD é um problema NP-difícil uma vez que generaliza o Traveling Salesman Problem (TSP). O TSP pode ser visto como um caso particular do TSPPD onde cada coleta coincide espacialmente com a respectiva entrega. As variantes com restrições de capacidade, janelas de tempo e diferentes políticas de carregamento têm recebido maior atenção na última década, embora ainda existam significantes avanços a serem realizados em termos de qualidades de soluções na versão básica do problema. Para resolver este problema, propomos um algoritmo meta-heurístico híbrido com vizinhanças largas exploradas eficientemente em O(n2). Nossos experimentos demonstram uma redução significativa no tempo computacional e também melhoria na qualidade de soluções previamente conhecidas na literatura. / [en] In various distribution and logistics issues, products must be collected at one source and delivered to a destination. Examples include disabled people transportation, express mail services, medical supplies logistics, etc. The routing problem addressed by this work, known as Traveling Salesman Problem with Pickup and Delivery (TSPPD), belongs to the class of traveling salesman problems with precedence constraints. In this problem, there is a one-to-one pickup-delivery mapping in which, for each pickuptype client, there is exactly one associated delivery-type client. Delivery clients can only be visited after the associated pickup. Since the TSPPD generalizes the TSP it is also a NP-hard problem, as the TSP is a particular casa of TSPPD where each pickup matches spatially with it s respective delivery. Variants with capacity constraints, time windows and different loading policies have received more attention in the last decade, although there are still significant advances to be made in terms of solution quality for the basic version of the problem. To solve this problem, we propose a hybrid metaheuristic algorithm with large neighborhoods efficiently explored in O(n2). Our experiments demonstrate a significant computational time reduction and also solutions quality improvement compared to the previous works.

Dans cette thèse, nous nous intéressons à deux thèmes d'analyse géométrique. Le premier concerne le comportement asymptotique des fonctions harmoniques en relation avec la géométrie, sur des graphes et des variétés. Nous étudions des critères de convergence au bord des fonctions harmoniques, comme celui de la bornitude non-tangentielle, de la finitude de l'énergie ou encore de la densité de l'énergie. Nous nous plaçons pour cela dans différents cadres comme les graphes hyperboliques au sens de Gromov, les variétés hyperboliques au sens de Gromov, les graphes de Diestel-Leader ou encore dans un cadre abstrait pour obtenir des résultats pour les points du bord minimal de Martin. Les méthodes probabilistes utilisées exploitent le lien entre les fonctions harmoniques et les martingales. Le deuxième thème abordé dans cette thèse concerne l'étude des propriétés des ensembles rectifiables de dimension 1 dans le groupe de Heisenberg, en relation avec des opérateurs d'intégrales singulières. Nous étendons à ce contexte sous-riemannien une partie des résultats de la théorie des ensembles uniformément rectifiables de David et Semmes. Nous obtenons notamment un théorème géométrique du voyageur de commerce qui fournit une condition pour qu'un ensemble Ahlfors-régulier du premier groupe de Heisenberg soit contenu dans une courbe Ahlfors-régulière. / In this thesis, we are interested in two topics of geometric analysis. The first one is concerned with the asymptotic behaviour of harmonic functions in connection with geometry on graphs and manifolds. We study criteria for convergence at boundary of harmonic functions such as non-tangential boundedness, finiteness of non-tangential energy or finiteness of the energy density. We deal with Gromov hyperbolic manifolds, Gromov hyperbolic graphs, Diestel-Leader graphs and with an abstract frame to obtain criteria at minimal Martin boundary points. The methods, coming from probability theory and metric geometry, use the relation between harmonic functions and martingales. The second topic concerns the rectifiability properties of 1-dimensional sets in the Heisenberg group in connection with the boundedness of singular integral operators. We extend to this sub-Riemannian setting parts of the theory of uniformly rectifiable sets due to David and Semmes. In particular, we obtain a geometric traveling salesman theorem which provides a condition for an Ahlfors regular set of the first Heisenberg group to be contained in an Ahlfors regular curve.

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.

nÃo hà / The planning of preventive maintenance is key role in the performance and quality of service of a power utility. The control of vegetation in the process of the electricity distribution network maintenance is of great importance to and continuous improvement of quality indicators of electricity supply, accompanied by the National Electric Energy Agency (ANEEL). The degree of criticality of pruning and productivity of teams are critical in this process. To resolve this issue it proposed a routing algorithm, in order to meet all the anomalies detected in previews, ensuring priority execution of critical cases within the period of maturity of the anomalies and before the occurrence of the failure. A genetic algorithm was developed and applied in solving this problem. The proposed technique has been adapted to a practical case of an electric utility and contributed a good economy and gains in productivity compared the current situation. / O planejamento da manutenÃÃo preventiva à papel fundamental para o bom desempenho e qualidade dos serviÃos prestados de uma concessionÃria de energia. O controle da vegetaÃÃo no processo de manutenÃÃo da rede de distribuiÃÃo de energia elÃtrica à de grande importÃncia para e melhoria contÃnua dos indicadores de qualidade do fornecimento de energia elÃtrica, acompanhado pela AgÃncia Nacional de Energia ElÃtrica (ANEEL). O grau de criticidade da poda e produtividade das equipes sÃo fatores crÃticos neste processo. Para resolver este problema foi proposto um algoritmo de roteirizaÃÃo, com o objetivo de atender todas as anomalias detectadas em inspeÃÃes prÃvias, garantindo a execuÃÃo prioritÃria dos casos mais crÃticos, dentro do prazo do vencimento das anomalias e antes da ocorrÃncia da falha. Um Algoritmo GenÃtico foi desenvolvido e aplicado na resoluÃÃo deste problema. A tÃcnica proposta foi adaptada a um caso prÃtico de uma concessionÃria de energia elÃtrica e contribuiu com uma boa economia e ganhos em produtividade, quando comparada a situaÃÃo atual.

Made available in DSpace on 2016-03-15T19:37:31Z (GMT). No. of bitstreams: 1 Ricardo Fabio Sato.pdf: 2268590 bytes, checksum: 40455266ba2f27af16965ee2b98d813a (MD5) Previous issue date: 2010-08-04 / Algorithms for solving the classical optimization problem called traveling salesman problem are proposed. These algorithms are inspired on the fact that synapses connecting biological neurons can be altered as the time passes in function of the neuronal activity. Thus, analogies between neurons and cities to be visited by the salesman and between roads and synapses coupling neurons are made. The performances of the proposed algorithms are evaluated by comparing the lengths of the paths produced by them with the length of the optimal solution. The results obtained in experiments performed by using randomly-generated instances and ten instances from a public database suggest that this is a promising approach. / Propõem-se algoritmos para solucionar o clássico problema de otimização chamado de o problema do caixeiro viajante. Esses algoritmos são inspirados no fato de que sinapses que conectam neurônios biológicos podem se alterar com o passar do tempo em função da atividade desses neurônios. Assim, fazem-se analogias entre neurônios e cidades a serem visitadas pelo caixeiro, e entre estradas e sinapses que conectam os neurônios. Os desempenhos dos algoritmos propostos são avaliados comparando-se os comprimentos dos caminhos gerados por eles com o comprimento do caminho ótimo. Os resultados obtidos em testes realizados em instâncias geradas aleatoriamente e em dez instâncias de base de dados pública indicam que essa é uma abordagem promissora.

Orientador: Flávio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T18:16:55Z (GMT). No. of bitstreams: 1 Hokama_PedroHenriqueDelBianco_M.pdf: 1340789 bytes, checksum: b5cc3f26e41b90afabdfac5c7a33bf05 (MD5) Previous issue date: 2011 / Resumo: Nesta dissertação de mestrado apresentamos um método exato para o Problema do Caixeiro Viajante com Restrições de Empacotamento Tridimensional, que combina o Problema do Caixeiro Viajante o Problema de Empacotamento Tridimensional com Restrição de Ordem. Neste problema, um veículo deve partir carregado de um depósito e entregar caixas em pontos pré-definidos para seus clientes. Cada cliente tem um conjunto de caixas que deve receber e o objetivo é minimizar o custo de deslocamento do veículo. As caixas devem ser retiradas a partir da porta do contêiner do veículo e a remoção das caixas de um cliente não podem ser obstruídas pelas caixas a serem descarregadas posteriormente. Propomos uma abordagem exata baseada em branch-and-cut para buscar uma rota de custo mínimo. Apresentamos algumas adaptações de algoritmos da literatura e uma formulação em Programação por Restrições para encontrar um empacotamento que obedece restrições de ordem. Realizamos testes computacionais em instâncias geradas aleatoriamente e comparamos resultados com os algoritmos adaptados da literatura. Os resultados foram bastante satisfatórios resolvendo instâncias de tamanho médio em tempo computacional aceitável na prática / Abstract: We present an exact method for the Traveling Salesman Problem with Three-dimensional Loading Constraints. This problem combines the Traveling Salesman Problem, and the Three- Dimensional Packing Problem With Loading Constraints. In this problem, a vehicle must be loaded at the depot and deliver boxes to the customers. Every customer has a set of boxes that should receive and our goal is to minimize the travel cost of the vehicle. Unloading is done through a single side of the container and items from an unloading customer must not be blocked by items to be delivered later. We propose exact and heuristic branch-and-cut algorithm to find a minimum cost route. Adaptations of algorithms from the literature and a Constraint Programming formulation is presented to find a packing that consider unloading contraints. We performed computational tests on instances randomly generated and compared results with the algorithms adapted from literature. The results were quite satisfactory resolving several instances in reasonable computational time / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

The aim of this diploma thesis is to describe the logistic processes in the processing of municipal waste in the company Local Enterprise in Hluboká nad Vltavou. Describe the business and analyze its decision-making issues. Then analyze the current situation and propose changes to apply optimization methods through a special computer program. The conclusion of the thesis is a concrete proposal of route optimization to improve the current situation of the company, which will lead to a positive economic effect on logistics of waste processing.

Plusieurs problèmes d'optimisation combinatoire sont dits NP-difficiles et ne peuvent être résolus de façon optimale par des algorithmes exacts. Les métaheuristiques ont prouvé qu'elles pouvaient être efficaces pour résoudre un grand nombre de ces problèmes en leur trouvant des solutions approchées en un temps raisonnable. Cependant, face à des instances de grande taille, elles ont besoin d'un temps de calcul et d'une quantité d'espace mémoire considérables pour être performantes dans l'exploration de l'espace de recherche. Par conséquent, l'intérêt voué à leur déploiement sur des architectures de calcul haute performance a augmenté durant ces dernières années. Les approches de parallélisation existantes suivent généralement les paradigmes de passage de messages ou de mémoire partagée qui conviennent aux architectures traditionnelles à base de microprocesseurs, aussi appelés CPU (Central Processing Unit).Cependant, la recherche évolue très rapidement dans le domaine du parallélisme et de nouvelles architectures émergent, notamment les accélérateurs matériels qui permettent de décharger le CPU de certaines de ses tâches. Parmi ceux-ci, les processeurs graphiques ou GPU (Graphics Processing Units) présentent une architecture massivement parallèle possédant un grand potentiel mais aussi de nouvelles difficultés d'algorithmique et de programmation. En effet, les modèles de parallélisation de métaheuristiques existants sont généralement inadaptés aux environnements de calcul de type GPU. Certains travaux ont d'ailleurs abordé ce sujet sans toutefois y apporter une vision globale et fondamentale.L'objectif général de cette thèse est de proposer un cadre de référence permettant l'implémentation efficace des métaheuristiques sur des architectures parallèles basées sur les GPU. Elle débute par un état de l'art décrivant les travaux existants sur la parallélisation GPU des métaheuristiques et les classifications générales des métaheuristiques parallèles. Une taxonomie originale est ensuite proposée afin de classifier les implémentations recensées et de formaliser les stratégies de parallélisation sur GPU dans un cadre méthodologique cohérent. Cette thèse vise également à valider cette taxonomie en exploitant ses principales composantes pour proposer des stratégies de parallélisation originales spécifiquement adaptées aux architectures GPU. Plusieurs implémentations performantes basées sur les métaheuristiques d'Optimisation par Colonie de Fourmis et de Recherche Locale Itérée sont ainsi proposées pour la résolution du problème du Voyageur de Commerce. Une étude expérimentale structurée et minutieuse est réalisée afin d'évaluer et de comparer la performance des approches autant au niveau de la qualité des solutions trouvées que de la réduction du temps de calcul. / Several combinatorial optimization problems are NP-hard and can only be solved optimally by exact algorithms for small instances. Metaheuristics have proved to be effective in solving many of these problems by finding approximate solutions in a reasonable time. However, dealing with large instances, they may require considerable computation time and amount of memory space to be efficient in the exploration of the search space. Therefore, the interest devoted to their deployment on high performance computing architectures has increased over the past years. Existing parallelization approaches generally follow the message-passing and shared-memory computing paradigms which are suitable for traditional architectures based on microprocessors, also called CPU (Central Processing Unit). However, research in the field of parallel computing is rapidly evolving and new architectures emerge, including hardware accelerators which offloads the CPU of some of its tasks. Among them, graphics processors or GPUs (Graphics Processing Units) have a massively parallel architecture with great potential but also imply new algorithmic and programming challenges. In fact, existing parallelization models of metaheuristics are generally unsuited to computing environments like GPUs. Few works have tackled this subject without providing a comprehensive and fundamental view of it.The general purpose of this thesis is to propose a framework for the effective implementation of metaheuristics on parallel architectures based on GPUs. It begins with a state of the art describing existing works on GPU parallelization of metaheuristics and general classifications of parallel metaheuristics. An original taxonomy is then designed to classify identified implementations and to formalize GPU parallelization strategies in a coherent methodological framework. This thesis also aims to validate this taxonomy by exploiting its main components to propose original parallelization strategies specifically tailored to GPU architectures. Several effective implementations based on Ant Colony Optimization and Iterated Local Search metaheuristics are thus proposed for solving the Travelling Salesman Problem. A structured and thorough experimental study is conducted to evaluate and compare the performance of approaches on criteria related to solution quality and computing time reduction.

This thesis deals with optimization problems of the parcels distribution. This issue can be solved on the ground of traveling salesman problem whose mathematical and economic model, including their modifications, are presented in the theoretical part of the thesis. We can solve these problems by using exact methods, heuristic and metaheuristic algorithms. In the theoretical part are described traveling salesman problem, traveling salesman problem with time windows, traveling salesman problem with multiple time windows and dynamic traveling salesman problem including possible ways of solution. In the practical part we can find application of problems on the real example, when we are finding the shortest possible route for the PPL's employee under different assumptions. The solution is obtained by using solver Gurobi within the modelling system MPL for Windows. In conclusion of the thesis the results are summarized and models are compared with each other.