(385b) Fast Computational Strategies for Large Scale Distribution-Inventory Planning of Industrial Gases Under Demand Uncertainty | AIChE

(385b) Fast Computational Strategies for Large Scale Distribution-Inventory Planning of Industrial Gases Under Demand Uncertainty


You, F. - Presenter, Cornell University
Grossmann, I. E. - Presenter, Carnegie Mellon University
Capón, E. - Presenter, Universitat Politècnica de Catalunya - ETSEIB

A distribution network of industrial gases (Nitrogen, Oxygen, Argon, Carbon Dioxide, Helium and Hydrogen) consists of plants and customers, as well as storage facilities, trucks and trailers. In particular, customer inventories in this distribution network are managed by the vendor of industrial gases, i.e. the vendor installs storage tanks in customer locations with proper sizes and manages their replenishments to satisfy customer demands by coordinating the deliveries. [1-3] The short-term distribution planning decisions involve deciding which customers receives a delivery each day, by which route and what the size of that delivery is, using which truck and trailer for each delivery, and what is the capacity of each truck for delivery. The long-term inventory decisions involve deciding how many tanks to install in each customer location, what size of each tank, and when and how to upgrade, downgrade and install new tanks at customers [3-4]. To minimize the total capital and operating cost, the short-term distribution planning decisions should be integrated and jointly optimized with the long-term inventory decisions. This integration requires to account for the synergies between customers in terms of locations and tank sizes, and to consider the interactions of tank sizes and inventories between customers. The resulting challenge is how to effectively solve the large scale mixed-integer programming model to optimize asset allocation in the industrial gas distribution network by incorporating operating decisions.

In order to address the above problem, we develop an integrated mixed-integer linear programming (MILP) model for industrial gas distribution-inventory planning under demand uncertainty using slot-based scheduling model for vehicle routing. While effective for short-term version of the problem, the model becomes computationally expensive to solve for long planning horizons, which is necessary for the integration of strategic tank sizing decisions and operational vehicle routing decisions. Hence, we propose a two-stage solution approach to reduce the computational effort. The model is decomposed into an upper level continuous approximation model and a lower level detailed routing model. The upper level determines the sizes of tanks to be installed, downgraded and upgraded in each customer location over the given planning horizon and the safety stock level in each tank at each time period. Using continuous approximation method for capacitated vehicle routing for a rough estimation of the total distribution cost, [5-8] the upper level model trades offs the exact capital cost from tank sizing with the operating cost from continuous approximation of vehicle routing and stochastic inventory management [8-9] without considering the routing details. The resulting upper level problem is a non-convex mixed-integer nonlinear programming (MINLP) model with nonlinear terms from the continuous approximation constraints and stochastic inventory management constraints. This problem can be globally optimized very effectively even for large scale instances due to the model structure [8-10]. The lower level is solved in the reduced space after fixing the tank sizing decisions and safety stock decisions obtained from the upper level model; therefore it yields an upper bound on the total cost. The lower level determines the detailed vehicle routing decisions including the sizes of delivery and inventory levels of each customer over the planning horizon, as well as the detailed timing and sequence of deliveries with trucks of different capacities. To further reduce the computational effort of solving the lower level detailed routing problem, a location-based heuristic method is proposed by partitioning the customers into clusters based on their locations, and then the lower level detailed routing problem for each individual cluster and each time period are solved independently [11]. Application of the proposed model and solution approach is illustrated with several examples which show that the proposed solution approach can obtain near-optimal solutions very quickly especially for large scale problems. The models and solution approach also produce Pareto optimal curves that reveal how the tank sizes, safety stock levels and routing decisions change as the required service level changes.


[1] Glankwamdee, W., Linderoth, J., Shen, J., Connard, P., & Hutton, J. (2007), Combining Optimization and Simulation for Strategic and Operational Industrial Gas Production and Distribution, Computers and Chemical Engineering., Vol. 32, No. 11, 2536-2546

[2] Campbell, A., Clarke, L., Savelsbergh, MVP. (2002), Inventory routing in practice, Chapter 12 in ?The vehicle routing problem? (eds. P. Toth and D. Vigo), SIAM Press, Philadelphia, PA

[3] Campbell, A., Clarke, L., Savelsbergh, MVP, (2004) A Decomposition Approach for the Inventory-Routing Problem, Transportation Science, Vol. 38, No. 4, 488-502

[4] Song, J.-H., (2004) Inventory Routing Investigations, Ph.D Dissertation, Georgia Institute of Technology.

[5] Burns, L.D.; Hall, R.W.; Blumenfeld, D.E. (1985), Distribution Strategies that Minimize Transportation and Inventory Costs. Operations Research, Vol. 33, No. 3, 469-489

[6] Haimovich, M.; Rinnooy Kan, A.H.G. (1985), Bounds and Heuristics for Capacitated Routing Problems. Mathematics of Operations Research, Vol. 10, No. 4, 527-541

[7] Langevin, A.; Mbaraga, P.; Campbell, J.F. (1996), Continuous Approximation Models for Freight Distribution: An Overview. Transportation Research B., Vol. 30, No. 3, 163-188

[8] Shen, Z.-J.M.; Qi, L. (2007), incorporating inventory and routing costs in strategic location models. European Journal of Operations Research, Vol. 179, 372-389

[9] Laporte, G. (2007), What You Should Know about the Vehicle Routing Problem. Naval Research Logistics, Vol. 54, 811-819

[10] Sindhuchao, S.; Romeijn, H.E.; Akcali, E.; Boondiskulchok, R. (2005), An Integrated Inventory-Routing System for Multi-item Joint Replenishment with Limited Vehicle Capacity. Journal of Global Optimization, Vol. 32, 93-118

[11] Barreto, S.; Ferreira, C.; Paixao, J.; Santos, B.S. (2007), Using clustering analysis in a capacitated location-routing problem, European Journal of Operational Research, Vol. 179, 968-977