A NEW HEURISTIC FOR INVENTORY ROUTING PROBLEM WITH BACKLOG

Proceedings of the 5th Annual ISC Research Symposium
ISCRS 2011
April 7, 2011, Rolla, Missouri
A NEW HEURISTIC FOR INVENTORY ROUTING PROBLEM WITH BACKLOG
Scott E. Grasman /Missouri University of
Science and Technology
ABSTRACT
Inventory routing problem (IRP) is a major concern in
operation management of a supply chain. The aim is to
integrate the transportation activities and inventory
management along the supply chain and avoid inefficiencies
caused by solving the underlying vehicle routing and inventory
sub-problems separately. This paper can be considered as an
extension of single depot IRP with order backlogs to a multidepot case. We develop a mixed integer mathematical model
for multi-depot inventory routing problems allowing order
backlogs. The mathematical model is used to find the best
compromise among transportation, holding and backlog costs
for small instances. A novel method based on Simulated
Annealing (SA) is proposed to solve larger IRPs with multiple
depots. Computational results for single depot problems are
compared with those reported in a recent article with similar
assumptions. We have extended the proposed SA algorithm for
solving multi-depot IRPs with the possibility of order
backlogging. Since we could not find any reported
computational results for this type of multi-depot problems; we
have compared the results with exact solutions obtained by
Cplex solver.
1. INTRODUCTION
In recent years, one of the most interesting and challenging
issues in the area of supply chain management is the integration
and coordination of activities. Inventory routing problem (IRP)
is one of the famous issues in this category. [1] Introduced this
problem as a combination of Vehicle Routing Problem (VRP)
and inventory control and showed that it is NP-hard . Another
interpretation of IRP was given in [2], as determination of the
set of customers in a supply network with specific demands to
be served in each day. A more precise definition, as suggested
by [3], states that an IRP is how to distribute a single product
from a single supplier to a set of geographically scattered
retailers/ customers by a fleet of homogenous vehicles over a
period of time [4]. The retailers store specific amount of
inventory that is consumed by a certain rate. The objective is to
find the minimum total distribution and inventory holding cost
while assuring customers’ demands are satisfied in due time.
Other constraints have been added to the original problem over
time that led to various types of IRPs.
There exist various applications of this class of problems
reported in the literature; for instance, distributing liquid
propane in petrochemical industry [5], retail products in
Netherland [6], automobile components [7] and frozen products
[8]. In maritime, the distribution of ammoniac from a central
depot to a group of consumers has been reported in [9].
Golbarg Kazemi Tutunchi/ Missouri University
of Science and Technology
/[email protected]
According to a recent survey in [9], there exists very few
reported research on inventory routing problem with backlog
(IRPB). [10] Proposed a mixed integer mathematical model for
a single period IRP with possibility of backlog and
deterministic demands in which they assumed that a central
depot would serve a set of customers using heterogeneous
vehicles. Later, a single-depot multi-period IRPB was put
forward by [11] while the demand rates were supposed to be
deterministic. The solution method used therein was based on
decomposition of the problem into ordering and distributing
sub-problems. [12, 13] investigated IRPB with infinite time
horizon and stochastic demands. They found a lower bound for
cost of serving the customers by unlimited number of
homogenous vehicles in a direct shipping format. [14]
Investigated a single depot IRPB with stochastic demand. They
assumed a single vehicle would serve the retailers in direct and
multiple formats and their solution approach was Monte-Carlo
simulation and heavy traffic analysis. [15] Put forward an IRPB
with stochastic demand in which a single vehicle serves the
retailers. They proposed an analytical model and solved it using
simulation and a change-revert heuristic method. Other
researchers investigated the many-to-many topology in IRP
with finite time horizon [16-19]. [20] Introduced a single depot
IRPB with deterministic demand allowing multiple trips taken
by a fleet of heterogeneous vehicles. They introduced a geneticbased constructive heuristic method for solving the problem.
Recently, they proposed another constructive heuristic method
for the same problem and improved their solution [21].
Multi-depot IRPs have been investigated in several cases
before but without considering the possibility of order backlogs
[9]. This paper can be considered as an extension of single
depot IRP with order backlogs to a multi-depot problem. We
develop a mixed integer mathematical model for multi-depot
inventory routing problems allowing order backlogs. The
mathematical model is used to find the best compromise among
transportation, holding and backlog costs for small instances.
We extend and combine the best existing heuristics for solving
the vehicle routing and inventory routing sub-problems and
improve their solutions by applying the algorithms iteratively.
This allows one to solve larger problems and get solutions
closer to optimality in reasonable time. Furthermore, an
efficient simulated annealing algorithm has been developed and
used for solving medium to large instances.
The rest of this paper is organized as follows. In Section 2,
a mathematical model is developed for the problem. The
solution algorithm is described in Section 3, followed by the
computational results in Section 4. Conclusions are in Section
5.
1
2. PROBLEM DEFINITION AND THE MATHEMATICAL
MODEL
We consider a two echelon supply chain in which a set of
retailers are served by a fleet of capacitated homogenous
vehicles In the first case, a central depot (supplier) serves a set
of geographically scattered retailers having certain demands.
Retailers have limited storage capacities and cannot
accommodate as much supply as they want. The problem is a
multi-period planning with a finite time horizon. Retailers’
demands in each period are assumed to be known and should be
met by the end of the designated time period. The suppliers
incur a penalty named backlog cost if the delivery is late.
Retailers who encountered order backlogs shall get service in
later periods. The objective is to find the best trade-off among
transportation, backlog and holding cost. In the multi-depot
case, the central depot is replaced with several depots. All other
assumptions remain unchanged. The assumptions on the VRP
part in both cases are the same as in the classical models.
In this section, we develop a mixed integer mathematical
model for Multi Depot Inventory Routing Problem with
Backlog (MDIRPB). First, the sets, constants, parameters and
decision variables used in the model are introduced.
Sets:
R: retailer set
D: depot set
T: time period set
K: vehicle set
Constants and Parameters:
𝑐𝑖𝑗 : Travel cost from retailer/depot i to retailer/depot j for
∀ 𝑖, 𝑗𝜖 (𝑅 ∪ 𝐷)
Satisfying the triangular inequality:
∀ 𝑖, 𝑗𝜖 (𝑅 ∪ 𝐷)
(1)
𝑐𝑖𝑘 + 𝑐𝑘𝑗 ≥ 𝑐𝑖𝑗
𝜋𝑖 : Backlog cost per period per unit for ∀ 𝑖𝜖𝑅
ℎ𝑖 : holding cost per period per unit for ∀ 𝑖𝜖𝑅
𝑑𝑖𝑡 : Demand of retailer 𝑖 in period 𝑡 for ∀ 𝑖𝜖 (𝑅 ∪ 𝐷), ∀ 𝑡𝜖 𝑇
𝑣𝑖 : Storage capacity of retailer 𝑖 for ∀ 𝑖𝜖𝑅
𝑠𝑖𝑘 : Time to serve retailer 𝑖 by vehicle k for ∀ 𝑖𝜖𝑅 , ∀𝑘𝜖𝐾
𝑡𝑖𝑗 : travel time from retailer/ supplier 𝑖 to retailer/supplier 𝑗 for
∀ 𝑖, 𝑗𝜖 (𝑅 ∪ 𝐷)
𝑏𝑖 : Initial amount of inventory of retailer 𝑖 for ∀ 𝑖𝜖𝑅
𝐿: Length of each time period
𝑄: Vehicle capacity
M: a big positive constant
𝑁: Maximum number of the retailers
Decision variables:
+
: Inventory amount in retailer 𝑖 store in period 𝑡, for
𝐼𝑖,𝑡
∀ 𝑖𝜖𝑅, ∀ 𝑡𝜖𝑇
𝑊𝑖𝑘𝑡 : The amount delivered to retailer 𝑖 by vehicle 𝑘 in period
𝑡, for ∀ 𝑖𝜖𝑅, ∀ 𝑘𝜖𝐾, ∀ 𝑡𝜖𝑇
𝑈𝑖,𝑡 : If a vehicle is serving retailer 𝑖, the number of the other
retailers that should be visited by that vehicle after customer 𝑖
in each period of time. It should be noted that 𝑈𝑖,𝑡 is unique
for ∀ 𝑖𝜖𝑅, ∀ 𝑡𝜖𝑇
The Mathematical Model is given by:
𝑀𝑖𝑛 𝑧 = � �
� � � 𝑐𝑖𝑗 𝑋𝑖𝑗𝑘𝑡 �
𝑖∈𝑅∪𝐷 𝑗∈𝑅∪𝐷 𝑘∈𝐾 𝑡∈𝑇
−
+
+ �� � 𝜋𝑖 𝐼𝑖,𝑡
� + �� � ℎ𝑖 𝐼𝑖,𝑡
�
𝑖∈𝑅 𝑡∈𝑇
Subject to:
𝑖∈𝑅 𝑡∈𝑇
� � 𝑋𝑖𝑗𝑘𝑡 ≤ 1
∀ 𝑖 ∈ 𝑅, ∀ 𝑡 ∈ 𝑇
𝑘∈𝐾 𝑗∈𝑅∪𝐷
� 𝑋𝑖𝑛𝑘𝑡 − � 𝑋𝑛𝑗𝑘𝑡 = 0
𝑖∈𝑅∪𝐷
𝑛≠𝑖
(2)
𝑗∈𝑅∪𝐷
𝑛≠𝑗
(3)
(4)
∀𝑘 ∈ 𝐾, ∀𝑛 ∈ 𝑅 ∪ 𝐷, ∀𝑡 ∈ 𝑇
𝑋𝑖𝑗𝑘𝑡 ≤ � 𝑋𝑝𝑖𝑘𝑡 + 𝑀�𝑈𝑖,𝑡 − 1�
(5)
𝑝∈𝐷
∀ 𝑖, 𝑗 ∈ 𝑅 𝑖 ≠ 𝑗, ∀ 𝑡 ∈ 𝑇, ∀𝑘 ∈ 𝐾
�
�
𝑖∈𝑅∪𝐷 𝑗∈𝑅∪𝐷,𝑖≠𝑗
+
𝐼𝑖,𝑡−1
𝑠𝑖𝑘 𝑋𝑖𝑗𝑘𝑡 + �
≤𝐿
+ � 𝑊𝑖𝑘𝑡 +
𝑘∈𝐾
∀ 𝑖 ∈ 𝑅, ∀𝑡 ∈ 𝑇
+
𝐼𝑖,𝑡
≤ 𝑣𝑖
−
𝐼𝑖,𝑡
𝑊𝑗𝑘𝑡 ≤ 𝑄 � 𝑋𝑖𝑗𝑘𝑡
𝑖∈𝑅∪𝐷
� 𝑊𝑗𝑘𝑡 ≤ 𝑄
𝑗∈𝑅
�
𝑖∈𝑅∪𝐷 𝑗∈𝑅∪𝐷,𝑖≠𝑗
=
+
𝐼𝑖,𝑡
𝑡𝑖𝑗 𝑋𝑖𝑗𝑘𝑡
∀𝑘 ∈ 𝐾, ∀𝑡 ∈ 𝑇
−
+ 𝑑𝑖𝑡 + 𝐼𝑖,𝑡−1
∀ 𝑖 ∈ 𝑅, ∀ 𝑡 ∈ 𝑇, ∀ 𝑘 ∈ 𝐾
∀𝑗 ∈ 𝑅, ∀𝑘 ∈ 𝐾, ∀𝑡 ∈ 𝑇
∀𝑘 ∈ 𝐾, ∀𝑡 ∈ 𝑇
𝑈𝑖,𝑡 − 𝑈𝑗,𝑡 + �(𝑁 − 1)𝑋𝑖𝑗𝑘𝑡 ≤ (𝑁 − 1) − 1
𝑘∈𝐾
(6)
(7)
(8)
(9)
(10)
(11)
∀𝑖, 𝑗 ∈ 𝑅 𝑖 ≠ 𝑗 ∀ 𝑡 ∈ 𝑇
𝑈𝑖,𝑡 ≤ 𝑁 − 1
∀ 𝑖 ∈ 𝑅, ∀ ∈ 𝑇
(12)
𝑈𝑖,𝑡 ≥ 1 𝑎𝑛𝑑 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 ∀ 𝑖 ∈ 𝑅 , ∀ 𝑡 ∈ 𝑇
(13)
𝑋𝑖𝑗𝑘𝑡 ∈ {0,1}
∀ 𝑖, 𝑗 ∈ 𝑅 ∪ 𝐷 𝑖 ≠ 𝑗 , ∀ 𝑘 ∈ 𝐾, ∀ 𝑡 ∈ 𝑇 (14)
For ∀ 𝑖, 𝑗𝜖 {𝑅 ∪ 𝐷} , ∀ 𝑡𝜖𝑇 , ∀ 𝑘𝜖𝐾,
(15)
𝑊𝑖𝑘𝑡 ≥ 0
∀ 𝑖 ∈ 𝑅 , ∀ 𝑘 ∈ 𝐾, ∀ 𝑡 ∈ 𝑇
+
𝑋𝑖𝑗𝑘𝑡
𝐼𝑖,𝑡
≥0
∀ 𝑖 ∈ 𝑅 ,∀ 𝑡 ∈ 𝑇
(16)
1,
𝑖𝑓 𝑣𝑒ℎ𝑖𝑐𝑙𝑒 𝑘 𝑡𝑟𝑎𝑣𝑒𝑙𝑠 𝑓𝑟𝑜𝑚 𝑛𝑜𝑑𝑒 𝑖 𝑡𝑜 𝑛𝑜𝑑𝑒 𝑗 𝑖𝑛 𝑝𝑒𝑟𝑖𝑜𝑑 𝑡 𝐼 + = 𝑏
∀
𝑖
∈
𝑅
(17)
=�
𝑖,0
0,
𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
−
𝐼𝑖,𝑡 ≥ 0
∀ 𝑖 ∈ 𝑅 ,∀ 𝑡 ∈ 𝑇
(18)
−
𝐼𝑖,𝑡
: Backlog amount incurred by retailer 𝑖 in period 𝑡, for
The objective function Eq. (2) minimizes the total cost of
∀ 𝑖𝜖𝑅, ∀ 𝑡𝜖𝑇
transportation, backlog and holding inventories. The shortage
and inventory carrying costs are calculated by the net backlog
2
and inventory amount in the retailer’s store at the end of each
period. Equation (3) reassures that each retailer is visited only
once by only one vehicle in each time period. Equation (4)
explains the ordinary flow conservation relationship. Equation
(5) indicates that each vehicle starts its trip from a depot and
returns to the same depot during each time period (according to
both Eq. (4) and (5)). It is implied by Eq. (6) that the transfer
time between retailers and suppliers does not exceed the length
of a time period which is considered to be an eight hour time
period. All the retailers are supposed to be served by the end of
that period. Equation (7) is the inventory balance equation.
Equation (8) indicates that the inventory of each retailer cannot
exceed its storage capacity. Equation (9) and (10) define upper
bounds on the delivery amounts by the vehicle capacity.
Equations (11)-(13) are the MTZ sub-tour elimination
relationships (Tucker et al. 1960). Equations (14)-(16) and
equation (18) are the domain constraints. Equation (17)
indicates the initial amount of inventory at the retailer’s store.
The resulting model, called MDIRPB, is mixed integer
linear program and can be thought of as a combination of
MDVRP and an inventory control model. Because of the
underlying VRP component, the problem is NP-hard and its
complexity grows exponentially by increasing the number of
retailers, depots, time periods. The tighter the due dates and
capacity limitations, the more difficult the problem becomes to
solve.
3. THE SOLUTION METHOD
One of the key decision in inventory routing problem is to
determine how much to deliver to each retailer in each period
and by which vehicle (𝑤𝑖𝑘𝑡 ). Once this decision has been made,
the inventory and backlog amounts can be determined using
Equations (7) and (8). Then, a VRP can be solved for each
period to find the best possible routes. Many researchers
decompose an IRP into two sub problems: an inventory control
sub-problem (SUB1) and a vehicle routing sub-problem
(SUB2) (see for instance, [22, 23]). We make an integrated
decision on both sub-problems using the proposed heuristic
algorithm, named SA-UFT in this paper.
In the first sub-problem, the amount of 𝑊𝑖𝑘𝑡 is computed
first, and then the second sub-problem uses these amounts to
find the most appropriate routes in each period. The proposed
heuristic method is based on determining the values of 𝑊𝑖𝑘𝑡
appropriately. For this purpose, it does an efficient trade-off
among transportation, holding and backlog costs. In this
section, the solution procedure for solving multi-depot vehicle
routing problem is described first. Then, a procedure for
neighborhood generation is explained in the next section.
Finally, the proposed SA-UFT algorithm for solving MDIRPB
is described.
3.1. MDVRP Solution Procedure
Vehicle routing problem is one of the key components of
inventory routing problem. Therefore, the algorithm used for
solving the underlying VRP should be an efficient one. In this
paper, we employ an efficient algorithm for solving multi-depot
vehicle routing problem. The method decomposes the multidepot problem to several single depot ones following the ideas
in [24]. Then, each VRP is solved using an efficient saving
based algorithm of Clarke and Wright [25]. Afterwards, the
solution is improved using a nearest neighborhood heuristic
(NNH). The combination of these three algorithms helps us find
a good solution for MDVRP part of MDIRPB.
3.2. SA-UFT Algorithm for Solving MDIRPB
We propose a simulated annealing (SA) based heuristic
method, named SA-UFT, for solving MDIRPB. Simulated
annealing is a probabilistic method for finding the global
minimum of a cost function that may have several local minima
[26]. We have devised a heuristic rule for generating
appropriate neighborhoods based on evaluating an unfitness
function defined below. It involves the process of interchanging
sets of retailers to be served in different periods of the planning
horizon. All retailers are evaluated according to the unfitness
function which shows how improperly retailers are assigned to
be served in their designated periods. Then, a set of the retailers
are selected to be removed from a specific period and assigned
to another period so that their unfitness function is improved.
The whole process of the solution method are explained in
Fig.1. The Parameters and Notations used in the proposed SAUFT neighborhood generation are as follows:
𝑇: Number of planning periods
𝑖𝑡𝑒𝑟: Iterations counter
𝑈𝐹𝑇. 𝑐ℎ𝑎𝑛𝑔𝑒𝑤𝑡𝑜𝑖𝑘𝑡 : New delivery amount to customer 𝑖 in
period 𝑡 by vehicle 𝑘
𝑐ℎ𝑎𝑛𝑔𝑒𝑟𝑎𝑡𝑒: The delivery probability
𝑈𝐹𝑇. 𝑉𝑎𝑙𝑢𝑒𝑖,𝑡 : Unfitness value for retailer 𝑖 in period 𝑡
𝑉𝑅𝑃: Vehicle routing cost
Neighborhood generation for each retailer:
Step1: Get the initial solution (𝑊𝑖𝑘𝑡 ), and evaluate (𝐼𝑛𝑣𝑖,𝑡 );
Step 2: For each period (𝑡 = 1: 𝑇) specify (𝑊𝑖𝑘𝑡 > 0), and call
them (𝐶𝑊𝑡 );
Step 3: For each period (𝑡 = 1: 𝑇);
Specify the retailers of (𝐶𝑊𝑡 );
Sort those retailers in an ascendant order according to their
travel cost;
Step 4: For each period (𝑡 = 1: 𝑇);
𝑖𝑓 𝑖𝑛𝑣𝑖,𝑡 > 0
𝑈𝐹𝑇. 𝑐ℎ𝑎𝑛𝑔𝑒𝑤𝑡𝑜𝑖𝑘𝑡 = 0;
else
𝑈𝐹𝑇. 𝑐ℎ𝑎𝑛𝑔𝑒𝑤𝑡𝑜𝑖𝑘𝑡 = max (0, −𝐼𝑛𝑣𝑖,𝑡 );
Set 𝑑𝑡 = 1;
While (𝑡 + 𝑑𝑡 < 𝑇)
𝑖𝑓 (𝑟𝑎𝑛𝑑 > 𝑐ℎ𝑎𝑛𝑔𝑒𝑟𝑎𝑡𝑒)
𝑖𝑓(𝑈𝐹𝑇. 𝑐ℎ𝑎𝑛𝑔𝑒𝑤𝑡𝑜𝑖𝑘𝑡 + 𝑑𝑖(𝑡+𝑑𝑡)
< 𝐶𝑖 && 𝑈𝐹𝑇. 𝑐ℎ𝑎𝑛𝑔𝑒𝑤𝑡𝑜𝑖𝑘𝑡 + 𝑑𝑖(𝑡+𝑑𝑡) < 𝑄)
𝑈𝐹𝑇. 𝑐ℎ𝑎𝑛𝑔𝑒𝑤𝑡𝑜𝑖𝑘𝑡 = 𝑈𝐹𝑇. 𝑐ℎ𝑎𝑛𝑔𝑒𝑤𝑡𝑜𝑖𝑘𝑡 + 𝑑𝑖(𝑡+𝑑𝑡) ;
𝑒𝑙𝑠𝑒
Break;
3
Update 𝑑𝑡 = 𝑑𝑡 + 1;
𝑒𝑛𝑑 𝑜𝑓 𝑙𝑜𝑜𝑝
Step 5: Calculate the unfitness value of each retailer for each
period
𝑈𝐹𝑇. 𝑉𝑎𝑙𝑢𝑒𝑖,𝑡 = max�0, 𝑖𝑛𝑣𝑖,𝑡 � ℎ𝑖 + max�0, −𝑖𝑛𝑣𝑖,𝑡 � 𝜋𝑖 +
𝑉𝑅𝑃(𝑊𝑖𝑘𝑡 ) −
max�0, 𝑖𝑛𝑣𝑖,𝑡 − 𝑊𝑖𝑘𝑡 + 𝑈𝐹𝑇. 𝑐ℎ𝑎𝑛𝑔𝑒𝑤𝑡𝑜𝑖𝑘𝑡 � ℎ𝑖 −
max �0, −�𝑖𝑛𝑣𝑖,𝑡 − 𝑊𝑖𝑘𝑡 + 𝑈𝐹𝑇. 𝑐ℎ𝑎𝑛𝑔𝑒𝑤𝑡𝑜𝑖𝑘𝑡 �� 𝜋𝑖 −
𝑉𝑅𝑃(𝑈𝐹𝑇. 𝑐ℎ𝑎𝑛𝑔𝑒𝑤𝑡𝑜𝑖𝑘𝑡 )
Step 6: Sort 𝑈𝐹𝑇. 𝑉𝑎𝑙𝑢𝑒𝑖,𝑡 in a descendant order.
4. COMPUTATIONAL RESULTS
To test the efficiency of the proposed heuristic method, IRPB
problems have been solved in two cases: single depot IRPB and
multi depot IRPB. For the first case, we use [21] data set and
compare SA-UFT costs with those of the ETCH-H and BDXH
starting with ETCH-H algorithms of the mentioned article. For
the second case, we generate random data, and benchmark the
solution found by SA-UFT against the lower and upper bounds
obtained by AMPL-CPLEX 10.1. The heuristic method has
been coded and compiled in MATLAB (version R2008b)
running under a Pentium dual-core processor with a clock
speed of 1.67 GHz with 2GB RAM.
For single depot there are three scenarios proposed in [21].
The first and second scenarios contain 12 problem types. For
each type, they generate and solve five samples. Each sample is
shown by six digits. The first one represents the scenario
number. The second and third ones are for customer count, and
the fourth one is for time period count. The fifth one stands for
the vehicle count, and the last one is the sample number in that
problem type. Tables 1, shows some samples of results for the
three scenarios. The results reported in Table 1 shows that SAUFT makes a better trade-off between holding and
transportation cost in almost all cases and leads to lower total
costs for all the samples of ETCH-H. The run time for SA-UFT
in all the scenarios is less than 5 seconds.
To evaluate SA-UFT efficiency for multi-depot IRPB, we
generate test problems. Table 2 shows the results multi-depot
IRPB. As can be seen in this table, the results obtained by SAUFT are very close to those of Cplex. Furthermore, for
displaying the impact of allowing order backlog, we compare
the results of IRP with those of IRPB solved by the proposed
algorithm and the results are in Table 3. We see that the results
for IRPB are better than those of IRP for all the cases. Figure 2
shows the optimal routes for sample 1-0551-2. Figure 3 shows
the convergence of SA-UFT in the total cost.
5. CONCLUSION
This paper investigates multi-depot inventory routing
problems allowing order backlogs. Due to the inevitability of
backlogging in real world problems, and the existence of more
than one supplier depot in most cases, the combination of these
two features in an integrated model is of practical importance.
The method developed herein helps to decrease the cost in
comparison with the case where single depot IRP with no
Fig. 1 Flowchart of the Proposed Solution Procedure
Fig. 2 Vehicle Routing Plots for the given example
possibility of shortage is considered. The resulting mixed
integer model has been solved using a SA-based heuristic
method proposed herein. The performance of the proposed
heuristic is compared to that of ETCH-H appeared in a recent
paper for single depot case [21]. The effectiveness of IRPB for
4
[5]
14000
12000
[6]
10000
8000
[7]
6000
4000
[8]
2000
0
0
10
20
30
40
50
60
70
80
Fig. 3 Cost Convergence Plot for the given example
multi-depot case is verified by comparing the results with those
obtained by Cplex solver. The numerical results show that SAUFT outperforms existing ETCH-H in terms of cost
minimization. Another comparison shows that the quality of
solutions obtained by SA-UFT in multi-depot test problems is
reasonably better than those found by Cplex. However, the
main advantage of the proposed SA-UFT method is its ability
to solve larger instances of multi-depot IRPB in a reasonable
time.
Future research could be aimed at finding efficient lower
bounds and an exact solution method for integrated inventory
and routing problems as well as considering uncertainty of the
model parameters in the development of a solution procedure
for it.
8. ACKNOWLEDGMENTS
This research is sponsored by Intelligent System Center at
Missouri University of Science and Technology. The writer would
like to thank this center for their kind support. The writers would
also like to thank Dr. Scott Grasman, for his invaluable help in the
process of research.
9. REFERENCES
Golden BL, Assad A, Dahl R, (1984), “Analysis of a large
scale vehicle routing problem with an inventory
component”, Large Scale Systems; 7:181–90.
[2] Custo´ dio AL, Oliveira C. Redesigning distribution
operations: a case study on integrating inventory
management and vehicle routes design. International
Journal of Logistics: Research and Applications 2006;
9:169–87.
[3] Campbell AM, Clarke L, Kleywegt A, Savelsbergh MWP,
1998, “Inventory routing. In: Crainic TG, Laporte G,
editors.”, Fleet management and logistics. Dordrecht:
Kluwer Academic Publishers.
[4] Boudia, M., M.A.O. Louly & C. Prins. (2007). A reactive
grasp and path relinking for a combined productiondistribution problem. Computers & Operations Research,
34(11), 3402-3419.
[1]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]
5
Savelsbergh MWP, Song J-H, 2007, “Inventory routing
with continuous moves”, Computers & Operations
Research; 34:1744–63.
Dror M, Ball M, 1987, “Inventory/routing: reduction from
an annual to a short- period problem”, Naval Research
Logistics; 34:891–905.
Al-Khayyal F, Hwang S-J, 2007, “Inventory constrained
maritime routing and scheduling for multi-commodity
liquid bulk, partI: applications and model”, European
Journal of Operational Research; 176:106–30.
Cerny V., 1985, “A thermodynamic approach to the
traveling salesman problem: An efficient simulation.
Journal of Optimization Theory and Applications 45; 4151.
Andersson H, Hoff A, Christiansen M, Hasle G,
Lokketangen A,2009, “ Industrial Aspects and Literature
Survey: Combined Inventory Management and Routing”,
Computers & Operations Research.
Chien TW, Balakrishnan A, Wong RT, 1989, “An
integrated inventory allocation and vehicle routing
problem”, Transportation Science; 23:67–76.
Chandra P. A dynamic distribution model with warehouse
and customer replenishment requirements. Journal of the
Operational Research Society 1993; 44:681–92.
Barnes-Schuster D, Bassok Y, 1997, “Direct shipping and
the dynamic single-depot/ multi-retailer inventory
system”, European Journal of Operational Research;
101:509–18.
Bard JF, Huang L, Jaillet P, Dror M. 1998, “A
decomposition approach to the inventory routing problem
with satellite facilities”, Transportation Science;32:189–
203.
Reiman MI, Rubio R, Wein LM, 1999, “Heavy traffic
analysis of the dynamic stochastic inventory-routing
problem”, Transportation Science; 33:361–80.
Schwartz LB, Ward JE, Zhai X, 2006, “On the interactions
between routing and inventory-management policies in a
distribution
system”,
one-warehouse
N-retailer
Manufacturing & Service Operations Management
;8:253–72.
Christiansen M, 1999, “Decomposition of a combined
inventory and time constrained ship routing problem”,
Transportation Science; 33:3–16.
Flatberg T, Haavardtun J, Kloster O, Løkketangen A,
2000, “Combining exact and heuristic methods for solving
a vessel routing problem with inventory constraints and
time windows”, Ricerca Operativa;29:55–68.
Persson JA, G¨othe-Lundgren M, 2005, “Shipment
planning at oil refineries using column generation and
valid inequalities”, European Journal of Operational
Research; 163:631–52.
Savelsbergh M and Song J, 2008, “An optimization
algorithm for the inventory routing problem with
continuous moves”, Computers & Operations Research 35
-2266–2282.
[20] Abdelmaguid TF, Dessouky MM, 2006, “A genetic
[24] Gillett B E, Miller L R, 1971, “A Heuristic Algorithm for
algorithm approach to the integrated inventorydistribution problem”, International Journal of Production
Research; 44:4445–64.
[21] Abdelmaguid TF, Dessouky MM and Fernando O, 2009,
“Heuristic approaches for the inventory-routing problem
with backlogging”, Computers & Industrial Engineering
(56) 1519–1534.
[22] Bard, J.F. and N. Nananukul (2009b), “Heuristics for a
multiperiod inventory routing problem with production
decisions,” Computers & Industrial Engineering, 57(3),
713-723.
[23] Boudia, M. and C. Prins (2009), “A memetic algorithm
with dynamic population management for an integrated
production–distribution problem,” European Journal of
Operational Research, 195(3), 703-715.
the Vehicle-Dispatch Problem”, Operations Research, 22,
340-349.
[25] Clarke, G., and Wright, J. 1964. “Scheduling of vehicles
from a central depot to a number of delivery points.”
Operations Research, 12, 568–581.
[26] kirkpatrick S., Gelett C.D. and Vecchi M.P. (1983),
“Optimization by simulated annealing” Science 220; 621630.
Problem
1-1072-1
1-1072-2
1-1072-3
1-1072-4
1-1072-5
2-1572-1
2-1572-2
2-1572-3
2-1572-4
2-1572-5
3-3027-1
3-3027-2
3-3027-3
3-3027-4
3-3027-5
Table 1. Comparison of the Results of ETCH-H with those of SA-UFT for the First Scenario
ETCH-H
SA-UFT
Holding
Backlog
Transp.
Total
Holding
Backlog
Transp.
149.97
0
351
500.97
124.9
0
297.708
126.52
0
436
562.52
148.09
0
291.41
114.39
0
342
456.39
137.47
0
283.14
74.34
0
453
527.34
108.49
0
284.08
103.68
0
441
544.68
122.43
0
294.53
51.92
0
1194
1245.92
233.71
93.21
854.13
25.56
72.41
1137
1234.97
239.09
18.76
718.18
65.88
40.5
1244
1350.38
198.01
130.27
899.02
99.43
15.65
1080
1195.08
207.19
22.8
869.1
20.89
188.07
1180
1388.96
229.83
59.32
782.36
51.05
16.25
781
848.3
171.16
75.65
565.86
55.4
6.18
766
827.58
181.33
26.78
579.83
51.16
0
883
934.16
137.87
45.52
641.13
50.61
10.47
827
888.08
164.98
81.77
562.7
31.59
0
870
901.59
149.54
94.65
643.16
Total
422.6
439.5
420.61
392.57
416.98
1181.1
976.03
1227. 3
1099.1
1071.5
812.67
787.94
824.52
809.45
887.35
Table 2. Computational Results for Small Samples of Multi-Depot IRPs
Problem
Time
05-2-7-1
05-2-7-2
05-2-7-3
10-2-5-1
10-2-5-2
10-2-5-3
Holding
231.97
188.59
204.56
222.23
232.93
00:31:47
00:03:45
02:23:29
02:34:05
02:44:03
02:35:57
Backlog
19.97
68.56
55.11
33.96
48.8
Cplex
SA-UFT
Best
O.F
Total
Holding
Backlog
Transp.
Bound
227.18
227.19
234.98
50.85
0
184.11
148.64
148.66
152.03
31.23
0
120.8
213.378
213.4091
215.65
72.32
0
143.34
213.76
227.23
230.24
65.76
0
164.48
230.61
253.53
237.35
76.27
0
161.08
229.89
246.91
240.85
63.95
0
176.9
Table 3. Comparison of the Results of IRPB with those of IRP
IRPB
IRP
Transp.
Total
Holding
Backlog
Transp.
404.73
656.67
253.43
0
863.47
396.77
653.92
265.71
0
429.34
362.34
622.01
277.79
0
475.26
363.78
619.78
273.46
0
434.26
463.52
742.08
295.51
0
527.63
6
Time
00:00:02
00:00:01
00:00:02
00:00:03
00:00:07
00:00:05
Total
1116.9
695.05
753.05
707.72
823.14