La 1ere partie de ce travail traite l'optimisation des tournées sous forme d'un problème d'optimisation nommé Le problème de Voyageur de Commerce. Dans cette partie nous nous intéressons à faire une riche présentation du problème de Voyageur de Commerce, ses variantes, puis nous proposons une stratégie de génération de contrainte pour la résolution du TSP. Ensuite on traite sa version stochastique : le problème de Voyageur de commerce Probabiliste. Nous proposons une formulation mathématique du PTSP et nous présentons des résultats numériques obtenus par résolution exacte pour une série d'instances de petite taille. Dans la seconde partie, nous proposons une méthode d'approximation générale permettant d'approcher différents type de données, d'abord nous traitons l'approximation d'un signal de vent (cas simple, ID), ensuite l'approximation d'un champ de vecteurs avec prise en compte de la topographie qui constitue la principale contribution de cette partie. / The first part of this work deals with route optimization in the form of an optimization problem named The Traveler's Business Problem. In this part we are interested to make a rich presentation of the problem of Traveler Commerce, its variants, then we propose a strategy of constraint generation for the resolution of the TSP. Then we treat its stochastic version : the probabilistic business traveler problem. We propose a mathematical formulation of the PTSP and we present numerical results obtained by exact resolution for a series of small instances. In the second part, we propose a method of general approximation to approximate different type of data, first we treat the approximation of a wind signal (simple case, 1D), then the approximation of a vector field taking into account the topography which is the main contribution of this part.

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.

This thesis addresses the problem of setting up a surface mount placement machine for production. The objective is to minimize the number of machine changeovers made during a production run consisting of a number of circuit cards. The solution to the problem involves two separate decisions. The first decision considers determining how to combine feeders together in "bays" or groups of feeders, and how to assign the bays to the circuit cards. The second decision considers the circuit card production sequence. A mathematical programming formulation is given, however, its solution is very difficult for problems of a realistic size. Several heuristic approaches are suggested and used to solve actual and test problems. The heuristic for bay design uses clustering techniques used in Group Technology while the sequencing problem is solved using heuristics based on solution techniques for the Traveling Salesman problem.

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.

Digitized by Kansas Correctional Industries

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.

In this research, we investigate and propose new operators to improve Genetic Algorithm’s performance to solve the multi-stop routing problem. In a multi-stop route, a user starts at point x, visits all destinations exactly once, and then return to the same starting point. In this thesis, we are interested in two types of this problem. The first type is when the distance among destinations is fixed. In this case, it is called static traveling salesman problem. The second type is when the cost among destinations is affected by traffic congestion. Thus, the time among destinations changes during the day. In this case, it is called time-dependent traveling salesman problem. This research proposes new improvements on genetic algorithm to solve each of these two optimization problems. First, the Travelling Salesman Problem (TSP) is one of the most important and attractive combinatorial optimization problems. There are many meta-heuristic algorithms that can solve this problem. In this paper, we use a Genetic Algorithm (GA) to solve it. GA uses different operators: selection, crossover, and mutation. Sequential Constructive Crossover (SCX) and Bidirectional Circular Constructive Crossover (BCSCX) are efficient to solve TSP. Here, we propose a modification to these crossovers. The experimental results show that our proposed adjustment is superior to SCX and BCSCX as well as to other conventional crossovers (e.g. Order Crossover (OX), Cycle Crossover (CX), and Partially Mapped Crossover (PMX)) in term of solution quality and convergence speed. Furthermore, the GA solver, that is improved by applying inexpensive local search operators, can produce solutions that have much better quality within reasonable computational time. Second, the Time-Dependent Traveling Salesman Problem (TDTSP) is an interesting problem and has an impact on real-life applications such as a delivery system. In this problem, time among destinations fluctuates during the day due to traffic, weather, accidents, or other events. Thus, it is important to recommend a tour that can save driver’s time and resources. In this research, we propose a Multi-Population Genetic Algorithm (MGA) where each population has different crossovers. We compare the proposed MG against Single-Population Genetic Algorithm (SGA) in terms of tour time solution quality. Our finding is that MGA outperforms SGA. Our method is tested against real-world traffic data [1] where there are 200 different instances with different numbers of destinations. For all tested instances, MGA is superior on average by at least 10% (for instances with size less than 50) and 20% (for instances of size 50) better tour time solution compared to SGA with OX and SGA with PMX operators, and at least 4% better tour time compared toga with SCX operator.

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.

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.

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