Keywords

1 Introduction

The Inventory Routing Problem (IRP) combines the two principal decisions in supply chain. It comprises the vehicle routing (VRP) and the inventory management problem. The IRP is one of the most complete problem in the logistic distribution. The goal is to minimize the total cost of VRP and inventory management. The idea of combining both problems, the inventory allocation problem and the VRP was first introduced by [1] which studied the IRP with a single customer. Several varaints of the IRP are described in literature. A classification of the different variants of the IRP can be found in [2,3,4,5]. The authors of [6] studied an unique-product IRP where the objective is to deliver a product to a set of clients. [8] solved a multi-product IRP with homogenous fleet types with limited number of vehicles. [7] established an IRP for perishable products. [8] considered a model of IRP with stochastic demand. [9] presented a IRP model, which the horizontal corroboration of suppliers was explicitly considered. The location inventory routing problem [10,11,12] is another variant of IRP. In this problem, several depots must be located to distribute the products to customers in each period.

Recently, [13] considered a green IRP with time windows. The main idea of this problem is to minimize fuel consumption throughout the distribution. Since the IRP combines two several NP-hard problems, authors have performed large works on it in order to make many techniques. [8] proposed a modified Ant Colony Optimization (ACO) to optimize the difference between the shortage and transportation cost. The authors developed a heuristic method adopted to the IRP with time windows and stochastic demand, which was hybrid two approaches, the Markov Decision Process (MDP) and Clarke-Wright algorithm. Another heuristic method developed permits to solve the IRP with multiple vehicles. They used an approach permits to improve the initial solution, this method is Adaptive Large Neighborhood Search (ALNS), and another optimization technic to determine the optimal solution (Branch-and-Cut algorithm). Another approach used a hybridation between simulated annealing and Tabu search for solving an IRP for perishable goods. The researchers presented a genetic algorithm in order to obtain the solotution of the IRP in an attempt to optimize the sales loss to solve the IRP. An approach integrated green logistics in IRP with a multi-period. They employed an axact method based on Branch-and-Cut to solve the proposed problem. [14] proposed variable neighborhood search and Tabu search algorithms to solve the IRP with location depots.

In this work, we focus on solving the multi-product IRP. The main objective is to optimize the two decisions: the vehicles routing and the inventory management at each period. [15] is one of the first to simulate an IRP with multiple products. They proposed an heuristic method based on a Genetic Algorithm to detrmine the optimal solution for this problem. Also, [16] developed an heuristic based on Variable Neighborhood Search (VNS) for the same objective. Our proposed scheme in this paper containes two levels in order to determine the solution of this problem. The heuristic method named Ant Colony Optimization is used in the first level to solve periodic vehicle routing problem. In the second stage, we develop a hybrid heuristic based on an efficient heuristic to determine the inventory decision and the Two-opt algorithm to improve the total cost.

The structure of this work as follows. We define our problem and present mathematical formulation in [15] in Sect. 2. The Sect. 3 descibes the algorithms used to solve the model. In next section, we give the computational experiments. In the last section, we include some conclusions and discusses opportunities for future research.

2 Problem Description

In this work, we address a multi-product IRP similar to the one proposed by [21]. The problem consists of delevering the products of an assembly plant for each period \(s \in S\). A fleet of \(M\) homogeneous vehicles with a capacity \(Q\) is available. The products are collected from a set of \(n\) uppliers. Vehicles are located at the depot. Each supplier can be served by more than one vehicle at each period. Moreover, the inventory costs are calculated just at the manufacturing plant. At each period \(s \in S = \left\{ {1, \ldots ,\tau } \right\}\), the demand of the manufacturing plant equals to \(d_{is}\) for each product \(i \in N = \left\{ {1, \ldots ,n} \right\}\). The corresponding product i defines supplier. At each period, a vehicle k leaves the warehouse 0, visits the suppliers affected to this vehicle, and distributs products to the manufacturing plants n + 1. when a vehicle finishes its tour it returns to the depot. Since IRP aims at simultaneously reducing the fixed cost \(F\) of using a vehicle, the traveling cost between node \(i\) and node \({ }j,\,c_{ij}\), and the inventory cost of product, \(h_{i}\). The illustration of the problem can be dfined in Fig. 1.

Fig. 1.
figure 1

Example of the IRP

Full size image

A mathematical formulation based on [15] is given here. We first introduce the following decision variables:

  • \(a_{is}\): Total quantity to be collected from each supplier \(i\) at each period \({ }s\).

  • \(I_{is}\): Stock level of each product \(i\) at the assembly plant at each period \(s\).

  • \(I_{i0}\): Initial stock of each product \(i\) at the assembly plant.

  • \(q_{ijs}\): Quantity of products distributed between the two arcs \({ }i\) and \(j\) during the period \(s\).

  • \(x_{ijt}\): Number of visits between the two arcs \({ }i\) and \(j\) during the period \(s\).

The mathematical formulation states as follows:

$$ min\mathop \sum \limits_{i \in V} h_{i} \left( {\mathop \sum \limits_{s \in S} I_{is} } \right) + V\left( {\mathop \sum \limits_{i \in N} \mathop \sum \limits_{{\begin{array}{*{20}c} {i \in N \cup \left\{ 0 \right\}} \\ {i \ne j} \\ \end{array} }} c_{ij} \left( {\mathop \sum \limits_{s \in S} x_{ijs} } \right) + \mathop \sum \limits_{i \in N} c_{i,n + 1} \mathop \sum \limits_{s \in S} x_{i,n + 1,s} } \right) + \left( {F + Vc_{n + 1,0} } \right)\mathop \sum \limits_{i \in N} \mathop \sum \limits_{s \in S} x_{0is} $$
(1)
$$ {\text{Subject}}\,{\text{to}}: $$
$$ I_{is} = I_{i,s - 1} + a_{is} - d_{is} \quad \quad \forall i \in N,\forall s \in S $$
(2)
$$ \sum\nolimits_{{\mathop {i \in N \cup \left\{ 0 \right\}}\limits_{i \ne j} }} {q_{ijs} + a_{js} = } \sum\nolimits_{{\mathop {i \in N \cup \left\{ {n + 1} \right\}}\limits_{i \ne j} }} {q_{ijs} \forall j \in N,\forall s \in S} $$
(3)
$$ \sum\nolimits_{i \in N} {q_{i,n + 1,s} } = \sum\nolimits_{i \in N} {a_{is} \quad \quad \quad \quad \quad \forall s \in S} $$
(4)
$$ \sum\nolimits_{{\mathop {i \in N \cup \left\{ 0 \right\}}\limits_{i \ne j} }} {x_{ijs} = } \sum\nolimits_{{\mathop {i \in N \cup \left\{ {n + 1} \right\}}\limits_{i \ne j} }} {x_{jis} \quad \quad \quad \quad \forall j \in N,s \in S} $$
(5)
$$ \sum\nolimits_{j \in N} {x_{0js} = } \sum\nolimits_{j \in N} {x_{j,n + 1,t} \quad \quad \quad \forall s \in S} $$
(6)
$$ q_{ijs} \le cx_{ijs} \quad \quad \quad \forall i \in N,\forall j \in N \cup \left\{ {n + 1} \right\},i \ne j,\forall s \in S $$
(7)
$$ I_{is} \ge 0\quad \quad \quad \forall i \in N,\quad \quad \quad \forall s \in S $$
(8)
$$ x_{i,0,s} = x_{n + 1,i,s} = 0,\quad \forall i \in N \cup \left\{ {0,n + 1} \right\},\quad \forall s \in S $$
(9)
$$ a_{is} \ge 0\quad \quad \quad \forall i \in N,\quad \quad \quad \forall s \in S $$
(10)
$$ x_{i,j,s} \ge 0,entier,\quad \forall i,\,j \in N \cup \left\{ {0,n + 1} \right\},\quad \forall s \in S $$
(11)
$$ q_{ijs} \ge 0,\quad \forall i \in N,\,j \in N \cup \left\{ {n + 1} \right\},\quad \forall s \in S $$
(12)
$$ q_{0is} = 0,\quad \quad \quad \forall i \in N,\forall s \in S $$
(13)

The objective function (1) aims to minimize both the fixed cost of using vehicles, the routing cost, and the inventory costs. Constraints (2) ensure the inventory level of products at the manufacturing plant. Constraints (3) eliminate all sub tours an assure the flow balance at each supplier. Constraints (4) ensure equality between the quantities of products collected by all vehicles and the demand of the assembly plant at each period. Constraints (5) and (6) guarantee equality between the number of vehicles leaving the depot and the number of vehicles returning to the manufacturing plant. Constraints (7) garantie the respect of the vehicle capacity. Constraints (8) guarantee the satisfaction of the demand at each period. Constraints (9) guarantee the elimination of a direct route from the suppliers to the depot. Finally, constraints (10)–(13) define the decision variables.

3 Solution Presentation and Approach Structures

In this paper, we search to solve the inventory routing problem using a hybrid heuristic based on the Ant Colony algorithm (AC) and an efficient heuristic. Firstly, we use an AC to solve a periodec VRP. More precisely, we must determine the optimum number of routes to collect the number of products from each supplier and transported them to an assembly plant at each period, without considering into the inventory cost. Then we use a combination of two heuristics to minimize the routing and inventory costs simultaneously. In this step, we seek to determine the quantities of products to collect from each supplier while respecting the constraint of storage at the assembly plant. Then, we implement the Two-opt local search to improve the solution.

3.1 Ant Colony Algorithm

The ant colony algorithm was first proposed by [17]: the principle of this heuristic is to simulate the ability of ant colonies to find the shortest path to food. Artificial ant systems have been shown to be effective in solving classic vehicle routing problems [18]. The basic phases of the ACO algorithm are the ant’s travel construction and pheromone information (update). In the route construction phase, \(M\) simple artificial agents concurrently construct the initial routes starting from the depot selected in the network of \(N\) supplier nodes (plus the depot and the assembly plant). At each constructive procedure, the ant \(k\) moves from a node \({ }i{ }\) to the next node \(j\) by choosing among the nodes that have not been visited yet, the AC algorithm follows the equation to build periodic routes.

$$ P_{ij}^{k} \left( s \right) = \left\{ {\begin{array}{*{20}c} {\frac{{\left( {\tau_{ij} \left( s \right)} \right)^{\alpha } .\left( {\eta_{ij} } \right)^{\beta } }}{{\mathop \sum \nolimits_{{l \epsilon N_{i}^{k} }} (\left( {\tau_{il} \left( s \right)} \right)^{\alpha } .\left( {\eta_{il} } \right)^{\beta } }}, \quad \quad \quad j \in N_{i}^{k} } \\ {\,\,0, \quad \quad \quad \quad \quad \quad{\text{otherwise}},\quad\quad\,\,} \\ \end{array} } \right. $$

  • \(\tau_{ij}\) denotes the level of pheromone on the arc \(\left( {i,j} \right)\).

  • \(\eta_{ij} \left( s \right)\) denotes the visibility of the arc \(\left( {i,j} \right)\) at planning period \(s\),usually indicates the inverse of the distance/cost on the arc from node \(i\) to node \(j\).

  • \(\alpha \wedge \beta\) denote the relative influence of the pheromone trails.

  • \(N_{i}^{k}\) denotes the ants working memory (i.e. the nodes which are already accessible from node \(i\) and not previously choose.

After each passage in the arc \(\left( {i,j} \right)\) the pheromone trail is updated locally. The local update is performed during the ant constructive route, and it is calculated according to the following way:

$$ \tau_{ij} \left( {s + 1} \right) = \left( {1 - \rho } \right).\tau_{ij} \left( s \right) + \rho .\tau_{0} $$
(15)

Where \(\tau_{ij} \left( {s + 1} \right)\) the pheromone level between node \(i\) and \(j\) after updating, \(\tau_{ij} \left( s \right)\) is the pheromone level between node \(i\) and \(j\) before updating, \(\rho\) is the constant that optimize the speed of evaporation.

A solution is obtained when all suppliers are visited or no vehicle cannot add a supplier due to capacity of vehicle. The best Ant is the one who visited more suppliers. Once the ants have finished their iterations, the global update is performed using the best solution found. This global pheromone updating guides the following ants in their construction of solutions. The following formula represents the calculation of this update:

$$ \tau_{ij} \left( {s + 1} \right) = \left( {1 - \rho } \right).\tau_{ij} \left( s \right) + \rho .\Delta \tau_{ij} $$
(16)

Where the arcs \(\left( {i,{ }j} \right)\) belong to current optimum route \(T^{ + }\) of length \(L^{ + }\) and \(\Delta \tau_{ij} = \frac{1}{{L^{ + } }}\).

3.2 Efficient Method for the Inventory Management

In this section, we describe the perfermant heuristic used to calculate the amount of products to be assembled. This method is based on a backward technic; it is can generally be divided into two steps: the first determine which suppliers should be visited first in order to collect the demands in each period. The second step determines the order of vehicles that visit a supplier. We note \(\delta_{is}\) the priority of supplier \(i \in K\) at period \(s \in S\), it is based on the warehouse cost of its product and on its the distribution period \(s^{\prime} < s\). The following formulation defines this priority:

$$ \delta_{is} = h_{i} \left( {s - max\left\{ {max\left\{ {s^{\prime} < s:if\,supplier\,i\,is\,visited\,at\,period\,s^{\prime}} \right\},0} \right\}} \right) $$
(17)

The supplier that has the higher value of \(\delta_{is}\) is the first visited. The list of suppliers is ordered in descending order after the supplier is assigned to a period \(s\). Then, we determine the order of the corresponding allocation of vehicles. We define the second priority rule for this assignment. We start by estimating the average cost. After we control if one unit of product is collected or not by a vehicle \(v\), in period \(s\). This process of estimating is calculated using the formulation as folow:

$$ h_{vs}^{*} = \frac{{\mathop \sum \nolimits_{{i \in K\left( {s,v} \right)}} \left( {d_{is} + I_{i,s + 1} } \right)\delta_{is} }}{{\mathop \sum \nolimits_{{i \in K\left( {s,v} \right)}} \left( {d_{is} + I_{i,s + 1} } \right)}}{ } $$
(18)

A vehicle \(v\) with the highest priority at each period \({ }s{ }\) is one who has the smallest \(\gamma_{vs} ,\) where:

$$ \gamma_{vs} = h_{vs}^{*} \sum\nolimits_{{i \epsilon N\left( {s,v} \right)}} {max\left( {d_{is} + I_{i,s + 1} - C,0} \right)} $$
(19)

3.3 Two-Opt for Improvement Solution

We present here the Two-opt procedure used to improve the solution. The two-opt local search was proposed by Bertsimas. It is one of the most widely used local search for improving vehicle routes. This algorithm consists of eliminating two arcs and combining the two resulting paths in a different way to obtain a new route. The two-opt procedur is based on exchange edges and search the neighborhood of the current route, that is, perform a local search and provide an optimal route. Figure 2 shows an example of the Two-opt operator.

Fig. 2.
figure 2

Example of two-opt algorithm

Full size image
figure a

4 Computational Results

The proposed method was implemented in C++. This section presents the detailed experiments from the proposed approaches. A comparaison between our methods and two algorithms published in the reviws is presented.

We adopt a set of 14 benchmark instances based on the original 4 instances provide in [19], the same ones used in [16]. These four data sets are small instances S12T14 and S20T21 that comprise (12 suppliers, 14 periods) and (20 suppliers, 21 periods), respectively. The medium instances S50T21 with 50 suppliers and 21 periods. The large instances S98T14 with 98 suppliers and 14 periods. The characteristics of the instances are provided in Table 1.

Table 1. Information of instances
Full size table

  • N. Sup: Number of suppliers

  • T.C/U.D: Travel cost per unit distance

  • V.C: Vehicle Capacity

  • R.H.C: Rang of Holding Costs

  • R.D.S: Range of demand at each supplier

In the first phase, we apply an ACO method to minimize only the routing costs. This method finishes when one of the stopping criteria is satisfied (no improvement). Once it stops, we use an efficient heuristic and the two-opt method, in order to ameliorate the existing solution. Each instance is performed to 10 runs. In Table 2, we report the best result of 10 runs for our proposed algorithm, the result of the Genetic Algorithm (GA) by [15], and the result found by the 2p-VNS method presented by [16]. In the first column, the instances are presented while in the second column the number of suppliers (n) and the number of periods for each instance are given. In columns, 3–6, the best cost of the ten runs and the optimal number of vehicles (op_v) of the solutions of the GA (columns 3 and 4), and the 2p-VNS (columns 5 and 6) are presented, respectively. In columns 7–8, the numerical results of our method (the best cost of the ten runs, the optimal number of vehicles (op_v) are presented. As it can be seen from Table 2.

Table 2. Comparaison results
Full size table

It can be seen that our approach produces the new best solutions to six instances out of the 14 instances. The average improvement of the algorithm is about 239410,91.

Table 3 shows a comparison of the numerical result of each method applied on the same dataset. It includes the value of the lower bound presented in [15] (BI), the comparison based on percentage gaps, and shows the computational time (CPU) consumed for obtaining the good result. For the other instances, the quality of the solutions is between 0.4% and 28,38%.

Table 3. Comparison of the two approach and the proposed heuristic
Full size table

In Table 3, we report the value of the lower bound presented in [18] in column BI. We also give the execution time (CPU) required to find the optimal solution and the deviation from the best solution found (Gap) for each of the three approaches. we denote by g(S) the cost of the solution S qiven by one of the methods. The deviation with respect to the BI is calculated by the following formula:

$$ \left( {\frac{cost\_of\_the\_solution - BI}{{BI}}} \right)*100 $$

For the last two instances, the lower bound is not defined in [18]. In this case, we calculated the deviation between the value of the solution found by one of the methods and the best value obtained (bestSol) by one of the three algorithms. The objective is to find the best solution found (bestSol) of the two last instances. This formula is presented as follows:

$$ \left( {\frac{cost\_of\_the\_solution - bestSol}{{bestSol}}} \right)*100 $$

From this table, we can observe that the average of the gaps found vary from 0.4% to 28.38%. From these results, our approach clearly shows its reliability and stability.

5 Conclusion and Future Works

This paper has developed an efficient technic for solvig the inventory routing problem multi-product. The proposed method consists of two phases: the first phase determines an initial solution by solving a periodic vehicle routing problem with Ant colony optimization algorithm. The second stage improves this initial solution. The inventory decisions are optimized at the second phase. For this stage, we combine an efficient heuristic for inventory management to determine the quantities of products to collect from suppliers during each period. Finally, a simple 2-opt is implemented to improve the routes. As the results showed, the proposed method is able to provide better results when compared to the existing approach from the literature, both in terms of solution quality and computational times. We will adopt other approach to this problem using more dataset.