To see the other types of publications on this topic, follow the link: Application of travelling salesman problem.
Dissertations / Theses on the topic 'Application of travelling salesman problem'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Application of travelling salesman problem.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Haghighi, Maryam. "Application of Combinatorial Optimization Techniques in Genomic Median Problems." Thèse, Université d'Ottawa / University of Ottawa, 2011. http://hdl.handle.net/10393/20484.
Full textAbstract:
Constructing the genomic median of several given genomes is crucial in developing evolutionary trees, since the genomic median provides an estimate for the ordering of the genes in a common ancestor of the given genomes.
This is due to the fact that the content of DNA molecules is often similar, but the difference is mainly in the order in which the genes appear in various genomes. The mutations that affect this ordering are called genome rearrangements, and many structural differences between genomes can be studied using genome rearrangements.
In this thesis our main focus is on applying combinatorial optimization techniques to genomic median problems, with particular emphasis on the breakpoint distance as a measure of the difference between two genomes. We will study different variations of the breakpoint median problem from signed to unsigned, unichromosomal to multichromosomal, and linear to circular to mixed.
We show how these median problems can be formulated in terms of problems in combinatorial optimization, and take advantage of well-known combinatorial optimization techniques and apply these powerful methods to study various median problems.
Some of these median problems are polynomial and many are NP-hard. We find efficient algorithms and approximation methods for median problems based on well-known combinatorial optimization structures. The focus is on algorithmic and combinatorial aspects of genomic medians, and how they can be utilized to obtain optimal median solutions.
2
Pogiatzis, Thomas. "Application of mixed-integer programming in chemical engineering." Thesis, University of Cambridge, 2013. https://www.repository.cam.ac.uk/handle/1810/245023.
Full textAbstract:
Mixed-Integer Programming has been a vital tool for the chemical engineer in the recent decades and is employed extensively in process design and control. This dissertation presents some new Mixed-Integer Programming formulations developed for two well-studied problems, one with a central role in the area of Optimisation, the other of great interest to the chemical industry. These are the Travelling Salesman Problem and the problem of scheduling cleaning actions for heat exchanger networks subject to fouling. The Travelling Salesman Problem finds a plethora of applications in many scientific disciplines, Chemical Engineering included. None of the mathematical programming formulations proposed for solving the problem considers fewer than O(n^2) binary degrees of freedom. The first part of this dissertation introduces a novel mathematical description of the Travelling Salesman Problem that succeeds in reducing the binary degrees of freedom to O(nlog2(n)). Three Mixed-Integer Linear Programming formulations are developed and the computational performance of these is tested through computational studies. Sophisticated methods are now available for scheduling the cleaning actions for networks of heat exchangers subject to fouling. In the majority of these, only one form of cleaning is used, which restores the performance of the exchanger back to its clean level. A recent study revised the scheduling problem for the case where there are several cleaning methods available. The second part of this dissertation extends their approach, developed for individual units, to heat exchanger networks and explores the concept of selection of cleaning techniques further. Mixed-Integer Programming formulations are proposed for the scheduling task, for two fouling scenarios: (i) chemical reaction fouling and (ii) biological fouling. A series of results are presented for the implementation of the scheduling formulations to networks of different sizes.
3
Fu, Yao. "Applications of Circulations and Removable Pairings to TSP and 2ECSS." Thèse, Université d'Ottawa / University of Ottawa, 2014. http://hdl.handle.net/10393/31078.
Full textAbstract:
In this thesis we focus on two NP-hard and intensively studied problems: The travelling salesman problem (TSP), which aims to find a minimum cost tour that visits every node exactly once in a complete weighted graph, and the 2-edge-connected spanning subgraph problem (2ECSS), which aims to find a minimum size 2-edge-connected spanning subgraph in a given graph.
TSP and 2ECSS have many real world applications. However, both problems are NP-hard which means it is unlikely that polynomial time algorithms exist to solve them, so methods that return close to optimal solutions are sought. In this thesis we mainly focus on k-approximation algorithms for the two problems, which efficiently return a solution within k times of the optimal solution.
For a special case of TSP called graph TSP, using ideas from Momke and Svensson, we present a 25/18-approximation algorithm for a special class of graphs using circulations and T-joins, which improves the previous known best bound of 7/5 for such graphs. Moreover, if the graph does not contain special nodes, our algorithm ensures the ratio of 4/3.
For 2ECSS, given any k-edge-connected graph G=(V,E), |V|=n, |E|=m, we present an approximation algorithm that gives a 2-edge-connected spanning subgraph with the number of edges at most n+(m-n)/(k-1)-(k-2)/(k-1) with a novel use of circulations, which improves both the approximation ratio and the simplicity of the proof compared to a result by Huh in 2004.
4
Mitchell, Sophia. "A Cascading Fuzzy Logic Approach for Decision Making in Dynamic Applications." University of Cincinnati / OhioLINK, 2016. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1448037866.
Full text
5
Butler, Martin. "2-period travelling salesman problem." Thesis, University of Southampton, 1997. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.242250.
Full text
6
Gupta, Anil Kumar. "On a generalized travelling salesman problem." Thesis, University of Ottawa (Canada), 1986. http://hdl.handle.net/10393/4745.
Full text
7
Bryant, Kylie. "Genetic Algorithms and the Travelling Salesman Problem." Scholarship @ Claremont, 2000. https://scholarship.claremont.edu/hmc_theses/126.
Full textAbstract:
Genetic algorithms are an evolutionary technique that use crossover and mutation operators to solve optimization problems using a survival of the fittest idea. They have been used successfully in a variety of different problems, including the traveling salesman problem. In the traveling salesman problem we wish to find a tour of all nodes in a weighted graph so that the total weight is minimized. The traveling salesman problem is NP-hard but has many real world applications so a good solution would be useful. Many different crossover and mutation operators have been devised for the traveling salesman problem and each give different results. We compare these results and find that operators that use heuristic information or a matrix representation of the graph give the best results.
8
Ahrens, Barry. "A Tour Construction Framework for the Travelling Salesman Problem." NSUWorks, 2012. http://nsuworks.nova.edu/gscis_etd/74.
Full textAbstract:
The Tour Construction Framework (TCF) integrates both global and local heuristics in a complementary framework in order to efficiently solve the Travelling Salesman Problem (TSP). Most tour construction heuristics are strictly local in nature. However, the experimental method presented in this research includes a global heuristic to efficiently solve the TSP. The Global Path (GP) component and Super Node (SN) component comprise the TCF. Each component heuristic is tuned with one or more parameters. Genetic Algorithms (GA) are used to train the collection of parameters for the TCF components on subsets of benchmark TSPs. The GA results are used to run the TCF on the full TSP instances. The performance of the TCF is evaluated for speed, accuracy, and computational complexity, and it is compared against six mainstream TSP solvers: Lin-Kernighan-Helsgaun (LKH-2), 2-Opt, Greedy, Boruvka, Quick-Boruvka, and Nearest Neighbor. The empirical study demonstrates the effectiveness of the TCF in achieving near-optimal solutions for the TSP with reasonable costs.
9
Schmitting, Walter. "Das Traveling-Salesman-Problem Anwendungen und heuristische Nutzung von Voronoi-Delaunay-Strukturen zur Lösung euklidischer, zweidimensionaler Traveling-Salesman-Probleme /." Münster : Schmitting, 2000. http://deposit.ddb.de/cgi-bin/dokserv?idn=960608176.
Full text
10
Krishnamoorthy, Mohan. "Contributions to the solution of the symmetric travelling salesman problem." Thesis, Imperial College London, 1991. http://hdl.handle.net/10044/1/46875.
Full text
11
Itani, Sleiman M. "On the Stochastic Travelling Salesman problem for the Dubin's vehicle." Thesis, Massachusetts Institute of Technology, 2006. http://hdl.handle.net/1721.1/37932.
Full textAbstract:
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006.Includes bibliographical references (p. 53-56).
In this thesis, I solve the following problem: Given a rectangular region R in which n (n is large) targets are distributed according to some continuous or piece-wise continuous distribution, find the length of the optimal Stochastic Travelling Salesperson tour of a Dubin vehicle over the n targets and design an algorithm that performs within a. constant factor of the optimal expected tour length. We first solve the problem for the case when the distribution of the targets in uniform in R, and then generalize the results to any distribution. To solve the problem, we use an already known lower bound on the expected length of the optimal tour, and we design an algorithm that performs within a. constant factor of that lower bound. To create the constant factor algorithm, we first study the dynamic constraints on the Dubin vehicle to create a building block. and then solve an important auxiliary problem in which targets are not allowed to be too close to each other. After creating the algorithm for the uniform distribution scenario, we establish a lower bound for the scenario where the targets are sampled in R according to a continuous or a piece-wise continuous distribution. We finally generalize our algorithm to the non-uniform scenario and prove that it still performs within a constant factor of the lower bound we proved.
by Sleiman M. Itani.
S.M.
12
Höck, Barbar Katja. "An examination of heuristic algorithms for the travelling salesman problem." Master's thesis, University of Cape Town, 1988. http://hdl.handle.net/11427/22268.
Full textAbstract:
The role of heuristics in combinatorial optimization is discussed. Published heuristics for the Travelling Salesman Problem (TSP) were reviewed and morphological boxes were used to develop new heuristics for the TSP. New and published heuristics were programmed for symmetric TSPs where the triangle inequality holds, and were tested on micro computer. The best of the quickest heuristics was the furthest insertion heuristic, finding tours 3 to 9% above the best known solutions (2 minutes for 100 nodes). Better results were found by longer running heuristics, e.g. the cheapest angle heuristic (CCAO), 0-6% above best (80 minutes for 100 nodes). The savings heuristic found the best results overall, but took more than 2 hours to complete. Of the new heuristics, the MST path algorithm at times improved on the results of the furthest insertion heuristic while taking the same time as the CCAO. The study indicated that there is little likelihood of improving on present methods unless a fundamental new approach is discovered. Finally a case study using TSP heuristics to aid the planning of grid surveys was described.
13
DASTMARD, SOHOF. "The Asymmetric Travelling Salesman Problem : A Linear Programming Solution Approach." Thesis, KTH, Skolan för datavetenskap och kommunikation (CSC), 2014. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-157412.
Full textAbstract:
The travelling salesman problem is a well known optimization problem. The goal is to nd theshortest tour that visits each city in a given list exactly once. Despite the simple problem statementit belongs to the class of NP-complete problems. Its importance arises from a plethora of applicationsas well as a theoretical appeal. The asymmetric TSP is not as well researched as the symmetric TSP,in this paper we focus on a solution approach suitable for the asymmetric case. We demonstrate howa linear programming formulation can be used to solve the problem. We also show the limitationsof this solution approach and provide suggestions for improving it.i
14
Baltz, Andreas. "Algorithmic and probabilistic aspects of the bipartite traveling salesman problem." [S.l. : s.n.], 2001. http://e-diss.uni-kiel.de/diss]/d423.pdf.
Full text
15
Almulla, Mohammed Ali. "A class of greedy algorithms for solving the travelling salesman problem /." Thesis, McGill University, 1990. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=59557.
Full textAbstract:
The travelling salesman problem is one of the NP-complete problems. It has been under consideration in computer science for at least forty years. Solving this hard problem using search methods can be accomplished by choosing: a starting point, a solution generation scheme and a termination rule. When the termination rule is such that search stops if and only if the tour is optimal, we call the method "exact". When the termination rule is such that the search stops but not necessarily with an optimal tour, we call the method "approximate".This thesis looks closely at one of the approximate methods, namely sub-optimal tour building. In particular, it focuses on the nearest neighbour algorithm (a greedy algorithm). By being greedy at every step of the procedure, this algorithm returns an approximate solution that is near optimal in terms of solution cost. Next, this greedy algorithm is used in implementing a new algorithm that is called the "Multi-Degree Greedy Algorithm". By being greedy at half of the procedure steps, this algorithm returns optimal solutions to travelling salesman problems 99% of the time. Thus, this algorithm is an approximate algorithm, designed to run on small-scale travelling salesman problems (n $<$ 20).
16
Rohleder, Andreas. "Kandidatenmengen für das TSP : ein neuer heuristischer Ansatz /." Lohmar [u.a.] : Eul, 2006. http://deposit.d-nb.de/cgi-bin/dokserv?id=2837955&prov=M&dok_var=1&dok_ext=htm.
Full textAbstract:
Universiẗat, Diss., 2005 u.d.T.: Rohleder, Andreas: Ein Vorschlag zur Erzeugung von Kandidatenmengen zur Unterstützung der heuristischen Lösung des geometrischen zweidimensionalen Traveling Salesman Problems--Münster (Westfalen).
17
Rohleder, Andreas. "Kandidatenmengen für das TSP ein neuer heuristischer Ansatz." Lohmar Köln Eul, 2005. http://deposit.d-nb.de/cgi-bin/dokserv?id=2837955&prov=M&dok_var=1&dok_ext=htm.
Full textAbstract:
Zugl.: Münster (Westfalen), Univ., Diss., 2005 u.d.T.: Rohleder, Andreas: Ein Vorschlag zur Erzeugung von Kandidatenmengen zur Unterstützung der heuristischen Lösung des geometrischen zweidimensionalen Traveling Salesman Problems
18
Keuthen, Ralf. "Heuristic approaches for routing optimisation." Thesis, University of Nottingham, 2003. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.275960.
Full text
19
Desjardins, Nicholas. "On Applying Methods for Graph-TSP to Metric TSP." Thesis, Université d'Ottawa / University of Ottawa, 2016. http://hdl.handle.net/10393/35613.
Full textAbstract:
The Metric Travelling Salesman Problem, henceforth metric TSP, is a fundamental problem in combinatorial optimization which consists of finding a minimum cost Hamiltonian cycle (also called a TSP tour) in a weighted complete graph in which the costs are metric. Metric TSP is known to belong to a class of problems called NP-hard even in the special case of graph-TSP, where the metric costs are based on a given graph. Thus, it is highly unlikely that efficient methods exist for solving large instances of these problems exactly.
In this thesis, we develop a new heuristic for metric TSP based on extending ideas successfully used by Mömke and Svensson for the special case of graph-TSP to the more general case of metric TSP. We demonstrate the efficiency and usefulness of our heuristic through empirical testing.
Additionally, we turn our attention to graph-TSP. For this special case of metric TSP, there has been much recent progress with regards to improvements on the cost of the solutions. We find the exact value of the ratio between the cost of the optimal TSP tour and the cost of the optimal subtour linear programming relaxation for small instances of graph-TSP, which was previously unknown. We also provide a simplified algorithm for special graph-TSP instances based on the subtour linear programming relaxation.
20
Bullnheimer, Bernd, Gabriele Kotsis, and Christine Strauß. "Parallelization strategies for the ant system." SFB Adaptive Information Systems and Modelling in Economics and Management Science, WU Vienna University of Economics and Business, 1997. http://epub.wu.ac.at/1362/1/document.pdf.
Full textAbstract:
The Ant System is a new meta-heuristic method particularly appropriate to solve hard combinatorial optimization problems. It is a population-based, nature-inspired approach exploiting positive feedback as well as local information and has been applied successfully to a variety of combinatorial optimization problem classes. The Ant System consists of a set of cooperating agents (artificial ants) and a set of rules that determine the generation, update and usage of local and global information in order to find good solutions. As the structure of the Ant System highly suggests a parallel implementation of the algorithm, in this paper two parallelization strategies for an Ant System implementation are developed and evaluated: the synchronous parallel algorithm and the partially asynchronous parallel algorithm. Using the Traveling Salesman Problem a discrete event simulation is performed, and both strategies are evaluated on the criteria "speedup", "efficiency" and "efficacy". Finally further improvements for an advanced parallel implementation are discussed. (author's abstract)Series: Report Series SFB "Adaptive Information Systems and Modelling in Economics and Management Science"
21
Svensson, Erik R., and Klas Lagerqvist. "Evaluating pheromone intensities and 2-opt local search for the Ant System applied to the Dynamic Travelling Salesman Problem." Thesis, KTH, Skolan för datavetenskap och kommunikation (CSC), 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-209404.
Full textAbstract:
Ant Colony Optimization (ACO) algorithms have been successful in solving a wide variety of NPhard optimization problems. The Traveling Salesman Problem (TSP) has served as a benchmarking problem for many novel ACO algorithms. The slightly harder Dynamic Traveling Salesman Problem (DTSP) is more realistic in the sense that real-time changes happen in the graph belonging to a TSP instance. This thesis studied the original ACO algorithm: the Ant System, and how the amount of pheromone deposited by the ants within the algorithm affected the performance when solving both TSP and DTSP problems. Additionally, 2-opt local search was added to the algorithm, to see how it impacted the performance. We found that when the ants deposited a greater amount of pheromone, the performance for TSP increased, while the performance for DTSP decreased. We concluded that the Ant System in its original form is unsuitable for solving the DTSP. 2-opt local search improved the performance in all instances.Ant Colony Optimization-algoritmer (ACO) har visat sig vara bra på att lösa många olika NP-svåra optimeringsproblem. För att mäta prestandan för nya ACO-algoritmer har i många fall Handelsresandeproblemet (eng. TSP) använts. Den dynamiska varianten av TSP (eng. DTSP), är ett något svårare problem då förändringar i grafen kan ske i realtid. Denna uppsats utredde hur olika mängder feromon som avges av myrorna inuti algoritmen Ant System, påverkade prestandan för både TSPoch DTSP-instanser. Utöver detta studerades hur den lokala sökningsheuristiken 2-opt påverkade prestandan. Resultaten visade att om myrorna tilläts släppa mer feromoner, ökade prestantan för TSP, men minskade för DTSP. Därav drog vi slutsatsen att algoritmen Ant System i sin ursprungliga form ej är lämplig för att lösa DTSP. Den lokala söknigsheuristiken 2-opt förbättrade prestandan i alla tester.
22
Gunsel, H. Sinem. "Ammunition Transfer System Optimization Problem." Master's thesis, METU, 2012. http://etd.lib.metu.edu.tr/upload/12614166/index.pdf.
Full textAbstract:
Ammunition Transfer System (ATS) is the electro-mechanical system of the Ammunition Resupply Vehicle (ARV) which will be used to meet T-155 mm Firtina howitzers&rsquoammunition demand for tactical requirements of higher firing rate by off-road mobility and survivability. The transfer of ammunitions from ARV to Firtina is to be optimized for an effective improvement of firing rate. In this thesis the transferring order of carried ammunitions is being optimized to minimize the total ammunition transferring time. This transfer problem is modeled as a modification of Travelling Salesman Problem (TSP). The given locations of the ammunitions are treated as cities to be visited and the gripper of ATS is treated as the traveling salesman. By GAMS
the small-size problems are solved optimally but large-size ones get only local optimum. A heuristic algorithm that contains nearest neighbor heuristics as construction method and 2-opt exchange heuristic as improvement method is developed to obtain same or better solutions obtained by GAMS with less computational time.
23
Butavicius, Marcus A. "The perception of optimal path structure in random arrays : a connectionist approach to the travelling salesman problem and related tasks /." Title page, contents and introduction only, 1996. http://web4.library.adelaide.edu.au/theses/09AR.PS/09ar.psb983.pdf.
Full text
24
Škopek, Michal. "Problém obchodního cestujícího a metoda GENIUS." Master's thesis, Vysoká škola ekonomická v Praze, 2009. http://www.nusl.cz/ntk/nusl-76829.
Full textAbstract:
The target of this thesis is to explain the Travelling Salesman Problem and also create a special program, which will be able to make calculations using the heuristics GENIUS. The Travelling Salesman Problem will be described from two different points of view. The first one is the historical description of the idea of the Travelling Salesman Problem and later will be the problem will be described with some of the very wide number of the calculation methods. For the explanation of the methods, in the thesis there has been chosen some of the algorithms which belong to that methods. The heuristics and also the exact algorithms will be explained. The focus of this thesis is on the heuristics called GENIUS and also in the creation of the program which can calculate it. The program works first with the GENI algorithm and after that it works with US post-optimization algorithm. The program will be described from the point of view of the user and the manual will be written as well. The program will be tested on two different examples and will be compared with the exact algorithm.
25
Pavlovič, Dávid. "Problém obchodního cestujícího s časovými okny." Master's thesis, Vysoké učení technické v Brně. Fakulta strojního inženýrství, 2021. http://www.nusl.cz/ntk/nusl-442819.
Full textAbstract:
This thesis deals with the Travelling salesman problem with time windows. The problem is that the travelling salesman must pass through each defined location exactly once and finally return to the original place for the lowest possible price. The time windows in this problem are that each place can only be visited in a given time range, or it can happen that in a certain period of time there will be no path between some places. The thesis deals with an overview of this problem and problems similar to it. It also deals with the description of various methods by which this problem can be solved. As part of this thesis, an application in the Python programming language was also created, which is used to test selected methods for finding solutions. Finally, the given experiments are evaluated and the effectiveness of the given strategies is compared.
26
Farooq, Farhan. "Optimal Path Searching through Specified Routes using different Algorithms." Thesis, Högskolan Dalarna, Datateknik, 2009. http://urn.kb.se/resolve?urn=urn:nbn:se:du-4530.
Full textAbstract:
To connect different electrical, network and data devices with the minimum cost and shortest path, is a complex job. In huge buildings, where the devices are placed at different locations on different floors and only some specific routes are available to pass the cables and buses, the shortest path search becomes more complex. The aim of this thesis project is, to develop an application which indentifies the best path to connect all objects or devices by following the specific routes.To address the above issue we adopted three algorithms Greedy Algorithm, Simulated Annealing and Exhaustive search and analyzed their results. The given problem is similar to Travelling Salesman Problem. Exhaustive search is a best algorithm to solve this problem as it checks each and every possibility and give the accurate result but it is an impractical solution because of huge time consumption. If no. of objects increased from 12 it takes hours to search the shortest path. Simulated annealing is emerged with some promising results with lower time cost. As of probabilistic nature, Simulated annealing could be non optimal but it gives a near optimal solution in a reasonable duration. Greedy algorithm is not a good choice for this problem. So, simulated annealing is proved best algorithm for this problem. The project has been implemented in C-language which takes input and store output in an Excel Workbook
27
Mitas, Lukáš. "Využití matematických metod při plánování sítě obchodních zástupců." Master's thesis, Vysoká škola ekonomická v Praze, 2016. http://www.nusl.cz/ntk/nusl-262370.
Full textAbstract:
Companies from multiple branches use as one way to offer their products and services network of sales representatives. This thesis study mainly designing process of such network and process of planning day to day routes of sales representatives with focus on minimizing cost caused by their work. For designing such network set covering problem model and matching problem model were used. For planning sales representatives routes travelling salesman problem, multiple salesperson travelling salesman problem, vehicle routing problem, nearest neighbor heuristic and authors own solution were used. Usage of multicriterial decision making is briefly mentioned as tool for managing such network on examples of equipment selection. As demonstration on real case, data from Tata Global Beverages (Jemča) company were used.
28
Gentili, Mirco. "Modelli e Metodi per il Disegno di Aree di Tentata Vendita." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2019. http://amslaurea.unibo.it/19587/.
Full textAbstract:
L'elaborato tratta un problema tipico di molte aziende che hanno come l'obiettivo la tentata ventita, la consegna di prodotti a domicilio, il servizio porta a porta o altri servizi simili.
In generale vengono analizzati scenari composti da un certo numero di clienti ed un deposito, dal quale parte giornalmente una flotta di veicoli che si occupano della consegna della merce ai clienti. Il problema trattato è conosciuto in letteratura come VRP, e vengono presentati tre algoritmi euristici per ottenere una soluzione ammissibile. In particolare gli algoritmi si occupano del disegno di aree nelle quali sono suddivisi i clienti e la ricerca dei percorsi per soddisfare i servizi richiesti. Un ulteriore algoritmo euristico consente il miglioramento di una soluzione di partenza.
29
Krčmář, Pavel. "Optimalizace rozvozu piva na Jesenicku." Master's thesis, Vysoká škola ekonomická v Praze, 2012. http://www.nusl.cz/ntk/nusl-124608.
Full textAbstract:
The thesis deals with application of models of routing problems on a real problem, beer distribution in Jesenicko region provided by Viden plus, a.s. The goal of the thesis is to optimize daily distributional routes for two vehicles with different capacities. Total distance has to be minimized respecting time and capacity limits. In case the optimal solution is not found, sub-optimal solution will be accepted. Solutions are calculated with use of the optimization software LINGO and some heuristic methods. Models of travelling salesman problem and vehicle routing problem are used to find the solutions. Results are compared to the current state of distributional routes in conclusion of the thesis.
30
Jágerová, Tereza. "Analýza a optimalizace efektivnosti zemědělsko-dřevozpracujícího podniku (reálná situace)." Master's thesis, Vysoká škola ekonomická v Praze, 2008. http://www.nusl.cz/ntk/nusl-10013.
Full textAbstract:
This thesis aspires to optimize the processes in agriculture and wood-working company and to propose some changes if needed. At first, it is wood-working branch which is analyzed. The intent is to find an optimal route to distribute pallets and afterwards freight the vehicle by sawn wood and return back with. This is some modification of travelling salesman problem with more than one salesman and more centers including the condition that the travelling is dynamic in time and that only selected clients are visited. The agriculture problem is more complicated and complex because the model aims to find an optimal portfolio of diverse animal and vegetal production influenced by many factors and some of them are mentioned below. The agriculture model includes for example the stochastic character of weather and the condition that the herd of cattle should be stable.
31
Burdová, Jana. "Heuristické a metaheuristické metody řešení úlohy obchodního cestujícího." Master's thesis, Vysoká škola ekonomická v Praze, 2010. http://www.nusl.cz/ntk/nusl-75095.
Full textAbstract:
Minimal length of a travelling salesman's problem had been studied in this diploma these. Travelling salesman must come trough each place just once and then go back to the starting place. This problem can be illustrated as a problem of graph theory, such that places are the vertices, roads are the edges, distances of roads are the lengths of edges. The optimal travelling salesman's problem tour is the shortest Hamiltionian cycle in the graph. It is a classical NP-complete problem. There is no algorithm that solves this problem in polynomial time. This problem can be solved by using various approximation algorithms, they offer less time consumption and lowest quality than optimization. This diploma these had been dedicated to approximation algorithms, for example: nearest neighbor method, minimal spanning tree method, Christofide's method, 2-opt., genetic algorithm, etc.
32
Šimáně, Čestmír. "Optimalizace rozvozu léčiv ze skladu společnosti Movianto s.r.o." Master's thesis, Vysoká škola ekonomická v Praze, 2012. http://www.nusl.cz/ntk/nusl-197096.
Full textAbstract:
Nowadays, when great emphasis is put on cost savings, transport optimization is necessary part of every company life in which transportation costs produce significant part. There are optimization methods and possibilities presented in this thesis. In the first chapter there are explained methods such as the travelling salesman problem, the vehicle routing problem, the multiple vehicle routing problem and the split delivery vehicle routing problem and then the reader gets to know the heuristics methods in the chapter two where description of the nearest neighbour method, Clarke-Wright method and split delivery heuristic is mentioned. In the last but one chapter author applies previous methods on concrete distribution arranged by Movianto Česká republika s.r.o. on 5th September, 2013. Based on gained outputs, analysis and comparison of results (including the original distribution) are provided in the fourth chapter. Obtained results of analysis lead to recommendation on how the company should plan its future distribution.
33
Rexa, Denis. "Výpočetní úlohy pro řešení paralelního zpracování dat." Master's thesis, Vysoké učení technické v Brně. Fakulta elektrotechniky a komunikačních technologií, 2019. http://www.nusl.cz/ntk/nusl-400899.
Full textAbstract:
The goal of this diploma thesis was to create four laboratory exercises for the subject "Parallel Data Processing", where students will try on the options and capabilities of Apache Spark as a parallel computing platform. The work also includes basic setup and use of Apache Kafka technology and NoSQL Apache Cassandra database. The other two lab assignments focus on working with a Travelling Salesman Problem. The first lab was designed to demonstrate the difficulty of a task where the student will face an exponential increase in complexity. The second task consists of an optimization algorithm to solve the problem in cluster. This algorithm is subjected to performance measurements in clusters. The conclusion of the thesis contains recommendations for optimization as well as comparison of running with different number of computing devices.
34
Zahálka, Jaroslav. "Optimalizace pomocí algoritmů mravenčích kolonií." Master's thesis, Vysoká škola ekonomická v Praze, 2007. http://www.nusl.cz/ntk/nusl-4920.
Full textAbstract:
This diploma thesis deals with Ant Colony algorithms and their usage for solving Travelling Salesman Problems and Vehicle Routing Problems. These algorithms are metaheuristics offering new approach to solving NP-hard problems. Work begins with a description of the forementioned tasks including ways to tackle them. Next chapter analyses Ant Colony metaheuristic and its possible usage and variations. The most important part of the thesis is practical and is represented by application Ant Colony Optimization Framework. It is easily extensible application written in Java that is able to solve introduced problems. In conclusion this work presents analysis of solutions on test data.
35
Němec, Jan. "Efektivita evolučních algoritmů." Master's thesis, Vysoké učení technické v Brně. Fakulta elektrotechniky a komunikačních technologií, 2016. http://www.nusl.cz/ntk/nusl-242045.
Full textAbstract:
This master's thesis is focused on evolutionary algorithms. The goal of this thesis is to chooche a proper algorithm which will solve a chosen problem. In this case the chosen algorithm is the genetic algorithm and the chosen problem is the travelling salesman problem. The result of this thesis will be implementation of the algorithm, finding the proper setup and lastly the measurment of the results for various input data.
36
Hájek, Jan. "Využití grafických procesorů v úlohách celočíselného programování." Master's thesis, Vysoká škola ekonomická v Praze, 2010. http://www.nusl.cz/ntk/nusl-81881.
Full textAbstract:
A very wide-ranging subgroup of vehicle routing problems from the graph theory is a common and frequent problem handled daily by transport companies, airline businesses, hi-tech companies with planning drilling of printed circuits boards or other companies from different industries. During numerous previous researches of these problems a lot of analyses were made and many solutions proposed -- of which an outline is in this paper. Some of them giving better or worse results in longer or shorter computing time. In spite of the fact that the processors and new technologies performance is increasing, with some algorithms we cannon compute the result in a reasonable time. That is why this paper is asking a question, if there can be found a fitting algorithm which could be applied on different and faster processing unit structures so it could be ensured a multiple computing speed increase so far. The analysis was carried out using computer experiments on a new build and implemented branch and bound algorithm with a matrix rate reduction.
37
Rossi, Pier Cesare. "A Liner Shipping Speed Optimization Model to Reduce Bunker Cost and Pollutants Emitted." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2017. http://amslaurea.unibo.it/14476/.
Full textAbstract:
Environmental impact has become one of the most relevant issues in liner shipping during the
recent years. Maritime shipping is responsible for the 2.7 per cent of the world CO2 emissions,
of which 25 per cent is attributable to container ships. This business also produces a significant
quantity of sulphur, a very dangerous substance for human health, especially if it is emitted in
areas next to the coast. At the same time, bunker cost represents the biggest portion of the
operational cost of a shipping company. Slow steaming is a cheap and effective strategy from both
save pollutants emissions and bunker cost. Moreover, it can be immediately put into practice. This
report introduces a Mixed Integer Programming Model to solve the Liner Shipping Routing and
Speed Optimization Problem (LSRSOP). The final goal is to find the best route and to optimize
the the sailing speed of the vessel considering the Emission Control Areas and maximum transit
times between ports. Two Heuristic Methods -the 2-Steps Method and the Simulated Annealingare
proposed to solve big instances that would require too much running time to be solved until
optimality. Both of them use a Hill-Climbing Algorithm that generates a slight different route from
a given one. A Bi-Objective Function Model has been designed for instances whose the optimal
solution can be found in reasonable time. It considers the operative cost of the vessel and the
external cost of emissions. The results show efficient solutions that are the "golden line" between
the most convenient solution for the company and the most sustainable solution.
38
Eimontienė, Ieva. "Iteratyvioji tabu paieška ir jos modifikacijos komivojažieriaus uždaviniui." Master's thesis, Lithuanian Academic Libraries Network (LABT), 2007. http://vddb.library.lt/obj/LT-eLABa-0001:E.02~2007~D_20070816_142700-63591.
Full textAbstract:
Šiame darbe nagrinėjamas patobulintas tabu paieškos metodas, žinomas kaip iteratyvioji tabu paieška (ITP). Pasiūlytos kai kurios ITP metodo modifikacijos, besiremiančios tam tikromis sprendinių mutavimo (pertvarkymo) procedūromis (inversijos, įterpimai ir kt.), kurios įgalina pagerinti gaunamų sprendinių kokybę. Atlikti išsamūs sudaryto ITP algoritmo ir kitų pasiūlytų modifikacijų eksperimentiniai tyrimai, panaudojant testinius KU pavyzdžius iš KU testinių pavyzdžių bibliotekos TSPLIB. Gauti rezultatai patvirtina pasiūlytų modifikacijų pranašumą kitų ITP variantų atžvilgiu.In this work, one of the heuristic algorithm – the iterated tabu search and its modifications are discussed. The work is organized as follows. Firstly, some basic definitions and preliminaries are given. Then, the iterated tabu search algoritm and its variants based on special type mutations are considered in more details. The ITS algorithms modifications were tested on the TSP instances from the TSP library TSPLIB. The results of this tests (experiments) are presented as well. The work is completed with the conclusions.
39
Wååg, Håkan. "Development of a Framework for Genetic Algorithms." Thesis, Jönköping University, JTH, Computer and Electrical Engineering, 2009. http://urn.kb.se/resolve?urn=urn:nbn:se:hj:diva-11537.
Full textAbstract:
Genetic algorithms is a method of optimization that can be used tosolve many different kinds of problems. This thesis focuses ondeveloping a framework for genetic algorithms that is capable ofsolving at least the two problems explored in the work. Otherproblems are supported by allowing user-made extensions.The purpose of this thesis is to explore the possibilities of geneticalgorithms for optimization problems and artificial intelligenceapplications.To test the framework two applications are developed that look attwo distinct problems, both of which aim at demonstrating differentparts. The first problem is the so called Travelling SalesmanProblem. The second problem is a kind of artificial life simulator,where two groups of creatures, designated predator and prey, aretrying to survive.The application for the Travelling Salesman Problem measures theperformance of the framework by solving such problems usingdifferent settings. The creature simulator on the other hand is apractical application of a different aspect of the framework, wherethe results are compared against predefined data. The purpose is tosee whether the framework can be used to create useful data forthe creatures.The work showed how important a detailed design is. When thework began on the demonstration applications, things were noticedthat needed changing inside the framework. This led to redesigningparts of the framework to support the missing details. A conclusionfrom this is that being more thorough in the planning, andconsidering the possible use cases could have helped avoid thissituation.The results from the simulations showed that the framework iscapable of solving the specified problems, but the performance isnot the best. The framework can be used to solve arbitrary problemsby user-created extensions quite easily.
40
Kämpf, Michael. "Probleme der Tourenbildung." Universitätsbibliothek Chemnitz, 2006. http://nbn-resolving.de/urn:nbn:de:swb:ch1-200601999.
Full textAbstract:
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.
41
Raffa, Viviana. "Riorganizzazione di rotte prestabilite in base ad aree per la Distribuzione Urbana di Merci: algoritmo ed applicazione mobile." Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2018. http://amslaurea.unibo.it/17306/.
Full textAbstract:
Sempre più città decidono di adottare politiche di governance legate al concetto di Smart City. Con un crescente aumento della popolazione nelle zone urbane e delle infrastrutture, la Smart City consente di gestire e migliorare la qualità della vita sia del singolo cittadino sia dell’intera comunità. Uno degli assi portanti di questa realtà, è quello della Smart Mobility grazie alla quale si offrono ai cittadini soluzioni per muoversi sempre più efficienti e intelligenti, grazie al settore fortemente competitivo ed in espansione.
La seguente tesi propone un algoritmo che, dato un itinerario di punti a cui un corriere deve consegnare delle merci nella città di Barcellona, restituisce l’elenco delle aree DUM (Distribuzione Urbana di Merci) in cui viene consigliato di parcheggiare in base alla vicinanza di ciascuna zona di parcheggio ai punti dell’itinerario. L’algoritmo sfrutta il database a grafo Sparksee organizzato come un albero Red-Black.
Viene poi descritta la realizzazione di un prototipo di applicazione mobile Android che implementa tale proposta, con lo scopo di fungere da integrazione alle applicazioni per il routing già esistenti.
Con questo progetto di tesi si è quindi dimostrato che può essere creato un applicativo in grado di supportare i corrieri di merci nel loro lavoro quotidiano fornendo un'alternativa, basata sulle zone di parcheggio, al tradizionale percorso assegnatogli.
42
Amenabar, Leire, and Leire Carreras. "Augmented Reality Framework for Supporting and Monitoring Operators during Maintenance Operations in Industrial Environments." Thesis, Högskolan i Skövde, Institutionen för ingenjörsvetenskap, 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:his:diva-15717.
Full textAbstract:
In an ever-changing and demanding world where short assembly and innovation times are indispensable, it is of paramount importance to ensure that the machinery used throughout the whole process of a product are in their best possible condition. This guarantees that the performance of each machine will be optimal, and hence, the process times will be the shortest possible, while the best quality products are obtained. Moreover, having a machine in an impeccable status permits making the necessary changes to it, in order to fulfil the requirements that a more advanced or complex product may have. Maintenance operations and their corresponding trainings have historically been time-consuming, and a vast amount of information has been transmitted from an expert to a newer operator. This means that there has been the need of working with experienced operators to secure that a good service is provided. However, different technologies like augmented reality (AR) have been shown to have a positive impact in the support and monitoring of operators in industrial maintenance operations.The present project gathers information in regard to the framework of AR, with the aim of supporting and monitoring operators in industrial environments. The proposed method consists on the development of an artefact, which would lead to a possible improvement of the already existing solutions. It is believed that the development of an AR application could grant the necessary aid to any operator in maintenance operations. The result of this suggestion is an AR application which superimposes visual information on the physical equipment.
43
Hanskov, Palm Jakob. "Route Planning and Design of Autonomous Underwater Mine Reconnaissance Through Multi-Vehicle Cooperation." Thesis, Linköpings universitet, Fordonssystem, 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-172015.
Full textAbstract:
Autonomous underwater vehicles have become a popular countermeasure to naval mines. Saab’s AUV62-MR detects, locates and identifies mine-like objects through three phases. By extracting functionality from the AUV62-MR and placing it on a second vehicle, it is suggested that the second and third phases can be performed in parallel. This thesis investigates how to design the second vehicle so that the runtime of the mine reconnaissance process is minimized. A simulation framework is implemented to simulate the second and third phases of the mine reconnaissance process in order to test various design choices. The vehicle design choices in focus are the size and the route planning of the second vehicle. The route-planning algorithms investigated in this thesis are a nearest neighbour algorithm, a simulated annealing algorithm, an alternating algorithm, a genetic algorithm and a proposed Dubins simulated annealing algorithm. The algorithms are evaluated both in a static environment and in the simulation framework. Two different vehicle sizes are investigated, a small and a large, by evaluating their performances in the simulation framework. This thesis takes into account the limited travelling distance of the vehicle and implements a k-means clustering algorithm to help the route planner determine which mine-like objects can be scanned without exceeding the distance limit. The simulation framework is also used to evaluate whether parallel execution of the second and third phases outperforms the current sequential execution. The performance evaluation shows that a major reduction in runtime can be gained by performing the two phases in parallel. The Dubins simulated annealing algorithm on average produces the shortest paths and is considered the preferred route-planning algorithm according to the performance evaluation. It also indicates that a small vehicle size results in a reduced runtime compared to a larger vehicle.
44
Lima, J?nior Francisco Chagas de. "Algoritmo Q-learning como estrat?gia de explora??o e/ou explota??o para metaheur?sticas GRASP e algoritmo gen?tico." Universidade Federal do Rio Grande do Norte, 2009. http://repositorio.ufrn.br:8080/jspui/handle/123456789/15129.
Full textAbstract:
Made available in DSpace on 2014-12-17T14:54:52Z (GMT). No. of bitstreams: 1
FranciscoCLJ.pdf: 1181019 bytes, checksum: b3894e0c93f85d3cf920c7015daef964 (MD5)
Previous issue date: 2009-03-20Techniques of optimization known as metaheuristics have achieved success in the resolution of many problems classified as NP-Hard. These methods use non deterministic approaches that reach very good solutions which, however, don t guarantee the determination of the global optimum. Beyond the inherent difficulties related to the complexity that characterizes the optimization problems, the metaheuristics still face the dilemma of xploration/exploitation, which consists of choosing between a greedy search and a wider exploration of the solution space. A way to guide such algorithms during the searching of better solutions is supplying them with more knowledge of the problem through the use of a intelligent agent, able to recognize promising regions and also identify when they should diversify the direction of the search. This way, this work proposes the use of Reinforcement Learning technique - Q-learning Algorithm - as exploration/exploitation strategy for the metaheuristics GRASP (Greedy Randomized Adaptive Search Procedure) and Genetic Algorithm. The GRASP metaheuristic uses Q-learning instead of the traditional greedy-random algorithm in the construction phase. This replacement has the purpose of improving the quality of the initial solutions that are used in the local search phase of the GRASP, and also provides for the metaheuristic an adaptive memory mechanism that allows the reuse of good previous decisions and also avoids the repetition of bad decisions. In the Genetic Algorithm, the Q-learning algorithm was used to generate an initial population of high fitness, and after a determined number of generations, where the rate of diversity of the population is less than a certain limit L, it also was applied to supply one of the parents to be used in the genetic crossover operator. Another significant change in the hybrid genetic algorithm is the proposal of a mutually interactive cooperation process between the genetic operators and the Q-learning algorithm. In this interactive/cooperative process, the Q-learning algorithm receives an additional update in the matrix of Q-values based on the current best solution of the Genetic Algorithm. The computational experiments presented in this thesis compares the results obtained with the implementation of traditional versions of GRASP metaheuristic and Genetic Algorithm, with those obtained using the proposed hybrid methods. Both algorithms had been applied successfully to the symmetrical Traveling Salesman Problem, which was modeled as a Markov decision process
T?cnicas de otimiza??o conhecidas como metaheur?sticas t?m obtido sucesso na resolu??o de problemas classificados como NP - ?rduos. Estes m?todos utilizam abordagens n?o determin?sticas que geram solu??es pr?ximas do ?timo sem, no entanto, garantir a determina??o do ?timo global. Al?m das dificuldades inerentes ? complexidade que caracteriza os problemas NP-?rduos, as metaheur?sticas enfrentam ainda o dilema de explora??o/explota??o, que consiste em escolher entre intensifica??o da busca em uma regi?o espec?fica e a explora??o mais ampla do espa?o de solu??es. Uma forma de orientar tais algoritmos em busca de melhores solu??es ? supri-los de maior conhecimento do problema atrav?s da utiliza??o de um agente inteligente, capaz de reconhecer regi?es promissoras e/ou identificar em que momento dever? diversificar a dire??o de busca, isto pode ser feito atrav?s da aplica??o de Aprendizagem por Refor?o. Neste contexto, este trabalho prop?e o uso de uma t?cnica de Aprendizagem por Refor?o - especificamente o Algoritmo Q-learning - como uma estrat?gia de explora??o/explota??o para as metaheur?sticas GRASP (Greedy Randomized Adaptive Search Procedure) e Algoritmo Gen?tico. Na implementa??o da metaheur?stica GRASP proposta, utilizou-se o Q-learning em substitui??o ao algoritmo guloso-aleat?rio tradicionalmente usado na fase de constru??o. Tal substitui??o teve como objetivo melhorar a qualidade das solu??es iniciais que ser?o utilizadas na fase de busca local do GRASP, e, ao mesmo tempo, suprir esta metaheur?sticas de um mecanismo de mem?ria adaptativa que permita a reutiliza??o de boas decis?es tomadas em itera??es passadas e que evite a repeti??o de decis?es n?o promissoras. No Algoritmo Gen?tico, o algoritmo Q-learning foi utilizado para gerar uma popula??o inicial de alta aptid?o, e ap?s um determinado n?mero de gera??es, caso a taxa de diversidade da popula??o seja menor do que um determinado limite L, ele ? tamb?m utilizado em uma forma alternativa de operador de cruzamento. Outra modifica??o importante no algoritmo gen?tico h?brido ? a proposta de um processo de intera??o mutuamente cooperativa entre o os operadores gen?ticos e o Algoritmo Q-learning. Neste processo interativo/cooperativo o algoritmo Q-learning recebe uma atualiza??o adicional na matriz dos Q-valores com base na solu??o elite da popula??o corrente. Os experimentos computacionais apresentados neste trabalho consistem em comparar os resultados obtidos com a implementa??o de vers?es tradicionais das metaheur?sticas citadas, com aqueles obtidos utilizando os m?todos h?bridos propostos. Ambos os algoritmos foram aplicados com sucesso ao problema do caixeiro viajante sim?trico, que por sua vez, foi modelado como um processo de decis?o de Markov
45
Andersson, Åsa, and Abdiqafar Ismail. "Ruttoptimering : En jämförelse mellan mänsklig erfarenhet och optimeringsprogram." Thesis, Mittuniversitetet, Avdelningen för informationssystem och -teknologi, 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:miun:diva-30846.
Full textAbstract:
Route optimization aims to optimize routes for vehicles withregards to resource usage. Especially when the vehicle needsto visit multiple customers on the route, a route optimizationtool is beneficiary. The purpose of this study is to comparehuman experience with a route optimization program. This isdone by comparing how a truck driver makes his routes to theroute a GIS-tool has calculated and then see which of theroutes was shorter, measured in kilometers. The data for thisstudy was gathered from a big shipping company. In order toachieve the purpose of this study 10 routes were analysed bya GIS program called ArcGIS. The algorithm used by ArcGISin route optimization is tabu search, this type of program wasused because it is based on heuristic methods that is muchfaster than exact methods. Expert systems are based onknowledge from experts that have been accumulated duringmany years of experience. Providing recommendations basedon probability reasoning instead of absolute answer. Thesekind of systems is often used in GIS programs to improveresults and calculation time. The aim of this study wasanalyze if a optimization program finds a better route than theexpert. This study shows an improvement of 60% of theanalyzed routes. To verify the results of this study anhypothesis test was made which gave a level of significanceby more than 85 %. The routes were optimized to a certainextent even before the study was done due to the driveralready being familiar with the routes in question. Because ofthis the results of this study were lower compared to othersimilar studies. Another reason may be that the coordinatesgiven to us did not always correspond perfectly with actuallocation of the stops.Ruttoptimering avser att optimera rutter för fordon medminsta möjliga resursåtgång. När fordonet ska besöka ettflertal givna platser är ett ruttoptimeringsverktyg förmånligtatt använda. Denna studie syftar till att jämföra den mänskligaerfarenheten mot ett ruttoptimeringsprogram. Detta har gjortsgenom att jämföra hur en lastbilschaufför har kört en rutt mothur ett GIS-verktyg räknat fram den optimerade färdvägen avsamma rutt. Sedan jämfördes om det fanns skillnader ochvilken av rutterna som var kortast, räknat i kilometer. Datahar hämtats från ett stort fraktföretag. För att nå syftet har 10rutter undersökts i programmet ArcGIS Online som använderalgoritmen tabusökning. En kommersiell beräkningsmetodhar använts då det bygger på heuristiska metoder som ärbetydligt snabbare än exakta metoder. Expertsystem byggerpå erfarenhet som experter har samlat på sig genom åren, deger rekommendationer baserade på sannolikhetsresonemangistället för definitiva svar, dessa system sätts ofta in i GIS för att förbättra resultat och beräkningstider i systemen. Studienresulterade i en förbättring på 60 % av rutterna. Målet meddenna undersökning var att visa om ett optimeringsprogramhittar en bättre rutt än experten. För att verifiera resultaten istudien gjordes en hypotesprövning vilket gav ensignifikansnivå på över 85%. Chauffören har kört dessa rutteri flera år vilket gör att rutterna är optimerade i en viss månredan innan studien gjordes. Det har inverkat på resultatetsom gett ett lågt medelvärde av den procentuella skillnaden,jämfört med tidigare undersökningar. En annan faktor kanvara att koordinaterna i datan från företaget inte helt stämdemed den verkliga placeringen av stoppen på rutterna.
46
Fontes, F?bio Francisco da Costa. "Algoritmo mem?tico com infec??o viral: uma aplica??o ao problema do caixeiro viajante assim?trico." Universidade Federal do Rio Grande do Norte, 2006. http://repositorio.ufrn.br:8080/jspui/handle/123456789/15107.
Full textAbstract:
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-19The 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
47
Silva, Neto Jo?o Saturnino da. "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?trico." Universidade Federal do Rio Grande do Norte, 2009. http://repositorio.ufrn.br:8080/jspui/handle/123456789/17005.
Full textAbstract:
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-10The 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
48
Miček, David. "Genetické algoritmy." Master's thesis, Vysoké učení technické v Brně. Fakulta elektrotechniky a komunikačních technologií, 2009. http://www.nusl.cz/ntk/nusl-218215.
Full textAbstract:
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.
49
Hula, Tomáš. "Experimenty s rojovou inteligencí (swarm intelligence)." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2008. http://www.nusl.cz/ntk/nusl-235936.
Full textAbstract:
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.
50
Sahuc, Cyril. "Approches mathématiques pour l’aménagement de zones commerciales : modèles linéaires, algorythmes et systèmes multi-agents." Thesis, Avignon, 2020. http://www.theses.fr/2020AVIG0276.
Full textAbstract:
Les zones commerciales sont depuis plusieurs dizaines d'années en constante expansion, souvent au coup par coup sans plan d'ensemble prédéfini. Les opérateurs s'installent au gré des opportunités foncières en sur-dimensionnant, en général, les zones de stationnement dont ils ont besoin. Cette absence de plan global entraîne une raréfaction des sols. Nous proposons plusieurs modèles mathématiques d'aide à la décision permettant de gérer de façon globale ces zones commerciales. Ils permettent d'agir sur des leviers de décision comme la taille et la localisation des parkings ainsi que la localisation des commerces. Ils sont résolus par programmation linéaire directe, par des schémas heuristiques, ainsi qu'à l'aide de procédés de simplifications. Les modèles sont couplés avec le simulateur multi-agent MatSim, permettant ainsi de prendre en compte les phénomènes de congestion. Plusieurs expérimentations numériques sur des instances générées aléatoirement sont données et commentéesCommercial zones have been constantly expanding for decades, often without a predefined plan. Operators settle according to land opportunities by generally oversizing the parking areas they need. This lack of a comprehensive plan leads to soil scarcity. We offer mathematical models for decision-making that allow global management of these commercial areas. These allow us to act on decision levers such as the size and location of car parks and the location of shops. We solve these models by direct linear programming, by heuristic schemes, and with simplification processes. Models are coupled with the MatSim multi-agent simulator, thus making it possible to take into account congestion phenomena. Several numerical experiments by randomly generated instances are given and commented on