This dissertation considers sheltering network planning and operations for natural disaster preparedness and responses with a two-stage stochastic program. The first phase of the network design decides the locations, capacities and held resources of new permanent shelters. Both fixed costs for building a new permanent shelter and variable costs based on capacity are considered. Under each disaster scenario featured by the evacuee demand and transportation network condition, the flows of evacuees and resources to shelters, including permanent and temporary ones, are determined in the second stage to minimize the transportation and shortage/surplus costs. Typically, a large number of scenarios are involved in the problem and cause a huge computational burden. The L-shaped algorithm is applied to decompose the problem into the scenario level with each sub-problem as a linear program. The Sheltering Network Planning and Operation Problem considered in this dissertation also has a special structure in the second-stage sub-problem that is a minimum cost network flow problem with equal flow side constraints. Therefore, the dissertation also takes advantages of the network simplex method to solve the response part of the problem in order to solve the problem more efficiently. This dissertation investigates the extending application of special minimum cost equal flow problem. A case study for preparedness and response to hurricanes in the Gulf Coast region of the United States is conducted to demonstrate the usage of the model including how to define scenarios and cost structures. The numerical experiment results also verify the fast convergence of the L-shaped algorithm for the model.

Tato diplomová práce uvádí základní poznatky matematického a především stochastického programování. Navíc se zabývá použitím softwaru AIMMS při vytváření a řešení optimalizačních problémů. Naším hlavním cílem je naprogramovat v softwaru AIMMS několik metod řešení problémů stochastického programování a ukázat jejich použití a užitečnost na vybraných problémech. Jedním z problémů, který jsme si zvolili, je model spalovny. Všechny AIMMS programy, které v našem textu použijeme a popíšeme, a jejich zdrojové kódy budou přiloženy v dodatcích.

The thesis deals with the algorithms for two-stage stochastic programs. The first chapter considers the basic properties and theory. Specifically, we introduce the properites of the feasibility region and the objective function. Further, optimality conditions are discussed. In the second chapter we present algoritms which can be used to solve two-stage linear programs with fixed recourse. In the first section the basic L-shaped method is described in detail. The second section provides an explanation of the Stochastic Decomposition algorithm with the inclusion of a regularization term. The last chapter presents computational results. Three practical examples are provided both with a brief description of the problem and solutions by the studied algorithms.

Forest fires cause a significant amount of damage and destruction each year. Optimally dispatching resources reduces the amount of damage a forest fire can cause. Models predict the fire spread to provide the data required to optimally dispatch resources. However, the models are only as accurate as the data used to build them. Satellites are one valuable tool in the collection of data for the forest fire models. Satellites provide data on the types of vegetation, the wind speed and direction, the soil moisture content, etc. The current operating paradigm is to passively collect data when possible. However, images from directly overhead provide better resolution and are easier to process. Maneuvering a constellation of satellites to fly directly over the forest fire provides higher quality data than is achieved with the current operating paradigm. Before launch, the location of the forest fire is unknown. Therefore, it is impossible to optimize the initial orbits for the satellites. Instead, the expected cost of maneuvering to observe the forest fire determines the optimal initial orbits. A two-stage stochastic programming approach is well suited for this class of problem where initial decisions are made with an uncertain future and then subsequent decisions are made once a scenario is realized. A repeat ground track orbit provides a non-maneuvering, natural solution providing a daily flyover of the forest fire. However, additional maneuvers provide a second daily flyover of the forest fire. The additional maneuvering comes at a significant cost in terms of additional fuel, but provides more data collection opportunities. After data are collected, ground stations receive the data for processing. Optimally selecting the ground station locations reduce the number of built ground stations and reduces the data fusion issues. However, the location of the forest fire alters the optimal ground station sites. A two-stage stochastic programming approach optimizes the selection of ground stations to maximize the expected amount of data downloaded from a satellite. The approaches of selecting initial orbits and ground station locations including uncertainty will provide a robust system to reduce the amount of damage caused by forest fires.

Cette thèse s’intéresse aux problèmes de tournées de véhicules où l’on retrouve des contraintes de chargement ayant un impact sur les séquences de livraisons permises. Plus particulièrement, les items placés dans l’espace de chargement d’un véhicule doivent être directement accessibles lors de leur livraison sans qu’il soit nécessaire de déplacer d’autres items. Ces problèmes sont rencontrés dans plusieurs entreprises de transport qui livrent de gros objets (meubles, électroménagers). Le premier article de cette thèse porte sur une méthode exacte pour un problème de confection d’une seule tournée où un véhicule, dont l’aire de chargement est divisée en un certain nombre de piles, doit effectuer des cueillettes et des livraisons respectant une contrainte de type dernier entré, premier sorti. Lors d’une collecte, les items recueillis doivent nécessairement être déposés sur le dessus de l’une des piles. Par ailleurs, lors d’une livraison, les items doivent nécessairement se trouver sur le dessus de l’une des piles. Une méthode de séparation et évaluation avec plans sécants est proposée pour résoudre ce problème. Le second article présente une méthode de résolution exacte, également de type séparation et évaluation avec plans sécants, pour un problème de tournées de véhicules avec chargement d’items rectangulaires en deux dimensions. L’aire de chargement des véhicules correspond aussi à un espace rectangulaire avec une orientation, puisque les items doivent être chargés et déchargés par l’un des côtés. Une contrainte impose que les items d’un client soient directement accessibles au moment de leur livraison. Le dernier article aborde une problème de tournées de véhicules avec chargement d’items rectangulaires, mais où les dimensions de certains items ne sont pas connus avec certitude lors de la planification des tournées. Il est toutefois possible d’associer une distribution de probabilités discrète sur les dimensions possibles de ces items. Le problème est résolu de manière exacte avec la méthode L-Shape en nombres entiers. / In this thesis, we study mixed vehicle routing and loading problems where a constraint is imposed on delivery sequences. More precisely, the items in the loading area of a vehicle must be directly accessible, without moving any other item, at delivery time. These problems are often found in the transportation of large objects (furniture, appliances). The first paper proposes a branch-and-cut algorithm for a variant of the single vehicle pickup and delivery problem, where the loading area of the vehicle is divided into several stacks. When an item is picked up, it must be placed on the top of one of these stacks. Conversely, an item must be on the top of one of these stacks to be delivered. This requirement is called “Last In First Out” or LIFO constraint. The second paper presents another branch-and-cut algorithm for a vehicle routing and loading problem with two-dimensional rectangular items. The loading area of the vehicles is also a rectangular area where the items are taken out from one side. A constraint states that the items of a given customer must be directly accessible at delivery time. The last paper considers a stochastic vehicle routing and loading problem with two- dimensional rectangular items where the dimensions of some items are unknown when the routes are planned. However, it is possible to associate a discrete probability distribution on the dimensions of these items. The problem is solved with the Integer L-Shaped method.

Cette thèse s’intéresse aux problèmes de tournées de véhicules où l’on retrouve des contraintes de chargement ayant un impact sur les séquences de livraisons permises. Plus particulièrement, les items placés dans l’espace de chargement d’un véhicule doivent être directement accessibles lors de leur livraison sans qu’il soit nécessaire de déplacer d’autres items. Ces problèmes sont rencontrés dans plusieurs entreprises de transport qui livrent de gros objets (meubles, électroménagers). Le premier article de cette thèse porte sur une méthode exacte pour un problème de confection d’une seule tournée où un véhicule, dont l’aire de chargement est divisée en un certain nombre de piles, doit effectuer des cueillettes et des livraisons respectant une contrainte de type dernier entré, premier sorti. Lors d’une collecte, les items recueillis doivent nécessairement être déposés sur le dessus de l’une des piles. Par ailleurs, lors d’une livraison, les items doivent nécessairement se trouver sur le dessus de l’une des piles. Une méthode de séparation et évaluation avec plans sécants est proposée pour résoudre ce problème. Le second article présente une méthode de résolution exacte, également de type séparation et évaluation avec plans sécants, pour un problème de tournées de véhicules avec chargement d’items rectangulaires en deux dimensions. L’aire de chargement des véhicules correspond aussi à un espace rectangulaire avec une orientation, puisque les items doivent être chargés et déchargés par l’un des côtés. Une contrainte impose que les items d’un client soient directement accessibles au moment de leur livraison. Le dernier article aborde une problème de tournées de véhicules avec chargement d’items rectangulaires, mais où les dimensions de certains items ne sont pas connus avec certitude lors de la planification des tournées. Il est toutefois possible d’associer une distribution de probabilités discrète sur les dimensions possibles de ces items. Le problème est résolu de manière exacte avec la méthode L-Shape en nombres entiers. / In this thesis, we study mixed vehicle routing and loading problems where a constraint is imposed on delivery sequences. More precisely, the items in the loading area of a vehicle must be directly accessible, without moving any other item, at delivery time. These problems are often found in the transportation of large objects (furniture, appliances). The first paper proposes a branch-and-cut algorithm for a variant of the single vehicle pickup and delivery problem, where the loading area of the vehicle is divided into several stacks. When an item is picked up, it must be placed on the top of one of these stacks. Conversely, an item must be on the top of one of these stacks to be delivered. This requirement is called “Last In First Out” or LIFO constraint. The second paper presents another branch-and-cut algorithm for a vehicle routing and loading problem with two-dimensional rectangular items. The loading area of the vehicles is also a rectangular area where the items are taken out from one side. A constraint states that the items of a given customer must be directly accessible at delivery time. The last paper considers a stochastic vehicle routing and loading problem with two- dimensional rectangular items where the dimensions of some items are unknown when the routes are planned. However, it is possible to associate a discrete probability distribution on the dimensions of these items. The problem is solved with the Integer L-Shaped method.

[pt] Este trabalho apresenta uma proposta de aceleração da decomposição de Benders aplicada a uma versão mais geral e compacta (menos restrições e variáveis) do modelo de gestão de estoques, otimizado via programação estocástica de dois estágios que considera uma camada, um item, demanda incerta e política de controle (R, S). De maneira a ser possível considerar problemas de grande porte, foram aplicados os métodos L-Shaped tradicional com corte único e a sua forma estendida com múltiplos cortes. Resultados computacionais preliminares mostraram um substancial melhor desempenho computacional do método L-Shaped tradicional em relação à sua forma multi-cut L-Shaped, mesmo o primeiro necessitando de mais iterações para convergir na solução ótima. Tal observação motivou o desenvolvimento de uma nova técnica de aceleração da decomposição de Benders e de um conjunto de desigualdades válidas. Experimentos numéricos mostram que a abordagem proposta de combinar a técnica de aceleração elaborada com as desigualdades válidas desenvolvidas provê significativa redução do tempo computacional necessário para a solução de instâncias de grande porte. / [en] This dissertation presents a speed up proposal for the Benders decomposition applied to a more general and compact version (less constraints and variables) of inventory management model, optimized via two-stage stochastic programming, which considers one layer, one item, uncertain demand and control policy (R, S). In order to be possible to consider large scale problems, the L-Shaped traditional method with single cuts and its extended form with multiple cuts were applied. Preliminary computational results showed a substantially better computational performance of the traditional L-Shaped method in comparison to the multi-cut L-Shaped method, even with the first requiring more iterations to converge on optimum solutions. This observation led to the development of a new technique to accelerate the decomposition of Benders and a set of valid inequalities. Numerical experiments show that the proposed approach of combining the elaborate acceleration technique with the developed valid inequalities, provide significant reduction in the computational time required to solve large scale instances.