Mathematical Modelling for a Multi-Product Inventory Routing Problem with Split Delivery

Show more

1. Introduction

Transportation and inventory costs are the two main components of a supply chain. Both transportation and inventory costs ought to be considered concurrently in the logistic planning functions as these two areas might lead to significant gains and more competitive distribution strategies (Moin et al. 2011). Although this is a well known fact that approaches for supply chain optimization usually consider inventory control and transportation independently, the interrelationship between these two components is always ignored. The coordination of these two drivers, often known as the inventory routing problems (IRPs), is critical in improving the supply chain management (SCM). IRP has been studied for the last decades, for the single item IRP such as [2] [3] [8] [9] [10], and for the MIRP [1] [4] [5] [6] [7] [11] [12] [13] [14] as well. However, fewer of the researches take the split delivery issue into account [4] [5] [10].

2. Problem Description and Assumption

Consider one distribution center (DC, as the depot) and many customers in a supply chain system. The DC is responsible to deliver different products to meet the demands in each customer in finite time horizon without backorder. There are limited storage capacity shared by all the products in DC and customers. The manager of the supply chain in DC has full information of the inventory level and future demands of each customer. The holding cost happens in both sides. A homogeneous fleet of vehicles with limited capacity to deliver all the products and split delivery is allowed. The total cost includes holding cost, the fixed cost of vehicle using and flexible cost of traveling distances. The manager has to decide simultaneously the quantities of different products to deliver to each customer in the planning horizon, how many vehicles to use, and the route of each vehicle whereas minimizing the total cost.

To simplify the formulation for the proposed mixed integer programming (MIP) model, some assumptions are described as follows.

(1) The DC has sufficient inventory to meet all the demands.

(2) All the demands are deterministic.

(3) Each product has the same volume and weight.

(4) Leading time is not considered.

(5) No time window for transportation is considered.

(6) There are sufficient vehicles to satisfy the routing decision.

(7) The traveling distance matrix is symmetric and known.

3. Model Formulation

3.1. Notations

V: Set of nodes. 0 is the depot (DC); others are customers (retailers).

${V}^{\text{'}}$ : ${V}^{\text{'}}=V\backslash \left\{0\right\}$ .

i, j: Indices of nodes. $i,j\in V.$ .

p: Index of the product. P is the set of all products. $p\in P.$

k, h: Indices of the vehicle. K is the set of all vehicles. $k,h\in K.$

t: Index of the time period. T is the set of all time periods. $t\in T.$

${h}_{ip}$ : Unit holding cost of product p at node i. It is constant throughout the planning time horizon.

${L}_{ipt}$ : Inventory level of product p at node i in the end of time t.

${R}_{pt}$ : The available quantity of product p from suppliers at depot 0 in the beginning of time t.

${D}_{ipt}$ : The demand of product p at node i in the end of time t.

$R{C}_{i}$ : Storage capacity of node i. It is shared by all products.

$V{C}_{k}$ : Vehicle capacity.

${C}_{ij}$ : Unit distance cost from node i to node j.

M: A extremely big number.

FC: Fixed cost of vehicle used.

${S}_{ipkt}$ : Shipping quantity of product p of node i by vehicle k in time t.

$TK{S}_{ikt}$ : Total shipping quantity of node i by vehicle k in time t.

$T{S}_{it}$ : Total shipping quantity of node i in time t.

${W}_{kt}$ : Binary variable. It equals 1 if and only if vehicle k is used in time t, 0 otherwise.

${U}_{ijkt}$ : The flow of vehicle k traveling from node i to node j in time t.

$TK{S}_{ikt}$ : Fraction of the shipping quantity of node i by vehicle k in time t.

${X}_{ijkt}$ : Binary variable. It equals 1 if and only if vehicle k from node i to node j in time t, 0 otherwise.

3.2. Model

Minimize

$\underset{i\in V}{\sum}{\displaystyle \underset{p\in P}{\sum}{\displaystyle \underset{t\in T}{\sum}H{C}_{ip}\times {L}_{ipt}}}}+{\displaystyle \underset{i\in V}{\sum}{\displaystyle \underset{j\in V}{\sum}{\displaystyle \underset{k\in K}{\sum}{\displaystyle \underset{t\in T}{\sum}{C}_{ij}\times {X}_{ijkt}}}}}+{\displaystyle \underset{k\in K}{\sum}{\displaystyle \underset{t\in T}{\sum}{W}_{kt}\times FC}$ (1)

${L}_{0pt}={L}_{0p(t-1)}+{R}_{pt}-{\displaystyle \underset{i\in {V}^{\text{'}}}{\sum}{\displaystyle \underset{k\in K}{\sum}{S}_{ipkt}}}$ $\forall p\in P$ , $t\in T>0$ (2)

${L}_{ipt}={L}_{ip(t-1)}+{\displaystyle \underset{k\in K}{\sum}{S}_{ipkt}-{D}_{ipt}}$ $\forall i\in {V}^{\text{'}}$ , $\forall p\in P$ , $t\in T>0$ (3)

$\underset{p\in P}{\sum}{L}_{ipt}}\le R{C}_{i$ $\forall i\in V$ , $t\in T$ (4)

$\underset{p\in P}{\sum}{\displaystyle \underset{k\in K}{\sum}{S}_{ipkt}}\le R{C}_{i}-{\displaystyle \underset{p\in P}{\sum}{L}_{ip(t-1)}}$ $\forall i\in {V}^{\text{'}}$ , $t\in T>0$ (5)

$\underset{p\in P}{\sum}{S}_{ipkt}}=TK{S}_{ikt$ $\forall i\in {V}^{\text{'}}$ , $\forall k\in K$ , $t\in T$ (6)

$\underset{p\in P}{\sum}TK{S}_{ikt}}=T{S}_{it$ $\forall i\in {V}^{\text{'}}$ , $t\in T$ (7)

$\underset{j\in V}{\sum}{X}_{ijkt}}-{\displaystyle \underset{j\in V}{\sum}{X}_{jikt}}=0$ $\forall i\in {V}^{\text{'}}$ , $\forall k\in K$ , $t\in T$ (8)

$\underset{k\in K}{\sum}{F}_{ikt}}=1$ $\forall i\in {V}^{\text{'}}$ , $t\in T$ (9)

$\underset{i\in {V}^{\text{'}}}{\sum}T{S}_{it}\times {F}_{ikt}}\le V{C}_{k$ $\forall k\in K$ , $t\in T$ (10)

$\underset{j\in V}{\sum}{X}_{jikt}\ge {F}_{ikt}$ $\forall i\in {V}^{\text{'}}$ , $\forall k\in K$ , $t\in T$ (11)

$\underset{j\in V}{\sum}{U}_{jikt}}-{\displaystyle \underset{j\in V}{\sum}{U}_{ijkt}}=TK{S}_{ikt$ $\forall i\in {V}^{\text{'}}$ , $\forall k\in K$ , $t\in T$ (12)

$\underset{j\in V}{\sum}{U}_{jikt}}-{\displaystyle \underset{j\in V}{\sum}{U}_{ijkt}}=T{S}_{it}\times {F}_{ikt$ $\forall i\in {V}^{\text{'}}$ , $\forall k\in K$ , $t\in T$ (13)

${U}_{ijkt}\le {X}_{ijkt}\times V{C}_{k}$ $\forall i,j\in V$ , $\forall k\in K$ , $t\in T$ (14)

$\underset{i\in V}{\sum}{\displaystyle \underset{j\in V}{\sum}{X}_{ijkt}\le M\times {W}_{kt}}$ $\forall k\in K$ , $t\in T$ (15)

${W}_{ht}\le {W}_{kt}$ $\forall h,k(h>k)\in K$ , $t\in T$ (16)

${U}_{i0kt}=0$ $\forall i\in {V}^{\text{'}}$ , $\forall k\in K$ , $t\in T$ (17)

${X}_{iikt}=0$ $\forall i\in V$ , $\forall k\in K$ , $t\in T$ (18)

${L}_{ipt}\ge 0$ $\forall i\in V$ , $\forall p\in P$ , $t\in T$ (19)

${S}_{ipkt}$ , $TK{S}_{ikt}$ , $T{S}_{it}$ , ${D}_{ipt}\ge 0$ $\forall i\in {V}^{\text{'}}$ , $\forall p\in P$ , $\forall k\in K$ , $t\in T$ (20)

${W}_{kt}$ , ${X}_{ijkt}=\left\{0,1\right\}$ $\forall i,j\in V$ , $\forall k\in K$ , $t\in T$ (21)

The objective function (1) minimizes the total cost, including inventory cost, traveling distance cost and vehicle using cost. Constraints (2) and (3) ensure the inventory balance at depot and customers while constraints (4) define the maximum inventory capacity. Constraints (5) state the total shipping quantity of each customer is not over the remaining inventory capacity. Constraints (6) and (7) link the shipping quantity to the vehicle routing variables. Constraints (8) ensure the same vehicle arrives and leaves the customer served. Constraints (9) make sure each customer served by at least one vehicle receives its full planned shipment in each time period. Constraints (10) limit the delivery quantity to vehicle capacity while constraints (11) permit each customer to be served by more than one vehicle. Constraints (12) and (13) are the flow balance constraints and eliminate the sub-tours. Constraints (14) ensure the flow is not over the vehicle capacity when traveling between two nodes. Constraints (15) state the customers can be served only by the vehicle which is used. Constraints (16) say the vehicle using order. Constraints (17) ensure there is no product when the vehicle returns to the depot. Constraints (18) prohibit the same vehicle back to the same customer served. Constraints (19) and (20) state the non-negative integer variables while constraints (21) define the binary variables.

4. Example Illustration

For a MIRP problem, one distribution center and two customers (C1, C2) with two products (P1, P2) are considered. The planning horizon is 3 days. The inventory and demand information, and distance matrix are given in Table 1 and Table 2, respectively. The storage capacity of the DC and retailers are 999, 20, 20. The available amount of P1 and P2 from suppliers are 20, 20 in each period. Holding cost of P1 and P2 in DC are both 0.01 and in customers are 0.05 and 0.08. There are three homogenous vehicles with 10 units of capacity in each day. Unit cost of traveling distance is 1 while fixed cost of vehicle using is 5.

The addressed problem is solved by the Lingo 11. The total cost is obtained as 98.6, and the results are summarized in Table 3 and Table 4, and the routes in each day are shown in Figure 1 as well.

Table 1. Initial inventory and demand information of DC and customers.

Table 2. Distance matrix.

Table 3. Delivery quantity for the addressed example.

Table 4. Stock level for the addressed example.

Figure 1. Vehicle routes for the addressed example.

5. Conclusion

In this article, a mathematical model is proposed for solving MIRP problem with split delivery allowed. Although the proposed model can solve the addressed problem optimally, it is run time consuming with the problem scale increasing. Therefore, some meta-heuristics such as genetic based algorithms, particle swarming can be applied in the future study for solving the large scale problem.

References

[1] Abdelmaguid, T.F. and Dessouky, M.M. (2006) A Genetic Algorithm Approach to the Integrated Inventory-Distribution Problem. International Journal of Production Re-search, 44, 4445-4464. https://doi.org/10.1080/00207540600597138

[2] Archetti, C., Bertazzi, L., Hertz, A. and Speranza, M.G. (2012) A Hybrid Heuristic for an Invento-ry-Routing Problem. INFORMS Journal on Computing, 24, 101-116.
https://doi.org/10.1287/ijoc.1100.0439

[3] Archetti, C., Bertazzi, L., Laporte, G. and Speranza, M.G. (2007) A Branch-and-Cut Algorithm for a Vendor-Managed Invento-ry-Routing Problem. Transportation Science, 41, 382-391. https://doi.org/10.1287/trsc.1060.0188

[4] Bell, W.J., Dalberto, L.M., Greenfield, A.J., Jaikumar, R., Kedia, P., Mack, R.G. and Prutzman, P.J. (1983) Improving the Distribution of Industrial Gases with an On-line Computerized Routing and Scheduling Optimizer. Interfaces, 13, 4-23.
https://doi.org/10.1287/inte.13.6.4

[5] Bertazzi, L., Speranza, M.G. and Ukovich, W. (1997) Minimization of Logistic Costs with Given Frequencies. Transportation Re-search Part B, 31, 327-340.
https://doi.org/10.1016/S0191-2615(96)00029-X

[6] Coelho, L.C., and Laporte G. (2013) A Branch-and-Cut Algorithm for the Multi-Product Multi-Vehicle Invento-ry-Routing Problem. International Journal of Production Research, 51, 7156-7169. https://doi.org/10.1080/00207543.2012.757668

[7] Coelho, L.C. and Laporte G. (2014) Optimal Joint Replenishment, Delivery and Inventory Management Policies for Perishable Products. Computers and Operations Research, 47, 42-52. https://doi.org/10.1016/j.cor.2014.01.013

[8] Federgruen, A. and Zipkin, P. (1984) A Combined Vehicle Routing and Inventory Allocation Problem. Operations Research, 32, 1019-1037.
https://doi.org/10.1287/opre.32.5.1019

[9] Hewitt, M., Nemhauser, G., Savelsbergh, M. and Song, J. (2013) A Branch-and-Price Guided Search Approach to Maritime In-ventory Routing. Computers and Operations Research, 40, 1410-1419. https://doi.org/10.1016/j.cor.2012.09.010

[10] Huang, S.H. and Lin, P.C. (2010) A Modified Ant Colony Optimization Algorithm for Multi-Item Inventory Routing Prob-lems with Demand Uncertainty. Transportation Research Part E, 46, 598-611. https://doi.org/10.1016/j.tre.2010.01.006

[11] Liu, S. and Lee, W. (2011) A Heuristic Method for the Inventory Routing Problem with Time Windows. Expert Systems with Applications, 38, 3223-3231.
https://doi.org/10.1016/j.eswa.2011.04.138

[12] Moin, N.H., Salhi, S. and Aziz, N.A.B. (2011) An Efficient Hybrid Genetic Algorithm for the Multi-Product Mul-ti-Period Inventory Routing Problem. International Journal of Production Economics, 133, 334-343.
https://doi.org/10.1016/j.ijpe.2010.06.012

[13] Popovic, D., Vidovic, M. and Radivojevic, G. (2012) Variable Neighborhood Search Heuristic for the Inventory Routing Problem in Fuel Delivery. Expert Systems with Applications, 39, 1390-1398. https://doi.org/10.1016/j.eswa.2012.05.064

[14] Vidovic, M., Popovic, D. and Rat-kovic, B. (2013) Mixed Integer and Heuristics Model for the Inventory Routing Prob-lem in Fuel Delivery. International Journal of Production Economics, 147, 593-604. https://doi.org/10.1016/j.ijpe.2013.04.034