Some oil and gas companies are drilling and developing fields in the Arctic Ocean, which has an environment with sea ice called ice floes. These companies must protect their platforms from ice floe collisions. One proposal is to use a system that consists of autonomous underwater vehicles (AUVs) and docking stations. The AUVs measure the under-water topography of the ice floes, while the docking stations launch the AUVs and recharge their batteries. Given resource constraints, we optimize quantities and locations for the docking stations and the AUVs, as well as the AUV scheduling policies, in order to provide the maximum protection level for the platform. We first use an queueing approach to model the problem as a queueing system with abandonments, with the objective to minimize the abandonment probability. Both M/M/k+M and M/G/k+G queueing approximations are applied and we also develop a detailed simulation model based on the queueing approximation. In a complementary approach, we model the system using a multi-stage stochastic facility location problem in order to optimize the docking station locations, the AUV allocations, and the scheduling policies of the AUVs. A two-stage stochastic facility location problem and several efficient online scheduling heuristics are developed to provide lower bounds and upper bounds for the multi-stage model, and also to solve large-scale instances of the optimization model. Even though the model is motivated by an oil industry project, most of the modeling and optimization methods apply more broadly to any radial detection problems with queueing dynamics. / text

The blood supply chain, starting from the donor until the blood is used to meet transfusion demands of patients, is a multi-echelon and complex system. The perishable and lifesaving characteristics of blood products, such as red blood cells and platelets, as well as uncertainties in both supply and demand make it difficult to maintain a balance between shortage and wastage due to expiry. An effective blood supply chain should be able to meet the demand while at the same time reducing wastage and total operational cost. In order to be cost effective, the related organizations have to decide how much blood should be collected from donors, how much blood products should be produced at the blood center, and how much blood products should be distributed to hospitals or transshipped between hospitals. The objective of this dissertation is to provide these tactical and operational decisions to guide those who work in healthcare supply chain management and explore new opportunities on performance improvement for an integrated blood supply chain by optimization with aim of minimizing total cost, consideration of transshipment between hospitals, and application of a coordinated multi-product model. This dissertation presents three multi-stage stochastic models for an integrated blood supply chain to minimize total cost incurred in the collection, production, inventory, and distribution echelons under centralized control. The scope of this study focuses on modeling a supply chain of blood products in one regional blood center, several hospitals and blood collection facilities. First, we develop an integrated model for the platelet supply chain that accounts for demand uncertainty and blood age information, then we develop this model further by investigating the impact of transshipment between hospitals on cost savings, and then we propose a multi-product model that accounts for red blood cells and platelets at the same time and compare it with an uncoordinated model where the red blood cell and platelet supply chains are considered separately.

In this dissertation, we study several stochastic capacity expansion models in the presence of permanent, spot market, and contract capacity for acquisition. Using a scenario tree approach to handle the data uncertainty of the problems, we develop multi-stage stochastic integer programming formulations for these models. First, we study multi-period single resource stochastic capacity expansion problems, where different sources of capacity are available to the decision maker. We develop efficient algorithms that can solve these models to optimality in polynomial time. Second, we study multi-period stochastic network capacity expansion problems with different sources for capacity. The proposed models are NP-hard multi-stage stochastic integer programs and we develop an efficient, asymptotically convergent approximation algorithm to solve them. Third, we consider some decomposition algorithms to solve the proposed multi-stage stochastic network capacity expansion problem. We propose an enhanced Benders' decomposition algorithm to solve the problem, and a Benders' decomposition-based heuristic algorithm to find tight bounds for it. Finally, we extend the stochastic network capacity expansion model by imposing budget restriction on permanent capacity acquisition cost. We design a Lagrangian relaxation algorithm to solve the model, including heuristic methods to find tight upper bounds for it. / Thesis / Doctor of Philosophy (PhD)

Governments in many counties are taking measures to promote electric vehicles. An important strategy is to build enough charging infrastructures so as to alleviate drivers’ range anxieties. To help the governments make plans about the public charging network, we propose a multi-stage stochastic integer programming model to determine the locations and capacities of charging facilities over finite planning horizons. We use the logit choice model to estimate drivers’ random choices towards different charging stations nearby. The objective of the model is to minimize the expected total cost of installing and operating the charging facilities. Two simple algorithms are designed to solve this model, an approximation algorithm and a heuristic algorithm. A branch-and-price algorithm is also designed for this model, and some implementation details and improvement methods are explained. We do some numerical experiments to test the efficiency of these algorithms. Each algorithm has advantages over the CPLEX MIP solver in terms of solution time or solution quality. A case study of Oakville is presented to demonstrate the process of designing an electric vehicle public charging network using this model in Canada. / Thesis / Master of Science (MSc)

The main objective of this thesis is to build a multi-stage stochastic pro- gram within an asset-liability management problem of a leasing company. At the beginning, the business model of such a company is introduced and the stochastic programming formulation is derived. Thereafter, three various risk constraints, namely the chance constraint, the Value-at-Risk constraint and the conditional Value-at-Risk constraint along with the second-order stochastic dominance constraint are applied to the model to control for riski- ness of the optimal strategy. Their properties and their effects on the optimal decisions are thoroughly investigated, while various risk limits are considered. In order to obtain solutions of the problems, random elements in the model formulation had to be approximated by scenarios. The Hull - White model calibrated by a newly proposed method based on maximum likelihood esti- mation has been used to generate scenarios of future interest rates. In the end, the performances of the optimal solutions of the problems for unconsid- ered and unfavourable crisis scenarios were inspected. The used methodology of such a stress test has not yet been implemented in stochastic programming problems within an asset-liability management. 1

Multi-Stage Stochastic Programming with CVaR: Modeling, Algorithms and Robustness RNDr. Václav Kozmík Abstract: We formulate a multi-stage stochastic linear program with three different risk measures based on CVaR and discuss their properties, such as time consistency. The stochastic dual dynamic programming algorithm is described and its draw- backs in the risk-averse setting are demonstrated. We present a new approach to evaluating policies in multi-stage risk-averse programs, which aims to elimi- nate the biggest drawback - lack of a reasonable upper bound estimator. Our approach is based on an importance sampling scheme, which is thoroughly ana- lyzed. A general variance reduction scheme for mean-risk sampling with CVaR is provided. In order to evaluate robustness of the presented models we extend con- tamination technique to the case of large-scale programs, where a precise solution cannot be obtained. Our computational results are based on a simple multi-stage asset allocation model and confirm usefulness of the presented procedures, as well as give additional insights into the behavior of more complex models. Keywords: Multi-stage stochastic programming, stochastic dual dynamic programming, im- portance sampling, contamination, CVaR