# Integrated Inventory Routing Problem with Quality Time Windows and Loading Cost for Deteriorating Items under Discrete Time

Authors: Tao Jia; Xiaofan Li; Nengmin Wang; Ran Li
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

We investigate an integrated inventory routing problem (IRP) in which one supplier with limited production capacity distributes a single item to a set of retailers using homogeneous vehicles. In the objective function we consider a loading cost which is often neglected in previous research. Considering the deterioration in the products, we set a soft time window during the transportation stage and a hard time window during the sales stage, and to prevent jams and waiting cost, the time interval of two successive vehicles returning to the supplier’s facilities is required not to be overly short. Combining all of these factors, a two-echelon supply chain mixed integer programming model under discrete time is proposed, and a two-phase algorithm is developed. The first phase uses tabu search to obtain the retailers’ ordering matrix. The second phase is to generate production scheduling and distribution routing, adopting a saving algorithm and a neighbourhood search, respectively. Computational experiments are conducted to illustrate the effectiveness of the proposed model and algorithm.


---

## Body

## 1. Introduction

Perishable items exist widely in our daily life, such as fresh products, fruits, vegetables, and seafood, which decrease in quantity (or utility) during their delivery and storage stages. Deteriorating items can be classified by different criteria. According to the study of Raafat [1], two classes of deteriorating items are mainly of concern: (1) items with continuous decay, for example, inventory models that are subject to exponential decay, and (2) items with a fixed shelf life. Corresponding to theoretical research, two methods are always used in operations management practice to calculate the deteriorating costs of these two classes of deteriorating items, that is, the “weight discount” and “shelf life window.” The “Weight discount” is to calculate the deterioration (quantity/weight) loss in the storage and transportation stages; it is a weight discount rate that is generally negotiated by sellers and buyers, based on the delivered amount of goods, the preservation conditions, or the storage and transportation time. In the real world, this accounting method is always used in Chinese seafood cold chains. For most deteriorating items that are sold in the supermarkets, retailers can consider the quality corruption and set a fixed shelf-life window. Once they exceed the expiration date, the goods will be rejected, and their values will drop to zero instantaneously. Lukasse and Polderdijk [2] studied the quality degradation of mushrooms and established a piecewise nonlinear function of mushroom quality decline. Considering the randomness of the perishable food delivery speed and the time-varying temperatures, Hsu et al. [3] divided the corruption into transportation corruption and customer-site corruption that results from handling under normal temperatures. Perishable food had different spoilage rates in the above processes, and the customer site corruption rate was larger. Rong et al. [4] studied the distribution plan of a single product with a known demand rate. The objective of the production and distribution problem was to determine the varying deterioration that was caused by the time and temperature in different transportation and storage processes. If the quality requirements were not satisfied, then the goods would be abandoned and a penalty cost would be incurred.Transportation is an important logistics activity in the deteriorating items distribution channel, and it is also a key decision that connects the whole supply network as an effective integrated system. Moreover, for perishable products, the transportation process is more difficult to manipulate because of the changing environmental factors; thus, more attention should be paid to the transportation stage. In a joint decision-making supply chain, the order quantity from the network nodes is also an important factor that influences the transportation decision. Thus, to achieve the minimal total relevant cost of the channel, the managers should consider the transportation cost (the space value of the logistics) and the inventory cost (the time value of the logistics) simultaneously. The inventory routing problem (IRP) just seeks to determine simultaneously an optimal inventory and distribution strategy that minimises the total cost; thus, it is one of the hot spots in recent academic research. Federgruen and Zipkin [5] are amongst the first to study a single-day inventory routing problem. Customers’ demands were assumed to be a random variable. A limited inventory at the distribution centre can lead to shortages at the customer sites; as a result, the holding and shortage costs were considered in the decision along with the transportation costs. Some of the available methods for the deterministic vehicle routing problem had been extended to this case. This paper clearly identified the research category of the inventory routing problem and is widely regarded as the first real IRP model in academia. Anily and Federgruen [6] proposed a class of strategies in which a collection of regions (sets of retailers) was specified that cover all outlets; if an outlet belonged to several regions, then a specific fraction of its sales/operations was assigned to each of these regions. Each time one of the retailers in a given region received a delivery, this delivery was made by a vehicle that visited all of the other outlets in the region as well (in an efficient route) to achieve economies of scale. This strategy was widely used in follow-up studies of IRP. Kleywegt et al. [7] established an IRP model in which customers’ demands on different days were independent random vectors with a joint probability distribution F that did not change with time. They formulated the inventory routing problem as a Markov decision process and proposed approximation methods to find good solutions that had reasonable computational effort. Aghezzaf et al. [8] used the concept of a vehicle multitour, which implies that a vehicle’s travel plan might possibly contain more than one tour and vehicles could be reloaded. Sales points within a partition were divided into regions that were similar to the regions in the study by Anily and Federgruen [6]. To solve the nonlinear mixed integer formulation of this problem, a column generation-based approximation method was suggested.In some of the papers on the IRP, the planning time horizon is divided into integer periods according to some natural properties of time, that is, the study of the inventory routing problem under discrete time. A discrete time model is conducive to solving a problem that has varying retailer demand (changing with time), and the delivery time interval must be integer multiples of a unit period; thus, it is easy to manipulate in operations management practice. The unit for the discrete time is called one period, and the definition of a period, depending on the context of the problem, might be an hour, a day, or a week. Bard and Nananukul [9] established an IRP model with discrete time. By assessing a series of heuristics algorithms, they first developed a two-step procedure that estimated daily delivery quantities and then solved the vehicle routing problem for each day over the planning horizon. Abdelmaguid et al. [10] studied an inventory routing problem with backlogging under discrete time. Based on a two-phase approach, transitions that use the idea of exchanging customers’ delivery amounts between periods were conducted, and the transitions could further reduce the total cost by balancing the inventory costs, backordering costs, and transportation costs. In most studies of inventory routing models with discrete time, the deliveries were assumed to be finished within one single period, but Savelsbergh and Song [11] investigated an inventory routing problem with designed delivery tours that spanned several days, covering enormous geographical areas and involving product pickups at different facilities. They developed an integer programming-based optimisation algorithm that was embedded in a local search procedure to improve solutions that were produced by a randomised greedy heuristic.With the increasing fierce global competition and continuous advancement of information technology, the idea of having a decision that is integrated between the upstream and downstream enterprises within a supply chain is widely accepted. Based on this idea, research about the joint economic lot-sizing problem (JELP) for supply chains has become a hotspot in the area of inventory management theory, referring to the review by Ben-Daya et al. [12] for details. Lacking consideration about distribution routing information makes the JELP model more suitable for the medium- and long-term planning process for enterprises. Furthermore, focusing on retailers’ lot-sizing and distribution routing, the integrated inventory routing problems take suppliers’ production costs and inventory costs into account; thus, the coordinated production-distribution scheduling can further reduce the total relevant cost of the supply chain. Lei et al. [13] were the first to formulate the production-inventory-distribution-routing problem as a mixed-integer program and illustrated the benefits that were brought by the coordination. Bard and Nananukul [14] adopted a branch-and-price framework to solve the integrated inventory routing problem. A hybrid methodology that combined the column generation heuristic, bounded heuristic algorithm, and tabu search algorithm was developed. The result demonstrated that the performance of hybrid methodology was much better than that of either CPLEX or the standard branch and price algorithm.In this paper, we consider an integrated production-distribution model. It is assumed that no deterioration occurs at the supplier’s factory (or facilities) because of good protection and production conditions. However, the perishable goods have different quality degradation processes during the transportation and sales stages. Besides, the retailers and customers have their own acceptable quality standards. For example, the shelf life of bread is 3 days (or 3 periods) after its production. If the storage time is more than 3 days, then the customers will absolutely not accept it; however, for the retailers, the appointed time for delivery might be within one day after the bread’s production because they need time to sell it. Thus, different time windows are set in the transportation and sales stages. The purpose of setting the transportation time window and the sales time window (shelf-life limit) is to make it convenient to describe deteriorating items’ quality control standards for enterprises. The time windows here can also be generalised to other decision contexts, for example, McDonald’s asks the Xia Hui Logistics Company (a Chinese firm) to make delivery to each of its stores between 11 p.m. and 1 a.m., which can also be considered in this model.In general IRP and its variants, the transportation cost usually includes the fixed cost and variable cost. The fixed cost occurs once a vehicle is used, and the variable cost is in proportion to the sum of the distance. However, an important cost is often neglected in the variable cost, that is, the loading cost. The loading cost is an important part of the charge for the consumption of gas, and it changes due to the amount of load in the vehicle [15]. In reality, the vehicle load varies from one customer to another within a given route, and the load cost will decrease because of unloading at each customer site. When deciding the vehicle distribution paths, neglecting the loading cost will lead to a larger gap between reality and the analytical model. In this paper, we consider an integrated IRP model with a loading cost.Moreover, when planning the distribution routing and assigning the vehicle loading tasks, we also consider the time interval between two successive vehicles’ returning to the supplier’s factory or a distribution centre. Because the model is based on a discrete time, vehicles’ dispatching and returning in each period will not overlap. If the time interval is too short, a vehicle jam and insufficiency of handling equipment and personnel could occur and cause much chaos at the shipment facilities, for example, the delivery platform, which is not a preferred scenario for the manager. Additionally, a suitable time interval can enable multiple deliveries by one vehicle, and the number of vehicles used will decline.In this paper, we propose a new formulation of a production-distribution-inventory IRP model with quality time windows and loading cost under discrete time. In the transportation and storage stages, different time windows are set, and if the time interval between two successive vehicles’ returning to the supplier’s factory is too short, then an extra cost would be incurred. The objective of the model is to determine the supplier’s production plan, the delivery schedule and the vehicle routing in such a way that the total relevant cost is minimised while satisfying both the quality and delivery requirements.The remainder of this paper is organised as follows. In Section2, a mathematical model is formulated for the proposed problem along with the problem assumptions. Combining the features of the model, a two-phase algorithm is developed in Section 3. In Section 4, the computational results of the algorithm and sensitivity analysis are presented. Finally, Section 5 provides several conclusions.


## 2. Problem Description and Notation

### 2.1. Problem Description

We study a supply chain system that is composed of one supplier and a set of retailers. Each retailer faces a deterministic and independent demand for a single item per time period. The planning horizon considersτ periods, and the length of each period is T. Deliveries to retailers are made by a homogeneous fleet of vehicles from the supplier. The production capacity of the supplier is limited. The item has different shelf lives in the transportation stage and sales stage. The demand at each retailer is relatively small compared with the vehicle capacity, and the retailers are located closely, which enables one vehicle to cover many retailers within one trip. The delivery in each period is an independent vehicle routing problem. Our study is under discrete time. In one period, the supply chain has three series stages: production, distribution, and sales. They are called production in period p, distribution in period p, and sales in period p, respectively. Because the production and distribution have a lead time, the starting time of the production and distribution can be extrapolated backward based on the sales time.To be more practical, the vehicle’s loading cost in the transportation is considered. The lower bound of the interval of two successive vehicles’ returning time is set to avoid jams in the platform. If the actual interval is less than the threshold value, then an extra penalty cost would be incurred. Hence, we generate the production schedule and distribution routing over the planning horizon to minimise the total costs while meeting the time windows and other constraints such as the time interval.The problem that we consider can be formulated as a mixed integer programming model, and the modelling method and process can be referred from previous research. Bell et al. [16] consider the problem of gas distribution, and they determine a set of routes that have at most four customers; they use a mixed integer problem (MIP) approach to define the quantities to deliver, the set of vehicles to use, and the dates of visit. Savelsbergh and Song [17] consider the IRP that considers the delivery of one product to two types of customers. To solve this problem, they present three heuristics that define the routes and the quantities to deliver. They also solve an MIP to redefine the quantities to deliver. Other similar research adopts a mixed integer programming model to study relative problems that can be found in researches by Resende and Ribeiro [18], Lei et al. [13], Boudia et al. [19, 20], Bard and Nananukul [14], and Moin et al. [21]. Based on their research, we develop our model as follows.


### 2.2. Assumptions

(1)
The production capacity of the supplier is limited but sufficient to satisfy the retailers’ demands. At the end of each period, inventory is measured to calculate the inventory costs.
(2)
The number of homogeneous vehicles is unlimited. Each of these vehicles could make at most one trip per period.
(3)
The inventory capacities of the retailers are not limited, and shortages are not permitted. The demands of the retailers could not be divided.
(4)
The loading and unloading periods are not considered here alone.
(5)
All of the initial inventories are zero as well as the end of the planning horizon.


### 2.3. Notation

(1) Parameters:f
s: setup cost of the supplier,
C: maximal production capacity of the supplier in one period,
h
s: unit holding cost of the supplier,
m
p: production quantity in period p,
f
v: fixed cost when a vehicle is used,
c
v: driving cost per unit distance,
t
max
1: the longest driving time limit for a vehicle travelling from the supplier’s facilities to any of the retailers within which there is no penalty,
t
max
2: the longest driving time limit for a vehicle travelling from the supplier’s facilities to any of the retailers,
b: deteriorating cost/unit product/unit time when the arriving time is between t
max
1 and t
max
2,
T: the time length of one period,
s
p: the speed of the vehicles in period p,
d
i
j: the distance from site i to j,
ψ: the capacity of the vehicles,
i
t
v: the lower bound time interval of two successive vehicles’ returning to the supplier’s facilities,
c
p: when the actual interval is less than the threshold value i
t
v, the cost per unit time,
c
g: the cost of delivering product per unit weight and per unit distance,
V
p: the number of delivery paths in period p,
h
c: the unit holding cost of the retailers,
d
i
p: the demand of retailer i in period p,
φ: the unloading cost of the retailers,
ε: the upper bound of the periods that goods can be saved at retailers’ stores,
S: the set of retailers,
S
+: the set of retailers and the supplier,
S
v
,
p: the set of retailers that have been served by vehicle v in period p,
V: the set of vehicles,
H: the set of periods in the planning horizon.(2) Variables:I
p: inventory of the supplier at the beginning of period p,
t
i
p: the time that the vehicles arrive at site i (including the supplier),
t
v
last
p: the time that vehicle v arrives at its last retailer in period p,
t
i
j
p: the driving time from i to j in period p (t
i
j
p
=
d
i
j
/
s
p),
end
t
i
p: the returning time of vehicle i in period p to the supplier’s facilities,
l
i
j
v
,
p: the load of vehicle v on arc (
i
,
j
) in period p,
I
i
p: the inventory of retailer i at the beginning of period p,
w
i
p: the amount of products delivered to retailer i at the beginning of period p,
A
i
p: the set of successive periods from period p (including period p) to the period of the next arrival to retailer i, decided by the 0-1 matrix z
i
p,
x
i
,
j
v
,
p: 1 if vehicle v drives from site i to j in period p; 0 otherwise (decision variable),
y
v
,
p: 1 if vehicle v is used in period p; 0 otherwise (decision variable),
z
i
p: 1 if there is an arrival at retailer i in period p; 0 otherwise (decision variable),
u
p: 1 if there is production in period p; 0 otherwise (decision variable).


## 2.1. Problem Description

We study a supply chain system that is composed of one supplier and a set of retailers. Each retailer faces a deterministic and independent demand for a single item per time period. The planning horizon considersτ periods, and the length of each period is T. Deliveries to retailers are made by a homogeneous fleet of vehicles from the supplier. The production capacity of the supplier is limited. The item has different shelf lives in the transportation stage and sales stage. The demand at each retailer is relatively small compared with the vehicle capacity, and the retailers are located closely, which enables one vehicle to cover many retailers within one trip. The delivery in each period is an independent vehicle routing problem. Our study is under discrete time. In one period, the supply chain has three series stages: production, distribution, and sales. They are called production in period p, distribution in period p, and sales in period p, respectively. Because the production and distribution have a lead time, the starting time of the production and distribution can be extrapolated backward based on the sales time.To be more practical, the vehicle’s loading cost in the transportation is considered. The lower bound of the interval of two successive vehicles’ returning time is set to avoid jams in the platform. If the actual interval is less than the threshold value, then an extra penalty cost would be incurred. Hence, we generate the production schedule and distribution routing over the planning horizon to minimise the total costs while meeting the time windows and other constraints such as the time interval.The problem that we consider can be formulated as a mixed integer programming model, and the modelling method and process can be referred from previous research. Bell et al. [16] consider the problem of gas distribution, and they determine a set of routes that have at most four customers; they use a mixed integer problem (MIP) approach to define the quantities to deliver, the set of vehicles to use, and the dates of visit. Savelsbergh and Song [17] consider the IRP that considers the delivery of one product to two types of customers. To solve this problem, they present three heuristics that define the routes and the quantities to deliver. They also solve an MIP to redefine the quantities to deliver. Other similar research adopts a mixed integer programming model to study relative problems that can be found in researches by Resende and Ribeiro [18], Lei et al. [13], Boudia et al. [19, 20], Bard and Nananukul [14], and Moin et al. [21]. Based on their research, we develop our model as follows.


## 2.2. Assumptions

(1)
The production capacity of the supplier is limited but sufficient to satisfy the retailers’ demands. At the end of each period, inventory is measured to calculate the inventory costs.
(2)
The number of homogeneous vehicles is unlimited. Each of these vehicles could make at most one trip per period.
(3)
The inventory capacities of the retailers are not limited, and shortages are not permitted. The demands of the retailers could not be divided.
(4)
The loading and unloading periods are not considered here alone.
(5)
All of the initial inventories are zero as well as the end of the planning horizon.


## 2.3. Notation

(1) Parameters:f
s: setup cost of the supplier,
C: maximal production capacity of the supplier in one period,
h
s: unit holding cost of the supplier,
m
p: production quantity in period p,
f
v: fixed cost when a vehicle is used,
c
v: driving cost per unit distance,
t
max
1: the longest driving time limit for a vehicle travelling from the supplier’s facilities to any of the retailers within which there is no penalty,
t
max
2: the longest driving time limit for a vehicle travelling from the supplier’s facilities to any of the retailers,
b: deteriorating cost/unit product/unit time when the arriving time is between t
max
1 and t
max
2,
T: the time length of one period,
s
p: the speed of the vehicles in period p,
d
i
j: the distance from site i to j,
ψ: the capacity of the vehicles,
i
t
v: the lower bound time interval of two successive vehicles’ returning to the supplier’s facilities,
c
p: when the actual interval is less than the threshold value i
t
v, the cost per unit time,
c
g: the cost of delivering product per unit weight and per unit distance,
V
p: the number of delivery paths in period p,
h
c: the unit holding cost of the retailers,
d
i
p: the demand of retailer i in period p,
φ: the unloading cost of the retailers,
ε: the upper bound of the periods that goods can be saved at retailers’ stores,
S: the set of retailers,
S
+: the set of retailers and the supplier,
S
v
,
p: the set of retailers that have been served by vehicle v in period p,
V: the set of vehicles,
H: the set of periods in the planning horizon.(2) Variables:I
p: inventory of the supplier at the beginning of period p,
t
i
p: the time that the vehicles arrive at site i (including the supplier),
t
v
last
p: the time that vehicle v arrives at its last retailer in period p,
t
i
j
p: the driving time from i to j in period p (t
i
j
p
=
d
i
j
/
s
p),
end
t
i
p: the returning time of vehicle i in period p to the supplier’s facilities,
l
i
j
v
,
p: the load of vehicle v on arc (
i
,
j
) in period p,
I
i
p: the inventory of retailer i at the beginning of period p,
w
i
p: the amount of products delivered to retailer i at the beginning of period p,
A
i
p: the set of successive periods from period p (including period p) to the period of the next arrival to retailer i, decided by the 0-1 matrix z
i
p,
x
i
,
j
v
,
p: 1 if vehicle v drives from site i to j in period p; 0 otherwise (decision variable),
y
v
,
p: 1 if vehicle v is used in period p; 0 otherwise (decision variable),
z
i
p: 1 if there is an arrival at retailer i in period p; 0 otherwise (decision variable),
u
p: 1 if there is production in period p; 0 otherwise (decision variable).


## 3. Model Formulation

### 3.1. Cost Analysis

The total costs include the supplier’s costZ
S, the transportation cost Z
T, the retailers’ cost Z
C, and the cost of returning the time interval penalty Z
I.The supplier’s cost includes the production setup cost∑
p
∈
H
f
s
u
p and the inventory holding cost ∑
p
∈
H
h
s
I
p
+
1, where ∑
p
∈
H
h
s
I
p
+
1
=
∑
p
∈
H
h
s
(
I
p
+
m
p
-
∑
i
∈
S
w
i
p
). The inventory of the supplier at the beginning of period p is I
p
=
I
p
-
1
-
∑
i
∈
S
w
i
p
-
1
+
m
p
-
1, m
p
≤
C
u
p, which means that the inventory of the supplier at the beginning of period p is determined by the inventory at the beginning of period p
-
1, the production quantity, and the delivery amount in period p.The transportation cost includes the vehicle fixed usage cost∑
p
∈
H
∑
v
∈
V
f
v
y
v
,
p, the driving cost ∑
p
∈
H
∑
v
∈
V
∑
j
∈
S
+
∑
i
∈
S
+
c
v
d
i
j
x
i
j
v
,
p, the loading cost ∑
p
∈
H
∑
i
∈
S
+
∑
j
∈
S
+
c
g
d
i
j
x
i
j
v
,
p
l
i
j
v
,
p, and the cost of arriving overtime at the retailers ∑
p
∈
H
∑
v
∈
V
∑
i
∈
S
b
w
i
p
max
{
t
i
p
z
i
p
-
t
max
1
,
0
}. Deteriorating item quality is a fuzzy concept. The actual quality of the deteriorating items is changing or decreasing due to their deteriorating characteristics; for example, the amount of bacterial flora is changing. However, in reality, these items are still regarded as qualified products because they are within the time window. If the delivery time to the retailers exceeds the appointed time (still within the time window), the retailers might not completely reject the products, but they might allow the suppliers to provide some compensation. Therefore, we set two thresholds: t
max
1 and t
max
2 (t
max
2
≥
t
max
1), and the vehicle driving time should not exceed t
max
2. When the driving time is smaller than t
max
1, no extra penalty cost will be calculated, but if the travelling time t
i
p is between t
max
1 and t
max
2, then extra compensation cost will be incurred.The cost of each retailer includes the unloading costφ and the inventory holding cost ∑
p
∈
H
h
c
T
(
I
i
p
-
d
i
p
). The inventory of retailer i at the beginning of period p is equal to the inventory at the beginning of period p
-
1 plus the products that arrived at the beginning of period p and minus the inventory consumption in period p
-
1; that is, I
i
p
=
I
i
p
-
1
+
w
i
p
-
d
i
p
-
1. The delivery of products to retailer i at the beginning of period p is the sum of the demands within the vehicles’ arrival time intervals, and the interval here is expressed as integer multiples of a unit period; that is, w
i
p
=
z
i
p
∑
p
∈
A
i
p
d
i
p. In the problem, retailers’ demands of many periods can be met by one delivery, which results in overstock and inventory cost at the retailers. Therefore, the retailers’ cost is an important part of the objective function. Moreover, the production decision and distribution decision will change the retailers’ inventory status; thus, consideration of the retailers’ cost is a more comprehensive and practical method.The cost of the two successive vehicles’ returning time interval penalty is∑
p
∈
H
∑
i
∈
V
p
∑
j
∈
V
p
,
i
≠
j
c
p
max
{
i
t
v
-
|
end
t
i
p
-
end
t
j
p
|
,
0
}. Assume that the lower bound of the time interval of the vehicles’ returning to the supplier’s facilities is i
t
v. If the actual interval is less than the threshold value, that is, |
end
t
i
p
-
end
t
j
p
|
<
i
t
v, then the cost of the returning time interval penalty will be calculated.


### 3.2. Mathematical Model

The objective function and constraints are listed as follows over the planning horizon:(1)
min
Z
=
∑
p
∈
H
(
f
s
u
p
+
h
s
I
p
)
+
∑
i
∈
S
∑
p
∈
H
[
h
c
T
(
I
i
p
-
d
i
p
)
+
φ
z
i
p
]
+
∑
p
∈
H
∑
v
∈
V
f
v
y
v
,
p
+
∑
p
∈
H
∑
v
∈
V
∑
j
∈
S
+
∑
i
∈
S
+
c
v
d
i
j
x
i
j
v
,
p
+
∑
p
∈
H
∑
v
∈
V
∑
i
∈
S
b
w
i
p
max
{
t
i
p
z
i
p
-
t
max
1
,
0
}
+
∑
p
∈
H
∑
i
∈
S
+
∑
j
∈
S
+
c
g
d
i
j
x
i
j
v
,
p
l
i
j
v
,
p

+

∑
p
∈
H
∑
i
∈
V
p
∑
j
∈
V
p
,
i
≠
j
c
p
max
{
i
t
v

-

|
end
t
i
p

-

end
t
j
p
|
,
0
}
subject to
(2)
∑
p
=
m
m
+
ε
i
z
i
p
≥
1
,
∀
m
,
(
m
+
ε
i
)
∈
H
,
∀
i
∈
S
,
(3)
z
i
p
=
∑
v
∈
V
∑
j
∈
S
+
x
j
i
v
,
p
,
∀
i
∈
S
,
p
∈
H
,
(4)
∑
v
∈
V
∑
i
∈
S
+
x
i
j
v
,
p
≤
1
,
∀
j
∈
S
,
p
∈
H
,
(5)
∑
i
∈
S
+
x
i
j
v
,
p
-
∑
k
∈
S
+
x
j
k
v
,
p
=
0
,
∀
v
∈
V
,
j
∈
S
,
p
∈
H
,
(6)
y
v
,
p
≤
∑
i
∈
S
∑
j
∈
S
+
x
i
j
v
,
p
,
∀
v
∈
V
,
p
∈
H
,
(7)
x
i
j
v
,
p
-
y
v
,
p
≤
0
,
∀
v
∈
V
,
i
∈
S
+
,
j
∈
S
+
,
p
∈
H
,
(8)
w
i
p
=
z
i
p
∑
p
∈
A
i
p
d
i
p
,
∀
i
∈
S
,
p
∈
H
,
(9)
∑
i
∈
S
v
,
p
w
i
p
≤
ψ
v
,
∀
p
∈
H
,
v
∈
V
,
(10)
t
i
j
p
=
d
i
j
s
p
,
∀
i
∈
S
+
,
j
∈
S
+
,
(11)
t
j
p
x
i
j
v
,
p
-
t
i
p
x
i
j
v
,
p
=
t
i
j
p
x
i
j
v
,
p
,
∀
i
∈
S
+
,
j
∈
S
+
,
v
∈
V
,
p
∈
H
,
(12)
t
i
p
z
i
p
≤
t
max
2
,
∀
i
∈
S
,
(13)
∑
j
∈
S
i
≠
j
∑
v
∈
V
(
l
j
i
v
,
p
x
j
i
v
,
p
-
l
i
j
v
,
p
x
i
j
v
,
p
)
=
d
i
p
,
∀
i
∈
S
,
p
∈
H
,
(14)
I
i
1
=
0
,
∀
i
∈
S
,
(15)
I
i
p
=
I
i
p
-
1
+
w
i
p
-
d
i
p
-
1
,
∀
i
∈
S
,
p
∈
H
∖
{
1
}
,
(16)
I
1
=
0
,
(17)
I
p
=
I
p
-
1
-
∑
i
∈
S
w
i
p
-
1
+
m
p
-
1
,
∀
p
∈
H
∖
{
1
}
,
(18)
m
p
≤
C
u
p
,
∀
p
∈
H
,
(19)
∑
i
∈
S
w
i
1
≤
m
1
,
(20)
∑
i
∈
S
w
i
p
≤
I
p
+
m
p
,
∀
p
∈
H
∖
{
1
}
.The model is a mixed integer programming formulation (because there are 0-1 decision variables and continuous decision variables). Constraint (2) represents that the time interval between the vehicles that service a retailer cannot exceed a certain value, to avoid shortages; it means that after the arrival of deteriorating items to retailer i in period m, there must be at least one other arrival to retailer i before the period m
+
ε
i. Constraint (3) indicates that when there is a product arrival at retailer i, a vehicle must be arranged to serve the retailer in this period. Constraint (4) shows that the demand of a retailer cannot be divided. Route continuity is enforced by constraint (5). Constraints (6) and (7) indicate the constraint relationship between y
v
,
p and x
i
j
v
,
p. Constraint (8) guarantees that there are no shortages at retailers. Here, ∑
p
∈
A
i
p
d
i
p represents the sum of the demands of retailer i between its two successive arrivals. A
i
p denotes the set of periods between two successive deliveries to retailer i from period p. For example, retailer 1 is served in periods 1 and 4, and now, period p is period 1, and A
1
1 represents the period set {
1
,
2
,
3
}. The demands in A
1
1 will be delivered to retailer 1 in period 1 because the next delivery will occur in period 4 and shortages are not permitted. Constraint (9) is the vehicle capacity constraint. Constraint (10) defines the time that it takes for the vehicles to drive from retailer i to j in one period. Constraint (11) states the relationship between the absolute time t
i
p and the relative time t
i
j
p. Constraint (12) is the upper bound of the delivery time. Constraint (13) shows the logic relationship between the demand of retailer i and the vehicle loads on the two arcs that link retailer i. Constraints (14) and (16) represent that the initial inventories of the retailers and supplier are zero in period 0. Constraints (15) and (17) are the inventory flow balance equations. Constraint (18) bounds the production in each period to the capacity of the supplier. Constraints (19) and (20) indicate the maximal delivery quantity in period p.


## 3.1. Cost Analysis

The total costs include the supplier’s costZ
S, the transportation cost Z
T, the retailers’ cost Z
C, and the cost of returning the time interval penalty Z
I.The supplier’s cost includes the production setup cost∑
p
∈
H
f
s
u
p and the inventory holding cost ∑
p
∈
H
h
s
I
p
+
1, where ∑
p
∈
H
h
s
I
p
+
1
=
∑
p
∈
H
h
s
(
I
p
+
m
p
-
∑
i
∈
S
w
i
p
). The inventory of the supplier at the beginning of period p is I
p
=
I
p
-
1
-
∑
i
∈
S
w
i
p
-
1
+
m
p
-
1, m
p
≤
C
u
p, which means that the inventory of the supplier at the beginning of period p is determined by the inventory at the beginning of period p
-
1, the production quantity, and the delivery amount in period p.The transportation cost includes the vehicle fixed usage cost∑
p
∈
H
∑
v
∈
V
f
v
y
v
,
p, the driving cost ∑
p
∈
H
∑
v
∈
V
∑
j
∈
S
+
∑
i
∈
S
+
c
v
d
i
j
x
i
j
v
,
p, the loading cost ∑
p
∈
H
∑
i
∈
S
+
∑
j
∈
S
+
c
g
d
i
j
x
i
j
v
,
p
l
i
j
v
,
p, and the cost of arriving overtime at the retailers ∑
p
∈
H
∑
v
∈
V
∑
i
∈
S
b
w
i
p
max
{
t
i
p
z
i
p
-
t
max
1
,
0
}. Deteriorating item quality is a fuzzy concept. The actual quality of the deteriorating items is changing or decreasing due to their deteriorating characteristics; for example, the amount of bacterial flora is changing. However, in reality, these items are still regarded as qualified products because they are within the time window. If the delivery time to the retailers exceeds the appointed time (still within the time window), the retailers might not completely reject the products, but they might allow the suppliers to provide some compensation. Therefore, we set two thresholds: t
max
1 and t
max
2 (t
max
2
≥
t
max
1), and the vehicle driving time should not exceed t
max
2. When the driving time is smaller than t
max
1, no extra penalty cost will be calculated, but if the travelling time t
i
p is between t
max
1 and t
max
2, then extra compensation cost will be incurred.The cost of each retailer includes the unloading costφ and the inventory holding cost ∑
p
∈
H
h
c
T
(
I
i
p
-
d
i
p
). The inventory of retailer i at the beginning of period p is equal to the inventory at the beginning of period p
-
1 plus the products that arrived at the beginning of period p and minus the inventory consumption in period p
-
1; that is, I
i
p
=
I
i
p
-
1
+
w
i
p
-
d
i
p
-
1. The delivery of products to retailer i at the beginning of period p is the sum of the demands within the vehicles’ arrival time intervals, and the interval here is expressed as integer multiples of a unit period; that is, w
i
p
=
z
i
p
∑
p
∈
A
i
p
d
i
p. In the problem, retailers’ demands of many periods can be met by one delivery, which results in overstock and inventory cost at the retailers. Therefore, the retailers’ cost is an important part of the objective function. Moreover, the production decision and distribution decision will change the retailers’ inventory status; thus, consideration of the retailers’ cost is a more comprehensive and practical method.The cost of the two successive vehicles’ returning time interval penalty is∑
p
∈
H
∑
i
∈
V
p
∑
j
∈
V
p
,
i
≠
j
c
p
max
{
i
t
v
-
|
end
t
i
p
-
end
t
j
p
|
,
0
}. Assume that the lower bound of the time interval of the vehicles’ returning to the supplier’s facilities is i
t
v. If the actual interval is less than the threshold value, that is, |
end
t
i
p
-
end
t
j
p
|
<
i
t
v, then the cost of the returning time interval penalty will be calculated.


## 3.2. Mathematical Model

The objective function and constraints are listed as follows over the planning horizon:(1)
min
Z
=
∑
p
∈
H
(
f
s
u
p
+
h
s
I
p
)
+
∑
i
∈
S
∑
p
∈
H
[
h
c
T
(
I
i
p
-
d
i
p
)
+
φ
z
i
p
]
+
∑
p
∈
H
∑
v
∈
V
f
v
y
v
,
p
+
∑
p
∈
H
∑
v
∈
V
∑
j
∈
S
+
∑
i
∈
S
+
c
v
d
i
j
x
i
j
v
,
p
+
∑
p
∈
H
∑
v
∈
V
∑
i
∈
S
b
w
i
p
max
{
t
i
p
z
i
p
-
t
max
1
,
0
}
+
∑
p
∈
H
∑
i
∈
S
+
∑
j
∈
S
+
c
g
d
i
j
x
i
j
v
,
p
l
i
j
v
,
p

+

∑
p
∈
H
∑
i
∈
V
p
∑
j
∈
V
p
,
i
≠
j
c
p
max
{
i
t
v

-

|
end
t
i
p

-

end
t
j
p
|
,
0
}
subject to
(2)
∑
p
=
m
m
+
ε
i
z
i
p
≥
1
,
∀
m
,
(
m
+
ε
i
)
∈
H
,
∀
i
∈
S
,
(3)
z
i
p
=
∑
v
∈
V
∑
j
∈
S
+
x
j
i
v
,
p
,
∀
i
∈
S
,
p
∈
H
,
(4)
∑
v
∈
V
∑
i
∈
S
+
x
i
j
v
,
p
≤
1
,
∀
j
∈
S
,
p
∈
H
,
(5)
∑
i
∈
S
+
x
i
j
v
,
p
-
∑
k
∈
S
+
x
j
k
v
,
p
=
0
,
∀
v
∈
V
,
j
∈
S
,
p
∈
H
,
(6)
y
v
,
p
≤
∑
i
∈
S
∑
j
∈
S
+
x
i
j
v
,
p
,
∀
v
∈
V
,
p
∈
H
,
(7)
x
i
j
v
,
p
-
y
v
,
p
≤
0
,
∀
v
∈
V
,
i
∈
S
+
,
j
∈
S
+
,
p
∈
H
,
(8)
w
i
p
=
z
i
p
∑
p
∈
A
i
p
d
i
p
,
∀
i
∈
S
,
p
∈
H
,
(9)
∑
i
∈
S
v
,
p
w
i
p
≤
ψ
v
,
∀
p
∈
H
,
v
∈
V
,
(10)
t
i
j
p
=
d
i
j
s
p
,
∀
i
∈
S
+
,
j
∈
S
+
,
(11)
t
j
p
x
i
j
v
,
p
-
t
i
p
x
i
j
v
,
p
=
t
i
j
p
x
i
j
v
,
p
,
∀
i
∈
S
+
,
j
∈
S
+
,
v
∈
V
,
p
∈
H
,
(12)
t
i
p
z
i
p
≤
t
max
2
,
∀
i
∈
S
,
(13)
∑
j
∈
S
i
≠
j
∑
v
∈
V
(
l
j
i
v
,
p
x
j
i
v
,
p
-
l
i
j
v
,
p
x
i
j
v
,
p
)
=
d
i
p
,
∀
i
∈
S
,
p
∈
H
,
(14)
I
i
1
=
0
,
∀
i
∈
S
,
(15)
I
i
p
=
I
i
p
-
1
+
w
i
p
-
d
i
p
-
1
,
∀
i
∈
S
,
p
∈
H
∖
{
1
}
,
(16)
I
1
=
0
,
(17)
I
p
=
I
p
-
1
-
∑
i
∈
S
w
i
p
-
1
+
m
p
-
1
,
∀
p
∈
H
∖
{
1
}
,
(18)
m
p
≤
C
u
p
,
∀
p
∈
H
,
(19)
∑
i
∈
S
w
i
1
≤
m
1
,
(20)
∑
i
∈
S
w
i
p
≤
I
p
+
m
p
,
∀
p
∈
H
∖
{
1
}
.The model is a mixed integer programming formulation (because there are 0-1 decision variables and continuous decision variables). Constraint (2) represents that the time interval between the vehicles that service a retailer cannot exceed a certain value, to avoid shortages; it means that after the arrival of deteriorating items to retailer i in period m, there must be at least one other arrival to retailer i before the period m
+
ε
i. Constraint (3) indicates that when there is a product arrival at retailer i, a vehicle must be arranged to serve the retailer in this period. Constraint (4) shows that the demand of a retailer cannot be divided. Route continuity is enforced by constraint (5). Constraints (6) and (7) indicate the constraint relationship between y
v
,
p and x
i
j
v
,
p. Constraint (8) guarantees that there are no shortages at retailers. Here, ∑
p
∈
A
i
p
d
i
p represents the sum of the demands of retailer i between its two successive arrivals. A
i
p denotes the set of periods between two successive deliveries to retailer i from period p. For example, retailer 1 is served in periods 1 and 4, and now, period p is period 1, and A
1
1 represents the period set {
1
,
2
,
3
}. The demands in A
1
1 will be delivered to retailer 1 in period 1 because the next delivery will occur in period 4 and shortages are not permitted. Constraint (9) is the vehicle capacity constraint. Constraint (10) defines the time that it takes for the vehicles to drive from retailer i to j in one period. Constraint (11) states the relationship between the absolute time t
i
p and the relative time t
i
j
p. Constraint (12) is the upper bound of the delivery time. Constraint (13) shows the logic relationship between the demand of retailer i and the vehicle loads on the two arcs that link retailer i. Constraints (14) and (16) represent that the initial inventories of the retailers and supplier are zero in period 0. Constraints (15) and (17) are the inventory flow balance equations. Constraint (18) bounds the production in each period to the capacity of the supplier. Constraints (19) and (20) indicate the maximal delivery quantity in period p.


## 4. Solution Algorithm

### 4.1. Solution Procedure Outline

The IRP is NP-hard because it includes the vehicle routing problem (VRP) as a sub-problem. It might not be possible to calculate its exact value, especially for large problem sizes. An efficient heuristic, however, can be used to approximate it; this approach has been implemented in previous research; see, for example, Popović et al. [22] and Boudia et al. [19, 20]. Therefore, in this section, we propose a heuristic algorithm for this NP-hard problem.A key decision in solving the IRP is whether to deliver to retaileri in period p because a binary variable, which we define as z
i
p, effectively separates the production, distribution, and inventory problems. Thus, in this paper, we define the problem of solving the arrival matrix z
i
p as the main problem, and the problems of supplier decisions and vehicle routing decisions are two sub-problems: SUB1 and SUB2.After giving an arrival matrix for all of the retailers and all of the periods, the amount delivered to retaileri in period p can be calculated according to the retailers’ demands in each period because the shortages are not permitted. Obtaining the delivery period and amounts, the supplier can meet the production scheduling (production period, production quantity and relative cost). At the same time, the best routing solution for these delivery amounts can be obtained by solving τ separate capacitated vehicle routing problems. Therefore, identifying the arrival matrix is a key issue because what is left are production scheduling and vehicle routing problems.


### 4.2. Algorithm Implementation

(1)Master Problem. The model of the master problem is given as follows:
(21)
min
Z
=
∑
i
∈
S
∑
p
∈
H
[
h
c
T
(
I
i
p
-
d
i
p
)
+
φ
z
i
p
]
+
Z
S
+
Z
T
+
Z
I
,
subject to constraints (2), (8), (14), (15), and
(22)
w
i
p
≤
ψ
v
,
∀
p
∈
H
,
v
∈
V
,
(23)
∑
j
=
1
p
∑
i
∈
S
w
i
j
≤
p
C
.Constraint (22) indicates that the demand of the retailers must not be divided, which means that the delivery quantity to a retailer cannot exceed the vehicle capacity. Constraint (23) enforces that the supplier’s production capacity constraint must be met (as is stated in assumption (1)).To solve the main problem, we proposed a tabu search algorithm (TS) to decide the binary variablez
i
p. Many applications, such as job shop scheduling, graph coloring, TSP and other vehicle routing problems, have been successfully tackled by TS; see, for example, Glover and Laguna [23], for an overview, and Fallahi et al. [24]. In the following, the implemented TS is completely described by specifying the other components, namely, the initial solution, solution evaluation, neighbourhood definition, and stop condition.Initial Solution. The solution of the TS is an arrival matrix z
i
p, which represents whether to deliver to retailer i in period p. When the master problem is not optimised, we initialise the solution as all z
i
p
=
1; in other words, all of the retailers receive a delivery in each period.Solution Evaluation. After obtaining an arrival matrix and if the generated matrix z
i
p meets the relative constraints, SUB1 and SUB2 are solved to obtain the total cost. This cost is used to evaluate the solution’s performance.Neighbourhood Definition. A neighbourhood is a set of points that can be reached from the current solution by performing one or more moves. For this problem, we define the neighbourhood of the current solution as all feasible arrival matrixes z
i
p; in other words, the values are changed for some of the z
i
p in the current solution. When choosing the changed z
i
p, a variable neighbourhood search is presented. At the early stage of the search, a number of retailers (not in the tabu list) are randomly selected from the chosen period as candidates (the number is referred to as count); then num, the number of retailers, is randomly chosen from the candidates to make a conversion simultaneously (apparently, num is not greater than count). In the later stages of the search, num is set to a small value to make a more accurate search.Tabu list. The tabu list stores forbidden moves to avoid having the local search procedure trapped in a local optimum. The length of the tabu list in our algorithm is not constant. The tabu list can store a certain number of retailers, and the number is related to the number of retailers and periods. If the current solution can produce a better result, then these z
i
p that are in the solution will be added to the tabu list. At the same time, the tabu status of the same amount of z
i
p will be overridden according to the first-in-first-out principle. Each entry on the tabu list is a combination of a customer and period, which is represented by the 2-dimensional vector (customer i and period p).Stop Condition. If the search does not find a better solution within the predetermined steps, such as 500 steps, then it will stop. The steps can be changed according to the size of the problem.Algorithm Description. The solution procedure for the master problem is listed as follows.Step 1.
Initialisation. For every retaileri and period p, let z
i
p
=
1. Solve SUB1 and SUB2, and save the results as S
best, S
rem, and S
this. Calculate the total costs and save them as C
best and C
rem; initialise the tabu list T
A
B
U
=
⌀ and countnobetter = 0.Step 2.
Tabu search.Substep 1.
Lets
a
v
e
b
e
s
t
=
-
∞, K
=
⌀ and K
1
=
⌀.Substep 2.
Select one periodp randomly from the set H
∖
{
1
} in which not all of the retailers are set as tabu. Choose the count size of the different retailers from those that are not in tabu.Substep 3.
If countnobetter < 20, then produce a random numbernum as the number of retailers in a group; else, let n
u
m
=
1. Put the selected count groups of retailers from set K into set K
1.Substep 4.
Choose one group from setK
1 and change the selected retailers’ z
i
p value in solution S
rem in the current period. If the newly generated matrix z
i
p meets the relative constraints, then solve SUB1 and SUB2, and save the results as S
this and the total cost as C
this. Let s
a
v
e
=
C
rem
-
C
this. If s
a
v
e
>
s
a
v
e
b
e
s
t, then let s
a
v
e
=
s
a
v
e
b
e
s
t. If K
1
≠
⌀, then go to Substep 4; otherwise, go to Substep 5.Substep 5.
Ifs
a
v
e
b
e
s
t
≠
-
∞, then put the transferred z
i
p of solution S
now into the tabu list according to the first-in-first-out principle, and let S
rem
=
S
now and C
rem
=
C
now.Substep 6.
IfC
best
-
C
rem
>
0, then let countnobetter = 0, S
best
=
S
rem, and C
best
=
C
rem; otherwise, let countnobetter++.Substep 7.
If countnobetter < 500, then go to Substep1; otherwise, break out of the cycle and go to Step 3.Step 3.
Output the results. Output the final resultsS
best and the total cost C
best.(2)Supplier’s Production Decision Problem (SUB1). The model of SUB1 is listed as follows:
(24)
min
Z
S
=
∑
p
∈
H
(
f
s
u
p
+
h
s
I
p
)
subject to constraints (8), (16), (17), and (18).SUB1 decides the 0-1 variableu
p and the continuous variable m
p, which is to determine when and how many items the supplier prodeces. Because the structure of the solutions is simple, we adopt the saving algorithm and save a value that is equal to the setup cost minus the inventory cost. The latest produced principle is used in the production arrangement, which means that when we consider the production in period p, only when the production capacity is insufficient will we arrange the excess production quantity to the nearest satisfactory period.The flowchart of the solution procedure for SUB1 is depicted in Figure1.Figure 1
Flowchart of the solution procedure for SUB1.(3)Vehicle Routing Problem (SUB2). The model of SUB2 is listed as follows:
(25)
min
Z
T
=
∑
p
∈
H
∑
v
∈
V
f
v
y
v
,
p
+
∑
p
∈
H
∑
v
∈
V
∑
j
∈
S
+
∑
i
∈
S
+
c
v
d
i
j
x
i
j
v
,
p
+
∑
p
∈
H
∑
v
∈
V
∑
i
∈
S
b
w
i
p
max
{
t
i
p
z
i
p
-
t
max
1
,
0
}
+
∑
p
∈
H
∑
i
∈
S
+
∑
j
∈
S
+
c
g
d
i
j
x
i
j
v
,
p
l
i
j
v
,
p
subject to constraints (3)~(6) and (9)~(13).SUB2 decides 0-1 for the variablex
i
j
v
,
p and adopts a neighbourhood search. The neighbourhood structure is the improved exchange of a 2-opt path. When exchanging the paths, some retailers in one path are inserted into the other path according to a minimal insert cost criterion, where the cost of this inserting method is
(26)
∑
p
∈
H
∑
v
∈
V
f
v
y
v
,
p
+
∑
p
∈
H
∑
v
∈
V
∑
j
∈
S
+
∑
i
∈
S
+
c
v
d
i
j
x
i
j
v
,
p
+
∑
p
∈
H
∑
v
∈
V
∑
i
∈
S
b
w
i
p
max
{
t
i
p
z
i
p
-
t
max
1
,
0
}
+
∑
p
∈
H
∑
i
∈
S
+
∑
j
∈
S
+
c
g
d
i
j
x
i
j
v
,
p
l
i
j
v
,
p
+
∑
p
∈
H
∑
i
∈
V
p
∑
j
∈
V
p
,
i
≠
j
c
p
max
{
i
t
v
-
|
end
t
i
p
-
end
t
j
p
|
,
0
}
.To speed up obtaining the optimal solution, the algorithm developed by Taillard et al. [25] is referred to when choosing the exchanged paths; thus, paths that have a nearer distance will become easier to be selected. The CLOSE matrix is defined in this algorithm as the closeness of two paths, and the exchange probability of near paths will be larger than that of far paths.Definition  1. The CLOSE matrix is a two-dimensional matrix in which the number of both rows and columns is equal to the number of paths (or the number of vehicles used). This matrix represents the degree of closeness between two given paths. CLOSE
[
k
]
[
l
] refers to the value of closeness between path k (which contains m retailers that belong to S
k) and path l (which contains n retailers that belong to S
l); in other words, CLOSE
[
k
]
[
l
]
=
(
∑
i
∈
S
k
∑
j
∈
S
l
d
i
j
)
/
(
m
×
n
). When k
=
l, CLOSE
[
k
]
[
l
]
=
+
∞.When choosing the exchanged paths based on the CLOSE matrix, the probability of selecting the pair pathk and path l is directly proportional to 1
/
CLOSE
[
k
]
[
l
] (repeated selection is permitted).The flowchart of the solution procedure for SUB2 is depicted in Figure2.Figure 2
Flowchart of the solution procedure for SUB2.


## 4.1. Solution Procedure Outline

The IRP is NP-hard because it includes the vehicle routing problem (VRP) as a sub-problem. It might not be possible to calculate its exact value, especially for large problem sizes. An efficient heuristic, however, can be used to approximate it; this approach has been implemented in previous research; see, for example, Popović et al. [22] and Boudia et al. [19, 20]. Therefore, in this section, we propose a heuristic algorithm for this NP-hard problem.A key decision in solving the IRP is whether to deliver to retaileri in period p because a binary variable, which we define as z
i
p, effectively separates the production, distribution, and inventory problems. Thus, in this paper, we define the problem of solving the arrival matrix z
i
p as the main problem, and the problems of supplier decisions and vehicle routing decisions are two sub-problems: SUB1 and SUB2.After giving an arrival matrix for all of the retailers and all of the periods, the amount delivered to retaileri in period p can be calculated according to the retailers’ demands in each period because the shortages are not permitted. Obtaining the delivery period and amounts, the supplier can meet the production scheduling (production period, production quantity and relative cost). At the same time, the best routing solution for these delivery amounts can be obtained by solving τ separate capacitated vehicle routing problems. Therefore, identifying the arrival matrix is a key issue because what is left are production scheduling and vehicle routing problems.


## 4.2. Algorithm Implementation

(1)Master Problem. The model of the master problem is given as follows:
(21)
min
Z
=
∑
i
∈
S
∑
p
∈
H
[
h
c
T
(
I
i
p
-
d
i
p
)
+
φ
z
i
p
]
+
Z
S
+
Z
T
+
Z
I
,
subject to constraints (2), (8), (14), (15), and
(22)
w
i
p
≤
ψ
v
,
∀
p
∈
H
,
v
∈
V
,
(23)
∑
j
=
1
p
∑
i
∈
S
w
i
j
≤
p
C
.Constraint (22) indicates that the demand of the retailers must not be divided, which means that the delivery quantity to a retailer cannot exceed the vehicle capacity. Constraint (23) enforces that the supplier’s production capacity constraint must be met (as is stated in assumption (1)).To solve the main problem, we proposed a tabu search algorithm (TS) to decide the binary variablez
i
p. Many applications, such as job shop scheduling, graph coloring, TSP and other vehicle routing problems, have been successfully tackled by TS; see, for example, Glover and Laguna [23], for an overview, and Fallahi et al. [24]. In the following, the implemented TS is completely described by specifying the other components, namely, the initial solution, solution evaluation, neighbourhood definition, and stop condition.Initial Solution. The solution of the TS is an arrival matrix z
i
p, which represents whether to deliver to retailer i in period p. When the master problem is not optimised, we initialise the solution as all z
i
p
=
1; in other words, all of the retailers receive a delivery in each period.Solution Evaluation. After obtaining an arrival matrix and if the generated matrix z
i
p meets the relative constraints, SUB1 and SUB2 are solved to obtain the total cost. This cost is used to evaluate the solution’s performance.Neighbourhood Definition. A neighbourhood is a set of points that can be reached from the current solution by performing one or more moves. For this problem, we define the neighbourhood of the current solution as all feasible arrival matrixes z
i
p; in other words, the values are changed for some of the z
i
p in the current solution. When choosing the changed z
i
p, a variable neighbourhood search is presented. At the early stage of the search, a number of retailers (not in the tabu list) are randomly selected from the chosen period as candidates (the number is referred to as count); then num, the number of retailers, is randomly chosen from the candidates to make a conversion simultaneously (apparently, num is not greater than count). In the later stages of the search, num is set to a small value to make a more accurate search.Tabu list. The tabu list stores forbidden moves to avoid having the local search procedure trapped in a local optimum. The length of the tabu list in our algorithm is not constant. The tabu list can store a certain number of retailers, and the number is related to the number of retailers and periods. If the current solution can produce a better result, then these z
i
p that are in the solution will be added to the tabu list. At the same time, the tabu status of the same amount of z
i
p will be overridden according to the first-in-first-out principle. Each entry on the tabu list is a combination of a customer and period, which is represented by the 2-dimensional vector (customer i and period p).Stop Condition. If the search does not find a better solution within the predetermined steps, such as 500 steps, then it will stop. The steps can be changed according to the size of the problem.Algorithm Description. The solution procedure for the master problem is listed as follows.Step 1.
Initialisation. For every retaileri and period p, let z
i
p
=
1. Solve SUB1 and SUB2, and save the results as S
best, S
rem, and S
this. Calculate the total costs and save them as C
best and C
rem; initialise the tabu list T
A
B
U
=
⌀ and countnobetter = 0.Step 2.
Tabu search.Substep 1.
Lets
a
v
e
b
e
s
t
=
-
∞, K
=
⌀ and K
1
=
⌀.Substep 2.
Select one periodp randomly from the set H
∖
{
1
} in which not all of the retailers are set as tabu. Choose the count size of the different retailers from those that are not in tabu.Substep 3.
If countnobetter < 20, then produce a random numbernum as the number of retailers in a group; else, let n
u
m
=
1. Put the selected count groups of retailers from set K into set K
1.Substep 4.
Choose one group from setK
1 and change the selected retailers’ z
i
p value in solution S
rem in the current period. If the newly generated matrix z
i
p meets the relative constraints, then solve SUB1 and SUB2, and save the results as S
this and the total cost as C
this. Let s
a
v
e
=
C
rem
-
C
this. If s
a
v
e
>
s
a
v
e
b
e
s
t, then let s
a
v
e
=
s
a
v
e
b
e
s
t. If K
1
≠
⌀, then go to Substep 4; otherwise, go to Substep 5.Substep 5.
Ifs
a
v
e
b
e
s
t
≠
-
∞, then put the transferred z
i
p of solution S
now into the tabu list according to the first-in-first-out principle, and let S
rem
=
S
now and C
rem
=
C
now.Substep 6.
IfC
best
-
C
rem
>
0, then let countnobetter = 0, S
best
=
S
rem, and C
best
=
C
rem; otherwise, let countnobetter++.Substep 7.
If countnobetter < 500, then go to Substep1; otherwise, break out of the cycle and go to Step 3.Step 3.
Output the results. Output the final resultsS
best and the total cost C
best.(2)Supplier’s Production Decision Problem (SUB1). The model of SUB1 is listed as follows:
(24)
min
Z
S
=
∑
p
∈
H
(
f
s
u
p
+
h
s
I
p
)
subject to constraints (8), (16), (17), and (18).SUB1 decides the 0-1 variableu
p and the continuous variable m
p, which is to determine when and how many items the supplier prodeces. Because the structure of the solutions is simple, we adopt the saving algorithm and save a value that is equal to the setup cost minus the inventory cost. The latest produced principle is used in the production arrangement, which means that when we consider the production in period p, only when the production capacity is insufficient will we arrange the excess production quantity to the nearest satisfactory period.The flowchart of the solution procedure for SUB1 is depicted in Figure1.Figure 1
Flowchart of the solution procedure for SUB1.(3)Vehicle Routing Problem (SUB2). The model of SUB2 is listed as follows:
(25)
min
Z
T
=
∑
p
∈
H
∑
v
∈
V
f
v
y
v
,
p
+
∑
p
∈
H
∑
v
∈
V
∑
j
∈
S
+
∑
i
∈
S
+
c
v
d
i
j
x
i
j
v
,
p
+
∑
p
∈
H
∑
v
∈
V
∑
i
∈
S
b
w
i
p
max
{
t
i
p
z
i
p
-
t
max
1
,
0
}
+
∑
p
∈
H
∑
i
∈
S
+
∑
j
∈
S
+
c
g
d
i
j
x
i
j
v
,
p
l
i
j
v
,
p
subject to constraints (3)~(6) and (9)~(13).SUB2 decides 0-1 for the variablex
i
j
v
,
p and adopts a neighbourhood search. The neighbourhood structure is the improved exchange of a 2-opt path. When exchanging the paths, some retailers in one path are inserted into the other path according to a minimal insert cost criterion, where the cost of this inserting method is
(26)
∑
p
∈
H
∑
v
∈
V
f
v
y
v
,
p
+
∑
p
∈
H
∑
v
∈
V
∑
j
∈
S
+
∑
i
∈
S
+
c
v
d
i
j
x
i
j
v
,
p
+
∑
p
∈
H
∑
v
∈
V
∑
i
∈
S
b
w
i
p
max
{
t
i
p
z
i
p
-
t
max
1
,
0
}
+
∑
p
∈
H
∑
i
∈
S
+
∑
j
∈
S
+
c
g
d
i
j
x
i
j
v
,
p
l
i
j
v
,
p
+
∑
p
∈
H
∑
i
∈
V
p
∑
j
∈
V
p
,
i
≠
j
c
p
max
{
i
t
v
-
|
end
t
i
p
-
end
t
j
p
|
,
0
}
.To speed up obtaining the optimal solution, the algorithm developed by Taillard et al. [25] is referred to when choosing the exchanged paths; thus, paths that have a nearer distance will become easier to be selected. The CLOSE matrix is defined in this algorithm as the closeness of two paths, and the exchange probability of near paths will be larger than that of far paths.Definition  1. The CLOSE matrix is a two-dimensional matrix in which the number of both rows and columns is equal to the number of paths (or the number of vehicles used). This matrix represents the degree of closeness between two given paths. CLOSE
[
k
]
[
l
] refers to the value of closeness between path k (which contains m retailers that belong to S
k) and path l (which contains n retailers that belong to S
l); in other words, CLOSE
[
k
]
[
l
]
=
(
∑
i
∈
S
k
∑
j
∈
S
l
d
i
j
)
/
(
m
×
n
). When k
=
l, CLOSE
[
k
]
[
l
]
=
+
∞.When choosing the exchanged paths based on the CLOSE matrix, the probability of selecting the pair pathk and path l is directly proportional to 1
/
CLOSE
[
k
]
[
l
] (repeated selection is permitted).The flowchart of the solution procedure for SUB2 is depicted in Figure2.Figure 2
Flowchart of the solution procedure for SUB2.


## 5. Computational Experiments and Analysis

### 5.1. Numerical Example

An example is adopted to test the effectiveness of the proposed model and the impact of some of the parameters on the decisions. The relative parameters are as follows. The supply chain is made of one supplier and 12 retailers. The retailers’ demands are given in Table1. The distance between any two nodes is within 25, and the planning time horizon in this example consists of seven periods, each representing one day. Table 2 provides the distance matrix for the nodes. The vehicle velocities in each period are 35, 40, 40, 40, 35, 30, and 30, respectively. The supplier’s production setup cost is 1000 per order, and the inventory cost is 0.08 per day per unit. The daily production capacity is 1500. The fixed usage cost of the vehicles is 10, and the driving cost is 1 per kilometre. The longest driving time threshold value without the penalty t
max
1 is 2 hours, and 0.05 would be penalised per hour per unit after 2 hours but within 4 hours; that is, t
max
2
=
4. The vehicle capacity is 150 units. The cost of delivering a product of per unit weight and per unit distance is 0.05. The lower bound of the time interval of the vehicles’ returning to the supplier’s facilities i
t
v is 0.5 hour; if the actual interval is less than the threshold value, then the cost of a unit time is 5. The holding cost of the retailers is 0.1 per day per unit, and the unloading cost is 50. The deteriorating item’s shelf life at the retailer sites is 3 days.Table 1
Retailers’ demand in each period.
Period
Retailer
1
2
3
4
5
6
7
8
9
10
11
12
1
22.3
30.3
37.9
31.1
29.5
21.2
42.1
13.2
12.1
20.4
15.3
25.1
2
24.8
37.9
51.2
42.3
34.4
27.0
55.7
25.6
12.9
22.3
17.0
28.2
3
35.2
51.3
68.8
58.7
45.8
41.5
83.3
54.8
18.2
27.9
22.3
31.3
4
36.3
52.5
71.3
60.3
45.8
42.7
84.0
56.7
19.3
28.1
22.9
32.7
5
30.8
45.2
57.8
52.5
40.1
35.7
67.9
43.3
15.5
25.2
20.1
30.5
6
25.1
37.7
49.9
43.8
34.6
27.7
53.0
25.1
13.4
22.5
17.7
27.6
7
39.8
58.9
73.2
65.9
48.0
47.9
75.7
67.7
21.3
30.3
25.2
34.4Table 2
Distance matrix of nodes.
Nodes
Nodes
0
1
2
3
4
5
6
7
8
9
10
11
12
0
0
5.5
1.7
3.8
3.4
6.7
6.7
6.6
6.1
8.5
10.8
14.2
15.1
1
0
4.3
9
8.5
12.3
8.8
6.7
11.1
13.8
16.3
19.7
20.6
2
0
5.5
4.2
8.1
7.9
7.2
6.8
9.5
12.1
15.6
16.3
3
0
3.9
3.9
5.9
7.3
5.5
6.8
8.1
11
12.3
4
0
4.5
9.1
9.7
2.7
5.3
8
11.7
12.2
5
0
9.4
11.1
3.8
3.4
4.2
7.5
8.5
6
0
2.7
11.3
12.6
13.4
15.5
17.3
7
0
12.2
14
15.3
17.7
19.3
8
0
2.9
6
9.9
10
9
0
3.3
7.2
7.1
10
0
3.9
4.3
11
0
25
12
0The model is coded and run on the platform of Visual C++ 6.0. All of the tests are performed on the Intel(R) Core (TM)2 Duo at 2.00 GHz with 2 GB RAM under the Microsoft Windows 7 operation system. The results are presented in Tables3, 4, 5, and 6.Table 3
Arrival matrix of retailers.
Period
Retailer
1
2
3
4
5
6
7
8
9
10
11
12
1
1
1
1
1
1
1
1
1
1
1
1
1
2
0
0
0
0
0
0
1
0
0
1
1
0
3
1
1
1
0
0
0
0
0
1
0
0
0
4
0
1
1
1
1
1
1
1
0
0
0
1
5
0
0
0
0
1
1
1
0
0
1
1
1
6
1
0
1
1
0
0
0
1
1
0
0
0
7
0
1
0
0
1
0
1
0
1
0
0
0Table 4
Supplier’s production vectors.
Vectors
Value
Period
1
2
3
4
5
6
7
u
p
1
0
0
1
0
1
0
m
p
1371.8
0
0
1222.9
0
607.8
0Table 5
Distribution paths of vehicles.
Period
Paths
Transportation cost
1
0-2-1-0; 0-10-12-0; 0-3-0; 0-4-0; 0-6-7-0; 0-8-9-11-0; 0-5-0
458.879
2
0-7-0; 0-10-11-0
195.969
3
0-1-0; 0-2-0; 0-3-9-0
137.155
4
0-8-5-0; 0-7-6-0; 0-2-0; 0-4-12-0; 0-3-0
305.766
5
0-6-0; 0-10-11-0; 0-12-0; 0-7-0; 0-5-0
409.569
6
0-1-0; 0-8-9-0; 0-4-0; 0-3-0
177.119
7
0-2-7-0; 0-5-9-0
119.629Table 6
Cost distribution.
Value
Supplier’s cost
Production setup cost: 3000; inventory cost: 125.968
Total: 3125.97
Transportation cost
See Table4
Total: 1804.09
Retailers’ cost
Unloading cost: 2100; inventory cost: 211.17
Total: 2311.17
Cost of time interval penalty
Total: 220
Total cost
7461.23The original solution is the following: in each period, the supplier produces and each retailer receives a delivery. Each vehicle will serve only one retailer per trip. The total cost of the initial solution is 16287.2 (which is referred to as a lower bound of 1). Second, when only the master problem is not optimised, which means that all of the retailers are served in each period, the supplier makes his production decision with the saving algorithm, and vehicle routes are made with the neighbourhood search. The total cost of this solution is 9811.52, which is another low-value limitation of our numerical example (referred to as lower bound 2). This strategy is common in practice; for example, a supplier delivers different types of goods to stores once a day, and only the production scheduling and vehicle routes are optimised. Finally, when the master problem and two subproblems are all optimised, the result is our final solution, and the total cost is 7461.23. The optimised total cost is 54.19% lower than the lower bound of 1 and 23.95% lower than the lower bound of 2. The final results demonstrate that a mixed strategy that considers the supplier, retailers, and distribution routes simultaneously can save a substantial amount of cost in the distribution channel.From Tables3-4, we can see that, in the three production periods, the retailers’ goods arrival rates are all larger than those in the nonproduction periods. The average arrival number in the production periods is 8.33 compared to 4.25 in the nonproduction periods. It can be concluded that production decisions and arrival decisions are closely connected.If the shelf life of a considered deteriorating item is unlimited, then the total cost will be 6306.71, which is 240.84 lower than that in the case (3.23%). Thus, accounting for the corruption characteristics of the perishable products will change the decisions in the supply chain; additionally, considering the supplier costs and shelf life of the perishable goods in the model will have an obvious impact on the solutions and the total costs.


### 5.2. Sensitivity Analysis

The solution algorithm that is proposed above is derived from several existing mature algorithms, that is, a neighbourhood search, tabu search and saving algorithm; as a result, in this section, sensitivity analysis will be conducted mainly to illustrate the effectiveness of the proposed model. The parameters that are considered here include the storage life at the retailer sites, the upper bounds of the vehicle driving time, the unit loading cost, the vehicles’ return time interval and the driving cost per unit distance.Table7 shows that, with an increase in the shelf life at the retailer sites, it is more likely that a lower total relevant cost will be attained. However, due to the constraints of the other costs in the model, even if the shelf life at the retailer sites keeps rising, the decrease in the total cost is limited. All of the above shows that the improvement in the perishable goods shelf management at the retailers’ sites could have a positive influence on the total cost; while the sales stage is only part of the deterioration in the items’ life cycles, the impact on the total integrated cost is limited to a certain range.Table 7
Results of different shelf-lifeε in the retail stage.
ε
Largest delivery interval
Number of deliveries
Retailers’ cost
Supplier’s cost(production periods)
Transportation cost
Cost of time interval penalty
Total cost
1
1
84
4200
3198.93 (1, 3, 5)
2227.59
185
9811.52
2
2
52
2725.22
3134.74 (1, 3, 6)
1904.71
205
7969.68
3
3
42
2311.17
3125.97 (1, 4, 6)
1804.09
220
7461.23
4
4
36
2109.6
3098.67 (1, 4, 5)
1740.71
250
7198.98
5
5
37
2100.83
3107.35 (1, 4, 6)
1744.71
230
7182.89
6
5
37
2112.46
3096.1 (1, 4, 6)
1737.3
270
7215.26
7
6
37
2137.64
3115.14 (1, 3, 6)
1767.61
200
7220.39Table8 indicates that when the upper bounds of the vehicle driving time t
max
1 and t
max
2 are small, their increase could reduce the transportation cost, thus reducing the total cost. When the upper bounds are larger, a further improvement would have little impact. Then, we can illustrate that improving the preservation condition of the vehicles could reduce the total cost of the supply chain and improve the goods’ quality, which is of great benefit in the food supply chain. It is clear that the impacts of the vehicle’s largest driving time limit t
max
2 on the decision variables could achieve similar results by changing the vehicle velocity; as a result, the sensitivity analysis of the vehicle velocity is omitted here.Table 8
Results of different upper bounds for the vehicle driving time,t
max1  and t
max2.
t
max1
t
max2
Retailers’ cost
Supplier’s cost(production periods)
Transportation cost
Cost of time interval penalty
Driving distance
Total cost
0.5
2.5
2363.85
3097.29 (1, 4, 5)
1838.89
230
450.9
7530.03
0.8
2.8
2292.61
3081.32 (1, 3, 5)
1826.08
275
448.2
7475.01
1.1
3.1
2341.5
3089.47 (1, 3, 5)
1818.76
230
446.5
7479.73
1.3
3.3
2309.83
3111.38 (1, 3, 5)
1829.52
195
453.2
7445.73
1.7
3.7
2311.17
3125.97 (1, 4, 6)
1804.09
220
441.9
7461.23
2
4
2311.17
3125.97 (1, 4, 6)
1804.09
220
441.9
7461.23Table9 shows that with an increase in the unit loading cost, the ratio of the unit loading cost to the vehicle’s fixed usage cost also increases as well as the total number of vehicles and the transportation cost; it has little influence on the supplier’s and retailers’ costs. The variation extent of the transportation cost is not as obvious as for the unit loading cost. This finding arises because more vehicles are used to avoid having a distance that is too long and a load that is too large on a vehicle, which significantly restrains the increasing trends in the transportation cost.Table 9
Results of different unit loading costs of vehiclesc
g.
c
g
Vehicle numbers
Retailers’ cost
Supplier’s cost(production periods)
Transportation cost
Total cost
0
26
2270.73
3101.53 (1, 3, 5)
705.5
6242.76
0.03
26
2352.68
3107.03 (1, 4, 6)
1383.68
7008.39
0.05
28
2311.17
3125.97 (1, 4, 6)
1804.09
7461.23
0.08
28
2300.55
3125.61 (1, 4, 6)
2443.52
8119.68
0.1
28
2307.45
3108.43 (1, 4, 5)
2849.31
8485.19
0.15
29
2264.72
3094.8 (1, 3, 5)
3944.28
9533.8
0.2
31
2299.13
3120.12 (1, 3, 5)
4978.12
10662.4From Table10, we can see that as the value of i
t
v increases, that is, the supplier’s facilities have even tougher criteria on the vehicles’ returning time, the cost of the time interval penalty increases as well as the total cost of the system. Therefore, if the facilities have sufficient capacity to accommodate more vehicles simultaneously, then we will have a higher chance to decrease the total relevant cost of the supply chain.Table 10
Results of different intervals of vehicles’ returning timeitv.
itv
Driving distance
Retailers’ cost
Supplier’s cost(production periods)
Transportation cost
Cost of time interval penalty
Total cost
0
437
2305.27
3089.56 (1, 3, 5)
1797.19
0
7192.02
0.3
449.4
2300.3
3091.92 (1, 4, 6)
1817.48
195
7404.7
0.5
441.9
2311.17
3125.97 (1, 4, 6)
1804.09
220
7461.23
0.8
455.5
2357.68
3101.55 (1, 4, 6)
1842.53
265
7566.76
1
439.4
2347.04
3126.83 (1, 4, 6)
1819.26
255
7548.13
1.2
457.9
2344.8
3146.67 (1, 4, 6)
1827.35
225
7543.82
1.5
438.3
2366.42
3083.49 (1, 3, 5)
1805.22
280
7535.13
2
450.8
2340.47
3138.86 (1, 4, 6)
1815.84
260
7555.17From Table11, the results reveal that when the driving cost per unit distance c
v increases, the transportation cost increases and, in addition, the total relevant cost increases. Because of other constraints of the proposed model, the variation extent of decreasing the travelling distance of the vehicles is not as obvious as that of the driving cost per unit distance.Table 11
Results of different driving costs per unit distancec
v.
c
v
Driving distance
Retailers’ cost
Supplier’s cost
Transportation cost
Cost of time interval penalty
Total cost
0.25
438.6
2346.11
3104.82
1465.07
230
7146
0.5
452.7
2262.42
3104.1
1588.53
205
7160.05
1
441.9
2311.17
3125.97
1804.09
220
7461.23
1.5
461
2310.57
3110.07
2053.59
240
7714.23
2
453.1
2302.77
3127.84
2281.9
215
7927.51
5
426.8
2364.55
3116.3
3492.59
175
9148.45
10
433.6
2392.2
3113.18
5732.19
215
11452.6
20
407.1
2486.07
3108.1
9491.9
190
15276.1Whenc
g and i
t
v are equal to 0, the proposed model is transformed into the classical IRP with time windows, and the total cost is 6060.11.


## 5.1. Numerical Example

An example is adopted to test the effectiveness of the proposed model and the impact of some of the parameters on the decisions. The relative parameters are as follows. The supply chain is made of one supplier and 12 retailers. The retailers’ demands are given in Table1. The distance between any two nodes is within 25, and the planning time horizon in this example consists of seven periods, each representing one day. Table 2 provides the distance matrix for the nodes. The vehicle velocities in each period are 35, 40, 40, 40, 35, 30, and 30, respectively. The supplier’s production setup cost is 1000 per order, and the inventory cost is 0.08 per day per unit. The daily production capacity is 1500. The fixed usage cost of the vehicles is 10, and the driving cost is 1 per kilometre. The longest driving time threshold value without the penalty t
max
1 is 2 hours, and 0.05 would be penalised per hour per unit after 2 hours but within 4 hours; that is, t
max
2
=
4. The vehicle capacity is 150 units. The cost of delivering a product of per unit weight and per unit distance is 0.05. The lower bound of the time interval of the vehicles’ returning to the supplier’s facilities i
t
v is 0.5 hour; if the actual interval is less than the threshold value, then the cost of a unit time is 5. The holding cost of the retailers is 0.1 per day per unit, and the unloading cost is 50. The deteriorating item’s shelf life at the retailer sites is 3 days.Table 1
Retailers’ demand in each period.
Period
Retailer
1
2
3
4
5
6
7
8
9
10
11
12
1
22.3
30.3
37.9
31.1
29.5
21.2
42.1
13.2
12.1
20.4
15.3
25.1
2
24.8
37.9
51.2
42.3
34.4
27.0
55.7
25.6
12.9
22.3
17.0
28.2
3
35.2
51.3
68.8
58.7
45.8
41.5
83.3
54.8
18.2
27.9
22.3
31.3
4
36.3
52.5
71.3
60.3
45.8
42.7
84.0
56.7
19.3
28.1
22.9
32.7
5
30.8
45.2
57.8
52.5
40.1
35.7
67.9
43.3
15.5
25.2
20.1
30.5
6
25.1
37.7
49.9
43.8
34.6
27.7
53.0
25.1
13.4
22.5
17.7
27.6
7
39.8
58.9
73.2
65.9
48.0
47.9
75.7
67.7
21.3
30.3
25.2
34.4Table 2
Distance matrix of nodes.
Nodes
Nodes
0
1
2
3
4
5
6
7
8
9
10
11
12
0
0
5.5
1.7
3.8
3.4
6.7
6.7
6.6
6.1
8.5
10.8
14.2
15.1
1
0
4.3
9
8.5
12.3
8.8
6.7
11.1
13.8
16.3
19.7
20.6
2
0
5.5
4.2
8.1
7.9
7.2
6.8
9.5
12.1
15.6
16.3
3
0
3.9
3.9
5.9
7.3
5.5
6.8
8.1
11
12.3
4
0
4.5
9.1
9.7
2.7
5.3
8
11.7
12.2
5
0
9.4
11.1
3.8
3.4
4.2
7.5
8.5
6
0
2.7
11.3
12.6
13.4
15.5
17.3
7
0
12.2
14
15.3
17.7
19.3
8
0
2.9
6
9.9
10
9
0
3.3
7.2
7.1
10
0
3.9
4.3
11
0
25
12
0The model is coded and run on the platform of Visual C++ 6.0. All of the tests are performed on the Intel(R) Core (TM)2 Duo at 2.00 GHz with 2 GB RAM under the Microsoft Windows 7 operation system. The results are presented in Tables3, 4, 5, and 6.Table 3
Arrival matrix of retailers.
Period
Retailer
1
2
3
4
5
6
7
8
9
10
11
12
1
1
1
1
1
1
1
1
1
1
1
1
1
2
0
0
0
0
0
0
1
0
0
1
1
0
3
1
1
1
0
0
0
0
0
1
0
0
0
4
0
1
1
1
1
1
1
1
0
0
0
1
5
0
0
0
0
1
1
1
0
0
1
1
1
6
1
0
1
1
0
0
0
1
1
0
0
0
7
0
1
0
0
1
0
1
0
1
0
0
0Table 4
Supplier’s production vectors.
Vectors
Value
Period
1
2
3
4
5
6
7
u
p
1
0
0
1
0
1
0
m
p
1371.8
0
0
1222.9
0
607.8
0Table 5
Distribution paths of vehicles.
Period
Paths
Transportation cost
1
0-2-1-0; 0-10-12-0; 0-3-0; 0-4-0; 0-6-7-0; 0-8-9-11-0; 0-5-0
458.879
2
0-7-0; 0-10-11-0
195.969
3
0-1-0; 0-2-0; 0-3-9-0
137.155
4
0-8-5-0; 0-7-6-0; 0-2-0; 0-4-12-0; 0-3-0
305.766
5
0-6-0; 0-10-11-0; 0-12-0; 0-7-0; 0-5-0
409.569
6
0-1-0; 0-8-9-0; 0-4-0; 0-3-0
177.119
7
0-2-7-0; 0-5-9-0
119.629Table 6
Cost distribution.
Value
Supplier’s cost
Production setup cost: 3000; inventory cost: 125.968
Total: 3125.97
Transportation cost
See Table4
Total: 1804.09
Retailers’ cost
Unloading cost: 2100; inventory cost: 211.17
Total: 2311.17
Cost of time interval penalty
Total: 220
Total cost
7461.23The original solution is the following: in each period, the supplier produces and each retailer receives a delivery. Each vehicle will serve only one retailer per trip. The total cost of the initial solution is 16287.2 (which is referred to as a lower bound of 1). Second, when only the master problem is not optimised, which means that all of the retailers are served in each period, the supplier makes his production decision with the saving algorithm, and vehicle routes are made with the neighbourhood search. The total cost of this solution is 9811.52, which is another low-value limitation of our numerical example (referred to as lower bound 2). This strategy is common in practice; for example, a supplier delivers different types of goods to stores once a day, and only the production scheduling and vehicle routes are optimised. Finally, when the master problem and two subproblems are all optimised, the result is our final solution, and the total cost is 7461.23. The optimised total cost is 54.19% lower than the lower bound of 1 and 23.95% lower than the lower bound of 2. The final results demonstrate that a mixed strategy that considers the supplier, retailers, and distribution routes simultaneously can save a substantial amount of cost in the distribution channel.From Tables3-4, we can see that, in the three production periods, the retailers’ goods arrival rates are all larger than those in the nonproduction periods. The average arrival number in the production periods is 8.33 compared to 4.25 in the nonproduction periods. It can be concluded that production decisions and arrival decisions are closely connected.If the shelf life of a considered deteriorating item is unlimited, then the total cost will be 6306.71, which is 240.84 lower than that in the case (3.23%). Thus, accounting for the corruption characteristics of the perishable products will change the decisions in the supply chain; additionally, considering the supplier costs and shelf life of the perishable goods in the model will have an obvious impact on the solutions and the total costs.


## 5.2. Sensitivity Analysis

The solution algorithm that is proposed above is derived from several existing mature algorithms, that is, a neighbourhood search, tabu search and saving algorithm; as a result, in this section, sensitivity analysis will be conducted mainly to illustrate the effectiveness of the proposed model. The parameters that are considered here include the storage life at the retailer sites, the upper bounds of the vehicle driving time, the unit loading cost, the vehicles’ return time interval and the driving cost per unit distance.Table7 shows that, with an increase in the shelf life at the retailer sites, it is more likely that a lower total relevant cost will be attained. However, due to the constraints of the other costs in the model, even if the shelf life at the retailer sites keeps rising, the decrease in the total cost is limited. All of the above shows that the improvement in the perishable goods shelf management at the retailers’ sites could have a positive influence on the total cost; while the sales stage is only part of the deterioration in the items’ life cycles, the impact on the total integrated cost is limited to a certain range.Table 7
Results of different shelf-lifeε in the retail stage.
ε
Largest delivery interval
Number of deliveries
Retailers’ cost
Supplier’s cost(production periods)
Transportation cost
Cost of time interval penalty
Total cost
1
1
84
4200
3198.93 (1, 3, 5)
2227.59
185
9811.52
2
2
52
2725.22
3134.74 (1, 3, 6)
1904.71
205
7969.68
3
3
42
2311.17
3125.97 (1, 4, 6)
1804.09
220
7461.23
4
4
36
2109.6
3098.67 (1, 4, 5)
1740.71
250
7198.98
5
5
37
2100.83
3107.35 (1, 4, 6)
1744.71
230
7182.89
6
5
37
2112.46
3096.1 (1, 4, 6)
1737.3
270
7215.26
7
6
37
2137.64
3115.14 (1, 3, 6)
1767.61
200
7220.39Table8 indicates that when the upper bounds of the vehicle driving time t
max
1 and t
max
2 are small, their increase could reduce the transportation cost, thus reducing the total cost. When the upper bounds are larger, a further improvement would have little impact. Then, we can illustrate that improving the preservation condition of the vehicles could reduce the total cost of the supply chain and improve the goods’ quality, which is of great benefit in the food supply chain. It is clear that the impacts of the vehicle’s largest driving time limit t
max
2 on the decision variables could achieve similar results by changing the vehicle velocity; as a result, the sensitivity analysis of the vehicle velocity is omitted here.Table 8
Results of different upper bounds for the vehicle driving time,t
max1  and t
max2.
t
max1
t
max2
Retailers’ cost
Supplier’s cost(production periods)
Transportation cost
Cost of time interval penalty
Driving distance
Total cost
0.5
2.5
2363.85
3097.29 (1, 4, 5)
1838.89
230
450.9
7530.03
0.8
2.8
2292.61
3081.32 (1, 3, 5)
1826.08
275
448.2
7475.01
1.1
3.1
2341.5
3089.47 (1, 3, 5)
1818.76
230
446.5
7479.73
1.3
3.3
2309.83
3111.38 (1, 3, 5)
1829.52
195
453.2
7445.73
1.7
3.7
2311.17
3125.97 (1, 4, 6)
1804.09
220
441.9
7461.23
2
4
2311.17
3125.97 (1, 4, 6)
1804.09
220
441.9
7461.23Table9 shows that with an increase in the unit loading cost, the ratio of the unit loading cost to the vehicle’s fixed usage cost also increases as well as the total number of vehicles and the transportation cost; it has little influence on the supplier’s and retailers’ costs. The variation extent of the transportation cost is not as obvious as for the unit loading cost. This finding arises because more vehicles are used to avoid having a distance that is too long and a load that is too large on a vehicle, which significantly restrains the increasing trends in the transportation cost.Table 9
Results of different unit loading costs of vehiclesc
g.
c
g
Vehicle numbers
Retailers’ cost
Supplier’s cost(production periods)
Transportation cost
Total cost
0
26
2270.73
3101.53 (1, 3, 5)
705.5
6242.76
0.03
26
2352.68
3107.03 (1, 4, 6)
1383.68
7008.39
0.05
28
2311.17
3125.97 (1, 4, 6)
1804.09
7461.23
0.08
28
2300.55
3125.61 (1, 4, 6)
2443.52
8119.68
0.1
28
2307.45
3108.43 (1, 4, 5)
2849.31
8485.19
0.15
29
2264.72
3094.8 (1, 3, 5)
3944.28
9533.8
0.2
31
2299.13
3120.12 (1, 3, 5)
4978.12
10662.4From Table10, we can see that as the value of i
t
v increases, that is, the supplier’s facilities have even tougher criteria on the vehicles’ returning time, the cost of the time interval penalty increases as well as the total cost of the system. Therefore, if the facilities have sufficient capacity to accommodate more vehicles simultaneously, then we will have a higher chance to decrease the total relevant cost of the supply chain.Table 10
Results of different intervals of vehicles’ returning timeitv.
itv
Driving distance
Retailers’ cost
Supplier’s cost(production periods)
Transportation cost
Cost of time interval penalty
Total cost
0
437
2305.27
3089.56 (1, 3, 5)
1797.19
0
7192.02
0.3
449.4
2300.3
3091.92 (1, 4, 6)
1817.48
195
7404.7
0.5
441.9
2311.17
3125.97 (1, 4, 6)
1804.09
220
7461.23
0.8
455.5
2357.68
3101.55 (1, 4, 6)
1842.53
265
7566.76
1
439.4
2347.04
3126.83 (1, 4, 6)
1819.26
255
7548.13
1.2
457.9
2344.8
3146.67 (1, 4, 6)
1827.35
225
7543.82
1.5
438.3
2366.42
3083.49 (1, 3, 5)
1805.22
280
7535.13
2
450.8
2340.47
3138.86 (1, 4, 6)
1815.84
260
7555.17From Table11, the results reveal that when the driving cost per unit distance c
v increases, the transportation cost increases and, in addition, the total relevant cost increases. Because of other constraints of the proposed model, the variation extent of decreasing the travelling distance of the vehicles is not as obvious as that of the driving cost per unit distance.Table 11
Results of different driving costs per unit distancec
v.
c
v
Driving distance
Retailers’ cost
Supplier’s cost
Transportation cost
Cost of time interval penalty
Total cost
0.25
438.6
2346.11
3104.82
1465.07
230
7146
0.5
452.7
2262.42
3104.1
1588.53
205
7160.05
1
441.9
2311.17
3125.97
1804.09
220
7461.23
1.5
461
2310.57
3110.07
2053.59
240
7714.23
2
453.1
2302.77
3127.84
2281.9
215
7927.51
5
426.8
2364.55
3116.3
3492.59
175
9148.45
10
433.6
2392.2
3113.18
5732.19
215
11452.6
20
407.1
2486.07
3108.1
9491.9
190
15276.1Whenc
g and i
t
v are equal to 0, the proposed model is transformed into the classical IRP with time windows, and the total cost is 6060.11.


## 6. Conclusions

Accounting for the loading cost and the vehicles’ returning time interval, a new formulation of a production-distribution-inventory IRP model under discrete time is proposed. When making integrated decisions for deteriorating items in a physical distribution channel, it is reasonable to consider time windows that are in a transit stage as well as a sales stage, to control the product quality. With the objective of minimising the total relevant cost, this model determines the supplier’s production plan, the retailers’ delivery time, and the vehicle routing in each period over the planning horizon. Based on the features of the problem, a two-phase algorithm is developed. A numerical example and sensitivity analysis have also been conducted to demonstrate the effectiveness of the model and algorithm. The impact of the relevant parameter changes is also illustrated on the decision making and the total relevant costs.The results show that the vehicles’ loading cost and return time interval do have obvious impacts on the decision variables, and considering the joint total relevant cost of the supply chain will make the proposed model a useful tool in the operation of the production and distribution systems with deteriorating items.The primary contributions of this paper lie in the consideration of the vehicle’s loading cost and returning time interval, as well as in the deteriorating items’ quality control in an integrated supply chain. However, several factors, such as multiple products, split pickup, and other factors, are not considered. These factors can be explored in future studies, and their consideration would help to make the inventory routing problem more realistic; additionally, testing the effectiveness of the proposed algorithm will be the primary undertaking in our future research.



---

*Source: 537409-2014-01-29.xml*