Made available in DSpace on 2014-12-17T14:53:23Z (GMT). No. of bitstreams: 1 FabioFCF.pdf: 875120 bytes, checksum: 089fb9e8e722351411a9dbd3d86bbef4 (MD5) Previous issue date: 2006-05-19 / The Combinatorial Optimization is a basic area to companies who look for competitive advantages in the diverse productive sectors and the Assimetric Travelling Salesman Problem, which one classifies as one of the most important problems of this area, for being a problem of the NP-hard class and for possessing diverse practical applications, has increased interest of researchers in the development of metaheuristics each more efficient to assist in its resolution, as it is the case of Memetic Algorithms, which is a evolutionary algorithms that it is used of the genetic operation in combination with a local search procedure. This work explores the technique of Viral Infection in one Memetic Algorithms where the infection substitutes the mutation operator for obtaining a fast evolution or extinguishing of species (KANOH et al, 1996) providing a form of acceleration and improvement of the solution . For this it developed four variants of Viral Infection applied in the Memetic Algorithms for resolution of the Assimetric Travelling Salesman Problem where the agent and the virus pass for a symbiosis process which favored the attainment of a hybrid evolutionary algorithms and computational viable / A Otimiza??o Combinat?ria ? uma ?rea fundamental para empresas que buscam vantagens competitivas nos diversos setores produtivos, e o Problema do Caixeiro Viajante Assim?trico, o qual se classifica como um dos mais importantes problemas desta ?rea, devido a ser um problema da classe NP-dif?cil e tamb?m por possuir diversas aplica??es pr?ticas, tem despertado interesse de pesquisadores no desenvolvimento de Metaheur?sticas cada vez mais eficientes para auxiliar na sua resolu??o, como ? o caso do Algoritmo Mem?tico, o qual ? um algoritmo evolutivo que se utiliza dos operadores gen?ticos em combina??o com um procedimento de busca local. Este trabalho explora a t?cnica de Infec??o Viral em um Algoritmo Mem?tico, onde a infec??o substitui o operador de muta??o por conseguir uma r?pida evolu??o ou extin??o de esp?cies (KANOH et al., 1996), proporcionando uma forma de acelera??o e melhoria da solu??o. Para isto se desenvolveu quatro variantes de Infec??o Viral aplicadas no Algoritmo Mem?tico para resolu??o do Problema do Caixeiro Viajante Assim?trico, onde o agente e o v?rus passam por um processo de Simbiose, as quais favoreceram a obten??o de um algoritmo evolutivo h?brido e computacionalmente vi?vel

Made available in DSpace on 2014-12-17T15:26:37Z (GMT). No. of bitstreams: 1 JoaoSSN.pdf: 5224762 bytes, checksum: 4021177e0509af10223ad40751ece2f0 (MD5) Previous issue date: 2009-07-10 / The present essay shows strategies of improvement in a well succeded evolutionary metaheuristic to solve the Asymmetric Traveling Salesman Problem. Such steps consist in a Memetic Algorithm projected mainly to this problem. Basically this improvement applied optimizing techniques known as Path-Relinking and Vocabulary Building. Furthermore, this last one has being used in two different ways, in order to evaluate the effects of the improvement on the evolutionary metaheuristic. These methods were implemented in C++ code and the experiments were done under instances at TSPLIB library, being possible to observe that the procedures purposed reached success on the tests done / O presente trabalho prop?e estrat?gias de melhoria em uma bem sucedida metaheur ?stica evolucionaria para a resolu??o do Problema do Caixeiro Viajante Assim?trico. Tal procedimento consiste em um algoritmo mem?tico projetado especificamente para esse problema. Essas melhorias t?m por base a aplica??o de t?cnicas de otimiza??o conhecidas como Path-Relinking e Vocabulary Building, sendo essa ?ltima t?cnica utilizada de dois modos distintos, com o intuito de avaliar os efeitos de melhoria sobre a metaheur?stica evolucion?ria empregada. Os m?todos propostos foram implementados na linguagem de programa??o C++ e os experimentos computacionais foram realizados sobre inst?ncias disponibilizadas na biblioteca TSPLIB, tornando poss?vel observar que os procedimentos propostos alcan?aram ?xito nos testes realizados

Notre objectif dans cette thèse est de proposer des algorithmes efficaces pour résoudre des problèmes d’optimisation combinatoire difficiles. Dans un premier temps, nous établissons le principe de l’énumération ordonnée qui consiste à générer dans un ordre adéquat les solutions d’un problème relâché associé au problème principal jusqu’à l’obtention de la preuve d’optimalité d’une solution. Nous construisons une procédure générique dans le cadre général des problème d’optimisation combinatoire. Dans un second temps nous abordons les applications de notre algorithme sur des problèmes qui admettent le problème d’affectation comme relaxation. Le premier cas particulier que nous étudions est la recherche d’une solution de bon compromis pour le problème d’affectation multiobjectif. La seconde application se rapporte au problème du voyageur de commerce asymétrique qui présente la difficulté de comporter des contraintes qui interdisent les sous-tournées, en plus des contraintes du problème d’affectation. / Our aim in this thesis is to propose efficient algorithms for solving difficult combinatorial optimization problems. Our algorithms are based on a generic method of ordered enumeration. Initially, we describe the principle of ordered enumeration which consists in generating in a specific order solutions of a relaxed problem associated to the difficult main problem, until meeting a proof of the optimality of a feasible solution. We construct a generic procedure in the general context of combinatorial optimization problems. In a second step we discuss applications of our algorithm on some difficult problems which admit the assignment problem as relaxation. The first special case we study is the search for a compromise solution to the multiobjective assignment problem. The second application is the asymmetric travelling salesman problem, which contains sub-tour constraints in addition to the constraints of the assignment problem.

This thesis presents description of Genetic algorithm. The description begins with theory of complexity and following basic theory of genetic algorithm. Next part explains the principle of all three tasks – travelling salesman problem, knapsack problem and evolution of algorithm for five-in-a-row. The main focus was on developing the algorithm for five-in-a-row. The results were tested with other similar algorithms from internet. In case of travelling salesman problem and knapsack problem, the results were compared with gradient optimization methods.

Thesis deals with discrete optimization problems. It focusses on faster ways to find good solutions by means of heuristics and parallel processing. Based on ant colony optimization (ACO) algorithm coupled with k-optimization local search approach, it aims at massively parallel computing on graphics processors provided by Nvidia CUDA platform. Well-known travelling salesman problem (TSP) is used as a case study. Solution is based on dividing task into subproblems using tour-based partitioning, parallel processing of distinct parts and their consecutive recombination. Provided parallel code can perform computation more than seventeen times faster than the sequential version.

Die Tourenbildung beschäftigt sich mit der Konstruktion kostengünstiger Transportrouten zur Belieferung von Verbrauchern. Sie ist eine der weitreichensten Erfolgsgeschichten des Operations Research. Das starke Interesse an diesen Problemen durch Industrie und Forschung liegt zum einen am wirtschaftlichen Potenzial der Tourenbildung und -optimierung, zum anderen macht ihr Reichtum an Struktur sie zu einem faszinierenden Forschungsgebiet. In der vorliegenden Arbeit soll ein Überblick über einige, u. a. auch neuere mathematische Modell- und Lösungsansätze gegeben werden. Auf Grund der hohen Anzahl der Veröffentlichungen auf diesem Gebiet wird nicht zwingend ein Anspruch auf die vollständige Darlegung aller möglichen Problemstellungen im Zusammenhang mit dem TSP sowie dem VRP und deren Lösungsansätze erhoben. An den gegebenen Stellen wird statt dessen auf weiterführende Literatur verwiesen.

This work deals with the issue of swarm intelligence as a subdiscipline of artificial intelligence. It describes biological background of the dilemma briefly and presents the principles of searching paths in ant colonies as well. There is also adduced combinatorial optimization and two selected tasks are defined in detail: Travelling Salesman Problem and Quadratic Assignment Problem. The main part of this work consists of description of swarm intelligence methods for solving mentioned problems and evaluation of experiments that were made on these methods. There were tested Ant System, Ant Colony System, Hybrid Ant System and Max-Min Ant System algorithm. Within the work there were also designed and tested my own method Genetic Ant System which enriches the basic Ant System i.a. with development of unit parameters based on genetical principles. The results of described methods were compared together with the ones of classical artificial intelligence within the frame of both solved problems.

Solid waste management is a global issue that affects everyone. The management of waste collection routes is a critical challenge in urban environments, primarily due to inefficient routing. This thesis investigates the use of real-time virtual replicas, namely Digital Twins to optimize waste collection routes. By leveraging the capabilities of digital twins, this study intends to improve the effectiveness and efficiency of waste collection operations. The ‘gap’ that the study aims to uncover is hence at the intersection of smart cities, Digital Twins, and waste collection routing. The research methodology comprises of three key components. First, an exploration of five widely used metaheuristic algorithms provides a qualitative understanding of their applicability in vehicle routing, and consecutively waste collection route optimization. Building on this foundation, a simple smart routing scenario for waste collection is presented, highlighting the limitations of a purely Internet of Things (IoT)-based approach. Next, the findings from this demonstration motivate the need for a more data-driven and intelligent solution, leading to the introduction of the Digital Twin concept. Subsequently, a twin framework is developed, which encompasses the technical anatomy and methodology required to create and utilize Digital Twins to optimize waste collection, considering factors such as real-time data integration, predictive analytics, and optimization algorithms. The outcome of this research contributes to the growing concept of smart cities and paves the way toward practical implementations in revolutionizing waste management and creating a sustainable future. / Sophantering är ett globalt problem som påverkar alla, och hantering av sophämtningsrutter är en kritisk utmaning i stadsmiljöer. Den här avhandlingen undersöker användningen av virtuella kopior i realtid, nämligen digitala tvillingar, för att optimera sophämtningsrutter. Genom att utnyttja digitala tvillingars förmågor, avser den här studien att förbättra effektiviteten av sophämtning. Forskningsmetoden består av tre nyckeldelar. Först, en undersökning av fem välanvända Metaheuristika algoritmer som ger en kvalitativ förståelse av deras applicerbarhet i fordonsdirigering och således i optimeringen av sophämtningsrutter. Baserat på detta presenteras ett enkelt smart ruttscenario för sophämtning som understryker bristerna av att bara använda Internet of Things (IoT). Sedan motiverar resultaten av demonstrationen nödvändigheten för en mer datadriven och intelligent lösning, vilket leder till introduktionen av konceptet med digitala tvillingar. Därefter utvecklas ett ramverk för digitala tvillingar som omfattar den tekniska anatomin och metod som krävs för att skapa och använda digitala tvillingar för att optimera sophämtningsrutter. Dessa tar i beaktning faktorer såsom realtidsdataintegrering, prediktiv analys och optimeringsalgoritmer. Slutsatserna av studien bidrar till det växande konceptet av smarta städer och banar väg för praktisk implementation i revolutionerande sophantering och för skapandet för en hållbar framtid.

This diploma thesis deals with evolutionary algorithms used for travelling salesman problem (TSP). In the first section, there are theoretical foundations of a graph theory and computational complexity theory. Next section contains a description of chosen optimization algorithms. The aim of the diploma thesis is to implement an application that solve TSP using evolutionary algorithms.

This paper deals with optimal distribution issues. One may find listed problems of real life linked to distribution. Moreover, there are explained travelling salesman problem, vehicle routing problem and its variants. This work brings an overview of different ways how to solve vehicle routing problem. In practical part, there is an analysis of distribution of real company. The concept of application is presented in the second part of this paper. This concept could reduce costs of distribution in analyzed company. Testing is aimed mainly on the variant VRPCL (Vehicle Routing Problem with Continuos Loading).