Fengqi YouIgnacio E. GrossmannJose M. PintoPiecewise Linear Approximation and Branch-and-Refine Algorithm for PX Tank Sizing under Uncertainty ProblemEWO Meeting March 10, 20102• Tank Sizing Tank installation, upgrade & downgrade Several available discrete tank sizes Safety stock optimization for uncertainty• Vehicle Routing Several available truck sizes Routing and timing decisions • Integration Tradeoff: operating cost vs. capital cost Capture the effects of customer synergiesand truck availability Integration requires to solve “extended”routing problem for long term (e.g. years)  Integrated MILP model is very largeVehicle Routing – Tank Sizing Problem0500100015002000250030003500400012345# of Customers# of Possible Routes050000010000001500000200000025000003000000# of 0-1 Variables in the MILP# of Possible Routes# of Binary Variables in the MILP3Complexity – 4 customer case112212333DepartureReturn4441234 256 possible route, 230,448 binary variables in the MILP model for integrating tank sizing and vehicle routing4Modeling Challenges• How to effectively integrate tank sizing with vehicle routing? Continuous approximation (CA) approach tradeoff capital and operating cost in the strategic level reduce most integer variables with some nonlinearities• How to optimize the safety stocks for demand uncertainty? Employ stochastic inventory model Integrate safety stock optimization with tank sizing• How to model the uncertainty of adding/losing customers? Two-stage stochastic programming A network structure for each scenario in each yearTermination?Next clusterSelect the 1stclustering solutionDetailed Routing Model(obtain vehicle routing decisions)Fix tank sizesCont. Approximation Model+ safety stock optimization(obtain tank sizing decisions)Customer ClusteringxyωUncertainty revealUncertainty revealω = 1ω = 1ω = 2ω = 2ω = 3ω = 3ω = 4ω = 4ω = 5ω = 5ω = Ωω = Ω5Optimal Safety Stock LevelSafety Stock(Service Level)Lead time = T6“Cyclic” Inventory-Routing• Key Assumption: each customer is replenished ina “cyclic” way with interval T• Required tank size ≥ max. inv. = Safety Stock + demand rate× TMax. Inv.Safety StockTimeInventoryReplenishment Interval Tworking inventoryConstantdemand rate7Routing & Replenishment in CAM• T = R / (ave. speed) T - replenishment interval R - minimum distance to visit allthe customers in a cluster once Average travelling speed is known• If only one trip for each replenishment R = TSP distance of the cluster & plant• If allowing multiple trips for replenishment R = ?customerplant18CAM for Capacitated Routing Problems*• Bounds for minimum routing distance R n – number of customers in the cluster q – capacity, max. number of customers that can be visited in one trip  r – average distance from customers to the plant TSP – traveling salesman distance to visit all customers once• Examples Cluster 1: q=1, TSP=0, r = 67 Cluster 2: q=1, same as Cluster 1, Cluster 2: q=2, TSP=50, r = 1,100* M Haimovich, AHG Rinnooy Kan, “Bounds and heuristics for CRP”, Math. of Oper. Res., 1985, 10(4), 527-5411,1001,1002567Cluster 1Cluster 29solve deterministicrouting problem for each scenario (network structure)Decomposition for Scenario Planning Termination?Next clustering soln.Select the first clustering solutionDetailed Routing Model(obtain vehicle routing decisions)Pro: avoid integer variables in the 2ndstage recourseFix tank sizesSafety stockCont. Approximation Model+ safety stock (all customers)Minimize total expected cost(obtain tank sizing decisions)Customer ClusteringTank sizing decisions for 1ststage (int. var.);Routing decisions for 2ndstage (cont. var.)Each scenario has a network structure, problem size increases as scenarios increase10Branch-and-Refine Algorithm• Global Optimization for MINLPs with only Univariate Concave Terms Piece-wise linear approximation (MILP) provides global lower bounds Feasible solutions provide upper bounds – solving a reduced MINLP  Increasing the number of pieces as iteration number increasesxsecantUB1LB1LB2UB211• Example 1: 3-year planning horizon 4 customers, 6 tank sizes, 6 types of trucks N14 will not lose by the end of Year 3 N15 may lose in Year 1 with 30% chance N18 may lose in Year 2 with 40% chance N21 may lose in Year 3 with 50% chance• Scenario Tree:Case StudyPlantN14600 km1,253.00 kmN151,100 km12,835.47 L/Month5,250.88 L/MN18N21290 km950 km1,137.59 km993.28 km6,417.74 L/M1,123.61 km23,337.22 L/MonthN14, N15, N18, N21N14, N15, N18, N21N14, N15, N18, N21N14, N15, N18, N21N14, N15, N18, N21N14, N15, N18, N21N14, N15, N18, N21N14, N15, N18, N21N14, N15, N18, N21N14, N15, N18, N21N14, N15, N18, N21N14, N15, N18, N21N14, N15, N18, N21N14, N15, N18, N21N14, N15, N18, N21Year 10N15 may lose (30%)N21 may lose (50%)N18 may lose (40%)34127856Year 2 Year 312• Example 1: 3-year planning horizon 4 customers, 6 tank sizes, 4 types of trucks N14 will not lose by the end of Year 3 N15 may lose in Year 1 with 30% chance N18 may lose in Year 2 with 40% chance N21 may lose in Year 3 with 50% chance• 8 scenarios for two-stage stochastic programming S1 – Y1: N14, N15, N18, N21;  S2 – Y1: N14, N15, N18, N21;  S3 – Y1: N14, N15, N18, N21;  S4 – Y1: N14, N15, N18, N21;  S5 – Y1: N14, N15, N18, N21;  S6 – Y1: N14, N15, N18, N21;  S7 – Y1: N14, N15, N18, N21;  S8 – Y1: N14, N15, N18, N21; 3 Existing Customer and 1 New CustomerY2: N14, N15, N18, N21; Y2: N14, N15, N18, N21; Y2: N14, N15, N18, N21; Y2: N14, N15, N18, N21; Y2: N14, N15, N18, N21; Y2: N14, N15, N18, N21; Y2: N14, N15, N18, N21; Y2: N14, N15, N18, N21; Y3: N14, N15, N18, N21.Y3: N14, N15, N18, N21. Y3: N14, N15, N18, N21. Y3: N14, N15, N18, N21. Y3: N14, N15, N18, N21. Y3: N14, N15, N18, N21. Y3: N14, N15, N18, N21. Y3: N14, N15, N18, N21. PlantN14600 km1,253.00 kmN151,100 km12,835.47 L/Month5,250.88 L/MN18N21290 km950 km1,137.59 km993.28 km6,417.74 L/M23,337.22 L/Month1,123.61 km1350%55%60%65%70%75%80%85%90%95%100%110 115 120 125 130 135 140Total Expected Cost (10^3$)Service LevelPareto Curves and Scenario CostsPlantN14600 km1,253.00 kmN151,100 km12,835.47 L/Month5,250.88 L/MN18N21290 km950 km1,137.59 km993.28 km1,123.61 km6,417.74 L/M23,337.22 L/Month50%55%60%65%70%75%80%85%90%95%100%60 70 80 90 100 110 120 130 140 150Total Cost of Each Scenario