We present solution methodologies for vehicle routing problems (VRPs) with stochastic demand, with a specific focus on the vehicle routing problem with stochastic demand (VRPSD) and the vehicle routing problem with stochastic demand and duration limits (VRPSDL). The VRPSD and the VRPSDL are fundamental problems underlying many operational challenges in the fields of logistics and supply chain management. We model the VRPSD and the VRPSDL as large-scale Markov decision processes. We develop cyclic-order neighborhoods, a general methodology for solving a broad class of VRPs, and use this technique to obtain static, fixed route policies for the VRPSD. We develop pre-decision, post-decision, and hybrid rollout policies for approximate dynamic programming (ADP). These policies lay a methodological foundation for solving large-scale sequential decision problems and provide a framework for developing dynamic routing policies. Our dynamic rollout policies for the VRPSDL significantly improve upon a method frequently implemented in practice. We also identify circumstances in which our rollout policies appear to offer little or no benefit compared to this benchmark. These observations can guide managerial decision making regarding when the use of our procedures is justifiable. We also demonstrate that our methodology lends itself to real-time implementation, thereby providing a mechanism to make high-quality, dynamic routing decisions for large-scale operations. Finally, we consider a more traditional ADP approach to the VRPSDL by developing a parameterized linear function to approximate the value functions corresponding to our problem formulation. We estimate parameters via a simulation-based algorithm and show that initializing parameter values via our rollout policies leads to significant improvements. However, we conclude that additional research is required to develop a parametric ADP methodology comparable or superior to our rollout policies.

Games on graphs have become an indispensable tool in modern computer science. They provide powerful and expressive models for numerous phenomena and are extensively used in computer- aided verification, automata theory, logic, complexity theory, computational biology, etc. The infinite games on finite graphs we study in this thesis have their primary applications in verification, but are also of fundamental importance from the complexity-theoretic point of view. They include parity, mean payoff, and simple stochastic games. We focus on solving graph games by using iterative strategy improvement and methods from linear programming and combinatorial optimization. To this end we consider old strategy evaluation functions, construct new ones, and show how all of them, due to their structural similarities, fit into a unifying combinatorial framework. This allows us to employ randomized optimization methods from combinatorial linear programming to solve the games in expected subexponential time. We introduce and study the concept of a controlled optimization problem, capturing the essential features of many graph games, and provide sufficent conditions for solvability of such problems in expected subexponential time. The discrete strategy evaluation function for mean payoff games we derive from the new controlled longest-shortest path problem, leads to improvement algorithms that are considerably more efficient than the previously known ones, and also improves the efficiency of algorithms for parity games. We also define the controlled linear programming problem, and show how the games are translated into this setting. Subclasses of the problem, more general than the games considered, are shown to belong to NP intersection coNP, or even to be solvable by subexponential algorithms. Finally, we take the first steps in investigating the fixed-parameter complexity of parity, Rabin, Streett, and Muller games.

In dieser Dissertation werden erstmals Kenntnisse über ökologische Felder von Einzelbäumen mit Methoden der räumlichen Optimierung kombiniert, um ein Werkzeug zu schaffen, mit dem Empfehlungen für die Strukturierung von Beständen erarbeiten werden können. Dabei waren drei unterschiedliche waldbauliche Problemstellungen Ausgangspunkt der Arbeit. Die ausführliche Beschreibung der Probleme führte zur Ableitung eines allgemeinen Optimierungsproblems, das nach optimalen Stammverteilungsplänen bzgl. verschiedener, waldbaulicher Zielsetzungen sucht. Der erster Schwerpunkt war die mathematische Herleitung der Zielgrößen. Hierbei wurde die Idee der Einzelbaumeffekte und das Konzept der ökologischen Felder verwendet, um die Zielgrößen aus den Einzelbaumeffekten zu entwickeln. Der zweite Schwerpunkt umfasste die Suche nach einem geeigneten Optimierungsmodell, mit dem die Horizontalstruktur eines Bestandes basierend auf weitreichenden, stetigen Einzelbaumeffekten räumlich optimiert werden konnte. Der gegebene Überblick zum Stand der Forschung bzgl. der räumlichen Optimierung in der Forstwissenschaft zeigte auf, dass nur Teilaspekte des allgemeinen Optimierungsproblems bisher modelliert worden sind. Von den vier daraufhin neu entwickelten Optimierungsmodellen wurden ein kontinuierliches und ein diskretes Modells nach der Auswertung der Eigenschaften weiterverwendet. Die Bewertung von verschiedenen, vorgestellten Nachbarschaftsdefinitionen und Varianten von lokalen Suchverfahren, Meta- und Hybridheuristiken führte zur Verwendung von k-opt für das diskrete Optimierungsmodell, von Compass Search für das kontinuierliche Optimierungsmodell und von Threshold Accepting und Iterated Local Search für beide Modelle. Für alle drei Optimierungsprobleme wurden jeweils zwei Tests je Algorithmus mit einer in C++ implementierten Optimierungssoftware durchgeführt. Beim ersten Test sollten in kurzer Zeit wiederholt gute Lösungen berechnet werden, während im zweiten Test wesentlich mehr Funktionswertberechnungen zur Verfügung standen, um eine sehr gute Lösung zu erhalten. Die Auswertung der Testrechnungen zeigte, dass das diskrete Optimierungsmodell dem kontinuierlichen Modell außer bei einem geringen Bestockungsgrad des Bestandes vorzuziehen ist. Die Zielfunktionsdefinitionen hatten wesentlichen Einfluss auf die Lösungen, vor allem bei gegenläufigen Zielen. Sehr gute Lösungen wiesen dabei charakteristische Verteilungsschemata der Baumpositionen auf, die nur durch eine Optimierung und nicht durch das wiederholte, zufällige Verteilen von Bäumen gefunden werden konnten. Für das diskrete Modell lieferte Threshold Accepting vor 2-opt und Iterated Local Search fast immer die besten Ergebnisse. 4-opt war immer deutlich schlechter als die anderen Algorithmen. Threshold Accepting berechnete sowohl sehr schnell gute Lösungen und als auch die besten Lösungen, wenn eine intensive Suche mit sehr vielen Funktionswertberechnungen möglich war.

This thesis addresses the technical and linguistic aspects of discourse-level processing in phrase-based statistical machine translation (SMT). Connected texts can have complex text-level linguistic dependencies across sentences that must be preserved in translation. However, the models and algorithms of SMT are pervaded by locality assumptions. In a standard SMT setup, no model has more complex dependencies than an n-gram model. The popular stack decoding algorithm exploits this fact to implement efficient search with a dynamic programming technique. This is a serious technical obstacle to discourse-level modelling in SMT. From a technical viewpoint, the main contribution of our work is the development of a document-level decoder based on stochastic local search that translates a complete document as a single unit. The decoder starts with an initial translation of the document, created randomly or by running a stack decoder, and refines it with a sequence of elementary operations. After each step, the current translation is scored by a set of feature models with access to the full document context and its translation. We demonstrate the viability of this decoding approach for different document-level models. From a linguistic viewpoint, we focus on the problem of translating pronominal anaphora. After investigating the properties and challenges of the pronoun translation task both theoretically and by studying corpus data, a neural network model for cross-lingual pronoun prediction is presented. This network jointly performs anaphora resolution and pronoun prediction and is trained on bilingual corpus data only, with no need for manual coreference annotations. The network is then integrated as a feature model in the document-level SMT decoder and tested in an English–French SMT system. We show that the pronoun prediction network model more adequately represents discourse-level dependencies for less frequent pronouns than a simpler maximum entropy baseline with separate coreference resolution. By creating a framework for experimenting with discourse-level features in SMT, this work contributes to a long-term perspective that strives for more thorough modelling of complex linguistic phenomena in translation. Our results on pronoun translation shed new light on a challenging, but essential problem in machine translation that is as yet unsolved.

Minimum Concave Cost Multicommodity Network Design Problem arises in many application areas, such as transportation planning, distributed energy system and especially both circuit and packet switching backbone network design. Exact concave optimization algorithms have been developed, but these methods are applicable if the network size is small. Therefore, these problems are usually solved by non-exact iterative methods. In this thesis work, methods proposed for circuit switching and packet switching network design are evaluated in detail. After a comprehensive literate survey, Yaged&rsquo / s Linearization, Minoux greedy and Minoux accelerated greedy methods are found to be applicable to circuit switching network design when both solution quality and computational time is considered. Previously, it has been found that Minoux greedy methods may create routings with cycles and in order to eliminate these cycles a modification has been proposed. In this work, this modification is extended and evaluated in detail. Similarly, Gerla and Kleinrock&rsquo / s Concave Branch Elimination, Gersht&rsquo / s greedy and Stacey&rsquo / s Concave Link Elimination methods are investigated within the context of packet switching network design. All of these methods consider aggregate flows on each link simultaneously re-routing more than one commodity in one step. This thesis work also considers an alternative disaggregate approach, where only one commodity is handled at a time. Finally, algorithms proposed for circuit switching network design problem are adapted to the packet switching case and an extensive comparative computational study is performed to point out the best method with respect to time and solution quality for a number of networks and cost structure. Computational results have shown that modification on Minoux greedy to eliminate cycles leads to considerable improvements and the disaggregate approach gives the best result in some networks and cost structure.

La validation des charges utiles des satellites de télécommunication nécessite des opérations coûteuses en temps et en personnel. Ce coût augmente régulièrement du fait de la complexité croissante des charges utiles. Il est donc crucial pour Astrium d'optimiser la réalisation des opérations de test. L'objectif de cette thèse CIFRE menée en collaboration entre Astrium et l'Onera est de développer une suite logicielle d'aide à la génération de plans de test. Le problème de génération de plan de test a été modélisé sous forme de graphe orienté à états. La NP-complétude de ce problème a été établie. Des modèles mathématiques ont été construits en programmation linéaire en nombres entiers et en programmation par contraintes en vue d'une résolution par des solveurs génériques. Cependant, ces solveurs génériques se sont heurtés à des problèmes d'insuffisance de mémoire liés à la très grande taille des instances à traiter. Ceci nous a conduits à développer un solveur spécialisé à base de recherche arborescente faisant appel à des mécanismes spécifiques de choix de variables et de valeurs, de propagation de contraintes, de calcul de borne, de retour-arrière, d'apprentissage et de redémarrage. Un solveur spécialisé à base de recherche locale a été développé en parallèle. Les résultats obtenus par ces différents solveurs avec différents paramétrages ont pu être comparés. / Telecommunication satellite payload validation requires operations which are expensive in terms of time and manpower. This cost is constantly increasing as the payloads become more and more complex. It is crucial for Astrium to optimise the testing phase to keep these costs under control. The objective of this CIFRE thesis, conducted in collaboration with Astrium and Onera, is to develop a software suite to help generate test plans for the payloads.The problem of generating test plans was modeled using the form of a directed graph with states. The NP-completeness of this problem was proven. Mathematical models were built using integer linear programming and constraint programming with a view to solving the problems using generic solvers. However, these generic solvers had problems due to insufficient memory on account of the large size of instances to be handled. These problems led us to develop a specialised solver using a tree search, with special mechanisms for choosing variables and values, propagating constraints, computing bounds, backjumping,learning, and restarting. A specialised solver based on local search was developed in parallel.The results obtained by these different solvers with different settings were compared.

abstract: This thesis presents a successful application of operations research techniques in nonprofit distribution system to improve the distribution efficiency and increase customer service quality. It focuses on truck routing problems faced by St. Mary’s Food Bank Distribution Center. This problem is modeled as a capacitated vehicle routing problem to improve the distribution efficiency and is extended to capacitated vehicle routing problem with time windows to increase customer service quality. Several heuristics are applied to solve these vehicle routing problems and tested in well-known benchmark problems. Algorithms are tested by comparing the results with the plan currently used by St. Mary’s Food Bank Distribution Center. The results suggest heuristics are quite completive: average 17% less trucks and 28.52% less travel time are used in heuristics’ solution. / Dissertation/Thesis / Masters Thesis Industrial Engineering 2015

Made available in DSpace on 2015-05-14T12:36:51Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 1355559 bytes, checksum: fe1c88470e43ce75f706ec9d15cc7bb1 (MD5) Previous issue date: 2014-07-31 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / With the advent of technological advances, increasingly demand solutions that use fewer resources, are faster and low cost. As a result, this paper proposed a hybrid approach using metaheuristics Greedy Randomized Adaptive Search Procedure (GRASP) and Iterated Local Search (ILS) applied to the Response Time Variability Problem (RTVP). Since this problem may involve allocation of scarce resources, such as industrial machinery or meeting rooms, going for scheduling of banking customers that require certain conditions, planning of TV ads or route taken by vehicles of logistic companies, etc. For application of the procedure, the movements of shifting symbols, swapping positions between symbols and one called double bridge, which is a mix of movements of shifting and swapping involving opposite symbols were used. The neighborhood structures were based on the movements described above, varying the number of symbols involved. Thus, the results obtained demonstrate that such procedures satisfied the problem and brought consistent results when compared with the literature. / Com o advento dos avanços tecnológicos, cada vez mais se procura soluções que utilizem menos recursos, sejam mais rápidos e de baixo custo. Em virtude disso, este trabalho propôs uma abordagem meta-heurística híbrida utilizando Greedy Randomized Adaptive Search Procedure (GRASP) e Iterated Local Search (ILS) aplicados ao Problema da Variabilidade do Tempo de Resposta. Este problema pode envolver desde alocação de recursos escassos, como por exemplo, máquinas industriais ou salas de reunião, passando pelo agendamento de clientes de um banco que requerem certas condições, o planejamento das propagandas de TV ou o percurso feito por caminhões de empresas transportadoras, dentre outros. Para a aplicação do procedimento, foram utilizados os movimentos de deslocamento do mesmo, permuta de posição entre símbolos e de um movimento chamado double brigde, que é uma mistura dos movimentos de deslocamento e permutação envolvendo símbolos opostos. As estruturas de vizinhança compostas basearam-se nos movimentos descritos anteriormente, variando a quantidade de símbolos envolvidos. Desta forma, os resultados obtidos demonstram que tais procedimentos trouxeram resultados satisfatórios ao problema e condizentes quando comparados com a literatura.

Made available in DSpace on 2015-05-14T12:36:54Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 2485062 bytes, checksum: ad2a2349ad56d837e75386f8c9ba1027 (MD5) Previous issue date: 2010-03-27 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / The present dissertation deals with the Routing Circuits for Field Programable Gate Arrays (FPGAs). Due to the combinatorial nature of the problem, heuristics methods are commonly used to generate good quality solutions in an acceptable computationally time. In this context, a procedure based on GRASP (Greedy Randomized Adaptive Search Procedure) with a procedure of local search based on ILS (Iterated Local Search) is proposed. The algorithm has been tested in benchmark problems found in the literature, MCNC, exploring timing-driven and channel-width criteria, being able to improve 55% of the benchmarks on timing drive criteria and improve 5,3% of the benchmarks on channel width criteria. / A presente dissertação trata do problema de roteamento de circuitos para Field Programable Gate Arrays (FPGAs). Em função da natureza combinatória do problema, métodos heurísticos são comumente utilizados para gerar soluções de boa qualidade em um tempo computacionalmente aceitável. Neste contexto, um procedimento baseado na metaheurística GRASP (Greedy Randomized Adaptive Search Procedure) com um procedimento de busca local baseado em ILS (Iterated Local Search) é proposto. O algoritmo foi testado em instâncias encontradas na literatura, benchmark MCNC, explorando os critérios de tempo crítico e números de trilhas, onde mostrou-se capaz de melhorar 55% das instancias no critério de tempo crítico e 5,3% quanto ao número de trilhas.

In the last decades there has been a lot of interest in computational models and metaheuristics algorithms capable to solve combinatorial optimization problems. The recent trend is to define these algorithms taking inspiration by the observation of natural systems. In this thesis the Ant Colony System (ACS) is presented which has been inspired by the observation of real ant colonies. ACS is initially proposed to solve the symmetric and asymmetric travelling salesman problems where it is shown to be competitive with other metaheuristics. Although this is an interesting and promising result, it was immediately clear that ACS, as well as other metaheuristics, in many cases cannot compete with specialized local search methods. An interesting trend is therefore to couple metaheuristics with a local optimizer, giving birth to so-called hybrid methods. Along this line, the thesis investigates MACS-VRPTW (Multiple ACS for the Vehicle Routing Problem with Time Windows) and HAS-SOP: Hybrid Ant System for the Sequential Ordering Problem (SOP). In the second part the thesis introduces some modifications of the original ACS algorithm. These modifications are able to speed up the method and to make it more competitive in case of large problem instances. The resulting framework, called Enhanced Ant Colony System is tested for the SOP. Finally the thesis presents the application of ACS to solve real-life vehicle routing problems where additional constraints and stochastic information are included. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished