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)

In this thesis, we study three periodic-review, finite-horizon inventory systems in the presence of supply and demand uncertainties. In the first part of the thesis, we study a multi-period single-station problem in which supply uncertainty is modeled by partial supply. Formulating the problem under a robust optimization (RO) framework, we show that solving the robust counterpart is equivalent to solving a nominal problem with a modified deterministic demand sequence. In particular, in the stationary case the optimal robust policy follows the quasi-(s, S) form and the corresponding s and S levels are theoretically computable. In the second part of the thesis, we extend the RO framework to a multi-period multi-echelon problem. We show that for a tree structure network, decomposition applies so that the optimal single-station robust policy remains valid for each echelon in the tree. Furthermore, if there are no setup costs in the network, then the problem can be decomposed into several uncapacitated single-station problems with new cost parameters subject to the deterministic demands. In the last part of the thesis, we consider a periodic-review Assemble-To-Order (ATO) system with multiple components and multiple products, where the inventory replenishment for each component follows an independent base-stock policy and product demands are satisfied according to a First-Come-First-Served (FCFS) rule. We jointly consider the inventory replenishment and component allocation problems in the ATO system under stochastic component replenishment lead times and stochastic product demands. The problems are formulated under the stochastic programming (SP) framework, which are difficult to solve exactly due to a large number of scenarios. We use the sample average approximation (SAA) algorithms to find near-optimal solutions, which accuracy is verified by the numerical experiment results.

Thesis

Doctor of Philosophy (PhD)

In this thesis we explore three applications of chance constrained optimization in operations management. We first investigate the effect of consumer demand estimation error on new product production planning. An inventory model is proposed, whereby demand is influenced by price and advertising. The effect of parameter misspecification of the demand model is empirically examined in relation to profit and service level feasibility, and conservative approaches to estimating their effect on consumer demand is determined. We next consider optimization in Internet advertising by introducing a chance constrained model for the fulfillment of guaranteed display Internet advertising campaigns. Lower and upper bounds using Monte Carlo sampling and convex approximations are presented, as well as a branching heuristic for sample approximation lower bounds and an iterative algorithm for improved convex approximation upper bounds. The final application is in risk management for parimutuel horse racing wagering. We develop a methodology to limit potential losing streaks with high probability to the given time horizon of a gambler. A proof of concept was conducted using one season of historical race data, where losing streaks were effectively contained within different time periods for superfecta betting.

Thesis

Doctor of Philosophy (PhD)

In this paper, a two-stage stochastic facility location problem integrated with inven- tory and recourse decisions is studied and solved. This problem is inspired by an industrial supply chain design problem of a large retail chain with slow-moving prod- ucts. Uncertainty is expressed by a discrete and finite set of scenarios. Recourse actions can be taken after the realization of random demands. Location, inventory, transportation, and recourse decisions are integrated into a mixed-integer program with an objective minimizing the expected total cost. A dual heuristic procedure is studied and embedded into the sample average approximation (SAA) method. The computation experiments demonstrate that our combined SAA with dual heuristic algorithm has a similar performance on solution quality and a much shorter compu- tational time.

Thesis

Master of Applied Science (MASc)

We present and study the current research trends and advances for optimizing assemble-to-order systems with stochastic lead times. Assemble-to-order systems are widely used in several industries, where end products consist of multiple components and are customizable. Manufacturers can offer greater flexibility to their customers by delaying the assembly of the components until after the order is placed. This means they do not keep an inventory of end-products. Only components can be kept in the inventory and assembled upon demand. We compare and contrast different formulations and the features of assemble-to-order systems studied in the literature including system configuration, replenishment policy, lead time type, and demand distribution. Single-period systems, periodic-review systems, and continuous-review systems are considered. Current assumptions, formulations, solutions, and challenges are discussed.

Thesis

Master of Science (MSc)

The promotion of Electric Vehicles (EV) has become a key measure of the governments to reduce greenhouse gas emissions. However, range anxiety is a big barrier for drivers to choose EVs over traditional vehicles. Installing more charging stations in appropriate locations can relieve EV drivers’ range anxiety. To help decide the location and number of public charging stations, we propose two optimization models for two different charging modes - fast and slow charging, which aim at minimizing the total cost while satisfying certain spatial coverage goals. Instead of using discrete points we employ network and polygons to represent charging demands. Importantly, we resolve the partial coverage problem (PCP) by segmenting the geometric objects into smaller ones using Geographic Information System (GIS) functions. We compare the geometric segmentation method (GS) and the complementary partial coverage method (CP) developed by Murray (2005) to solve the PCP. After applying the models to Greater Toronto and Hamilton Area (GTHA) and to Downtown Toronto, we show that that the proposed models are practical and effective in determining the locations and number of required charging stations. Moreover, comparison of the two methods shows that GS can fully eliminate PCP and provide much more accurate result than CP.

Thesis

Master of Science (MSc)

In this thesis, we study the role of interdiction in the Vehicle Routing Problem (VRP), which naturally arises in humanitarian logistics and military applications. We assume that in a general network, each arc has a chance to be interdicted. When interdiction happens, the vehicle traveling on this arc is lost or blocked and thus unable to continue the trip. We model the occurrence of interdiction as a given probability and consider the multi-period expected delivery. Our objective is to minimize the total travel cost or to maximize the demand fulfillment, depending on the supply quantity. This problem is called the Vehicle Routing Problem with Interdiction (VRPI). We first prove that the proposed VRPI problems are NP-hard. Then we show some key analytical properties pertaining to the optimal solutions of these problems. Most importantly, we examine Dror and Trudeau's property applied to our problem setting. Finally, we present efficient heuristic algorithms to solve these problems and show the effectiveness through numerical studies.

Thesis

Master of Science (MSc)

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)

Long-term care facility network in Ontario, and in Canada as a whole, encounters critical issues regarding balancing demand with capacity. Even worse, it is faced with rising demand in the coming years. Moreover, there is an urgent need to provide long-term care for patients in their own language (particularly French). This study proposes a dynamic Mixed-Integer Linear Programming model based on the current standing of the long-term care system in Ontario, which simultaneously optimizes the time and location of constructing new long-term care facilities, adjusting the capacity (namely, human resources and beds) of each facility dynamically, and the assignment of patients to the facilities based on their demand region, gender, language, and age group over a finite time horizon. We apply the diversity-support constraints, based on patients’ gender and language, to save patients from loneliness and to comply with the Canadian values of providing care. Finally, we validate the model by performing a case study in Hamilton, Ontario. An extensive set of numerical analyses are explored to provide deeper insights into the whole issue. One set of such analysis is an extensive simulation study to examine the effect of distributional uncertainty in some of the input parameters on the optimal results, hence providing a much more realistic understanding of the optimization model.

Thesis

Master of Science (MSc)