Optimization Problems in Supply Chain Management

The goal of this thesis is the study of optimization models, which integrate both transportation and inventory decisions, to search for opportunities for improving the logistics distribution network. In contrast to Anily and Federgruen, who also study a model integrating these two aspects in a tactical-operational setting, we utilize the models to answer strategic and tactical questions. We evaluate an estimate of the total costs of a given design of the logistics distribution network, including production, handling, inventory holding, and transportation costs. The models are also suitable for clustering customers with respect to the warehouses, and through this they can be used as a first step towards estimating operational costs in the logistics distribution network related to the daily delivery of the customers in tours. The main focus of this thesis is the search for solution procedures for these optimization models. Their computational complexity makes the use of heuristics solution procedures for large-size problem instances advisable. We will look for feasible solutions with a class of greedy heuristics. For small or medium-size problem instances, we will make use of a Branch and Price scheme. Relevant characteristics of the performance of a solution procedure are the computation time required and the quality of the solution obtained if an optimal solution is not guaranteed. Conclusions about these characteristics are drawn by testing it on a collection of problem instances. The validity of the derived conclusions strongly depends on the set of problem instances chosen for this purpose. Therefore, the second focus of this thesis is the generation of experimental data for these optimization models to test these solution methods adequately. The well-known generalized assignment problem (GAP) can be seen as a static model to evaluate a two-level logistics distribution network where production and storage take place at the same location. Moreover, some of the dynamic models analyzed in this thesis can be reformulated as a GAP with a nonlinear objective function. Therefore, we will devote Part II of the thesis to studying this problem. In Parts III and IV we will study variants of a multi-period single-sourcing problem (MPSSP) that can be used for evaluating logistics distribution network designs with respect to costs in a dynamic environment. In particular, Part III is dedicated to the analysis of a logistics distribution network where production and storage take place at the same location and only the production capacity is constrained. In Chapter 10, we will separately add di_erent types of capacity constraints to this model. In particular, we will analyze the addition of constraints with respect to the throughput of products and the volume of inventory. Furthermore, we will analyze how to deal with perishable products. In Chapter 11, we will study models in which the production and storage levels are separated. In Parts III and IV, the customers' demand patterns for a single product are assumed to be known and each customer needs to be delivered by a unique warehouse in each period. The decisions that need to be made are (i) the production sites and quantities, (ii) the assignment of customers to facilities, and (iii) the location and size of inventories. These decisions can be handled in a nested fashion, where we essentially decide on the assignment of customers to facilities only, and where the production sites and quantities, and the location and size of inventories are determined optimally as a function of the customer assignments. Viewed in this way, the MPSSP is a generalization of the GAP with a convex objective function, multiple resource requirements, and possibly additional constraints, representing, for example, throughput or physical inventory capacities, or perishability of the product. To be able to deal with many variants of the MPSSP using a single solution approach, we will introduce in Chapter 2 a general class of convex capacitated assignment problems (CCAP's). A distinguished member of this class is the GAP. As mentioned above, we are concerned with adequately testing solution procedures for the CCAP. Therefore, we will introduce a general stochastic model for the CCAP, and derive tight conditions to ensure asymptotic feasibility in a probabilistic sense. To solve the CCAP, we have proposed two di_erent solution methods. Firstly, we have generalized the class of greedy heuristics proposed by Martello and Toth [88] for the GAP to the CCAP and we have proposed two local exchange procedures for improving a given (partial) solution for the CCAP. Secondly, we have generalized the Branch and Price scheme given by Savelsbergh for the GAP to the CCAP and have studied the pricing problem for a particular subclass of CCAP's for which bounds can be e_ciently found. Throughout Parts II-IV our goal will be to analyze the behaviour of the solution methods proposed in Chapter 2. We will show asymptotic feasibility and optimality of some members of the class of greedy heuristics for the CCAP for the particular case of the GAP. Similar results will be found for many variants of the MPSSP. We will show that the Branch and Price scheme is another powerful tool when solving MPSSP's to optimality. Our main concern will be to identify subclasses of these optimization models for which the pricing problem can be solved efficiently. The outline of the thesis is as follows. In Chapter 2 we introduce the class of CCAP's and present a general stochastic model for the CCAP and tight conditions to ensure asymptotic feasibility in a probabilistic sense. Moreover, we introduce a class of greedy heuristics and two local exchange procedures for improving a given (partial) solution for the CCAP, and a Branch and Price scheme together with the study of the pricing problem for a subclass of CCAP's. Part II is devoted to the study of the GAP which, as mentioned above, is a static model to evaluate two-level logistics distribution networks where production and storage take place at the same location. In Chapter 3 we show that the GAP belongs to the class of CCAP's, summarize the literature devoted to this problem, and we present some properties of the GAP which will be used in the rest of Part II. In Chapter 4 we analyze almost all the random generators proposed in the literature for the GAP and we numerically illustrate how the conclusions drawn about the performance of a greedy heuristic for the GAP di_er depending on the random generator used. In Chapter 5 we show that, for large problem instances of the GAP generated by a general stochastic model, two greedy heuristics, defined by using some information of the LP-relaxation of the GAP, find a feasible and optimal solution with probability one. Part III is devoted to the study of a class of two-level MPSSP's where production and storage take place at the same location and only the production capacity is constrained. In Chapter 6 we introduce this class, we show that it is contained in the class of CCAP's, and we present some properties which will be used in the rest of this part. In Chapter 7, as for the GAP, we find explicit conditions to ensure asymptotic feasibility in the probabilistic sense for some variants of the MPSSP. In Chapter 8 we show that, for large problem instances of the MPSSP generated by a general stochastic model, a greedy heuristic, defined by using some information of the LP-relaxation of the MPSSP, finds a feasible and optimal solution with probability one for some variants of the MPSSP, as for the GAP. In Chapter 9 we analyze the pricing problem for the MPSSP and we propose a class of greedy heuristics to find feasible solutions for the pricing problem. In Part IV we extend the model proposed in Part III in two directions. In Chapter 10 we show that the MPSSP with three di_erent types of additional constraints, namely throughput capacity, physical capacity and perishability constraints, can still be reformulated as a CCAP and we apply the results derived for the CCAP. In Chapter 11 we study three-level logistics distribution networks in which the plants and the warehouses have been decoupled, we show that these models can be almost reformulated as CCAP's, and that, except for the Branch and Price scheme, all the results derived for the CCAP still hold for these models. We end the thesis in Chapter 12 with a summary and some concluding remarks.