No description available.

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)

Closed-loop supply chains (CLSC) though present for decades, have seen significant research in optimization only in the last five years. Traditional sustainable CLSCs have generally implemented a Carbon Cap Trading (CCT), Carbon Cap (CC), or Carbon Taxes methodology to set carbon emissions limits but fail to minimize these emissions explicitly. Moreover, the traditional CCT model discourages investment in greener technologies by favoring established logistics over eco-friendly alternatives. This research tackles the sustainable CLSC problem by proposing a mixed-integer linear programming (MILP) carbon-conscious textit{p}-hub location model having the objective of minimizing emissions subject to profit constraints. The model is then extended to incorporate multi-periodicity, transportation modes, and end-of-life periods with a bi-objective cost and emissions function. Additionally, the model accounts for long-term planning and optimization, considering changes in demand and returns over time by incorporating a time dimension. The model's robustness and solving capabilities were tested for the case of electric vehicle (EV) battery supply chains. Demand for EVs is projected to increase by 18% annually, and robust supply chain designs are crucial to meet this demand, making this sector an important test case for the model to solve. Two baseline cases with minimum cost and minimum emissions objectives were tested, revealing a significant gap in emissions and underlining the need for an emissions objective. A sensitivity analysis was conducted on key parameters focusing on minimizing emissions; the analysis revealed that demand, return rates, and recycling costs greatly impact CLSC dynamics. The results showcase the model's capability of tackling real-world case scenarios, thus facilitating comprehensive decision-making goals in carbon-conscious CSLC design. / Master of Science / Closed-loop supply chain (CLSC) is a supply chain that recycles used products back to the manufacturer. CLSCs have been around for decades, but significant progress in optimizing them has only emerged over the last five years. Sustainable CLSC models often include limits on carbon emissions but usually don't directly minimize them. Traditional CLSC models tend to prioritize established logistics over greener technologies, discouraging investment in eco-friendly options. This study addresses this problem by introducing a mathematical model designed to minimize emissions while considering profit constraints. The model is expanded to factor in different time periods, transportation methods, and end-of-use phases with two goals in mind: cost and emissions. Additionally, it incorporates long-term planning, accounting for shifts in customer demand and product returns. The model's effectiveness was tested with electric vehicle (EV) battery supply chains, which serve as an important example given the predicted annual 18% growth in EV demand and the crucial need for efficient supply chain design. Two baseline scenarios were examined: one aiming to minimize costs and the other to minimize emissions. The results showed a notable disparity in emissions between the two, underscoring the importance of an emissions-focused objective. Key parameters, such as demand, return rates, and recycling costs, demonstrated a significant impact on CLSC operations. The findings highlight the model's ability to handle real-world challenges, enabling informed decision-making for designing carbon-conscious CLSCs.

Evacuation planning is an important disaster management tool. A large-scale evacuation of a region by automobile is a difficult task, especially as demand is often greater than supply. This is made more difficult as the imbalance of supply and demand actually reduces supply due to congestion. Currently, most of the emphasis in evacuation planning is on supply management. The purpose of this dissertation is to introduce and study sophisticated demand management tools, specifically, staging and routing of evacuees. These tools can be used to produce evacuation strategies that reduce or eliminate congestion. A strategic planning model is introduced that accounts for evacuation dynamics and the non-linearities in travel times associated with congestion, yet is tractable and can be applied to large-scale networks. Objective functions of potential interest in evacuation planning are introduced and studied in the context of this model. Insights into the use of staging and routing in evacuation management are delineated and solution techniques are developed. Two different strategic approaches are studied in the context of this model. The first strategic approach is to control the evacuation at a disaggregate level, where customized staging and routing plans are produced for each individual or family unit. The second strategic approach is to control the evacuation at a more aggregate level, where evacuation plans are developed for a larger group of evacuees, based on pre-defined geographic areas. In both approaches, shelter requirements and preferences can also be considered. Computational experience using these two strategic approaches, and their respective solution techniques, is provided using a real network pertaining to Virginia Beach, Virginia, in order to demonstrate the efficacy of the proposed methodologies. / Ph. D.

The facility layout problem (FLP) is one of the most important and challenging problems in both the operations research and industrial engineering research domains. In FLP research, the continuous-representation-based FLP can consider all possible all-rectangular department solutions. Given this flexibility, this representation has become the representation of-choice in FLP research. Much of this research is based on a methodology of mixed integer programming (MIP) models. However, these MIP-FLP models can only solve problems with a limited number of departments to optimality due to a large number of binary variables used in the models to prevent departments from overlapping. Our research centers around the sequence-pair representation, a concept that originated in the Very Large Scale Integration (VLSI) design literature. We show that an exhaustive search of the sequence-pair solution space will result in finding the optimal layout of the MIP-FLP and that every sequence-pair solution is binary-feasible in the MIP-FLP. Based on this fact, we propose a methodology that combines the sequence-pair and MIP-FLP model to efficiently solve large continuous-representation-based FLPs. Our heuristic approach searches the sequence-pair solution space and then use the sequence-pair representation to simplify and solve the MIPFLP model. Based on this methodology, we systematically study the different aspects of the FLP throughout this dissertation. As the first contribution of this dissertation, we present a genetic algorithm based heuristic, SEQUENCE, that combines the sequence-pair representation and the most recent MIPFLP model to solve the all-rectangular-department continuous-representation-based FLP. Numerical experiments based on different sized test problems from both the literature and industrial applications are provided and the solutions are compared with both the optimal solutions and the solutions from other heuristics to show the effectiveness and efficiency of our heuristic. For eleven data sets from the literature, we provide solutions better than those previously found. For the FLP with fixed departments, many sequence-pairs become infeasible with respect to the fixed department location and dimension restrictions. As our second contribution, to address this difficulty, we present a repair operator to filter the infeasible sequence-pairs with respect to the fixed departments. This repair operator is integrated into SEQUENCE to solve the FLP with fixed departments more efficiently. The effectiveness of combining SEQUENCE and the repair operator for solving the FLP with fixed departments is illustrated through a series of numerical experiments where the SEQUENCE solutions are compared with other heuristics' solutions. The third contribution of this dissertation is to formulate and solve the FLP with an existing aisle structure (FLPAL). In many industrial layout designs, the existing aisle structure must be taken into account. However, there is very little research that has been conducted in this area. We extend our research to further address the FLPAL. We first present an MIP model for the FLPAL (MIP-FLPAL) and run numerical experiments to test the performance of the MIP-FLPAL. These experiments illustrate that the MIP-FLPAL can only solve very limited sized FLPAL problems. Therefore, we present a genetic algorithm based heuristic, SEQUENCE-AL, to combine the sequence-pair representation and MIP-FLPAL to solve larger-sized FLPAL problems. Different sized data sets are solved by SEQUENCE-AL and the solutions are compared with both the optimal solutions and other heuristics' solutions to show the effectiveness of SEQUENCE-AL. The fourth contribution of this dissertation is to formulate and solve the FLP with non-rectangular-shaped departments. Most FLP research focuses on layout design with all rectangular-shaped departments, while in industry there are many FLP applications with non-rectangular-shaped departments. We extend our research to solve the FLP with nonrectangular-shaped departments. We first formulate the FLP with non-rectangular-shaped departments (FLPNR) to a MIP model (MIP-FLPNR), where each non-rectangular department is partitioned into rectangular-shaped sub-departments and the sub-departments from the same department are connected according to the department's orientation. The effect of different factors on the performance of the MIP-FLPNR is explored through a series of numerical tests, which also shows that MIP-FLPNR can only solve limited-sized FLPNR problems. To solve larger-sized FLPNR problems, we present a genetic algorithm based heuristic, SEQUENCE-NR, along with two repair operators based on the mathematical properties of the MIP-FLPNR to solve the larger-sized FLPNR. A series of numerical tests are conducted on SEQUENCE-NR to compare the SEQUENCE-NR solutions with both the optimal solutions and another heuristic's solutions to illustrate the effectiveness of SEQUENCE-NR. As the first systematic research study on a methodology that combines the sequence-pair representation and the MIP-based FLP, this dissertation addresses different types of continuous-representation based facility layout design problems: from block layout design with and without fixed departments to re-layout design with an existing aisle structure, and from layout design with all-rectangular-shaped departments to layout design with arbitrary non-rectangular-shaped departments. For each type of layout design problem, numerical experiments are conducted to illustrate the effectiveness of our specifically designed family of sequence-pair and MIP-based heuristics. As a result, better solutions than those previously found are provided for some widely used data sets from the literature and some new datasets based on both the literature and industrial applications are proposed for the first time. Furthermore, future research that continues to combine the sequence-pair representation and the MIP-FLP model to solve the FLP is also discussed, indicating the richness of this research domain. / Ph. D.

We present works on theory and applications for Mixed Integer Quadratically Constrained Quadratic Programs (MIQCQP). We introduce new mixed integer programming (MIP)-based relaxation and approximation schemes for general Quadratically Constrained Quadratic Programs (QCQP's), and also study practical applications of QCQP's and Mixed-integer QCQP's (MIQCQP). We first address a challenging tank blending and scheduling problem regarding operations for a chemical plant. We model the problem as a discrete-time nonconvex MIQCP, then approximate this model as a MILP using a discretization-based approach. We combine a rolling horizon approach with the discretization of individual chemical property specifications to deal with long scheduling horizons, time-varying quality specifications, and multiple suppliers with discrete arrival times. Next, we study optimization methods applied to minimizing forces for poses and movements of chained Stewart platforms (SPs). These SPs are parallel mechanisms that are stiffer, and more precise, on average, than their serial counterparts at the cost of a smaller range of motion. The robot will be used in concert with several other types robots to perform complex assembly missions in space. We develop algorithms and optimization models that can efficiently decide on favorable poses and movements that reduce force loads on the robot, hence reducing wear on this machine, and allowing for a larger workspace and a greater overall payload capacity. In the third work, we present a technique for producing valid dual bounds for nonconvex quadratic optimization problems. The approach leverages an elegant piecewise linear approximation for univariate quadratic functions and formulate this approximation using mixed-integer programming (MIP). Combining this with a diagonal perturbation technique to convert a nonseparable quadratic function into a separable one, we present a mixed-integer convex quadratic relaxation for nonconvex quadratic optimization problems. We study the strength (or sharpness) of our formulation and the tightness of its approximation. We computationally demonstrate that our model outperforms existing MIP relaxations, and on hard instances can compete with state-of-the-art solvers. Finally, we study piecewise linear relaxations for solving quadratically constrained quadratic programs (QCQP's). We introduce new relaxation methods based on univariate reformulations of nonconvex variable products, leveraging the relaxation from the third work to model each univariate quadratic term. We also extend the NMDT approach (Castro, 2015) to leverage discretization for both variables in a bilinear term, squaring the resulting precision for the same number of binary variables. We then present various results related to the relative strength of the various formulations. / Doctor of Philosophy / First, we study a challenging long-horizon supply acquisition problem for a chemical plant. For this problem, constraints with products of variables are required to track raw material composition from supply carriers to storage tanks to the production feed. We apply a mixed-integer nonlinear program (MIP) approximation of the problem combined with a rolling planning scheme to obtain good solutions for industry problems within a reasonable time frame. Next, we study optimization methods applied to a robot designed as a stack of Stewart platforms (SPs), which will be used in concert with several other types robots to perform complex space missions. When chaining these SPs together, we obtain a robot that is generally stiffer more precise than a classic robot arm, enabling their potential use for a variety of purposes. Our methods can efficiently decide on favorable poses and movements for the robot that reduce force loads on the robot, hence reducing wear on this machine, and allowing for a larger usable range of motion and a greater overall payload capacity. Our final two works focus on MIP-based techniques for nonconvex QCQP's. In the first work, we break down the objective into an easy-to-handle term minus some squared terms. We then introduce an elegant new MIP-based approximation to handle these squared terms. We prove that this approximation has strong theoretical guarantees, then demonstrate that it is effective compared to other approximations. In the second, we directly model each variable product term using a MIP relaxation. We introduce two new formulations to do this that build on previous formulations, increasing the accuracy with the same number of integer variables. We then prove a variety of useful properties about the presented formulations, then compare them computationally on two families of problems.

The global energy requirement is increasing at a rapid pace and fossil fuels have been one of the major players in meeting this growing energy demand. However, the resources for fossil fuels are finite. Therefore, it is essential to develop renewable energy sources like biofuels to help address growing energy needs. A key aspect in the production of biofuel is the biomass logistics chain that constitutes a complex collection of activities, which must be judiciously executed for a cost-effective operation. In this thesis, we introduce a two-phase optimization-simulation approach to determine tactical biomass logistics-related decisions cost effectively in view of the uncertainties encountered in real-life. These decisions include number of trucks to haul biomass from storage locations to a bio-refinery, the number of unloading equipment sets required at storage locations, and the number of satellite storage locations required to serve as collection points for the biomass secured from the fields. Later, an operational-level decision support tool is introduced to aid the "feedstock manager" at the bio-refinery by recommending which satellite storage facilities to unload, how much biomass to ship, how to allocate existing resources (trucks and unloading equipment sets) during each time period, and how to route unloading equipment sets between storage facilities. Another problem studied is the "Bale Collection Problem" associated with the farmgate operation. It is essentially a capacitated vehicle routing problem with unit demand (CVRP-UD), and its solution defines a cost-effective sequence for collecting bales from the field after harvest. / Master of Science

The presence of substitution among multiple similar products plays an important role in inventory management. It has been observed in the literature that incorporating the impact of substitution among products can substantially improve the profit and reduce the understock or overstock risk. This thesis focuses on exploring and exploiting the impact of substitution on inventory management problems by theoretically analyzing mathematical models and developing efficient solution approaches. To that end, we address four problems. In the first problem, we study different pricing strategies and the role of substitution for new and remanufactured products. Our work presents a two-stage model for an original equipment manufacturer (OEM) in this regard. A closed-form one-to-one mapping of product designs onto the optimal product strategies is developed, which provides useful information for the retailer. Our second problem is a multi-product newsvendor problem with customer-driven demand substitution. We completely characterize the optimal order policy when the demand is known and reformulate this nonconvex problem as a binary quadratic program. When the demand is stochastic, we formulate the problem as a two-stage stochastic program with mixed integer recourse, derive several necessary optimality conditions, prove the submodularity of the profit function, develop polynomial-time approximation algorithms, and show their performance guarantees. Our numerical investigation demonstrates the effectiveness of the proposed algorithms and, furthermore, reveals several useful findings and managerial insights. In the third problem, we study a robust multi-product newsvendor model with substitution (R-MNMS), where both demand and substitution rates are uncertain and are subject to cardinality-constrained uncertainty set. We show that for given order quantities, computing the worst-case total profit, in general, is NP-hard, and therefore, address three special cases for which we provide closed-form solutions. In practice, placing an order might incur a fixed cost. Motivated by this fact, our fourth problem extends the R-MNMS by incorporating fixed cost (denoted as R-MNMSF) and develop efficient approaches for its solution. In particular, we propose an exact branch-and-cut algorithm to solve small- or medium-sized problem instances of the R-MNMSF, and for large-scale problem instances, we develop an approximation algorithm. We further study the effects of the fixed cost and show how to tune the parameters of the uncertainty set. / Doctor of Philosophy / In a multi-product supply chain, the substitution of products arises if a customer's first-choice product is out-of-stock, and she/he have to turn to buy another similar product. It has been shown in the literature that the presence of product substitution reduces the assortment size, and thus, brings in more profit. %and reduce the inventory level. However, how to quantitatively study and analyze substitution effects has not been addressed in the literature. This thesis fills this gap by developing and analyzing the profit model, and therefore, providing judicious decisions for the retailer to make in order to maximize their profit. In our first problem, we consider substitution between new products and remanufactured products. We provide closed-form solutions, and a mapping that can help the retailer in choosing optimal prices and end-of-life options given a certain product design. In our second problem, we study multi-product newsvendor model with substitution. We first show that, when the probability distribution of customers' demand is known, we can tightly approximate the proposed model as a stochastic integer program under discrete support. Next, we provide effective solution approaches to solve the multi-product newsvendor model with substitution. In practice, typically, there is a limited information available on the customers' demand or substitution rates, and therefore, for our third problem, we study a robust model with a cardinality uncertainty set to account for these stochastic demand and substitution rates. We give closed-form solutions for the following three special cases: (1) there are only two products, (2) there is no substitution among different products, and (3) the budget of uncertainty is equal to the number of products. Finally, similar to many inventory management problems, we include a fixed cost in the robust model and develop efficient approaches for its solution. The numerical study demonstrates the effectiveness of the proposed methods and the robustness of our model. We further illustrate the effects of the fixed cost and how to tune the parameters of the uncertainty set.

The objective of this thesis is to demonstrate the use of the Activity-Based Costing (ABC) approach together with the Theory of Constraints (TOC) philosophy in determining the optimal product-mix and restrictive bottlenecks of a company. The contribution of this thesis is a new product-mix decision model that uses activity-based cost information. This new model is proposed to be used with the TOC philosophy in order to improve the financial performance of a company.</p> Four case studies, all of which are based on hypothetical data, are prepared in this research to show the applicability of the proposed model in different manufacturing environments. Specifically, the first case study shows that the conventional product-mix decision model and the model developed in this thesis can give significantly different results regarding the best product-mix and associated bottlenecks of a company. The second case study demonstrates the use of the proposed product-mix decision model in a complex manufacturing environment. Specifically, this case study shows how companies should consider alternatives such as activity flexibility and outsourcing to improve their profitability figures. The third case study is an extension of the second case study, and it is prepared to illustrate that the proposed model can be extended to include more than one time period. The final case study demonstrates the applicability of the proposed model in a lean manufacturing environment.</p> Using the proposed model developed in this research will give managers more accurate information regarding the optimum product-mix and critical bottlenecks of their companies. By applying the TOC philosophy based on this information, managers will be able to take the right actions that will improve the profitability of their companies. Specifically, they will be able to observe the effects of several alternatives, such as activity flexibility and outsourcing, on the throughput of the whole system. In addition, the proposed model should help managers to prevent making decisions that sub-optimize the system. This may occur, for example, when using only the most efficient methods to produce each product even though the capacities of these methods are limited and some other less efficient methods are currently available in the company. By extending the model to include more than one time period, managers will be able to estimate the potential bottlenecks and the amount of idle capacities of each non-bottleneck activity performed in the company ahead of time. This information is powerful and can give companies a substantial advantage over their competitors because the users of the new model will have enough time to improve the performance of their potential bottlenecks and to search for more profitable usage of excess capacities before the actual production takes place. / Master of Science

This dissertation deals with a class of nonconvex mathematical programs called Extreme Point Mathematical Programs (EPMP). These problems are generalizations of certain Integer Programming problems and also find their application in other nonconvex programs like the Concave Minimization problem. The research addresses the design and analysis of algorithms for EPMP. However, most of the ideas are quite general and apply to a wider class of mathematical programs including the Generalized Lattice Point Problem. We obtain a variety of cutting plane algorithms and analyze the convergence of such algorithms. Insightful examples of nonconvergence are also provided. Two finitely convergent algorithms are also presented. One of these is a cutting plane based procedure while the other is a branch and bound scheme. Computational experience with both algorithms is given. / Ph. D.