Optimal Distribution-Inventory Planning of Industrial Gases. I. Fast Computational Strategies for Large-Scale Problems

Fengqi You, José M. Pinto, Elisabet Capón, Ignacio E. Grossmann, Nikhil Arora, Larry MeganIndustrial 2011 · DOI

TL;DR

This paper tackles the complex problem of optimizing industrial gas distribution by simultaneously planning vehicle routes and storage tank sizes. They introduce two novel, computationally efficient strategies to solve large-scale problems that were previously intractable, demonstrating significant speedups while maintaining optimal or near-optimal solutions.

What Problem Does This Paper Address?

The efficient distribution of industrial gases (like nitrogen, oxygen, etc.) involves a delicate balance between long-term strategic decisions (how big should storage tanks be at customer sites?) and short-term operational decisions (when and how to deliver the gas). This integration is crucial for minimizing total costs, which include capital investment in tanks, service costs, distribution (trucking) costs, and potential outage costs if demand isn't met. The challenge lies in the sheer scale and complexity of these interconnected decisions, leading to massive mixed-integer linear programming (MILP) models that are computationally prohibitive for real-world, large-scale networks. Existing methods often struggle to handle both tank sizing and detailed vehicle routing simultaneously for extended planning horizons.

Methods

The authors propose two main computational strategies to overcome the computational burden:

  1. Two-Level Solution Strategy (Route Selection - Tank Sizing & Reduced Routing): This approach decomposes the problem into two stages.
  2. Upper Level: Solves a "route selection - tank sizing" model. This is a relaxation of the full MILP, focusing on identifying optimal tank sizes and potential delivery routes without getting bogged down in exact delivery schedules.
  3. Lower Level: Once tank sizes and routes are determined, a "reduced routing" problem is solved. This leverages the pre-selected routes, making it much more computationally efficient than solving the full routing problem from scratch.
  4. Continuous Approximation Approach: This strategy uses continuous functions to approximate discrete routing variables, allowing for strategic-level decision-making.
  5. Upper Level: A continuous approximation model estimates annual delivery costs and determines optimal tank sizes by trading off capital costs against approximated operational costs, without detailed routing. This model is reformulated into an MILP for efficient optimization.
  6. Lower Level: With tank sizing decisions fixed, a detailed routing problem is solved in a reduced variable space. This approach is particularly effective for strategic planning over long horizons.

Datasets

The paper uses data from three case studies to illustrate the application and performance of their proposed models and strategies. These case studies involve:

  • Case Study 1: A small network with 2 customers (one with an existing tank, one new; then both new).
  • Case Study 2: A network with 4 customers (one new, others with existing tanks; then all new).
  • Case Study 3: Large-scale instances with 30, 60, 100, and 200 customers, all treated as new customers.

Customer locations and demand rates for these case studies were either provided or generated randomly. TSP distances for larger instances were obtained using the Concorde TSP Solver.

Key Insights and Ideas

  • Decoupling for Efficiency: The core idea is that by decoupling the strategic tank sizing decisions from the highly complex operational routing decisions, significant computational gains can be achieved.
  • "Worst Case" Inventory for Tank Sizing: In the two-level approach, using a "worst case" working inventory for tank sizing helps ensure that the selected tank sizes are robust enough to handle potential demand fluctuations and replenishment scenarios.
  • Continuous Approximation for Strategic Planning: The continuous approximation method is particularly powerful for long-term strategic planning, allowing for the estimation of routing costs without needing to solve the full, computationally intensive routing problem at that stage. This enables a better trade-off analysis between capital investment and operational expenses.
  • Scalability is Key: The paper directly addresses the scalability issue of MILP models in supply chain optimization, demonstrating that specialized strategies are essential for practical application to large networks.

Key Results

The proposed strategies significantly outperform the integrated MILP approach in terms of computational time, especially for larger instances.

  • Case Study 1 (2 customers, 1 year): All approaches yielded the same optimal total cost ($18,128), but CPU times varied drastically: Integrated MILP (69s), Route Selection (12s+15s), Continuous Approximation (0.1s + 29s).
  • Case Study 1 (2 customers, 3 years): The integrated MILP failed due to memory constraints. The Route Selection approach found a solution of $53,329, while the Continuous Approximation approach also achieved $53,329 but with much faster computation (9s vs. 59s for the detailed routing part).
  • Case Study 2 (4 customers, 1 year): Integrated MILP failed. Route Selection and Continuous Approximation both found a lower cost solution ($33,824) compared to the suboptimal solution from the integrated MILP ($37,559).
  • Case Study 3 (up to 200 customers): The continuous approximation approach was the only one capable of solving these large instances within reasonable timeframes (e.g., <5 minutes for 200 customers), demonstrating its high computational efficiency.

Limitations and Future Work

  • Optimality Gap for Continuous Approximation: The authors acknowledge that for the continuous approximation approach, a theoretical lower bound is not available, making it difficult to estimate the optimality gap.
  • Tank Size Changes: The current model assumes tank sizes are fixed after installation in the first year. The authors suggest that a multi-period formulation allowing tank size changes each year could be a better approach for capital investment planning, though it would increase complexity.
  • Detailed Routing for Large Instances: For very large instances (like the 200-customer case study), solving the detailed routing model in the second stage of the continuous approximation approach was not performed due to its size. The authors suggest that heuristics and decomposition methods (like clustering) could be employed to obtain near-optimal solutions for this sub-problem.
  • Future Work: The paper mentions that a method for obtaining near-optimal solutions for the detailed routing problem within reasonable computational time will be introduced in a subsequent paper.

Summary updated

Abstract

In this paper, we address the optimization of industrial gas distribution systems, which consist of plants and customers, as well as storage tanks, trucks, and trailers. A mixed-integer linear programming (MILP) model is presented to minimize the total capital and operating costs, and to integrate short-term distribution planning decisions for the vehicle routing with long-term inventory decisions for sizing storage tanks at customer locations. In order to optimize asset allocation in the industrial gas distribution network by incorporating operating decisions, the model also takes into account the synergies among delivery schedule, tank sizes, customer locations, and inventory profiles. To effectively solve large-scale instances, we propose two fast computational strategies. The first approach is a two-level solution strategy based on the decomposition of the full-scale MILP model into an upper level route selection−tank sizing model and a lower level reduced routing model. The second approach is based on a continuous approximation method, which estimates the operational cost at the strategic level and determines the trade-off with the capital cost from tank sizing. Three case studies including instances with up to 200 customers are presented to illustrate the applications of the models and the performance of the proposed solution methods.
BibTeX
@inproceedings{you2011optimal,
  author = {Fengqi You and José M. Pinto and Elisabet Capón and Ignacio E. Grossmann and Nikhil Arora and Larry Megan},
  title = {{Optimal Distribution-Inventory Planning of Industrial Gases. I. Fast Computational Strategies for Large-Scale Problems}},
  booktitle = {Industrial},
  year = {2011},
  doi = {10.1021/ie1017578},
}
Figure