Column Generation II - Application in Distribution Network Design

Column Generation II : Application in Distribution Network Design 1 Supply Chain Challenges 1.1 Introduction Slide 1 Network of facilities: procurement of materials, transformation of these materials into intermediate and finished products, and the distribution of these finished products to customers. 1.1.1 Distribution Network Slide 2 Distribution Network Design looks at strategies to distribute finished products to customers efficiently at lowest cost - a difficult but important problem N1 • Factory storage with drop shipping • Warehouse storage with package carrier delivery • Local storage with last mile delivery • Factory or Warehouse storage with consumer pickup • Local storage with consumer pickup Note 1 Delivery Options • Drop shipping refers to the practice of shipping directly from the manufacturer to the end consumer, bypassing the warehouse who takes the order and initiates the delivery request. Delivery costs tend to be high with this option, but it eliminates the need to setup and manage warehouse delivery operations. • In warehouse storage with package carrier delivery, the customers request are met from a few centralized warehouse strategically located in the region. Transportation cost tends to be lower than the previous option, but inventory holding and warehouse management costs increase. 1 • In the local storage with last mile delivery option, more warehouses need to be setup and spread across the region (leading to higher warehouse and inventory cost), but transportation cost will be lower. • In the factory/Warehouse storage with consumer pickup approach, inventory is stored at the factory or warehouse but customers place their orders online and then go to designate pickup points to collect their orders. Inventory and warehousing cost will be low due to demand aggregation at the factory. however, new pickup sites have to built, leading to higher facility costs. A significant information infrastructure is also needed to provide visibility of the order until the customer picks it up. • In the last option, inventory is stored locally at a warehouse (or retail outlet) nearby. Customers either walk into the warehouse/retail outlet or place an order online or on the phone and pickup at the warehouse/retail store. Local storage increases inventory costs but transprotation cost reduces. This option is more suitable for fast moving goods so that there is only marginal increase in inventory even with local storage. Slide 3 How to set up the distribution network to move products from the factory to the customers? 2 Network Design 2.1 2.1.1 Issues Location Slide 4 Distribution Centers (DC): An intermediate storage location for stocking of finished products for subsequent shipment to customers. • Economy of scale in bulk shipping from factory in DC 2 • Faster response time to ship from DC, rather than to ship from factory direct. Location choices for the distribution centers? • Different sites may have different facility fixed cost structures 2.1.2 Transportation • Transportation Cost: depends on which DC is being used to serve the customer. Slide 5 • Outbound Transportation cost • Inbound Transportation cost Distribution center Retailer Retailer Plant Distribution center Transportation cost depends on distance shipped. Figure by MIT OCW. 2.1.3 Storage and Material Handling Warehousing and Material handling Cost: packaging, order-picking, replenishment. Depends on the volume of business served. Slide 6 $ Volume of Demand fj Figure by MIT OCW. 2.1.4 Safety Stock Inventory Inventory Management refer to means by which inventories are managed. Inventories exist at every stage of the supply chain as 3 Slide 7 • raw materials, • semi-finished, • finished goods, • in-transit between locations. Slide 8 • Replenishment Lead Time: Time from order is being placed to time when shipment is received. • To protect against stock out, company normally keeps excess inventory (called Safety Stock) to protect itself against stockout during the replenishment lead time. Slide 9 • Safety Stock: Excess above the expected lead time demand. Their primary purpose is to buffer against any uncertainty that might exist in the supply chain. But they cost $$$. • Safety stock (SS) level depends on the standard deviation (SD) of the lead time demand (denoted by σ). Eg. SS = 3σ indicate a close to 99.7% safety protection against stockout. Goal: To maintain high service level with the least safety stock investment 2.2 Comparison Slide 10 No. of DCs Fixed Cost Transportation Cost Handling Cost Safety Stock Cost 4 Few Many 2.3 The Problem Slide 11 • Find – Number and location of DCs – Assignment of customers to DCs • To minimize – Transportation costs: From factory to DC; DC to customers – Inventory (i.e., safety stock) costs at DCs – Warehousing and material handling cost. 2.4 Inputs and Parameters Slide 12 • W : set of potential DC locations • I: set of customer locations • µi : mean (yearly) demand at customer i • σi2 : variance of (daily) demand at customer i • Operating Cost – fj : fixed (annual) cost of locating a distribution center at location j – dij : cost per unit to ship from DC j to customer i – aj : per unit shipment cost from factory to distribution center j – Lj : Replenishment lead time for DC j – h: inventory holding cost per unit of product per year 2.5 Cost Model Slide 13 Decision Variables • Xj = 1, if customer j is selected as a distribution center location, and 0, otherwise • Yij = 1, if customer i is in served by a distribution center j, and 0, otherwise Cost: Suppose customers in set S is served by DC j. • Transportation cost for this set of customers � � � � (µi × dj,i + µi × aj ) = Yij (µi × dj,i + µi × aj ) i i∈S • Warehousing/Material handling cost � f j X j + Γj ( µi Yij ). i 5 • Safety Stock Inventory Cost � 3h Lj �� i 2.6 σi2 Yij . Complete Model �� � �� � �� � 2 ˆ min dij Yij + θΓj µi Yij + θqj σi Yij fj Xj + β j∈W i∈I subject to i∈I � Slide 14 i∈I Yij = 1, Yij − Xj ≤ 0 Xj ∈ {0, 1} Yij ∈ {0, 1}, j∈I • β and θ are weightage factors that we will adjust for computational testing. • dˆij = βµi (dj,i + aj ) � • qj = 3h Lj • Γj (·) is concave and non-decreasing Not surprisingly, this problem is NP-hard. 2.7 Set-Covering Model • Decision variables: Let zj,R = 1 if DC j is used to serve the customers in the set R. Slide 15 • Constraints: Each customer must be served by one DC. Hence we want to find a partition of the entire customer set into (R1 , . . . , Rk ) and the corresponding DC assignment (j1 , . . . , jk ). DC jl will be used to serve the customers in Rl . • Cost of using DC j to serve customers in R: cj,R = fj + β � �� � � ˆ dij + θΓj ( µi ) + θqj σi2 i∈R i∈R Let R denote the set of all subsets of customers. � � min c z �j∈W� R∈R j,R j,R subject to j∈I R∈R:i∈R zj,R ≥ 1, zj,R ∈ {0, 1}, ∀ j, R. i∈R Slide 16 ∀i ∈ I, The optimal solution actually gives rise to a partition of the customers. N2 Note 2 Covering=Partition 6 The set covering model proposed above can be shown to be equivalent to the following set-partitioning model: � � c z min � � j R∈R j,R j,R subject to ∀i ∈ I, j∈I R∈R:i∈R zj,R = 1, zj,R ∈ {0, 1}, ∀ j, R. This follows from monotinicity of the cost function cj,R , i.e., if S ⊂ T , cj,S ≤ cj,T . Hence all optimal 0-1 solution to the set covering model must be a solution to the set partitioning model. Slide 17 Example: W = {a, b}, I = {1, 2}. min ca,1 za,1 s.t. za,1 + + za,1 , 2.7.1 cb,1 zb,1 zb,1 + + zb,1 , ca,2 za,2 + cb,2 zb,2 + za,2 za,2 , + zb,2 zb,2 , + ca,12 za,12 za,12 za,12 za,12 , + + + Column Generation • Number of variables in the formulation = |W | × 2|I| . Huge! cb,12 zb,12 zb,12 zb,12 zb,12 Slide 18 • We solve the LP relaxation of the set covering model using column generation • Given a set of dual prices π ¯ (obtained by solving the restricted master problem), to find a column with negative reduced cost, we need to solve the following pricing problem: � – Is there any S with cj,S − i∈S πi < 0? Slide 19 To answer this question, we solve: min(cj,S − S i.e., πi ), i∈S � �� � � � ˆ (βdij − πi ) + θΓj ( µi ) + θqj σi2 min fj + S 2.7.2 � i∈S i∈S i∈S Pricing Problem Slide 20 For designated distribution center j ∈ I, define min gj (S) ≡ S⊂I � �� � ai + θΓj ( bi ) + θqj ci . i∈S i∈S 7 i∈S ≥ ≥ ≥ 1 1 0 where ai bi ci ≡ dˆij − πi , ≡ µi ≥ 0, ≡ σi2 ≥ 0. WLOG: ai < 0 for all i. Otherwise, i will not be in the optimal S. Slide 21 • There are 2|I| possible choices of S. • Impossible to enumerate over all possible S. General form of the pricing problem: � � � min h1 ( ai ) + h 2 ( b i ) + h3 ( ci ) S i∈S i∈S i∈S where h1 , h2 , h3 are concave, non-decreasing functions. Proposition: Slide 22 � � • Consider the convex hull C in 3D formed by the points ( i∈S ai , i∈S bi , � i∈S ci ), for all subset S. • Let S ∗ be an optimal solution to our pricing problem �� � � min gj (S) ≡ ai + θΓj ( bi ) + θqj ci . S⊂I i∈S i∈S i∈S � � � • ( i∈S ∗ ai , i∈S ∗ bi , i∈S ∗ ci ) is a corner point in C. • S ∗ : a corner point in the convex hull C. • There exists (α, β, γ) such that = = = αa(S ∗ ) + βb(S ∗ ) + γc(S ∗ ) min(x,y,z)∈C (αx + βy + γz) minS (αa(S) + βb(S) + γc(S)) � minS i∈S (αai + βbi + γci ). 8 Slide 23 Slide 24 Observation: • i ∈ S ∗ iff αai + βbi + γci < 0. Since ai < 0 for all i, this is equivalent to CHECK:α + β bi ci + γ > 0? ai ai • To recover S ∗ , search through all possible α, β and γ!. • Issue: How to find α, β, γ? Consider the set of points ( abii , acii ), i = 1, ..., |I|. The set S ∗ contains points that lie on one side of the line α + β abii + γ acii = 0 3 3.1 Slide 25 Slide 26 Computational Results Test Instances Slide 27 Transportation cost is proportional to the euclidian distance in the plane. 9 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 Retailer W/H 0 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Figure 1: Warehouse-Retailer Locations 3.2 Solving the pricing problem No. of Retailers 10 20 40 80 160 320 3.3 Slide 28 Total CPU Time(seconds) 0.01 0.07 0.73 6.91 60.3 554 40 customers and 40 warehouses INPUT β θ 0.001 0.1 0.002 0.1 0.003 0.1 0.004 0.1 0.005 0.1 0.001 0.1 0.002 0.2 0.005 0.5 0.005 0.1 0.005 1 0.005 5 0.005 10 No. of DCs Opened 5 7 8 10 14 5 6 9 14 11 8 7 CPU Time 62 16 7 6 5 62 16 6 5 6 9 28 10 OUTPUT No. of Columns Generated 2661 961 543 466 364 2661 974 492 364 430 828 1643 Slide 29 ZH /ZLP 1 1.001 1 1 1 1 1.001 1 1 1.003 1 1.001 3.4 80 customers and 80 warehouses INPUT β θ 0.001 0.1 0.002 0.1 0.003 0.1 0.004 0.1 0.005 0.1 0.001 0.1 0.002 0.2 0.005 0.5 0.005 0.1 0.005 1 0.005 10 3.5 CPU Time 414 201 94 47 26 414 84 52 26 102 364 OUTPUT No. of Columns Generated 9984 6031 2548 1042 511 9984 2077 1196 511 3096 9072 Slide 30 ZH /ZLP 1 1 1 1 1 1 1 1 1 1 1 120 customers and 120 warehouses INPUT β θ 0.0001 0.01 0.0002 0.01 0.0003 0.01 0.0004 0.01 0.0005 0.01 0.0001 0.01 0.0002 0.02 0.0005 0.05 0.0005 0.01 0.0005 0.1 0.0005 0.5 4 No. of DCs Opened 7 9 12 21 24 7 13 18 24 10 8 No. of DCs Opened 11 15 24 28 33 11 23 29 33 15 12 CPU Time 742 516 213 103 57 742 215 99 57 522 635 OUTPUT No. of Columns Generated 21537 11476 4997 2014 1043 21537 5021 1998 1043 11628 17142 Slide 31 ZH /ZLP 1 1 1.001 1 1 1 1 1 1 1 1.002 Column Generation 4.1 Speeding Up • Bottleneck: For each j, a related pricing problem where the j is assumed to be the DC is solved. Slide 32 • How to choose j wisely? Approach: We use information on the primal and dual solution to “fix” variables, so that we can determine whether a DC will or will not be selected in an optimal solution early in the column generation routine. 4.2 Variable Fixing Recall that the set covering model we are trying to solve is of the form: � � min j∈W R∈R c � �j,R zj,R � � subject to ≥ 1, ∀i ∈ I, R∈R:i∈R j∈R zj,R zj,R ∈ {0, 1}, ∀R ∈ R. At each stage of the column generation routine, we have: • A set of dual prices {πj }. • A set of primal feasible (fractional) solution zj,S . 11 Slide 33 Slide 34 • After solving the pricing problem (one for each � � potential DC), we obtain � the reduced cost rj ≡ minS cj,S − k∈S πk . Note that some of the rj ’s may be non-negative. Let ZIP and ZLP denote the optimal integral and fractional solution to the set covering problem. � � Claim 1 . j:rj ≤0 rj + j πj is a lowerbound to ZLP . Hence it is a lowerbound to ZIP too. Slide 35 N3 Let j ∗ be a customer such that rj∗ > 0. Let U B be an upperbound for ZIP . � � Claim 2 . If j:rj ≤0 rj + j πj + rj ∗ > U B, then customer j ∗ will never be used as a DC in the optimal solution to the (integral) set covering problem. N4 Note 3 Proof Proof: Note that for the set partitioning model, by monotonicity of cost function cR,j , we know that there is an optimal LP solution which satisfies each covering constraint at equality. Hence the optimal LP solution is actually a solution to a set partitioning problem. For each customer j, the constraint � z S:j∈S S,j ≤ 1 is thus a redundant constraint implicit in the formulation. The Lagrangian dual of the LP relaxation is thus equivalent to ��� � � � � � � λj +min (cj,S − λk )zj,S : 1 ≥ zj,S ≥ 0, zj,S ≤ 1 ∀ j . L(λ) = j j S:j∈S k∈S S:j∈S The problem decomposes for each customer j, and hence ZLP = maxλ L(λ) ≥ � � L(π) = j πj + j:rj ≤0 rj . Note 4 Proof Proof: To see this, suppose otherwise. Then ZIP remains unchanged if we im� pose the additional condition: S:j ∗ ∈S zj ∗ ,S = 1 to the set covering formulation for customer j ∗ . The Lagrangian dual, in this case, reduces to � ��� � � � � � �  L (λ) = λj +min (cj,S − λk )zj,S : 1 ≥ zj,S ≥ 0, zj,S ≤ 1 ∀ j, zj ∗ ,S = 1 . j j S:j∈S k∈S S:j∈S � � Hence ZIP ≥ maxλ L (λ) ≥ L (π) = j πj + j:rj ≤0 rj + rj ∗ . On the other hand, we have ZIP ≤ U B. This gives rise to a contradiction. 12 S:j ∗ ∈S 4.2.1 Heuristic Slide 36 The variable fixing method depends largely on the quality of the upperbound U B. • We generate an upperbound for the IP by generating a feasible (integral) solution using some heuristic. – Let z ∗ be the optimal LP solution obtained by solving the problem using a partial set of columns. – Order the customers accoring to non-decreasing value of µi . – Starting from the first customer (say i = 1) on the list, ∗ For some S and j, i ∈ S and z ∗ = 1: customer i is served by DC j. j,S ∗ Otherwise, if there exists S, T , both containing i, and j, k are the designated DCs for set S ∗ and T respectively: such that z > 0, z ∗ > 0. We serve i using the DC that will lead to j,S T ,k the least total cost. – 4.3 4.3.1 Proceed to the next customer, until all customers have been assigned. Computational Results 40 Customers and Warehouses INPUT β 0.001 0.002 0.003 0.004 0.005 0.001 0.002 0.005 0.005 0.005 0.005 0.005 4.3.2 θ 0.1 0.1 0.1 0.1 0.1 0.1 0.2 0.5 0.1 1 5 10 No. of DCs OUT 34 31 31 29 27 34 34 32 27 29 32 34 CPU Time 6 3 2 1 1 6 4 2 1 1 4 6 No. of Columns Generated 117 73 66 44 32 117 92 56 32 40 96 122 ZH /ZLP 1 1 1 1.001 1 1 1.001 1 1 1.002 1 1.001 80 Customers and Warehouses INPUT β 0.001 0.002 0.003 0.004 0.005 0.001 0.002 0.005 0.005 0.005 0.005 4.3.3 Slide 37 OUTPUT No. of DCs Opened 5 7 8 10 13 5 6 8 13 10 7 5 θ 0.1 0.1 0.1 0.1 0.1 0.1 0.2 0.5 0.1 1 10 Slide 38 OUTPUT No. of DCs Opened 6 8 12 21 24 6 13 18 24 10 7 No. of DCs OUT 74 72 67 58 56 74 66 62 56 69 72 CPU Time 31 20 14 9 7 31 14 10 7 15 27 No. of Columns Generated 348 202 147 84 66 348 142 113 66 162 303 ZH /ZLP 1 1 1 1 1 1 1 1 1 1 1 120 Customers and Warehouses INPUT β 0.0001 0.0002 0.0003 0.0004 0.0005 0.0001 0.0002 0.0005 0.0005 0.0005 0.0005 θ 0.01 0.01 0.01 0.01 0.01 0.01 0.02 0.05 0.01 0.1 0.5 Slide 39 OUTPUT No. of DCs Opened 10 15 24 28 33 10 23 29 33 15 11 No. of DCs OUT 109 105 94 90 87 109 96 90 87 104 109 CPU Time 94 61 38 27 16 94 38 26 16 62 90 13 No. of Columns Generated 804 480 296 184 97 804 309 166 97 496 743 ZH /ZLP 1 1 1 1 1 1 1 1 1 1 1.002 4.3.4 500 Customers and Warehouses INPUT β 0.0001 0.0002 0.0003 0.0004 0.0005 0.0001 0.0002 0.0005 0.0005 0.0005 0.0005 5 θ 0.01 0.01 0.01 0.01 0.01 0.01 0.02 0.05 0.01 0.1 0.5 Slide 40 OUTPUT No. of DCs Opened 42 57 95 114 146 42 90 132 146 61 44 No. of DCs OUT 458 442 404 386 354 458 409 368 354 439 455 CPU Time 512 426 248 146 86 512 314 117 86 404 503 No. of Columns Generated 3742 2819 1405 717 446 3742 1833 586 446 2633 3572 ZH /ZLP 1 1.001 1 1 1 1 1 1 1 1 1 Applications and Extensions The model captures the three most important concerns in distribution network design: Transportation cost, Material and Warehousing Cost and Safety stock inventory cost How about: • Service level, say defined in terms of response time? • Robustness issues, say a set of scenarios (concerning cost and input parameters) are given? • Capacity issues, say a DC can only handle up to a fixed amount of demand ? 14 Slide 41