Spelling suggestions: "subject:"travelling salesman"" "subject:"ravelling salesman""
51 |
Facets of a Balanced Minimum Evolution Network PolytopeDurell, Cassandra M. 27 June 2019 (has links)
No description available.
|
52 |
Routing for Autonomous Underwater Vehicles : Optimization for subsea operationsJansson, Kasper, Nyberg, Samuel January 2024 (has links)
Background Efficient underwater operations with autonomous underwater vehicles (AUVs) relying on several factors for a mission to be successful, such as operation time, distance covered, and waiting times. Today’s methods and processes for AUVs often struggle with inefficiencies and lack of route optimization. These challenges can result in increased operational costs and suboptimal performance. Minimizing operation time and utilizing route planning algorithms enables adaptation to operational challenges, potentially resulting in cost savings. Objectives This thesis aims to identify an efficient and practical solutions that will improve the operations for AUVs and the objective is to optimize the diving process through suboptimal routing algorithms in a predefined scenario. The study addresses one primary question to achive the aim. The question were: How can routing algorithms be implemented to improve the efficiency and reduce the operation time of Autonomous Underwater Vehicles? Methods The method describes three heuristic algorithms for optimizing the operations of AUVs. The first algorithm, the nearest neighbor heuristic (NNH) aims to minimize the distance an AUV needs to travel to recover and deploy ocean bottom nodes (OBN) within a cluster. The second algorithm, inspired by railway traffic, tries to prevent overlaps and minimizing the waiting times at the depot station. The third algorithm is highlighted as a local optimization algorithm that prioritizes the shortest waiting time over the nearest distance, adapting dynamically to available depot stations. Results The results in this thesis are derived from numerous simulations from different scenarios. The relationship between operations time and waiting time for different scenarios was obtained. The first algorithm proved to work for this type of situation. The second algorithm demonstrated its ability to yield superior solutions, albeit at the cost of being time-consuming due to a high number of iterations. The third algorithm was examined under conditions with and without delays. Even with delays, the algorithm consistently manages disturbances effectively. Conclusions While achieving an exact optimal solution remains challenging due to complexity, the research showed promising improvements in the endurance of the AUVs through the algorithms. The first algorithm was effective in minimizing the distance the AUVs traveled by selecting the most efficient path from numerous potential solutions. The second algorithm was slow due to a large number iterations, but the algorithm was able to find a solution where the operation and waiting time of the AUV could be reduced. The third algorithm was faster, but generally resulted in longer operation times. Also, increasing the number of AUVs resulted in shorter operation times but led to longer waiting times at the depot station, particularly in scenarios that became saturated with too many AUVs. / Bakgrund Undervattensoperationer med autonoma undervattensfarkoster (AUV:er) är beroende av flera faktorer för framgångsrika uppdrag, såsom driftstid, avstånd och väntetider. Dagens metoder och processer för AUV:er har ofta problem med ineffektivitet och bristande optimering av rutter. Dessa utmaningar kan leda till ökade driftkostnader och suboptimal prestanda. Genom att minimera operationstiden och använda ruttplaneringsalgoritmer möjliggörs anpassning till operativa utmaningar, vilket potentiellt kan resultera i kostnadsbesparingar. Syfte Detta examensarbete syftar till att utveckla effektiva och praktiska lösningar för att förbättra systemets prestanda och målet är att optimera rutterna genom suboptimala algoritmer i ett fördefinierat scenario. Arbetet behandlar en primärfråga för att uppnå målet. Frågan var: Hur kan ruttalgoritmer implementeras för att förbättra effektiviteten och minska drifttiden för autonoma undervattensfarkoster? Metod Metoden beskriver tre heuristiska algoritmer för att optimera driften förAUV:er. Den första algoritmen, närmaste granne heuristiken (NNH), syftar till attminimera avståndet en AUV behöver resa för att hämta och placera ut havsbottennoder (OBN) inom en kluster. Den andra algoritmen, inspirerad av tågtrafiken, syftar till att endast en AUV befinner sig vid depåstationen åt gången för att förhindra konflikter och minimera väntetider. Den tredje algoritmen är en lokal optimeringsalgoritm som prioriterar kortaste väntetiden över närmaste avstånd och anpassar sig dynamiskt till tillgängliga depåstationer. Resultat Resultaten i denna uppsats baseras på ett flertal simuleringar med olika scenarier. Förhållandet mellan drifttid och väntetid för olika scenarier erhölls. Den första algoritmen visade sig fungera bra för denna typ av situation. Den andra algoritmen visade sin förmåga att ge bättre lösningar, trots att den var tidskrävande pågrund av ett högt antal iterationer. Den tredje algoritmen undersöktes under förhållanden med och utan förseningar. Trots förseningar lyckades algoritmen konsekvent hantera störningar effektivt. Slutsats Trots komplexiteten med att tillhandahålla en exakt optimal lösning, visade arbetet förbättringar i AUV:ers uthållighet genom olika algoritmer. Den första algoritmen var effektiv för att minimera det avstånd som AUV:er färdades genom att välja en optimal väg bland många potentiella lösningar. Den andra algoritmen var långsam på grund av många iterationer, men algoritmen kunde hitta en lösning där AUV:ens drift- och väntetid kunde minskas. Den tredje algoritmen var snabbare men resulterade i längre drifttider. Vidare resulterade ökningen av antalet AUV:er i en minskning av drifttider men ökade väntetider, särskilt i scenarier som blev mättade med för många AUV:er.
|
53 |
Algoritmo mem?tico com infec??o viral: uma aplica??o ao problema do caixeiro viajante assim?trico / Memetic algorithm with viral infection: an application to the assimetric travelling salesman problemFontes, F?bio Francisco da Costa 19 May 2006 (has links)
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
|
54 |
Aplica?a? das t?cnicas Path-relinking e Vocabulary buiding na melhoria de performance do algoritmo mem?tico para o problema do caixeiro viajante assim?tricoSilva Neto, Jo?o Saturnino da 10 July 2009 (has links)
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
|
55 |
Résolution de problèmes d'optimisation combinatoire mono et multi-objectifs par énumération ordonnée / Solving single and multi-objective combinatorial optimization problems by ordered enumerationBelhoul, Lyes 09 December 2014 (has links)
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.
|
56 |
Genetické algoritmy / Genetic AlgorithmsMiček, David January 2009 (has links)
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.
|
57 |
Akcelerace heuristických metod diskrétní optimalizace na GPU / Acceleration of Discrete Optimization Heuristics Using GPUPecháček, Václav January 2012 (has links)
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.
|
58 |
Probleme der TourenbildungKämpf, Michael 24 November 2006 (has links)
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.
|
59 |
Experimenty s rojovou inteligencí (swarm intelligence) / Experiments with the Swarm IntelligenceHula, Tomáš January 2008 (has links)
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.
|
60 |
Investigating the Use of Digital Twins to Optimize Waste Collection Routes : A holistic approach towards unlocking the potential of IoT and AI in waste management / Undersökning av användningen av digitala tvillingar för optimering av sophämtningsrutter : Ett holistiskt tillvägagångssätt för att ta del av potentialen för IoT och AI i sophanteringMedehal, Aarati January 2023 (has links)
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.
|
Page generated in 0.1032 seconds