Minimizing the logistic ratio in the inventory routing problem

Abstract

Inventory routing problems (IRPs) aim at minimizing the cost of the total distance traveled over a time horizon discretized in periods, while guaranteeing that the customers do not incur a stock-out event. In an optimal solution of an IRP, the customers in general have no inventory at the end of the horizon. Some inventory may remain only if this does not increase the cost of the distance traveled. To avoid this ending drawback, we consider in this paper as objective function the so-called logistic ratio, which is the ratio of the total routing cost to the total quantity distributed. The logistic ratio gives rise to a new optimization problem whose mathematical programming formulation is non-linear. Using a classical method, we can solve exactly instances with up to 5 vehicles and 15 customers over 3 periods. The solutions are compared with those of a classical IRP, both from the worst-case point of view and computationally. The results show that on average the logistic ratio increases by 20.4 % in the classical IRP on instances with 3 periods and that the percentage decreases when the horizon length increases.

1 Introduction

The inventory routing problems (IRPs) aim at minimizing the cost of the total distance traveled, and possibly also the inventory cost, over a discretized time horizon, while guaranteeing that the customers do not incur a stock-out event. In vehicle routing problems (see Toth and Vigo 2014), one period is considered, the demands of the customers who request a delivery in the period are given and the routes of the vehicles are optimized. In IRPs, the daily consumption of the customers is known and the supplier is responsible for the decisions related to the timing of the deliveries and the quantities to deliver, besides the traditional vehicle routes. More than the quantity consumed in a period may be delivered and stocked for future need. IRPs model practical management policies such as the Vendor-Managed Inventory (VMI). For a general introduction to IRPs and overviews of the contributions, we refer to Bertazzi and Speranza (2012) and Bertazzi and Speranza (2013), and to Bertazzi et al. (2008) and Coelho et al. (2014), respectively. For applications, we refer to Andersson et al. (2010). Exact solution methods for IRPs have been proposed recently by several authors (see Coelho et al. 2012a, b; Coelho and Laporte 2013, 2014; Adulyasak et al. 2013; Archetti et al. 2014; Desaulniers et al. 2015).

Let us consider IRPs where the routing cost only is minimized. To optimize the routing cost which is usually proportional to the total distance traveled, the customers tend to have no inventory at the end of the planning horizon in an optimal solution. Some inventory may remain only if this does not increase the distance traveled. This ending condition is not satisfactory as it implies that almost all customers will need to be served the period immediately after the end of the horizon considered. As a consequence, the routing cost will be excessively high after the end of the planning horizon. The optimization of the routing cost over a certain period of time, i.e., over the planning horizon, is likely to generate a solution that is far from being optimal when the operations pursue after the end of the horizon. In fact, companies usually assess the efficiency of a distribution policy through measures that consider both the cost of distribution and the quantity distributed. The most commonly used measure is the so-called logistic ratio, that is, the ratio of the cost of the distribution to the total quantity distributed. The logistic ratio is the average cost to distribute one unit of product and captures the long-term impact of a short-term planning. When considering a long-term plan, the objective is to minimize the total cost to satisfy the demand over the long term. This is achieved when minimizing the cost per unit, which corresponds to minimizing the logistic ratio. Note that this objective is similar to the one proposed by Air Liquide for the ROADEF/EURO Challenge 2016 (ROADEF 2016) (their cost structure also includes driver shift costs). Furthermore, Air Liquide, which is a multinational company distributing different oil types, uses the logistic ratio to evaluate distribution plans generated by the logistic department for the replenishment of warehouses and customers. A similar measure was proposed in Golden et al. (1984) to evaluate distribution plans of a large company distributing liquid propane to both residential and industrial customers. In particular, the ratio between the total number of gallons distributed and the total number of hours spent in the delivery operations was used.

In this paper, we study an IRP with multiple vehicles over a planning horizon discretized in periods. The objective function is the logistic ratio. We consider a single product and a single depot where the vehicles start and end their routes. The depot is located at the supplier and the quantity produced in each period is known. The product is consumed by a set of customers and the quantity consumed in each period is known for each customer. The consumed product can be delivered from the depot at the beginning of the period or beforehand, in which case it is stored in inventory. Stock-out at the customers or the supplier is not allowed. Each customer has an inventory capacity that must be respected after each delivery, before consuming the product. We assume that the inventory capacity at the supplier is unlimited. At the supplier and at each customer, there might be an initial inventory. In typical IRPs, an inventory holding cost, which may vary from one location to another, is incurred for each unit of product in inventory at the supplier and the customers at the end of each period. Here, we assume that the holding costs are equal everywhere and can, thus, be omitted. Indeed, given that the total quantities produced and consumed in each period are known, the total quantity in inventory in each period is also known and the total holding cost is thus a constant (see, for example, Bertazzi and Speranza 2013 for a proof of this property). We consider a homogeneous fleet of vehicles with given capacity. A route starts and ends at the depot and visits a subset of the customers, all within the same period. We assume that each customer is visited at most once per period. Each movement between two locations incurs a travel cost.

The problem we study consists in determining in which period(s) each customer must be visited, the quantity delivered at each visit, and the delivery routes to perform in each period. The objective is the minimization of the logistic ratio that is the total routing cost divided by the total delivered quantity. To the best of our knowledge, the problem has never been studied. We call it IRP with logistic ratio (IRP-LR). The objective function of the IRP-LR yields a non-linear mathematical programming formulation. In this paper, we focus on the exact solution of the problem and on the comparison with the classical IRP with no inventory costs. In fact, among the multiple optimal solutions of the IRP, we consider the one that maximizes the total quantity delivered. We call the problem where distance is optimized first and quantity after, the Cost-first Quantity-second IRP (CQ-IRP). From a theoretical point of view, we show that the logistic ratio of the CQ-IRP optimal solution can be infinitely higher than the logistic ratio of the IRP-LR solution. Using a classical method due to Dinkelbach (1967) that can handle the non-linear objective function, we solve the problem exactly on instances with up to 5 vehicles and 15 customers on a horizon of 3 periods, and up to 10 customers on a horizon of 4 or 5 periods. Computational experiments show that the logistic ratio is on average 20.4 % higher in the IRP with respect to the IRP-LR on instances with a planning horizon of 3 periods and tends to decrease with the increase of the length of the planning horizon.

The paper is organized as follows. In Sect. 2, the problem notation is introduced and the optimal solutions of the CQ-IRP and of the IRP-LR are compared from the worst-case point of view. A mathematical programming formulation for the IRP-LR is presented in Sect. 3 and the proposed solution algorithm in Sect. 4. Section 5 is devoted to the computational experiments. Finally, some conclusions are drawn in Sect. 6.

2 Notation and worst-case analysis

The IRP-LR is represented on a complete undirected graph $G=(N,E)$. $N=\{0\}\cup N'$ is the set of locations (nodes), where 0 is the depot and $N'$ is the customer set while $E$ is the set of edges between locations. A cost $c_{ij}$ is associated with each edge $\langle i,j\rangle$. Each customer $i \in N'$ has an associated inventory capacity $U_i$. We consider a planning horizon $T= \{ 1, \ldots , H\}$ of H time periods. The quantity consumed (or the demand) at customer i in period t is denoted as $d_{it}$, $i \in N'$, $t \in T$, while $d_{0t}$ is the quantity produced at the depot at period t. $I_{i0}$ represents the initial inventory level at location i, $i \in N$. A fleet of K homogeneous vehicles of capacity Q is available to distribute the goods from the depot to the customers.

In the classical IRP, the objective function is given by the minimization of the sum of the traveling cost and the inventory cost. If the inventory cost is not considered, then only the traveling cost is minimized. In the following, we give an example of how the solution changes when considering the minimization of the logistic ratio, like in the IRP-LR, with respect to the case when the traveling cost is minimized, like in the classical IRP with no inventory holding cost. As mentioned above, there may exist many IRP optimal solutions, but we consider the ones maximizing the quantity delivered, i.e., CQ-IRP optimal solutions.

Example 1

Let us consider the following instance. $H=2$, $|N'|=2$, $K=1$ and $Q=25$. The demands of the customers are $d_{it}=10$, $i=1,2$, $t=1,2$ while maximum inventory levels are $U_1=U_2=20$. The initial inventory levels at the customers are $I_{1,0}=10$ and $I_{2,0}=0$. The production rate at the supplier is not binding. The edge costs are as follows: $c_{0i}=1$, $i=1,2$ and $c_{1,2}=\epsilon$. Let us now determine the solution of the CQ-IRP. We need to deliver at least 10 units to customer 1 (which are given by the total demand over the planning horizon minus the starting inventory level) and 20 units to customer 2. Thus, the minimum number of routes is equal to 2 and both customers have to be visited at least once. Note also that 2 is the maximum number of routes as $H=2$ and $K=1$. Each route can visit one or two customers. The optimal solution of the CQ-IRP is the one that visits customer 2 at period 1 delivering 20 units and customer 1 at period 2 delivering 20 units. Thus, the solution has a cost of 4 and delivers 40 units. The logistic ratio is $\frac{4}{40}$. Note that 40 units is the maximum quantity that can be delivered if you use two routes visiting one customer each. To increase the quantity delivered, we have to visit both customers in one or two routes. If only one route visits two customers, the maximum quantity that can be delivered is 45 and the cost is $4+\epsilon$. If both routes visit both customers, the maximum quantity that can be delivered is 50 and the cost is $4+2\epsilon$. When $\epsilon$ tends to 0, the solution of the IRP-LRis the latter with value $\frac{4+2\epsilon }{50}$. The routes performed by the two solutions are depicted in Fig. 1. The numbers close to the edges represent the traveling cost.

Fig. 1

Routes performed by the two solutions described in Example 1 (solid lines for period 1, dashed lines for period 2)

We now study the maximum increase in the value of the logistic ratio when the CQ-IRP is considered instead of the IRP-LR.

Example 2

Let us consider the following instance. $H=2$, $|N'|=2$, $K=1$, the demands of the customers are $d_{1t}=d_1$ and $d_{2t}=d_2$, $t=1,2$, with $d_2 \gg d_1$. The maximum inventory levels are $U_1=2d_1$ and $U_2=3d_2$. The initial inventory levels at the customers are $I_{1,0}=0$ and $I_{2,0}=2d_2$. Vehicle capacity is $Q=2d_2$. The production rate at the supplier is not binding. The edge costs are as follows: $c_{0i}=1$, $i=1,2$ and $c_{1,2}=\epsilon$. Note that customer 2 does not need to be visited as its initial inventory level is sufficient to cover the demand of the two periods. Thus, the optimal solution of the CQ-IRP is the one that visits customer 1 in period 1 only and delivers $2d_1$ units. The routing cost is 2 and the logistic ratio is $\frac{2}{2d_1}$. A feasible solution delivering a higher quantity is the one where customer 1 is served in period 1 with quantity $2d_1$ and customer 2 is served in period 2 with quantity $2d_2$. The cost of this solution is 4 and the logistic ratio is $\frac{4}{2d_1+2d_2}$. The ratio of the logistic ratios of the two solutions is $\frac{d_1+d_2}{2d_1}$ which tends to infinity when $d_2$ tends to infinity.

Note that in the previous example one of the customers does not need to be served and is not served by the solution of the CQ-IRP. Moreover, the ratio $\frac{d_1+d_2}{2d_1}$ increases when the demand of one customer increases. Now, we show an example where all customers need to be served and the ratio increases with the number of customers.

Example 3

Let us consider the following instance. $H=2$ and $K=|N'|$. Customer demands and maximum inventory levels are $d_{it}=d$, $i=1,\ldots ,|N'|$, $t=1,\ldots ,H$ and $U_i=U$, $i=1,\ldots ,|N'|$, respectively. Moreover, the maximum inventory level U is equal to the vehicle capacity Q and corresponds to $d(|N'|+1)$. The initial inventory levels are $I_{1,0}=0$ and $I_{i0}=d$, $i=2,\ldots ,|N'|$. The cost $c_{ij}$ of each edge $\langle i,j\rangle$ is equal to $\epsilon$. The production rate at the supplier is not binding. Note that each customer needs to be visited at least once and the optimal solution of the CQ-IRP is the one that makes a single route in period 1 visiting all customers and delivering 2d to customer 1 and d to all remaining customers. Thus, the cost is $(|N'|+1)\epsilon$ and the quantity delivered is U. When $\epsilon$ tends to 0, the optimal solution of the IRP-LR is the one which delivers the maximum quantity. The maximum deliverable quantity over the two periods is equal to U for all customers $i=2,\ldots ,|N'|$ and $U+d$ for customer 1. Thus, the solution that maximizes the delivered quantity is the one where one route is performed in period 1 delivering U units to customer 1 and $|N'|$ routes are performed in period 2, each one visiting a single customer and delivering U units to customers $i=2,\ldots ,|N'|$ and d units to customer 1. The routing cost is $2\epsilon (|N'|+1)$ and the quantity delivered is $|N'|U+d$. The ratio of the logistic ratios of the two solutions is thus $\frac{(|N'|+1)\epsilon (|N'|U+d)}{2U\epsilon (|N'|+1)}$ which goes to infinity when $|N'|$ tends to infinity. The routes performed by the two solutions for the case where $|N'|=5$ are depicted in Fig. 2. In this case, we do not report the traveling cost of each edge as it is identical for all edges and equal to $\epsilon$.

Fig. 2

Routes performed by the two solutions described in Example 3 (solid lines for period 1, dashed lines for period 2)

Let LR(s) be the logistic ratio of solution s and let $s^*_{P}$ be the optimal solution of problem P. Then, the following statement holds:

Proposition 1

There exists no finite bound to the ratio $\frac{LR(s^*_{\text {CQ-IRP}})}{LR(s^*_{\text {IRP-LR}})}$.

3 A mathematical formulation for the IRP-LR

In this section, we provide a path-flow formulation for the IRP-LR that differs from the IRP formulation proposed in Desaulniers et al. (2015) only by its linear fractional objective function. We present it here entirely, using the notation introduced at the beginning of Sect. 2, to make the paper self-contained.

The formulation of Desaulniers et al. (2015) relies on the key features of two existing formulations. First, it relies on continuous variables that are each associated with a route and a delivery pattern as in the model of Desaulniers (2010) for the split-delivery vehicle routing problem. This pattern indicates the quantity delivered to each customer visited along the route. Only extreme delivery patterns (defined below) need to be considered given that all the others can be obtained as convex combinations of the extreme ones. Second, as in the facility location-based formulation of the lot-sizing problem proposed by Krarup and Bilde (1977), the model stipulates the exact usage of each delivery, i.e., which demand(s) it will fulfill fully or partially and if some of it is dedicated to the end inventory. Hence, each delivery can be seen as a set of sub-deliveries, one for each demand it can fulfill or for the end inventory. Assuming without loss of optimality that each customer consumes the product it receives following a first-in, first-out (FIFO) rule, the number of potential sub-deliveries associated with a delivery is rather limited.

Given this FIFO rule, the initial inventory at each customer must be used to satisfy its demands in the first periods. Consequently, for each customer $i\in N'$, we determine the rest $I^t_{i0}$ of its initial inventory $I_{i0}$ left at the end of each period $t\in T$: $I^t_{i0} = \max \{ 0, I_{i0} - \sum _{s = 1}^t d_{is} \}$. Knowing the demands covered by the initial inventory, we define the residual demand $\bar{d}_{it}$ for customer $i\in N'$ in period $t\in T$ as follows:

$$\begin{aligned} \bar{d}_{it} = \left\{ \begin{array}{ll} \max \{ 0, d_{it} - I_{i0} \} &\quad \text {if }\,t = 1 \\ \max \{ 0, d_{it} - I^{t-1}_{i0} \} &\quad \text {otherwise}, \end{array} \right. \quad \forall t \in T. \end{aligned}$$

A positive residual demand cannot be covered by the initial inventory and must, therefore, be covered by delivered quantities.

Furthermore, according to the FIFO rule, for each customer $i\in N'$ and each period $t\in T$, we establish an upper bound on the quantity that can be delivered in each sub-delivery of a delivery to customer i in period t. More precisely, an upper bound $u^s_{it}$ on the quantity that can be delivered in period t and that is dedicated to satisfy the demand of a period $s\in T$ is given by

$$\begin{aligned} u^s_{it} = \left\{ \begin{array}{lll} 0 &{}\quad \text {if }\,s < t \\ \min \{ \bar{d}_{is}, U_i - I^{s-1}_{i0} \} &{}\quad \text {if }\,s = t \\ \min \{ \bar{d}_{is}, U_i - \sum _{\ell = t}^{s-1} d_{i\ell } - I^{s-1}_{i0} \} &{}\quad \text {otherwise}. \end{array} \right. \end{aligned}$$

We also define the upper bound $u^{H+1}_{it} = U_i - \sum _{\ell = t}^{H} d_{i\ell } - I^{H}_{i0}$ on the quantity delivered in period t and that is dedicated to the end inventory (associated with an extra period $H+1$).

Let R be the set of feasible routes. A feasible route is an elementary path in G starting and ending at depot 0 and visiting exactly once some customers in $N'$. The cost of a route $r\in R$, denoted $c_r$, is equal to the sum of the costs $c_{ij}$ of its edges $\langle i,j\rangle$. Moreover, let $N'_r \subseteq N'$ be the subset of customers visited in route r and let $a_{ri}$ be a binary parameter equal to 1 if $i\in N'_r$ and 0 otherwise. Note that a route can be used in any period.

With each route $r\in R$ and period $t\in T$, we associate a set of possible delivery patterns $W_{rt}$. A delivery pattern $w\in W_{rt}$ indicates for each customer $i\in N'_r$ and for each period $s\in T \cup \{ H+1 \}$ the quantity $q^s_{wi} \in [0, u^s_{it}]$ delivered in period t to customer i along route r that is dedicated to satisfy the demand of period s if $s\in T$ or that is destined to the end inventory if $s = H+1$. It is sufficient to restrict the set $W_{rt}$ to extreme delivery patterns, i.e., patterns with at most one value $q^s_{wi}$ that is strictly within its lower and upper bounds ($0< q^s_{wi} < u^s_{it}$). Indeed, convex combinations of these patterns can yield all non-extreme patterns. For a pattern $w\in W_{rt}$, let $q_w = \sum _{i\in N'_r}\sum _{s=t}^{H+1} q^s_{wi}$ be the total quantity delivered along route r in period t. Furthermore, let $b^s_{wi} = \sum _{\ell = s+1}^{H+1} q^\ell _{wi}$ be the quantity delivered in period t to customer $i\in N'_r$ that is still in inventory at the end of period $s\in T$, i.e., the quantity dedicated to satisfy the demands of the periods after s.

The path-flow formulation involves two types of variables. Non-negative variables $I_{0t}$, $t\in T$ indicate the inventory at the depot at the end of period t. Continuous variables $y^{w}_{rt}$, $r\in R$, $t\in T$, $w\in W_{rt}$, bounded in [0, 1], specify the proportion of route r operated in period t with delivery pattern w.

Using this notation, we can formulate the IRP-LR as follows:

$$\begin{aligned}&\min \quad \left( \sum _{t\in T}\sum _{r \in R}\sum _{w \in W_{rt}}c_{r}y_{rt}^w \right) \Big /\left( \sum _{t\in T}\sum _{r \in R}\sum _{w \in W_{rt}}q_{w}y_{rt}^w \right) \end{aligned}$$

(1a)

$$\begin{aligned}&\text {s.t.}\quad \sum _{t\in T}\sum _{r \in R}\sum _{w \in W_{rt}} q^s_{wi}y_{rt}^w = \bar{d}_{is},\quad \forall i \in N', s\in T, \end{aligned}$$

(1b)

$$\begin{aligned}&I_{0,t-1} + d_{0t} - \sum _{r \in R}\sum _{w \in W_{rt}} q_{w}y_{rt}^w = I_{0t},\quad \forall t \in T, \end{aligned}$$

(1c)

$$\begin{aligned}&I_{0t} \ge 0,\quad \forall t \in T, \end{aligned}$$

(1d)

$$\begin{aligned}&I^{s}_{i0} + \sum _{t\in T}\sum _{r \in R}\sum _{w \in W_{rt}} b^{s}_{wi}y_{rt}^w + d_{is} \le U_i,\quad \forall i \in N',\ s\in T, \end{aligned}$$

(1e)

$$\begin{aligned}&\sum _{r\in R}\sum _{w\in W_{rt}} a_{ri}y_{rt}^w \le 1,\quad \forall i \in N',\ t \in T, \end{aligned}$$

(1f)

$$\begin{aligned}&\sum _{r\in R}\sum _{w\in W_{rt}} y_{rt}^w \le K,\quad \forall t \in T, \end{aligned}$$

(1g)

$$\begin{aligned}&y_{rt}^w \ge 0,\quad \forall t \in T,\ r\in R,\ w \in W_{rt}, \end{aligned}$$

(1h)

$$\begin{aligned}&\sum _{w\in W_{rt}}y_{rt}^w \in \{0,1\},\quad \forall t \in T,\ r \in R. \end{aligned}$$

(1i)

The objective function (1a) aims at minimizing the logistic ratio. Constraints (1b) ensure that the residual demand of each customer (i.e., the demand not covered by the initial inventory) is met in each period. Constraints (1c) define the inventory level at the depot in each period while non-negativity requirements (1d) avoid stock-out situations at the depot. Inventory capacity at each customer in each period is imposed through constraints (1e). Recall that the maximum inventory in a period s (the left-hand side term of (1e)) is reached before demand consumption and after a possible delivery. It is, thus, equal to the inventory at the end of the period s, arising from the initial inventory or from past and current deliveries, plus the demand in this period. Constraints (1f) ensure that each customer is visited by at most one vehicle in each period, while constraints (1g) limit to K the number of vehicles that can be used in each period. Non-negativity requirements on the $y^w_{rt}$ variables are given by (1h). Binary requirements are not imposed directly on these variables, but rather on the routes themselves with (1i), allowing convex combinations of the extreme delivery patterns.

Given the non-linear objective function (1a), formulation (1a)–(1i) cannot be solved through a standard solution algorithm for mixed integer linear programs. This is the reason why we opted to solve the IRP-LR using an algorithm based on a variant of formulation (1a)–(1i) as described in the following section.

4 A solution algorithm for the IRP-LR

Model (1a)–(1i) is a linear fractional program. We propose to solve it using an algorithm that follows the general scheme developed by Dinkelbach (1967) for the solution of fractional programming problems. The basic idea of Dinkelbach’s algorithm is the following. Let $\mathbf {x}$ be the vector of decision variables, S the feasible domain that is compact and connected, $C(\mathbf {x})$ and $D(\mathbf {x})$ the two continuous functions of $\mathbf {x}$ such that $D(\mathbf {x}) > 0$ for all $\mathbf {x}\in S$. Given the fractional programming problem:

$$\begin{aligned} \min \{C(\mathbf {x})/D(\mathbf {x}) \, |\, \mathbf {x}\in S\} \end{aligned}$$

the algorithm solves, at each iteration k, the following problem:

$$\begin{aligned} \min \{C(\mathbf {x})-r_{k-1}D(\mathbf {x}) \, | \, \mathbf {x}\in S\} \end{aligned}$$

where $r_{k-1}$ is the ratio $C(\mathbf {x}_{k-1})/D(\mathbf {x}_{k-1})$ provided by the optimal solution $\mathbf {x}_{k-1}$ at iteration $k-1$. Let $\mathbf {x}_k$ be the computed optimal solution. The algorithm stops if $C(\mathbf {x}_k)-r_{k-1}D(\mathbf {x}_k)=0$. Otherwise, $C(\mathbf {x}_k)-r_{k-1}D(\mathbf {x}_k) < 0$, which means that $r_k = C(\mathbf {x}_k) / D(\mathbf {x}_k)$ yields a better ratio than $r_{k-1}$. Dinkelbach (1967) proves the convergence of the algorithm under the hypotheses stated above. In our case, S is not connected but our computational results show that the algorithm converges towards an optimal solution in a few iterations.

Now, let us discuss how Dinkelbach’s algorithm can be applied to the IRP-LR. Let $\mathbf {y}= (y^w_{rt})_{{ r\in R, t \in T \atop w\in W_{rt} }}$ and $\mathbf {I}= (I_{0t})_{t\in T}$. Thus

$$\begin{aligned}&\mathbf {x}:= (\mathbf {y}, \mathbf {I}) \end{aligned}$$

(2)

$$\begin{aligned}&C(\mathbf {y}, \mathbf {I}) \equiv C(\mathbf {y}):=\sum _{t\in T}\sum _{r \in R}\sum _{w \in W_{rt}}c_{r}y_{rt}^w \end{aligned}$$

(3)

$$\begin{aligned}&D(\mathbf {y}, \mathbf {I}) \equiv D(\mathbf {y}):=\sum _{t\in T}\sum _{r \in R}\sum _{w \in W_{rt}}q_{w}y_{rt}^w \end{aligned}$$

(4)

$$\begin{aligned}& S \text {\, is\,defined\,by\,}(1\text {b}){-}(1\text {i}). \end{aligned}$$

(5)

Given a logistic ratio r, the algorithm solves at each iteration the following mixed integer linear program:

$$\begin{aligned}&(MILP(r))\quad z(r)=\min\ C(\mathbf {y}) - r D(\mathbf {y}) \end{aligned}$$

(6a)

$$\begin{aligned}&\text {s.t.} \quad (\mathbf {y},\mathbf {I}) \in S. \end{aligned}$$

(6b)

To solve it, we use the branch-price-and-cut algorithm developed in Desaulniers et al. (2015). We refer the reader to Desaulniers et al. (2015) for details on the branch-price-and-cut algorithm. We simply mention that in Desaulniers et al. (2015) the authors show that the algorithm outperforms branch-and-cut algorithms previously proposed in the literature for the IRP when the number of vehicles is large, i.e., $K=4,5$ while branch-and-cut (Coelho and Laporte 2014) tends to be better for a lower number of vehicles. Anyway, for our tests, the branch-price-and-cut algorithm turned out to be sufficiently efficient when the number of vehicles is low and, thus, we decided to use this algorithm for all values of K.

The pseudo-code of Dinkelbach’s algorithm for the IRP-LR is given in Algorithm 1.

5 Computational experiments

To the best of our knowledge, this is the first study on the IRP-LR. Our aim is to gain insights into problem properties and solution characteristics and this is the reason why we proposed an exact solution approach. In fact, while on one side optimal solutions can be obtained only on small-sized instances, and on the other side optimal solutions allow us to perform a consistent and reliable analysis of the solution characteristics.

All computational experiments were conducted on a Linux computer equipped with an Intel Core i7-4770 processor clocked at 3.4 GHz (a single core was used). The branch-price-and-cut algorithm of Desaulniers et al. (2015) used to solve the MILP(r) problems in Algorithm 1 relied on CPLEX 12.4.0.0 for solving the restricted master problems.

5.1 Test instances

We performed computational tests on benchmark instances for the IRP proposed in Archetti et al. (2007) for the single-vehicle case, adapted to the multiple-vehicle case in Archetti et al. (2014) and used also in Coelho and Laporte (2013) and Desaulniers et al. (2015). The instances have the following characteristics. The value of H is equal to 3 and the number of customers is $|N'|=5\ell$ with $\ell =1,2,3$. The number of vehicles K varies from 1 to 5. The vehicle capacity is obtained by dividing the vehicle capacity of the corresponding instance for the single-vehicle case (defined in Archetti et al. 2007) by the number of vehicles. For each instance characteristic (number of customers, number of vehicles), 5 random instances were generated, for a total of 75 instances. Note that in Archetti et al. (2007, (2014), Coelho and Laporte (2013) and Desaulniers et al. (2015), larger instances were also considered, with up to 50 customers and a planning horizon of 6 periods. We did not consider these larger instances in our computational tests since, as shown in the following section, the IRP-LR proved to be very hard to solve and only small instances could be solved to optimality. The reason for which the IRP-LR is much harder to solve than the standard IRP can be explained by the objective function (6a). The value of the objective function tends to be flat around the optimal solution, i.e., there exist many solutions whose objective function value is close to the one of the optimal solution, and this creates difficulties in the solution algorithm as it is much harder to prune branch-and-bound nodes. Moreover, to gain some insights on the impact of the value of H on the logistic ratio, we solved the same set of instances where H was increased to 4 and 5. Unfortunately, the complexity of the problem increased dramatically with the value of H and, thus, we were not able to solve, in a reasonable amount of time, most instances with $|N'|=15$ when $H=4$ and $H=5$.

5.2 Computational results

A summary of the computational results is presented in Tables 1, 2 and 3 for $H=3$, $H=4$ and $H=5$, respectively. The tables are organized as follows. Each group of three rows reports the results on instances with the same number of vehicles K. In each group, each row provides the average results over the five instances with the same number of customers $|N'|$. The third column reports the computational time in seconds while the fourth shows the number of iterations performed by the algorithm described in Sect. 4 to reach the optimal solution. The fifth and sixth columns report the value of the logistic ratio of the solution of the CQ-IRP and of the solution of the IRP-LR, respectively. To obtain an optimal solution of the CQ-IRP, we first solved the IRP where the objective function is the minimization of the routing cost. We then solved the problem again, imposing the same routing cost found in the previous solution and maximizing the delivered quantity. The following column reports the ratio of the logistic ratios of the CQ-IRP solution and the IRP-LR solution. Columns eight, nine and ten show the ratio of the total costs (Cost), the total quantities delivered (TotQ) and the numbers of routes (# of routes) of the solutions of the CQ-IRP and the IRP-LR, respectively. Finally, the last column shows the ratio of the difference between the total quantity delivered in the IRP-LR solution and $D^{\mathrm{min}}$ to the difference between $D^{\mathrm{max}}$ and $D^{\mathrm{min}}$, where $D^{\mathrm{min}}$ and $D^{\mathrm{max}}$ are a lower and an upper bound on the total quantity delivered, respectively. They were computed as follows. The lower bound $D^{\mathrm{min}}$ is the sum of the demands that cannot be satisfied by the initial inventory, i.e.,

$$\begin{aligned} D^{\mathrm{min}} = \sum _{i\in N'} \, \max \left\{ 0, \sum _{t\in T} d_{it} - I_{i0} \right\} . \end{aligned}$$

(7)

A simple upper bound $D^{\mathrm{max}}$ can be computed as:

$$\begin{aligned} D^{\mathrm{max}} = \sum _{i\in N'} D^{\mathrm{max}}_i, \end{aligned}$$

where

$$\begin{aligned} D^{\mathrm{max}}_i = (U_i- d_{iH})+ \left( \sum _{t\in T} d_{it}-I_{i0}\right) \end{aligned}$$

is the upper bound on the maximum quantity that can be delivered to customer i. The quantity $D^{\mathrm{max}}_i$ depends on whether the initial inventory $I_{i0}$ is sufficient to satisfy the total demand of the customer or not. It is the maximum final inventory $U_i- d_{iH}$ plus the demand that exceeds the initial inventory, if $\sum _{t\in T} d_{it}-I_{i0}\ge 0$. Otherwise, it is the maximum final inventory minus the initial inventory that exceeds the demand.

The ratio $\frac{\mathrm{TotQ}_{\text {IRP-LR}}-D^{\mathrm{min}}}{D^{\mathrm{max}}-D^{\mathrm{min}}}$ represents the total quantity left in the customers end inventory by the solution of the IRP-LR with respect to the total inventory capacity at the customers. The asterisk (*) in the sixth row of Table 2 is due to the fact that one instance of this group was not solved to optimality and, thus, data refer to the remaining four instances. The same happens in the ninth row of Table 3. In this case, one instance turned out to be infeasible.

The tables show that Dinkelbach’s algorithm converges in a few iterations (between 3.0 and 3.8 on average). Even if the number of iterations does not vary much, the computational time increases dramatically with the number of customers. The logistic ratio decreases with the number of customers and increases with the number of vehicles for both the CQ-IRP and the IRP-LR solutions. Also, when considering the ratio of the two logistic ratios, we notice that there is no clear relation either with the number of vehicles or with the number of customers. The ratios of the total costs, the total quantities delivered and the numbers of routes indicate that the solutions of the CQ-IRP cost less than the solution of the IRP-LR but deliver less and use fewer routes. These three ratios seem to be more or less stable for the same value of H. When the value of H increases, these ratios increase, meaning that the two solutions tend to be more similar. This is due to the fact that, when H increases, $D^{\mathrm{min}}$ increases and the relative difference between $D^{\mathrm{max}}$ and $D^{\mathrm{min}}$ decreases. This reduces the difference between the solutions of the CQ-IRP and the IRP-LR. Finally, the ratio $(\text {TotQ}_{\text {IRP-LR}}-D^{\mathrm{min}})$/$(D^{\mathrm{max}}-D^{\mathrm{min}})$ decreases with the number of vehicles and with the value of H. This ratio shows that, to optimize the logistic ratio, we often need to deliver more than the minimum quantity. The excess with respect to the minimum quantity corresponds to the end inventory level and often amounts to more than half of the total inventory capacity of the customers. Thus, contrary to what typically happens in the classical IRP, some customers may have a positive final inventory level in the optimal solution of the IRP-LR.

Table 1 Computational results on instances with $H=3$

Table 2 Computational results on instances with $H=4$

Table 3 Computational results on instances with $H=5$

Table 4 shows a summary of the results reporting the computational time (in seconds) and the ratio of the logistic ratios of the CQ-IRP and the IRP-LR. Columns are organized by value of H while rows by values of K and $|N'|$.

Table 4 Summary of results

The table shows that the computational time is highly sensitive to the value of H. Moreover, the ratio of the logistic ratios decreases when the value of H increases. This is consistent with the increase, with respect to the value of H, of the ratio of the total quantity delivered to the total cost. We want to note that the instances with $H=4$ and $H=5$ were generated by taking the instances with $H=3$ and simply increasing the value of H. Thus, when H increases, $D^{\mathrm{min}}$ increases and the relative difference between $D^{\mathrm{max}}$ and $D^{\mathrm{min}}$ decreases. This reduces the ratio of the logistic ratios of the CQ-IRP and the IRP-LR. Clearly, results would change in case of changes in the value of other instance parameters. In particular, increasing the value of Q or $U_i$ would lead to larger differences between the logistic ratios of the solutions of the two problems.

Fig. 3

Logistic ratios of the CQ-IRP and the IRP-LR solutions for instances with $H=3$

In Fig. 3, we report the logistic ratios of the CQ-IRP and IRP-LR solutions for all instances with $H=3$. We show a plot for each value of K. In each plot, we compare the 15 instances with the corresponding number of vehicles. The first 5 pairs of bars are related to instances with 5 customers, the second 5 pairs of bars refer to instances with 10 customers and the last 5 to instances with 15 customers. We can notice that the trend is similar for all plots. Thus, the difference between the two logistic ratios is higher for instances with fewer customers. However, in terms of absolute values, we can see that the logistic ratios of both solutions increase with the number of vehicles. This is due to the fact that instances with a higher number of vehicles are obtained by dividing the capacity of the single-vehicle instances by K. Thus, the higher the number of vehicles, the smaller is the vehicle capacity and, as a consequence, the routing cost increases with the number of vehicles.

To provide further insights, we analyze in detail one instance for which the CQ-IRP solution substantially differs from the IRP-LR solution. The instance is ‘abs3n10’ with $H=3$, $K=3$ and $|N'|=10$. The CQ-IRP solution performs 3 routes all in period 2 while the IRP-LR solution performs two routes in period 2 and 3 routes in period 3. The routes of the CQ-IRP and IRP-LR solutions are depicted in Figs. 4 and 5, respectively. The CQ-IRP solution has a routing cost of 2409 and delivers a total quantity of 656. The logistic ratio is 3.67. The IRP-LR solution has a routing cost of 2836 and delivers a total quantity of 1092. The logistic ratio is 2.60. Thus, the ratio of the two logistic ratios is 1.41. As a consequence, the cost per unit delivered increases by 41 % in the CQ-IRP solution with respect to the IRP-LR solution.

Fig. 4

Routes performed by the CQ-IRP solution for instance ‘abs3n10’ with $H=3$ and $K=3$

Fig. 5

Routes performed by the IRP-LR solution for instance ‘abs3n10’ with $H=3$ and $K=3$

6 Conclusions

In this paper, we introduce the inventory routing problem with logistic ratio (IRP-LR), which is a variant of the classical inventory routing problem (IRP) where the objective function is the minimization of the logistic ratio, i.e., the ratio of the routing cost to the quantity delivered. The study of this problem is motivated by practical reasons: companies are more interested in minimizing the unitary distribution cost, that is the logistic ratio, than the routing cost only as the former measure captures the long-term impact of a distribution policy. In fact, in an optimal solution of a classical IRP, the customers in general have no stock at the end of the horizon. Thus, while the solution is optimal over the considered horizon, it is not when a longer horizon is considered.

The contribution of this paper is the formulation and the solution of the IRP-LR. Moreover, the solutions of the classical IRP are compared with the solutions of the IRP-LR. In fact, among the multiple optimal solutions of the IRP, we consider the one that maximizes the total quantity delivered. We call the problem where routing cost is optimized first and quantity after, the Cost-first Quantity-second IRP (CQ-IRP). This favors the IRP in the comparison. From the theoretical point of view, we show that the logistic ratio in the optimal solution of the CQ-IRP can be infinitely higher than the logistic ratio in the IRP-LR. Instances with up to 5 vehicles and 15 customers on a horizon of 3 periods, and up to 10 customers on a horizon of 4 or 5 periods were solved to optimality. Computational experiments show that the logistic ratio is on average 20.4 % higher for the IRP with respect to the IRP-LR on instances with a planning horizon of 3 periods and tends to decrease with the increase of the length of the horizon.

Future research should address the design of more efficient exact methods and of heuristics. Also, the adoption of the logistic ratio as objective function could be extended to other inventory routing problems.