A P-Robustness Approach for the Stochastic Inventory Routing Problem

Introduction

Setting up all supply chain elements is a key factor that companies face in the short and long term (it is seen as a planning task). Most manufacturing and logistics companies aim to produce and/or distribute goods to final customers, so the role of an efficient supply chain and its distribution network is essential in order to guarantee profits, sustainability, and operability. In this way, the integration of decision-making at different levels becomes a key factor for any supply chain, and the integration of inventory routing decisions integrates tactical problems (inventory management) and operative problems (routing) ¹. The integration of both levels into decision-making is known as the Inventory Routing Problem (IRP), inspired by the Vendor Managed Inventory (VMI) strategy, which consists of centralizing inventory-related decision-making.

Thereupon, the IRP implies coordinating two logistic decisions (inventory + routing), whose goal is to minimize the overall costs generated by inventory holding costs plus routing costs over a given planning horizon ². The decisions to be taken are summarized as follows: when to deliver goods required by each customer, their quantities, and how to ship them all while considering several constraints such as allowable inventory levels and vehicle capacity ³, ⁴. This model has been widely studied in the literature because of its importance in terms of applicability, where most of its variants deal with different practical issues that require designing appropriate solution methods. Most of the literature deals with deterministic parameters; it considers decision-makers to have complete information beforehand, but several factors have no deterministic behavior, which creates the need to include uncertainty in the analysis (seen as a degree-of-freedom factor). Now, one of the main issues that affects logistic operations over the planning horizon are customer demands, which induce variability/uncertainty since they are hard to estimate in many cases ⁵.

This paper is organized as follows: Section 2 presents a literature review; in Section 3, the mathematical model of our proposal is presented; Section 4 presents the results in a practical scenario; and Section 5 shows the conclusions of the study.

Literature review

Several approaches deal with the classic inventory routing problem, and their main efforts are steered towards finding optimal solutions within reasonable computing times. One of the main approaches for optimally solving this deterministic problem was presented in ⁽⁶, while its stochastic version is still a challenge. Some authors have approached solving the stochastic IRP; for instance ⁷presents an approach for the stochastic IRP considering two uncertainty sources, demands and travel times, which were also considered to be stationary, where the main approach is to solve a robust version of the IRP based on a robust optimal distribution plan solved by a combination of optimization and Monte Carlo simulation methods.

Similarly, ⁸ developed two approaches for solving two IRP instances: dynamic and stochastic. In the dynamic version, the information is revealed for each time period (i.e., demands which are considered as a source of uncertainty), so decision making happens at the beginning of each period. The stochastic version assumes the involvement of stochastic uncertainty, which affects predictions that are used for decision-making before demands occur. The authors then proposed the use of several heuristics to analyze how a moving horizon period increases computing efforts but does not improve the optimal solution of the problem.

A multi-objective approach is developed in ⁹, which is based on economic performance, shortage/delivery delays, and environmental footprint as three goals to be evaluated. The authors also considered different uncertainty sources such as the demands and transportation costs. The approach to modeling uncertainty is fuzzy sets and systems, which is divided into two parts: the first is the transformation of the proposed fuzzy mathematical model into an equivalent deterministic/crisp via a fuzzy possibilistic approach, while the second one corresponds to the NSGA-II (Non-Sorting Genetic Algorithm II).

In ⁽¹⁰, the authors propose the use of Markov chains along with simulated annealing, pattern search/ranking, and selection procedures to evaluate near-optimal solutions. Authors also solve a periodical stochastic inventory model with auto correlated demands using empirical probability distributions. The proposed method is a simulation-based optimization approach whose results show that inventory performance significantly declines as autocorrelation increases and it is then disregarded.

An interesting IRP application of industrial gases is shown in ¹¹, where the authors propose a Lagrangian relaxation method that obtains an approximate of 8 % in savings. Similarly, ¹² presents an inventory control system with periodic review to analyze replenishment decisions by choosing an appropriate replenishment size with different service levels.

Another stochastic IRP is analyzed in ¹³. The authors propose the use of the order-up-to-level policy, which consists of replenishing when necessary up to the top level of inventory capacity. The main approach here is to penalize stockouts and model the problem as a dynamic programming problem using a hybrid rollout algorithm, which can reduce computing time of large instances to reasonable times, thus constituting an improvement of the benchmark algorithms existing in the literature.

Mathematical approach

The main formulation considers the same basic ideas presented by ¹-³ handling stochastic uncertainty through the adaptation of the p-robustness criteria presented in ⁴ and ⁵, generating scenarios for modeling uncertainty such as those presented in ⁽⁶. Therefore, the mathematical model contemplates a set of nodes Vp = 2, . . . , n as the set of customers, where node “1” corresponds to the central depot that distributes products to the network, where, at each time period t ∈ T, there is an amount rtt of product available at the depot.

For each time period, each customer has a demand dtst i that is uncertain and is modeled with the scenario s ∈ S. The variable I st i represents the inventory levels at the depot and the customers, where each has a lower (Li) and upper (Ci) bound to be kept in inventory. Moreover, the depot must decide if there will be a delivery made by a vehicle represented by the set K, which has a specific capacity Qk, and each delivery is modeled with the variable q kt i . Finally, there are the binary variables Xkt ij and Y kt i , which determine if a customer is visited or not. This model considers uncertainty mainly with a two-stochastic optimization approach ¹⁹, where first-stage decisions are related to selecting visiting customers, second-stage decisions are related to inventory levels (customers/depot), and the decisions related to the amount of goods to be delivered to each customer per scenario. The mathematical model used is as follows:

The objective function aims to minimize the expected costs made up by the inventory/holding and transportation costs. Said function is presented in Eq. (1) which represents the overall scenario. Constraint (2) enforces the p-robustness condition, which considers the optimal function for each scenario and a predefined p-robustness. Constraints (3) and (4) determine inventory levels in the depot. Eqs. (5), (6), (7), and (8) determine the upper/lower bounds of inventory levels for every customer. Eq. (9) represents quantities to be delivered to each customer given the maximum capacity allowed by Eq. (10), which also establishes a relationship between integer and binary variables

Eq. (11) represents the fixed vehicle capacity, while (12) sets the relationship between the amount of products delivered, the capacity, and a binary variable that activates if a customer is visited. Flow constraints are shown in (13), and the relationship between the two binary variables is presented in (14). Finally, routing constraints are presented in (15) and (16), and (17) sets up the nature of delivering quantities. To get a better understanding of the problem, Fig. 1 presents a graphical description. The example is composed of four different time periods, where a delivery decision must be made for each customer (five in total, as represented by the blue circles). Each customer has their own inventory level constraints (maximum and minimum, represented by the bar) which must be fulfilled. For each time period, from the depot, it must be decided if a replenishment must be done (and the routing process), considering that demand over each time period is stochastic (thus, it is not known beforehand).

Experimentation and results

The mathematical model presented in section 3 is tested with the modification of instances presented in different studies ⁴, ¹⁵, ²⁰, considering the scenario generation presented by ⁽¹⁸. In this case the scenarios generated are 20, and they aim to analyze the variability of demand, where the model is solved using FICO-Xpress-MP v. 12.1. The analyzed instance has the reference “abs1n5_HC3”, which is composed of 6 customers that have different values of demand over three time periods of the planning horizon (the deterministic version has 65, 35, 58, 24, and 11 units of demand, respectively), and the scenarios are generated according to the behavior of the deterministic demand given variations of ± 20 %. The capacity of each vehicle is fixed to 289 units, and the amount of product available at the depot corresponds to 193 units. In this sense, in Fig. 1, we present the results for a single instance contrasting the variation of the objective function in terms of the p-robustness parameter.

Figure 1: Description of the problem under study

Fig. 2 shows that analyzing the trade-off between the p-robustness and the objective function (which measures the overall logistic costs) shows that, as the p-robustness value increases, the overall objective function decreases. This means that decision-makers can achieve cost reductions by choosing higher values of the p-robust parameter. In order to analyze the behavior of the obtained solution and regret for different scenarios, we have presented the results in Table I, where the first column corresponds to the uncertainty scenario, the second column is its optimal value, and the third column is the regret.

Figure 2: Variation of the objective function in terms of the p-robustness value

Table I shows the overall performance of the regret in every scenario of the optimization model. Roughly speaking, the obtained values are in some cases greater than those obtained by the deterministic model due to the uncertainty of the delivered quantities and the demand used in each scenario. On the other hand, as the regret obtained in different scenarios is somehow small, this model allows analysts to obtain robust solutions in order to deal with uncertain demands and manage logistic costs composed of the inventory holding and routing costs.

Table I: Regret over scenarios

Conclusions

In this paper, we have presented a mathematical model approach for the Inventory Routing Problem with demand uncertainty, where the modeling is carried out through the use of the probustness criteria, which minimizes the worst-case cost or regret and combines the two objectives by minimizing the expected cost while bounding the relative regret in each scenario of uncertainty. The mathematical model contemplates a single-depot and single product but considers several customers within a planning horizon with variations in the demand. The experiments performed allow us to analyze the trade-offs obtained with the objective function contrasted with the parameter of the approach selected. To solve the proposed approach, the p-robustness model requires that several mathematical models are 4solved (given the number of scenarios) for using this information in the general version as a parameter for building the p-robustness criteria (Constraint (2)).

This model can be extended to perform different analyses and increase the complexity of decisions; the impacts of several depots and products can be analyzed, and different types of sources of uncertainty can be considered, such as the transportation and inventory costs and the heterogeneity of vehicles. On the other hand, different methods for solving bigger instances can be proposed, such as heuristics, metaheuristics, or matheuristics, given the computational complexity of the basic problem, which is increased by the uncertainty.