Objective of this thesis is optimalization of route for inspectory technician. There were described traveling Salesman problem, vehicle Routing problem and it's modifications. Problem was solved by this three heuristics: nearest neighbour algorithm, savings method and insert method.

Nous nous intéressons dans cette thèse aux possibilités d’hybridation entre les méthodes exactes et les méthodes heuristiques afin de pouvoir tirer avantage de chacune des deux approches : optimalité de la résolution exacte, caractère moins déterministe et rapidité de la composante heuristique. Dans l’objectif de résoudre des problèmes NPdifficiles de taille relativement importante tels que les problèmes de transports, nous nous intéressons dans les deux dernières parties de ce mémoire à la conception de méthodes incomplètes basées sur ces hybridations. Dans la première partie, nous allons nous intéresser aux méthodes de résolution par recherche arborescente. Nous introduisons une nouvelle approche pour la gestion des décisions de branchement, que nous appelons Dynamic Learning Search (DLS). Cette méthode définit de manière dynamique des règles de priorité pour la sélection des variables à chaque noeud et l’ordre des valeurs sur lesquelles brancher. Ces règles sont conçues dans une optique de généricité, de manière à pouvoir utiliser la méthode indépendamment du problème traité. Le principe général est de tenir compte par une technique d’apprentissage de l’impact qu’ont eu les décisions de branchement dans les parties déjà explorées de l’arbre. Nous évaluons l’efficacité de la méthode proposée sur deux problèmes classiques : un problème d’optimisation combinatoire et un problème à satisfaction de contraintes. La deuxième partie de ce mémoire traite des recherches à grand voisinage. Nous présentons un nouvel opérateur de voisinage, qui détermine par un algorithme de programmation dynamique la sous-séquence optimale d’un chemin dans un graphe. Nous montrons que cet opérateur est tout particulièrement destiné à des problèmes de tournées pour lesquels tous les noeuds ne nécessitent pas d’être visités. Nous appelons cette classe de problème les Problèmes de Tournées avec Couverture Partielle et présentons quelques problèmes faisant partie de cette classe. Les chapitres 3 et 4 montrent, à travers des tests expérimentaux conséquents, l’efficacité de l’opérateur que nous proposons en appliquant cette recherche à voisinage large sur deux problèmes, respectivement le Problème de l’Acheteur Itinérant (TPP) et le Problème de Voyageur de Commerce Généralisé (GTSP). Nous montrons alors que cet opérateur peut être combiné de manière efficace avec des métaheuristiques classiques, telles que des algorithmes génétiques ou des algorithmes d’Optimisation par Colonies de Fourmis. Enfin, la troisième partie présente des méthodes heuristiques basées sur un algorithme de Génération de Colonnes. Ces méthodes sont appliquées sur un problème complexe : le problème de Tournées de Véhicules avec Contraintes de Chargement à Deux Dimensions (2L-VRP). Nous montrons une partie des possibilités qu’il existe afin de modifier une méthode a priori exacte en une méthode heuristique et nous évaluons ces possibilités à l’aide de tests expérimentaux / We are interested in this thesis in the possibilities of hybridization between the exact methods and the methods heuristics to be able to take advantage of each of both approaches: optimality of the exact resolution, the less determinist character and the speed of the constituent heuristics. In the objective to resolve problems NP-hard of relatively important size such as the transportation problems, we are interested in the last two parts of this report in the conception of incomplete methods based on these hybridizations. In the first part, we are going to be interested in the methods of resolution by tree search. We introduce a new approach for the management of the decisions of connection, which we call Dynamic Learning Search ( DLS). This method defines in a dynamic way rules of priority for the selection of variables in every knot and the order of the values on which to connect. These rules are conceived in an optics of genericity, so as to be able to use the method independently of the treated problem. The general principle is to take into account by a technique of learning of the impact which had the decisions of connection in the parts already investigated in the tree. We estimate the efficiency of the method proposed on two classic problems: a combinatorial optimization problem and a constraints satisfaction problem. The second part of this report handles large neighborhood search. We present a new operator of neighborhood, who determines by an algorithm of dynamic programming the optimal sub-sequence of a road in a graph. We show that this operator is quite particularly intended for problems of tours for which all the vertices do not require to be visited. We call this class of problem the Problems of Tours with Partial Cover and present some problems being a part of this class. Chapters 3 and 4 show, through consequent experimental tests, the efficiency of the operator which we propose by applying this search to wide neighborhood on two problems, respectively the Traveling Purchaser Problem (TPP) and Generalized Traveling Salesman Problem ( GTSP). We show while this operator can be combined in a effective way with classic metaheuristics, such as genetic algorithms or algorithms of Ant Colony Optimization

Orientador: Pedro José Catuogno / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-26T10:58:39Z (GMT). No. of bitstreams: 1 Fonte_CarlaCristina_M.pdf: 29679078 bytes, checksum: 0009a52938b1cb16c79bdc47af10d323 (MD5) Previous issue date: 2014 / Resumo: Neste trabalho, exploram-se os conceitos iniciais e aplicações importantes da teoria de grafos. Acentuam-se, nas aplicações, alguns problemas clássicos, como o das sete pontes de Königsberg, o do caixeiro viajante e o problema dos casamentos estáveis. Com o intuito de servir como material de apoio para a introdução de grafos ao ensino médio, expõe-se uma sugestão para plano de aula, cuja exploração sinaliza diversas propriedades matemáticas interessantes, além de estimular o raciocínio e o estudo / Abstract: This work focuses on the initial concepts and important applications of the graph theory. Detailing, in the applications, some classic problems such as the seven bridges of Königsberg problem, the travelling salesman problem and the stable marriage problem. In order to provide a supporting material for the introduction to graphs in high school, it is shown a suggestion to the lesson plan, which exploration indicates various interesting mathematical properties beyond stimulating the reasoning and the deep study in the field / Mestrado / Matemática em Rede Nacional / Mestra em Matemática em Rede Nacional

O problema do caixeiro viajante (PCV) é um problema clássico de otimização que possui diversas variações, aplicações e instâncias. Encontrar a solução ótima para muitas instâncias desse problema é geralmente muito difícil devido o alto custo computacional. Vários métodos de otimização, conhecidos como meta-heurísticas (MHs), são capazes de encontrar boas soluções para o PCV. Muitos algoritmos baseados em diversas MHs têm sido propostos e investigados para diferentes variações do PCV. Como não existe um algoritmo universal que encontre a melhor solução para todas as instâncias de um problema, diferentes MHs podem prover a melhor solução para diferentes instâncias do PCV. Desse modo, a seleção a priori da MH que produza a melhor solução para uma dada instância é uma tarefa difícil. A pesquisa desenvolvida nesta tese investiga o uso de abordagens de meta-aprendizado para selecionar as MHs mais promissoras para novas instâncias de PCV. Essas abordagens induzem meta-modelos preditivos a partir do treinamento das técnicas de aprendizado de máquina em um conjunto de meta-dados. Cada meta-exemplo, em nosso conjunto de meta-dados, representa uma instância de PCV descrita por características (meta-atributos) do PCV e pelo desempenho das MHs (meta-atributo alvo) para essa instância. Os meta-modelos induzidos são usados para indicar os valores do meta-atributo alvo para novas instâncias do PCV. Vários experimentos foram realizados durante a investigação desta pesquisa e resultados importantes foram obtidos / The traveling salesman problem (TSP) is a classical optimization problem that has several variations, applications and instances. To find the optimal solution for many instances of this problem is usually a very hard task due to high computational cost. Various optimization methods, known as metaheuristics (MHs), are capable to generate good solutions for the TSP. Many algorithms based on different MHs have been proposed and investigated for different variations of the TSP. Different MHs can provide the best optimization solution for different TSP instances, since there is no a universal algorithm able to find the best solution for all instances. Thus, a priori selection of the MH that produces the best solution for a given instance is a hard task. The research developed in this thesis investigates the use of meta-learning approaches to select the most promising MHs for new TSP instances. These approaches induce predictive meta-models from the training of machine learning techniques on a set of meta-data. In our meta-data, each meta-example is a TSP instance described by problem characteristics (meta-features) and performance of MHs (target meta-features) for this instance. The induced meta-models are used to indicate the values of the target meta-feature for new TSP instances. During the investigation of this research, several experiments were performed and important results were obtained

The processes and procedures covered the main core of the professional operations in the manufacturing plant. The enterprise should focus on the efficient running of the main processes and risks associated with these procedures. My thesis deals with the risk analysis of selected manufacturing processes particular company from qualitative and quantitative point of view. First, the results are presented from qualitative risk analysis, especially in scope of failures of the machines or in the sequences of production. Second part focus on the problems of optimization sequence batches that the total time required for pre-setting of machines between doses should be minimal. The thesis also takes random waiting period into the consideration and applies wait-and-see approach of stochaistic programming applied in task traveling salesman. Calculations are processed by the GAMS. The results from the GAMS are refered in MS Excel, they are further discussed and interpreted by using descriptive statistics.

The importance of balance between exploration and exploitation plays a crucial role while solving combinatorial optimization problems. This balance is reached by two general techniques: by using an appropriate problem solver and by setting its proper parameters. Both problems were widely studied in the past and the research process continues up until now. The latest studies in the field of automated machine learning propose merging both problems, solving them at design time, and later strengthening the results at runtime. To the best of our knowledge, the generalized approach for solving the parameter setting problem in heuristic solvers has not yet been proposed. Therefore, the concept of merging heuristic selection and parameter control have not been introduced. In this thesis, we propose an approach for generic parameter control in meta-heuristics by means of reinforcement learning (RL). Making a step further, we suggest a technique for merging the heuristic selection and parameter control problems and solving them at runtime using RL-based hyper-heuristic. The evaluation of the proposed parameter control technique on a symmetric traveling salesman problem (TSP) revealed its applicability by reaching the performance of tuned in online and used in isolation underlying meta-heuristic. Our approach provides the results on par with the best underlying heuristics with tuned parameters.:1 Introduction 1 1.1 Motivation 1 1.2 Research objective 2 1.3 Solution overview 2 2 Background and RelatedWork Analysis 3 2.1 Optimization Problems and their Solvers 3 2.2 Heuristic Solvers for Optimization Problems 9 2.3 Setting Algorithm Parameters 19 2.4 Combined Algorithm Selection and Hyper-Parameter Tuning Problem 27 2.5 Conclusion on Background and Related Work Analysis 28 3 Online Selection Hyper-Heuristic with Generic Parameter Control 31 3.1 Combined Parameter Control and Algorithm Selection Problem 31 3.2 Search Space Structure 32 3.3 Parameter Prediction Process 34 3.4 Low-Level Heuristics 35 3.5 Conclusion of Concept 36 4 Implementation Details 37 4.2 Search Space 40 4.3 Prediction Process 43 4.4 Low Level Heuristics 48 4.5 Conclusion 52 5 Evaluation 55 5.1 Optimization Problem 55 5.2 Environment Setup 56 5.3 Meta-heuristics Tuning 56 5.4 Concept Evaluation 60 5.5 Analysis of HH-PC Settings 74 5.6 Conclusion 79 6 Conclusion 81 7 FutureWork 83 7.1 Prediction Process 83 7.2 Search Space 84 7.3 Evaluations and Benchmarks 84 Bibliography 87 A Evaluation Results 99 A.1 Results in Figures 99 A.2 Results in numbers 105

This research is concerned with the modeling and development of algorithmic approaches for solving airport operational problems that arise in Air Traffic Control (ATC) systems within the terminal area at hub airports. Specifically, the problems addressed include the Aircraft Sequencing Problem (ASP) for runway operations, the Network Assignment Problem (NAP) for taxiway operations, and a simulation model for the evaluation of current or proposed ATC system in detail. For the ASP, we develop a mathematical model and apply the Reformulation-Linearization-Technique (RLT) of Sherali and Adams to construct an enhanced tightened version of the proposed model. Since ASP is NP-Hard and in fact, it is a variation of the well-known Traveling Salesman Problem with time-windows, sub-optimal solutions are usually derived to accommodate the real-time constraints of ATC systems. Nevertheless, we exhibit a significant advancement in this challenging class of problem. Also for the purpose of solving relatively large sized problems in practice, we develop and test suitable heuristic procedures. For the NAP, we propose a quasi-dynamic assignment scheme which is based on the incremental assignment technique. This quasi-dynamic assignment method assumes that the current aircraft route is influenced only by the previous aircraft assigned to the network. This simplified assumption obviates the need for iterative rerouting procedures to reach a pure equilibrium state which might not be achievable in practical taxiway operations. To evaluate the overall system, we develop a microscopic simulation model. The simulation model is designed to have the capability for reproducing not only the dynamic behavior of aircraft, but also incorporates communication activities between controllers and pilots. These activities are critical in ATC operations, and in some instances, might limit the capacity of the facility. Finally, using the developed simulation model named Virginia Tech Airport Simulation Model (VTASM) in concert with ASP and NAP, we compare the overall efficiencies of several control strategies, including that of the existing control system as well as of the proposed advanced control system. / Ph. D.

In this thesis scheduling problems with transportation aspects are studied. Classical scheduling models for problems with multiple operations are the so-called shop-scheduling models. In these models jobs consisting of different operations have to be planned on certain machines in such a way that a given objective function is minimized. Each machine may process at most one operation at a time and operations belonging to the same job cannot be processed simultaneously. We generalize these classical shop-scheduling problems by assuming that the jobs additionally have to be transported between the machines. This transportation has to be done by robots which can handle at most one job at a time. Besides transportation times which occur for the jobs during their transport, also empty moving times are considered which arise when a robot moves empty from one machine to another. Two types of problems are distinguished: on the one hand, problems without transportation conflicts (i.e. each transportation can be performed without delay), and on the other hand, problems where transportation conflicts may arise due to a limited capacity of transport robots. In the first part of this thesis several new complexity results are derived for flow-shop problems with a single robot. Since very special cases of these problems are already NP-hard, in the second part of this thesis some techniques are developed for dealing with these hard problems in practice. We concentrate on the job-shop problem with a single robot and the makespan objective. At first we study the subproblem which arises for the robot when some scheduling decisions for the machines have already been made. The resulting single-machine problem can be regarded as a generalization of the traveling salesman problem with time windows where additionally minimal time-lags between certain jobs have to be respected and the makespan has to be minimized. For this single-machine problem we adapt immediate selection techniques used for other scheduling problems and calculate lower bounds based on linear programming and the technique of column generation. On the other hand, to determine upper bounds for the single-machine problem we develop an efficient local search algorithm which finds good solutions in reasonable time. This algorithm is integrated into a local search algorithm for the job-shop problem with a single robot. Finally, the proposed algorithms are tested on different test data and computational results are presented.

Wireless sensor networks (WSN) are one of the most rapidly evolving technical areas right now. They can be used in a lot of different applications, environmental monitoring and health applications being two examples. The sensors can be placed in hazardous and remote environments since there is no need for cabling or manual maintenance. One of the biggest problems and constraints of today's WSNs is the limited energy capacity of the sensor nodes. Eventually they will be power-depleted, and the network will be dead. A solution to this can be wireless energy transfer technology which makes it possible to recharge sensor nodes with the help of a mobile charger and prolong the lifetime of networks.  This thesis aims to investigate how the charging completion time can be reduced by considering that the charger can charge while moving and by controlling its velocity. The charging completion time is the time from when the charger starts charging the first node until it returns to that starting point.  For this, a two-dimensional WSN was defined that contains sensor nodes and a mobile charger. Anchor nodes, which the charger travels between were defined by choosing the nodes with most neighbors within a defined charging radius. The traveling salesman problem were used to find a path that the charger travels along. A simulation environment was developed in Python to execute tests.  The results show that the charging while moving approach with controlled velocity could reduce the charging completion time with up to 20%. It was also ascertained that this approach works better in dense networks than in sparse. / Trådlösa sensornätverk är ett av de snabbast växande tekniska områdena just nu. De har många olika användningsområden, miljöövervakning och olika hälsotillämpningar är två exempel. Sensorerna kan placeras i farliga och avlägsna miljöer eftersom det inte finns något behov av kablar eller manuellt underhåll. Ett av de största problemen och begränsningarna på dagens trådlösa nätverk är den begränsade energikapaciteten hos sensornoderna. Slutligen kommer de att bli tömda på ström och nätverket kommer att dö. En lösning på detta kan vara trådlös strömöverföring vilket gör det möjligt att ladda sensorerna med hjälp av en mobil laddare och därmed förlänga livstiden på nätverket.  Syftet med detta examensarbete är att undersöka hur slutförandetiden för laddningen kan reduceras i betraktande av att laddaren kan ladda när den rör sig samt att reglera laddaren hastighet. Slutförandetiden för laddningen är den tid det tar från att laddaren börjar ladda den första sensor-noden tills att den kommer tillbaka till punkten den startade på.  För att göra detta definierades ett två-dimensionellt trådlöst sensornätverk som bestod av sensornoder och en mobil laddare. Ankarnoder, vilka laddaren rörde sig emellan, definierades genom att hitta de noder med flest antal grannar inom en bestämd laddningsradie. Handelsresandeproblemet användes för att bestämma rutten som laddaren färdas längs. En simuleringsmiljö utvecklades i Python för att utföra testerna i.  Resultaten visar att med laddaren som laddade när den rörde på sig samt hade reglerad hastighet kunde slutförande-tiden för laddning reduceras med upp till 20%. Det kunde även konstateras att detta tillvägagångssätt fungerar bättre i täta nätverk än i glesa.

This thesis presents new solution approaches for land leveling, using optimal earthmoving vehicle routing. It addresses the Shortest Route Cut and Fill Problem (SRCFP) developed by Henderson, Vaughan, Wakefield and Jacobson [2000]. The SRCFP is a discrete optimization search problem, proven to be NP-hard. The SRCFP describes the process of reshaping terrain through a series of cuts and fills. This process is commonly done when leveling land for building homes, parking lots, etc. The model used to represent this natural system is a variation of the Traveling Salesman Problem. The model is designed to limit the time needed to operate expensive, earthmoving vehicles. The model finds a vehicle route that minimizes the total time required to travel between cut and fill locations while leveling the site. An optimal route is a route requiring the least amount of travel time for an individual earthmoving vehicle. This research addresses the SRCFP by evaluating minimum function values across an unknown response surface. The result is a cost estimating strategy that provides construction planners a strategy for contouring terrain as cheaply as possible. Other applications of this research include rapid runway repair, and robotic vehicle routing. / Master of Science