# Integrated supply chain design under uncertainty

Contents Contents i List of Figures iv List of Tables v Acknowl edgements vi 1 Introduction 1 1.1 Introduction 1 1.2 Literature Review 4 1.2.1 Facility Location Models under Uncertainty 4 1.2.2 Inventory Models under Uncertainty 14 1.2.3 Integrated Supply Chain Design Models 18 2 Supply Chain Network Design wi th Dynami c Mul ti pl e Sourcing 23 2.1 Introduction 23 2.2 Related Literature 25 2.3 Supply Chain Design Problem with Dynamic Sourcing 28 2.3.1 Model Formulation 28 2.3.2 Optimal Inventory Control Policy Given Network Structure 32 2.3.3 Structural Properties 40 2.4 Solution Approach 47 2.4.1 Equivalent Formulation 47 2.4.2 Lagrangian Relaxation Algorithm 49 2.4.3 Multiple Transportation Modes 54 i

2.5 Computational Experiments 56 2.5.1 Performance of Algorithms 56 2.5.2 Effect of Demand Variability 57 2.5.3 Effect of Demand Dependence 65 2.5.4 Trade-off between Flexibility and Cost 67 2.6 Conclusion and Future Research 69 3 Risk-Diversification and Risk-Pooling 72 3.1 Introduction 72 3.2 Related Literature 73 3.3 Problem Description and Basic Formulation 75 3.4 Temporally-Independent Disruptions 77 3.4.1 Model Formulation 77 3.4.2 Model Properties 79 3.4.3 Solution Approach 82 3.5 Temporally-Dependent Disruptions 88 3.5.1 Model Formulation 88 3.5.2 Solution Approach 93 3.6 Computational Results 94 3.6.1 Effect of Disruption Probabilities 95 3.6.2 Effect of Risk-Aversion 97 3.7 Conclusion and Future Research 98 4 Analytical Study on Sourcing Flexibility 101 4.1 Introduction 101 4.2 Related Literature 104 4.3 Model Development 106 4.3.1 Problem Description 106 4.3.2 Design Cost Components 109 4.3.3 Tactical Cost Components 109 4.3.4 Operational Cost Components 110 4.4 Model Analysis 112 4.4.1 Total Cost Function and Optimal Solution 112 4.4.2 Effect of Flexibility Level 117 ii

4.4.3 First and Second-Order Inventory Sharing 118 4.4.4 Trade-off between Inventory and Shipping Costs 119 4.4.5 Comparative Statics 119 4.5 Solution without Flexibility 125 4.6 Benefits of Integrated Optimization 128 4.7 Conclusion and Future Research 131 5 Ti me-Based Service Requirements in Spare Parts Systems 134 5.1 Introduction 134 5.2 Related Literature 136 5.3 Model Formulation 138 5.3.1 Basic Formulation 138 5.3.2 Inventory Level at the Plant 143 5.3.3 Inventory Level at SCs 144 5.4 Solution Approach 147 5.4.1 Obtaining a Lower Bound 147 5.4.2 Obtaining an Upper Bound 156 5.4.3 Detecting Infeasibility 158 5.4.4 Summary of Lagrangian Relaxation Algorithm 159 5.5 Scenario-Based Model 160 5.6 Computational Results 165 5.6.1 Experimental Setup 165 5.6.2 Algorithmic Performance 165 5.6.3 Effects of Response Time Requirement and Penalty Cost 166 5.6.4 Trade-off Between Response Time and Cost 167 5.6.5 Benefits of Using Integrated Model 169 5.6.6 Comparisons with One-Echelon Systems 171 5.6.7 Results for Scenario-Based Problem 171 5.7 Conclusion and Future Research 174 Bibliography 177 A Definition of Stochastic Orders Used in Chapter 2 187 B Approxi mate Formula for a Transportation Probl em 190 in

List of Figures 2.1 Sequence of Events 30 2.2 Effect of Demand Variability 59 2.3 Example Solution for 30-City Problem 63 2.4 Effect of the Length of the Planning Horizon 64 2.5 Effect of Demand Dependence 66 2.6 Trade-off Between Cost and Flexibility 68 3.1 Effect of Disruption Probability 96 3.2 Example Solution for 30-City Problem with Disruptions 97 3.3 Effect of Risk-Aversion 99 4.1 Segment of Service Region with Square-shaped Primary Influence Areas . . 107 4.2 Approximating Line-Haul Routing Cost by Considering Four Sub-Zones Sur rounding Each DC I l l 4.3 Typical Shape of the €(N\S) Function 117 4.4 Differences between Solutions with and without Dynamic Sourcing 128 5.1 Optimal Costs of Using Penalty Cost and Response Time Constraint to Achieve a Certain Average Response Time 168 5.2 Trade-off Curve of Optimal Cost vs Response Time Requirement 169 5.3 Optimal Costs and Base Stock Levels of Using Integrated and Sequential Approaches 170 5.4 Costs of One-Echelon and Two-Echelon Systems 172 5.5 Expected Cost vs Service Time for Scenario-Based Problem 174 B.l Actual versus Fitted Values for /(.) Function 192 iv

List of Tables 2.1 Computational Performance 58 4.1 Effect of Input Parameters 121 4.2 Parameters of Simulation Study 131 4.3 Simulation Results 131 v

Ac knowl e dge me nt s I warn very grateful to my advisor Max Shen who guided my path to becoming a researcher. Through him I have gained an understanding of the academic profession and learned how to plan for my future research and career. I would like to thank him for giving me his trust and various opportunities, without which I would not be ready for the next stage. I am proud to have a strong and supportive thesis committee. Carlos Daganzo is a great scholar and a great person whom I always enjoy talking to. From him I learned a lot on how to approach problems from different angles. This is important not just in research but all aspects of life as well. I would like to take this chance to thank Mark Daskin for all his generous support since my undergraduate years at Northwestern. This path would not have been possible for me without all his help and guidance. I am also very grateful to Candi Yano for sparing so much of her precious time helping me prepare for my job search and improve the thesis. I am thankful to all the faculty members and students at the Department of Industrial Engineering and Operations Research at Berkeley. They have created a productive and encouraging environment to pursue graduate studies. My thanks also go to all the friends that I have met at Berkeley and Northwestern. They make the past eight years a very enjoyable journey. The strongest support for me has always come from my family. Regardless of what career path I choose, they have given me unreserved encouragement and backing. Last but definitely not least, special thanks go to Pui-Shan Ng, for all her patience, support and love. VI

Curriculum Vitae Ho Yin Mak Educati on 2005 2006 2009 Northwestern University B.S., Industrial Engineering and Management Sciences University of California, Berkeley M.S., Industrial Engineering and Operations Research University of California, Berkeley Ph.D., Industrial Engineering and Operations Research Per sonal Born January 28, 1982, Hong Kong Ho Yin Mak was born and raised in Hong Kong. Upon completion of secondary school (i.e., high school), he pursued higher education in the United States. In 2005, he graduated magna cum laude from Northwestern University, completing major requirements for both Industrial Engineering & Management Sciences and Economics. From 2005 to 2009, Ho Yin pursued graduate studies at the University of California, Berke ley. During this period, he completed a Master's degree in Industrial Engineering & Op erations Research. He also completed minor requirements in Transportation Engineering and Economics. In May 2009, Ho Yin completed his thesis titled "Integrated Supply Chain Design Under Uncertainty" under the supervision of research advisor Professor Zuo-Jun Max Shen. vn

viii

Chapter 1 Introduction 1.1 Introduction Supply chain management (SCM) is denned as the set of approaches utilized to efficiently integrate suppliers, manufacturers, warehouses, and stores, so that merchandize is produced in the right quantities, distributed to the right locations, and at the right time, in order to minimize system-wide costs (or maximize profits) while satisfying service level requirements (Simchi-Levi et al. 2003). Loosely speaking, SCM is the collection of practices that enable the efficient flow of information, materials and goods to meet customer demand. For a given supply chain structure, much research effort has been spent on identifying the best practices to make the flows efficient. However, one essential condition for these practices to be successful is that there exists a well-designed supply chain network. If the highway network in a city is poorly designed, road users will suffer congestion no matter how efficiently the traffic is routed. Similarly, if a supply chain is not carefully designed, even the best SCM methodologies will have limited effectiveness. Supply chain design is a critical and difficult decision. It involves choosing which prod ucts to manufacture, which markets to serve, what technology to acquire or develop, which suppliers to source from, where to locate plants and warehouses and which facilities to use to serve different markets. Most of these decisions are strategic in nature. Once made, they 1

continue to impact the firm's operations for the next few years or even decades. They also involve high fixed costs of investment, such as the cost of building a factory or acquiring a certain technology. Because of the strategic and irreversible nature of SCD decisions, long-term forecasts are extremely important. However, it is well known that forecasts are always less accurate with longer forecast horizons. Even with state-of-the-art forecasting technologies, it is impossible to perfectly anticipate the future environmental conditions over a long period. The success of a supply chain depends heavily on the business environment, including the uncertainty of future demand and supply, competitive environment and tax and government policy, among others. It is critical that all these factors and the associated impacts on profits and costs be carefully evaluated in the supply chain design phase. Unfortunately, the unavailability of perfect forecasts makes this task a challenge. Researchers have studied the use of various tactics to adapt to uncertainty. Tomlin (2006) classified tactics to adapt to supply uncertainty into two categories: mitigation and contingency. We may generalize his definition to include other types of uncertainty as well. Mitigation tactics are those in which the firm takes action in advance and incurs a cost to prepare for uncertainty. Holding safety stock is an example of a mitigation tactic to adapt to uncertain demand. In contrast, contingency tactics are those in which the firm takes action after some event occurs. For example, emergency inventory transshipment during stock-outs can be regarded as a contingency tactic to adapt to demand uncertainty. Traditionally, researchers and practitioners tackle the problem of designing physical supply chain structures using facility location models. Early models focus on optimizing system configurations under deterministic settings (e.g., the classical covering, median and fixed charge problems). More recently, researchers have been developing modeling method ologies to support facility location decisions under uncertainty. Many of these approaches, including robustness and reliability modeling, attempt to construct a network that performs reasonably well under all or most anticipated scenarios. However, the vast majority of these models do not consider mitigation and contingency 2

tactics adequately. Most stochastic and robust facility location models consider making facility location decisions before uncertain parameters are realized, and demand assignment decisions after the realization. Implicitly, this considers the cost of the contingency tactic of rerouting demand. However, the common assumption made is that any demand assignment is feasible, which is unreasonable since facilities have limited capacities. One other example is the work by Shen et al. (2003) who incorporate inventory risk- pooling effects into a facility location model. Risk-pooling (Eppen 1979) has long been studied and widely used in practice as a tactic to mitigate demand uncertainty. The authors argue that, without considering the tactical decisions in the design phase, the resulting network configuration will be sub-optimal. In their model, the effect of inventory risk- pooling enables cost savings if more demand sources are pooled together. This tends to reduce the optimal number of facilities opened. The above result has an important implication: sub-optimality will result from ignoring the possibilities and costs of mitigation and contingency tactics in the strategic design phase. Mitigation tactics such as inventory risk-pooling typically impact costs and therefore affect the optimal network structure. The possibility of using contingency tactics may have even heavier implications on the network structure, as many of these tactics rely on the existence of "slacks" in the network to be successful. For instance, contingency rerouting of a demand from a plant that has broken down to an alternative plant requires excess capacity at the second plant. The Shen et al. (2003) paper is an example of research in integrated supply chain design that has emerged in the literature recently. The main idea of integrated decision making is as follows. Since facility location decisions are difficult to reverse and carry long-lasting impacts on future supply chain management, it is important to factor in how the supply chain will be managed (i.e., incorporating tactical and operational decisions) under the network configurations being considered. The inclusion of costs incurred in the tactical and operational phases makes the objective function a better indicator of overall supply chain performance. Therefore the integrated approach yields facility location decisions of better quality. However, as we shall argue in the literature review section, the existing integrated 3

supply chain design literature does not adequately address mitigation and even less so, contingency tactics, under supply and demand uncertainty. Under uncertainty, it is clear that having "slacks" and therefore flexibility of applying contingency tactics in the supply chain is beneficial. Having extra capacity at nodes and adding extra arcs between nodes can enhance the efficiency of flows along the network under an uncertain environment. This can not only lower expected operational costs, but also enhance service level. The amounts of "slacks" at various locations in the supply chain are therefore determining factors of the chain's efficiency. On the other hand, adding these "slacks" will also increase the cost of investment. Therefore, there is a trade-off between strategic investment cost and operational efficiency. There has been little research on this trade-off in the literature. The focus of this thesis will be on enriching the integrated supply chain design literature by explicitly modeling the use of mitigation and contingency tactics, as well as incorporating the resulting costs and service levels. 1.2 Literature Review 1.2.1 Facility Location Models under Uncertainty The literature on facility location theory is rich, dating back to the Weber problem (Weber, 1957) which was originally formulated in 1909. Daskin (1995), Drezner (1995) and Drezner and Hamacher (2002) provide excellent introductions to and surveys of the development in the field. This thesis will mainly focus on facility location models under future uncertainty. Snyder (2006) provides an excellent and comprehensive survey of this subfield. Instead of replicating what has already been reviewed by Snyder (2006), we discuss a few important modeling approaches used in the literature and comment on their relative strengths and weaknesses. 4

Robust Location Model s This class of models applies techniques from robust optimization theory to facility loca tion problems. For an introduction to robust optimization, see Kouvelis and Yu (1997). In this class of models, uncertainties are typically defined using a set of possible realizations of the input parameters (e.g., costs and demand). The set of possible realizations can be discrete or continuous. In the discrete case, the set of possible outcomes can be represented by a finite set of distinct scenarios. In the continuous case, typically a "possible" range is defined for each uncertain parameter. In this case, the set of possible scenarios is infinite and defined by all combinations of parameter realizations within the defined intervals. In robust models, no probability distributions are assumed on the uncertain parameters. The objective functions in the majority of robust location models involve optimizing the worst-case outcome, often defined to be the worst value across all scenarios of (i) cost, (ii) absolute regret or (iii) relative regret. The first case is known as the minimax (or min-max) cost approach. The objective of the model is: min u x€X,u€M. subject to: z(x\s) < u for any s G S In the above, X is the set of feasible solutions, S is the defined "possible" set of param eter realizations and z(x\s) is the cost of solution x under parameter realization 5. Serra and Marianov (1998) use the minimax cost approach to formulate a P-median-like model to locate fire stations in the city of Barcelona. The uncertainty in parameters is defined using a set of discrete scenarios. An exchange-based heuristic is proposed to solve the problem. In the latter two approaches, the concept of regret is used. The absolute regret under a scenario is defined as the difference between the cost of the chosen solution under the scenario in question and the optimal cost under the same scenario, i.e., the case if the planner 5

could perfectly anticipate in advance that the scenario will occur without uncertainty. The relative regret under a particular scenario is denned as the absolute regret divided by the optimal cost under the scenario. Letting Xs denote the optimal solution under scenario s (under no uncertainty), the minimax absolute objective is defined as: min u x€X,u€M subject to: z(x\s) — z(xs\s) < u for any s S S The minimax relative regret objective is defined as: min u x6X,u€K subject to: z(x\s) - z(xs\s) v ' '—--r—— < u for any s € S z(xs\s) Serra and Marianov (1998) also formulate and solve minimax absolute and relative regret versions of the P-median-like model. An example of a minimax regret problem with continuous (interval) uncertainty is formulated by Averbakh and Berman (1997). They study a minimax absolute regret version of the classical weighted P-center problem on a general network with weights (demand) uncertain and defined on continuous intervals. They prove that the problem can be decomposed into n + 1 P-center problems, where n is the number of nodes on the network. Minimax regret (absolute or relative) is not equivalent to minimax cost, although Sny der (2006) shows that minimizing expected regret is equivalent to minimizing expected cost. The minimax cost approach attempts to optimize the worst case monetary perfor mance. This is suitable if the manager mostly cares about avoiding large losses. The major shortcoming of this approach is that the objective value will be dominated by extremely unfavorable scenarios, i.e., those in which monetary performance will be very bad no matter what action is taken. Since only the worst scenario is considered, the minimax cost solution may forgo possible large improvements in many other scenarios because of one dominating 6

unfavorable scenario. For a simple example, consider a case with two possible scenarios (A and B) and two feasible solutions (1 and 2). The cost under scenario A is either $10000 (solution 1) or $10001 (solution 2) and that under scenario B is $9000 (solution 1) or $5000 (solution 2). It is clear that solution 2 is almost always preferred since it saves $4000 in scenario B and costs only $1 more in scenario A. However, solution 1 is the optimal solution under the minimax cost objective because scenario A is dominating. In contrast, regret objectives focus on the potential for improvements. The difference between the optimal cost and the cost under the chosen solution measures the amount of cost reduction that can possibly be achieved in the scenario. Therefore the absolute regret represents the largest forgone potential for improvement in terms of monetary performance. In the previous example, the optimal solution under the minimax regret objective is solu tion 2 which is more sensible. A shortcoming of the minimax absolute regret objective is that scenarios with high costs (which often have high absolute regret values as well) will dominate. Consider the following example: the cost under scenario A is $10000 (solution 1) and $10100 (solution 2), and that under scenario B is $199 (solution 1) or $100 (solution 2). Scenario A has higher cost and absolute regret value. The minimax absolute regret so lution is solution 1. However, the relative improvement of choosing solution 1 over solution 2 is small (which improves cost by 1%), in comparison to that of choosing solution 2 over solution 1 in scenario B (which improves cost by 99%). In many situations, the relative regret objective yields more sensible solutions (solution 2 in this example). Overall, the major advantage of the minimax approach is that the absolute worst case is optimized. Then under all other anticipated scenarios, the performance is bounded below by the tightest possible bound. This approach caters to decision makers who are pessimistic and want to plan for the absolute worst case. However, being "too pessimistic" is also the major problem of the minimax approach. Optimizing the worst outcome tends to generate a solution in which the performance is uniform over all scenarios. The average case performance may be sacrificed in order to avoid the worst case scenario that may be extremely unlikely to occur. One problem with the robust approach is that it weighs all possible scenarios equally. 7

This is the most conservative approach taken given that there is not enough available data to define meaningful probability distributions on the outcome. However, even in the absence of detailed probabilistic information, the firm would always prefer to perform better under certain scenarios considered as "important" and willing to sacrifice the performance under other "unimportant" ones. In fact, optimizing the weighted performance across scenarios is equivalent to assuming a probability measure on the defined scenarios and optimizing an expected utility function. A few approaches have been taken to avoid focusing on the absolute worst case. For example, the a-reliable framework defines a subset of scenarios called the a-reliable set and minimize the worst cost or regret within this set. The a-reliable set is defined endogenously such that the total probability that the regret falls below the objective value is at least a, a level specified by the user. A reason for doing this is that the worst possible case has a low probability of occurring (less than 1 — a) and we do not want such a highly unlikely event to alter the decision by too much. An example is that an airport is never designed for the absolute peak demand (e.g., the Sunday following Thanksgiving) because the cost of doing so is so high and such high capacity is needed only for one or two days in a year. Daskin et al. (1997) formulate a new version of the P-median problem minimizing the minimax regret within the a-reliable set and evaluate the trade-off between having a higher value of a (probability that the regret will not exceed the optimal objective value) and having lower maximum regret. It turns out that the a-reliable objective is equivalent to the a-quantile, i.e., the Value at Risk (VaR). A shortcoming of this risk measure is that it does not consider anything beyond the a-quantile and therefore does not distinguish between a long tail and a short tail. To address this problem, it is possible to use a risk measure known as conditional value at risk (CVaR). The a-CVaR is the conditional expectation of losses above the a-VaR (Rockafellar and Uryasev 2000), i.e., the expected excess regret associated with outcomes outside the a-reliable set. Applying this with a regret objective, Chen et al. (2006) formu late the a-reliable mean excess regret version of the P-median model and compare it with the Daskin et al. (1997) model. With the CVaR objective, we know that with probability 8

of at least a, the regret will be less than the optimal objective value, and with probability 1 — a, the conditional expectation of the regret is equal to the optimal objective value. They show that the CVaR model is much easier to solve than the a-reliable model under a large number of scenarios. The notion of p-robustness is first introduced by Kouvelis et al. (1992) in a facility layout problem. A p-robust solution is one in which the maximum relative regret in any scenario does not exceed p > 0. Snyder and Daskin (2006) study the p-robust versions of the median and fixed charge problems. These models are structurally the same as the straightforward scenario-based extension of the deterministic models, except that p-robust constraints are added. The authors propose Lagrangian relaxation algorithms for both problems that produce tight optimality bounds. Although p-robustness allows the optimization of expected performance while ensuring that the regret would not be excessive, it adds complications concerning feasibility. Snyder and Daskin (2006) show that the feasibility problem for the p-robust median model is iVP-complete. They embed an efficient method for detecting infeasibility early into their algorithms. Another important issue in robust location models is the definition of "possible" sce narios. Most papers model uncertainty using discrete scenarios or possible intervals for parameters. However, both techniques are somewhat questionable. Firstly, defining a "pos sible" interval for a parameter is problematic. How can we know for sure that the demand at a certain retailer is between 1000 units and 10000 units, but not 900 or 10100 units? Likewise, defining all distinct possible scenarios is impossible. Even coming up with the "meaningful" scenarios relies heavily on expert judgment. Some scenarios are so unlikely to happen that they can be regarded as "impossible" even by experts. Yet the consequences of such events can be catastrophic. For example, it is unlikely that anyone anticipated the complete collapse of the World Trade Center as a "possible" scenario in business planning before September 11th. To avoid the above problem, alternative techniques are adopted in special problem set tings. To model disruptions, Church et al. (2004) formulate the median and covering interdiction problems to identify critical facilities. Their idea is to identify the worst case 9

by solving an optimization problem to maximize the median and covering objectives after disrupting a subset of given facilities, as if an attacker were choosing a subset of facilities to attack so as to generate the largest loss. The resulting r-interdiction covering and me dian models are solved using the CPLEX integer programming solver. Building upon this technique, Church and Scaparra (2007) and Scaparra and Church (2008) consider fortifying a subset of q existing facilities. The enemy is then assumed to choose r of the remaining facilities to attack, maximizing the resulting median objective after the disruption. They show that fortifying the facilities identified in the r-interdiction model is not optimal. Fi nally, Scaparra and Church (2008) formulate the fortification-interdiction problem as a two-person sequential game. The resulting model is solved using a bi-level programming branch-and-bound algorithm. Stochastic Location Model s Besides Snyder (2006), Owen and Daskin (1998) also provide a survey of stochastic as well as dynamic facility location research. Unlike robust models discussed above, stochastic location models assume probability distributions on the uncertain outcome. The distri butions can either be discrete or continuous. In the discrete finite set of distinct scenarios can be defined as in the robust models. In the continuous case, the uncertain pa rameters are assumed to follow certain probability distributions. Unlike the robust models that require uncertain parameters to be bounded in the continuous case, the parameters in stochastic models can have infinite support (e.g., normal distribution). Typically, stochastic location models are formulated as two-stage stochastic program ming problems with recourse. Birge and Louveaux (1997) provide a textbook treatment of stochastic programming. In two-stage problems, some decisions are made in the first stage based on probabilistic information before uncertainty is realized. Then after the random parameters are realized and observed, second-stage (recourse) decisions are made. In the facility location setting, the first-stage decisions are location decisions (i.e., where to locate facilities) and the second-stage decisions involve demand assignment. Let S denote the set of scenarios, qs denote the probability of scenario s happening and superscript s denote the 10