A Two-Stage Matheuristic Algorithm for Classical Inventory Routing Problem

Zhouxing Su, Shihao Huang, Chungen Li, Zhipeng LüIJCAI 2020 · DOI

TL;DR

This paper introduces a novel two-stage matheuristic algorithm (TSMH) to tackle the complex Inventory Routing Problem (IRP), which combines inventory management and vehicle routing. TSMH achieves state-of-the-art results by first optimizing the overall schedule and then refining it with a sophisticated tabu search, demonstrating significant improvements on benchmark instances.

What Problem Does This Paper Address?

The Inventory Routing Problem (IRP) is a critical challenge in supply chain management, particularly with the rise of e-business and the adoption of Vendor Managed Inventory (VMI) models. IRP aims to minimize the total cost of inventory holding and vehicle transportation while ensuring no customer runs out of stock. This problem is notoriously difficult because it intertwines two classic optimization problems: inventory management (deciding how much to deliver and when) and vehicle routing (deciding where to go and in what order). Traditionally, these were handled separately, leading to inefficiencies. Solving IRP requires determining optimal delivery quantities, replenishment schedules, and delivery routes over multiple periods, all while respecting vehicle capacities and customer demands. The problem's NP-hard nature makes finding optimal solutions computationally expensive, especially for large-scale real-world scenarios.

Methods

The paper proposes a Two-Stage Matheuristic Algorithm (TSMH), a hybrid approach that combines mathematical programming with metaheuristics.

  • Stage 1: Structural Optimization (Relax-and-Repair): This stage focuses on obtaining a good initial overall schedule. It relaxes the complex subtour elimination constraints from the standard IRP Mixed-Integer Programming (MIP) model, creating a more tractable "Relaxed IRP" (RIRP). The RIRP is solved to get a preliminary solution. This solution is then "repaired" by solving Traveling Salesman Problems (TSPs) for each period to create feasible routes. This relax-and-repair cycle is repeated, with violated subtour constraints being added back lazily to gradually tighten the solution space until a time limit is reached or a feasible solution is found. This stage aims to produce high-quality initial solutions.
  • Stage 2: Detailed Refinement (Solution-based Tabu Search): Starting from the best solution found in Stage 1, this stage performs a fine-grained optimization. It employs a solution-based tabu search that records the complete state of evaluated solutions (unlike traditional attribute-based tabu search). This approach uses four neighborhood structures (addition, removal, move, and swap operations) to modify delivery schedules. To improve efficiency, a filtering technique is used to prioritize promising moves based on approximate objective improvements. The algorithm then evaluates the exact holding costs using a Linear Programming (LP) model and selects the best move. A perturbation operator is used to escape local optima when improvement stalls.

Datasets

The TSMH algorithm was evaluated on two sets of widely used benchmark instances for the IRP:

  • 160 small instances from Archetti et al. [2007].
  • 60 large instances from Archetti et al. [2012].

These instances vary in the number of periods (3 or 6) and clients (5 to 200), and are categorized by inventory cost levels (low or high). No new datasets were introduced in this paper.

Key Insights and Ideas

  • The Power of Hybridization: The core insight is that combining mathematical programming (for precise optimization of subproblems) with metaheuristics (for robust exploration of complex solution spaces) is highly effective for IRP. The two-stage approach allows for tackling different aspects of the problem at different granularities.
  • Solution-Based Tabu Search is Key for Refinement: The paper highlights that a "solution-based" tabu strategy, which remembers entire evaluated solutions rather than just attributes, is crucial for avoiding cycles and effectively exploring the solution space during the refinement stage.
  • Relax-and-Repair for Initial Structure: The first stage's relax-and-repair method is effective at generating good starting points by decoupling the routing and inventory aspects initially, then iteratively reintroducing constraints.
  • Trade-offs Between Inventory and Routing: The paper implicitly reinforces the fundamental trade-off in IRP: reducing inventory costs by making smaller, more frequent deliveries can increase transportation costs, and vice-versa. The TSMH algorithm effectively balances these competing objectives.

Key Results

  • State-of-the-Art Performance: TSMH achieved competitive results on 220 benchmark instances. It matched or improved upon the best known solutions for 40 out of 60 large instances.
  • Efficiency and Scalability: TSMH demonstrated superior efficiency compared to existing methods, particularly on larger instances. Its average computational time was significantly lower than some exact algorithms.
  • Effectiveness of Two Stages: Experiments comparing the full TSMH with simplified versions (only Stage 1 or only Stage 2) showed that the combination of both stages is essential for achieving the best performance. The solution-based tabu search (Stage 2) generally performed better than the relax-and-repair method (Stage 1) when used alone, but the full TSMH was superior to either stage in isolation.

Limitations and Future Work

  • Parameter Tuning: Like most metaheuristic algorithms, TSMH's performance can be sensitive to parameter settings. While the paper provides settings, further exploration of parameter tuning might yield even better results.
  • Generalization to Variants: The proposed TSMH is designed for the "classical" IRP. Future work could extend it to handle more complex variants, such as those with multiple vehicles, heterogeneous fleets, time windows, or stochastic demands.
  • Further Exploration of Hybridization: The authors suggest that further research into combining different metaheuristics or mathematical programming techniques could lead to even more powerful algorithms for IRP and its variants.

Summary updated

BibTeX
@inproceedings{su2020two,
  author = {Zhouxing Su and Shihao Huang and Chungen Li and Zhipeng Lü},
  title = {{A Two-Stage Matheuristic Algorithm for Classical Inventory Routing Problem}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/474},
}
Figure