# A Hybrid Dynamic Programming for Solving Fixed Cost Transportation with Discounted Mechanism

Authors: Farhad Ghassemi Tari
Journal: Journal of Optimization
 (2016)

---

## Abstract

The problem of allocating different types of vehicles for transporting a set of products from a manufacturer to its depots/cross docks, in an existing transportation network, to minimize the total transportation costs, is considered. The distribution network involves a heterogeneous fleet of vehicles, with a variable transportation cost and a fixed cost in which a discount mechanism is applied on the fixed part of the transportation costs. It is assumed that the number of available vehicles is limited for some types. A mathematical programming model in the form of the discrete nonlinear optimization model is proposed. A hybrid dynamic programming algorithm is developed for finding the optimal solution. To increase the computational efficiency of the solution algorithm, several concepts and routines, such as the imbedded state routine, surrogate constraint concept, and bounding schemes, are incorporated in the dynamic programming algorithm. A real world case problem is selected and solved by the proposed solution algorithm, and the optimal solution is obtained.


---

## Body

## 1. Introduction

Transportation is a critical part of global logistics systems, because of the long distances that can separate a firm from its customers. Among five primary modes of transportation, rail, road, pipeline, water, and air, trucks carry the highest percentage of the weight and value of goods in the United States [1]. Since logistics is often insensitive to transport costs, the total costs of transport must be analyzed more thoroughly.In this paper the problem of designing a cost efficient road transportation model is considered. The proposed transportation model is motivated by a vehicle-depots assignment in the transportation model of Solico Industrial Group (SIG) in a developing country with an existing distribution network. While considering this real world problem a more generalized version of this transportation model is explored. A thorough investigation reveals that most of developing countries, such as Afghanistan, India, Iraq, Pakistan, Turkey, all the Gulf Corporation Council countries, and the Commonwealth of Independent State countries, have the transportation models very similar to the scope of SIG. Therefore our approach may later be adapted by the similar manufacturers in developing countries.Based on these assumptions the problem is defined as a distribution system for delivering a set of products from a manufacturing firm to a set of distinct depots/cross docks and allocating the appropriate vehicles to the distribution branches to minimize the total transportation costs. A mathematical model in the form of the nonlinear integer programming is employed to formulate the problem. Then an exact solution approach for solving the proposed problem is developed. The proposed solution approach is employed for solving a case problem and the result is reported.


## 2. Literature Review

Recently, by the use of e-commerce most of the logistics activities have been changed. However physical delivery still relies on the transportation system to finish the operations. Many mathematical models and quantitative methods have been developed for optimizing the operation of transport systems in order to serve the customers demand. Logistics adds value to the supply chain process. According to the 26th annual “State Logistics Report” by the Council of Supply Chain Management Professionals published in 2015, United States business logistics costs are $1.45 trillion US dollars in 2014, and the transportation costs for the same year run to nearly one trillion US dollars that constitute over 65% of the total logistics costs [1]. As these statistics indicate the largest contribution to logistic costs is transportation. Logistics optimization has significantly grown in popularity over the last few decades [2]. Changes over the last 3 decades have given companies increased flexibility and control over their logistics activities [3]. Design of large-scale distribution networks which involves decision making on a large number of issues makes it difficult to develop a competitive distribution strategy [4]. Recent technological developments could enable the trading of formalized options around transportation and logistics services. The modeling of logistics systems is performed to seek the best possible system configuration to minimize costs or maximize operational performance, in order to meet or exceed customer expectations [5]. The study of the cost concept of logistics is due to work of Waller and Fawcett [6] and Kowalski et al. [7].Transportation is also considered as an important element of logistics and supply chain process. Goossens and Spieksma [8] considered a generalization of the ordinary transportation problem with some exclusionary side constraints. In their work they confirmed that their proposed model is NP-hard. Then Waldherr et al. [9] presented a new extension of the bottleneck transportation problem with additionally auxiliary resources for supporting the transports. A transportation system with a single commodity for satisfying the total demand is presented. Adlakha and Kowalski [10] proposed a solution algorithm for certain transportation problems. The concept of absolute points developed in [11] is employed and a direct analytical algorithm for transportation problems with quadratic function cost coefficients is explored.Other research attempts are those considering the discounting mechanisms and their impacts on the overall transportation costs. Discounted fixed cost transportation can be considered as a version of fixed cost transportation problem. This is considered to be NP-hard problem since the cost structure causes the value of the objective function to behave like a step function [12]. Numerous models have been developed to overcome this issue. For models considering discounted price according to the variation of quantities refer to Das et al. [13], Acharya et al. [14], Blazewicz et al. [15], and Osuji et al. [16].Design of a cost efficient distribution network and a better utilization of vehicles for transporting goods have been studied and implemented in several real world instances. One of these studies is an experiment conducted by Donselaar and Sharman [17]. This experiment focused on the transportation and distribution sector in a province in the Netherlands. Bhadury et al. [18] developed a comprehensive methodology to optimize the planning of acquiring motor carriers in transportation companies. An infrastructure development program is conducted in Hong Kong for modernizing its outdated and inadequate transportation systems. On completion of this project, the strategic position of Hong Kong as a port of Southern China was enhanced [19]. Another attempt is the study of the Brazilian motor carrier industry for evaluating the impact of different types of cargoes and geographic regions serviced on trucking managerial efficiency levels [20]. A systematic review of the literature on the design of global production and distribution networks is due to work of Olhager et al. [21].The other attempt is the work of Reimann et al. [22] that reviewed existing literature on integrated production and distribution decisions at the tactical and operational level. The focus was thereby on problems that explicitly consider deliveries to multiple clients in a less-than-truckload fashion. They distinguished between tactical and operational production problems by considering lot-sizing/capacity allocation and scheduling models, respectively. The trends of the mathematical models and the solution algorithms for handling the fleet management systems were presented in the research work of Biellia et al. [23]. They identified the most relevant problems in fleet management according to different transport modes, each one with specific characteristics, and presented an overview of recent contributions both in the development of mathematical models and in the design of computation algorithms. There are some attempts using simulation for fleet management problems. Those who are interested are referred to Kiani et al. [24], Netto and Botter [25], and Sebbah et al. [26].To solve the proposed mathematical programming model a dynamic programming approach can be employed. Dynamic programming is a powerful approach through which the global optimal solution can be obtained even in the case of discrete solution space. The use of this powerful approach however is limited since the growth of the number of decision variables and state variables requires an extensive computer memory storage and computational time. Considerable research has been devoted to overcoming the problem of state variables dimensionality in the dynamic programming techniques. Earlier attempts were made through employing the concept of Lagrangian multipliers [27]. Another attempt was the use of surrogate constraint [28]. Both Lagrangian and surrogate constraint framework suffer from existence of the duality gap. Although Glover [29], Greenberg [30], and Mizukami and Sikrorski [31] have shown that the occurrence and the size of the gap in surrogate approach are usually less compared to the Lagrangian method, however a unified theory to provide a basis for an algorithmic procedure using the surrogate constraint method has not emerged and general computational difficulties are waiting for a unified theory. The third attempt is the approach of Morin and Esogbue [32] who proposed a dynamic programming algorithm which is searching over the imbedded state for obtaining an optimal solution. Latter attempt provides a powerful solution procedure for solving a general class of the dynamic programming models. Since then a set of research works have been devoted to the reduction of state space solution [33], Righini and Salani [34], Fang et al. [35], Russo et al. [36], and Chebil and Khemakhem [37].The proposed problem actually is an extension of the fixed charge transportation problems. The fixed charge transportation problem is classified as a NP-hard combinatorial optimization problem [38]. Due to the computational complexity of the proposed problem, a hybrid dynamic programming (DP) solution algorithm is developed. To increase the computational efficiency of the solution approach, several concepts and routines such as the imbedded state routine, surrogate constraint concept, and bounding schemes are incorporated in the powerful enumerating approach of the DP algorithm. In Section 3 the development of the mathematical programming will be presented. In Section 4, the process of developing the hybrid DP will be described. Section 5 is devoted to the computational experiments. Finally the paper is concluded in Section 6.


## 3. Development of the Mathematical Models

In order to obtain the optimal allocation of vehicles for delivering the products to depots/cross docks we need to formulate the problem in the form of a mathematical programming model. As we will see later the mathematical models for handling such problems are in the form of the nonlinear discrete optimization models. Due to the computational complexity of such problems a need for developing an efficient solution approach is required. In the following sections we will describe the development of the mathematical models and the solution approach.


### 3.1. Problem Description

Consider a directed graphG
=
N
,
A with the set A of directed arcs and the set N of nodes representing a manufacture and depots/cross docks. The manufacture is indexed 0 and depots/cross docks (branches) are indexed from 1 to n. Branch j has a known demand with the total goods weight of W
j
,
j
∈
N
∖
0. There are m types of vehicles, and the total number of vehicles for type i is T
i (there is no limitation on the number of vehicles for most of the vehicle’s types, but in our case problem only two types of the vehicles are limited). The capacity of the vehicle type i in terms of weight it can deliver is designated by C
i, and the transpiration charge of vehicle type i for the route ending to depot/cross dock j is K
i
j. We want to allocate the proper vehicle’s type for delivering the total demand of a depot/cross dock to minimize the total transportation costs of distributing products to all the depots/cross docks. It is also assumed that there exists a discount policy for the vehicles to be rented. This discount varies according to the number of rented vehicles and is applied on their fixed cost. By this discount policy, if the number of rented type i vehicles is less than n
i
1, the renting companies ask for the fixed cost of F
i
1. If the number of type i vehicles is greater than or equal to n
i
1, but less than n
i
2, when n
i
1
<
n
i
2, the renting companies charge a discounted value of F
i
2 as the fixed charge. Let us consider x
i
j as the number of type i vehicles for transporting the products to depot/cross dock j. Assuming there are as many as v number of discount intervals, the general formula for determining the fix cost can be written as follows: (1)Fi=0for∑j=1nxij=0,∀i=1,2,…,mFi1for∑j=1nxij<ni1,∀i=1,2,…,mFi2forni1≤∑j=1nxij<ni2,∀i=1,2,…,m⋮⋮Fivforniv≤∑j=1nxij≤Ti,∀i=1,2,…,m,where F
i
1
>
F
i
2
>
⋯
>
F
i
v.Due to existing distribution network, the distances from the manufacturing firm to depots/cross docks are fixed and are given. The objective is assigning a set of vehicles to each branch leading to depot/cross dock, to minimize the total transporting costs. The mathematical model is developed and will be presented in the following section.


### 3.2. Mathematical Model

Some parameters used in the proposed mathematical models are listed as follows:x
i
j: number of vehicles of type i allocated for transporting products to depot/cross dock j.
C
i: weight capacity of vehicle type i.
c
i
j: variable transportation costs of vehicle type i to depot/cross dock j.
T
i: total number of vehicles of type i.
W
j: total weight of products ordered by depot/cross dock j.
t
c
j
x
i
j: a step function denoting the total transportation costs of branch j (leading to depot/cross dock j) of the distribution network.
F
i: fixed cost of using vehicle type i
,
i
=
1,2
,
…
,
m.
n: total number of the depots/cross docks.
m: total number of the vehicles types.
X
0: total transportation costs.
UB: the upper bound of the objective function value.
λ
i: weighting factor of the ith constraint for defining the surrogate constraint.
UBB: the upper bound of the objective function value, obtained by the subroutine bound.
UBS: the upper bound of the objective function value, obtained by the optimal solution of the surrogate problem.
SO: a matrix for recording the imbedded state variables, in each stage of the DP solution process, of the original problem.
SR: a vector for recording the return values of the imbedded state variables, in each stage of the DP solution process, of the original problem.
SOS: a matrix for recording the imbedded state variables, in each stage of DP solution process, of the surrogate problem.
SRS: a vector for recording the return values of the imbedded state variables, in each stage of the DP solution process, of the surrogate problem.The objective function for the proposed problem can be written as(2)MinX0=∑i=1m∑j=1nFixij+∑i=1m∑j=1ncijxij,where F
i is a step function denoting the fixed part of the transportation costs and c
i
j is the variable part of the transportation costs. Let us define the total transportation costs of each depot/cross dock (branch) as follows.Then we will have(3)tcjxij=∑i=1mFixij+∑i=1mcijxij∀j=1,2,…,nMinX0=∑j=1ntcjxijS.T.∑i=1mCixij≥Wj∀j=1,2,…,n∑j=1nxij≤Ti∀i=1,2,…,mxij=0,1,2,…∀j=1,2,…,n,i=1,2,…,m.As it can be realized, the above mathematical model can be decomposed according to branches as follows:(4)MinX0=∑i=1mtc1xi1+∑i=1mtc2xi2+⋯+∑i=1mtcnxinS.T.∑i=1mCixi1≤W1∑i=1mCixi2≤W2⋮∑i=1mCixin≤Wnxi1+xi2+⋯+xin≤Ti∀i=1,2,…,mxij=0,1,2,…∀j=1,2,…,n,i=1,2,…,m.Due to the decomposed mathematical model, the dynamic programming (DP) solution approach seems to be the best candidate for solving the proposed problem. Considering this approach the recursive equations for forward computations of the DP approach can be developed as follows.LetY
j
=
y
1
j
,
y
2
j
,
…
,
y
m
j be The state variable of the jth stage indicating the vehicle type 1,2
,
…
,
m, allocated to the 1,2
,
…
,
jth depot/cross dock.f
j
Y
j
=
f
j
y
1
j
,
y
2
j
,
…
,
y
m
j is The total transportation costs of the 1,2
,
…
,
jth depot/cross dock.The recursive equations of the stages can be formulated as(5)f1Y1=f1y11,y21,…,ym1=Minx11,x21,…,xm1≤y11,y21,…,ym1∑i=1mCix1i≤W1∑i=1mtc1xi1fjYj=fjy1j,y2j,…,ymj=Minx1j,x2j,…,xmj≤y1j,y2j,…,ymj∑i=1mCixji≤Wj∑i=1mtcjxij+fj-1y1j-1,y2j-1,…,ymj-1=Minx1j,x2j,…,xmj≤y1j,y2j,…,ymj∑i=1mCixji≤Wj∑i=1mtcjxij+fj-1y1j-x1j,y2j-x2j,…,ymj-xmj∀j=2,3,…,n.The DP solution algorithm is an efficient solution approach for the cases that the dimensions of the state variables are small. Therefore the selection of the DP approach is actually based on the practical conditions of the case problem which provides some considerations for reducing the state variable dimensions. In addition practical conditions of the case problem provide some other computational aspects which enabled us to find the optimal solution for the relatively large mathematical model of the case problem. In following sections we will present the development of an exact solution algorithm for the proposed problem.


## 3.1. Problem Description

Consider a directed graphG
=
N
,
A with the set A of directed arcs and the set N of nodes representing a manufacture and depots/cross docks. The manufacture is indexed 0 and depots/cross docks (branches) are indexed from 1 to n. Branch j has a known demand with the total goods weight of W
j
,
j
∈
N
∖
0. There are m types of vehicles, and the total number of vehicles for type i is T
i (there is no limitation on the number of vehicles for most of the vehicle’s types, but in our case problem only two types of the vehicles are limited). The capacity of the vehicle type i in terms of weight it can deliver is designated by C
i, and the transpiration charge of vehicle type i for the route ending to depot/cross dock j is K
i
j. We want to allocate the proper vehicle’s type for delivering the total demand of a depot/cross dock to minimize the total transportation costs of distributing products to all the depots/cross docks. It is also assumed that there exists a discount policy for the vehicles to be rented. This discount varies according to the number of rented vehicles and is applied on their fixed cost. By this discount policy, if the number of rented type i vehicles is less than n
i
1, the renting companies ask for the fixed cost of F
i
1. If the number of type i vehicles is greater than or equal to n
i
1, but less than n
i
2, when n
i
1
<
n
i
2, the renting companies charge a discounted value of F
i
2 as the fixed charge. Let us consider x
i
j as the number of type i vehicles for transporting the products to depot/cross dock j. Assuming there are as many as v number of discount intervals, the general formula for determining the fix cost can be written as follows: (1)Fi=0for∑j=1nxij=0,∀i=1,2,…,mFi1for∑j=1nxij<ni1,∀i=1,2,…,mFi2forni1≤∑j=1nxij<ni2,∀i=1,2,…,m⋮⋮Fivforniv≤∑j=1nxij≤Ti,∀i=1,2,…,m,where F
i
1
>
F
i
2
>
⋯
>
F
i
v.Due to existing distribution network, the distances from the manufacturing firm to depots/cross docks are fixed and are given. The objective is assigning a set of vehicles to each branch leading to depot/cross dock, to minimize the total transporting costs. The mathematical model is developed and will be presented in the following section.


## 3.2. Mathematical Model

Some parameters used in the proposed mathematical models are listed as follows:x
i
j: number of vehicles of type i allocated for transporting products to depot/cross dock j.
C
i: weight capacity of vehicle type i.
c
i
j: variable transportation costs of vehicle type i to depot/cross dock j.
T
i: total number of vehicles of type i.
W
j: total weight of products ordered by depot/cross dock j.
t
c
j
x
i
j: a step function denoting the total transportation costs of branch j (leading to depot/cross dock j) of the distribution network.
F
i: fixed cost of using vehicle type i
,
i
=
1,2
,
…
,
m.
n: total number of the depots/cross docks.
m: total number of the vehicles types.
X
0: total transportation costs.
UB: the upper bound of the objective function value.
λ
i: weighting factor of the ith constraint for defining the surrogate constraint.
UBB: the upper bound of the objective function value, obtained by the subroutine bound.
UBS: the upper bound of the objective function value, obtained by the optimal solution of the surrogate problem.
SO: a matrix for recording the imbedded state variables, in each stage of the DP solution process, of the original problem.
SR: a vector for recording the return values of the imbedded state variables, in each stage of the DP solution process, of the original problem.
SOS: a matrix for recording the imbedded state variables, in each stage of DP solution process, of the surrogate problem.
SRS: a vector for recording the return values of the imbedded state variables, in each stage of the DP solution process, of the surrogate problem.The objective function for the proposed problem can be written as(2)MinX0=∑i=1m∑j=1nFixij+∑i=1m∑j=1ncijxij,where F
i is a step function denoting the fixed part of the transportation costs and c
i
j is the variable part of the transportation costs. Let us define the total transportation costs of each depot/cross dock (branch) as follows.Then we will have(3)tcjxij=∑i=1mFixij+∑i=1mcijxij∀j=1,2,…,nMinX0=∑j=1ntcjxijS.T.∑i=1mCixij≥Wj∀j=1,2,…,n∑j=1nxij≤Ti∀i=1,2,…,mxij=0,1,2,…∀j=1,2,…,n,i=1,2,…,m.As it can be realized, the above mathematical model can be decomposed according to branches as follows:(4)MinX0=∑i=1mtc1xi1+∑i=1mtc2xi2+⋯+∑i=1mtcnxinS.T.∑i=1mCixi1≤W1∑i=1mCixi2≤W2⋮∑i=1mCixin≤Wnxi1+xi2+⋯+xin≤Ti∀i=1,2,…,mxij=0,1,2,…∀j=1,2,…,n,i=1,2,…,m.Due to the decomposed mathematical model, the dynamic programming (DP) solution approach seems to be the best candidate for solving the proposed problem. Considering this approach the recursive equations for forward computations of the DP approach can be developed as follows.LetY
j
=
y
1
j
,
y
2
j
,
…
,
y
m
j be The state variable of the jth stage indicating the vehicle type 1,2
,
…
,
m, allocated to the 1,2
,
…
,
jth depot/cross dock.f
j
Y
j
=
f
j
y
1
j
,
y
2
j
,
…
,
y
m
j is The total transportation costs of the 1,2
,
…
,
jth depot/cross dock.The recursive equations of the stages can be formulated as(5)f1Y1=f1y11,y21,…,ym1=Minx11,x21,…,xm1≤y11,y21,…,ym1∑i=1mCix1i≤W1∑i=1mtc1xi1fjYj=fjy1j,y2j,…,ymj=Minx1j,x2j,…,xmj≤y1j,y2j,…,ymj∑i=1mCixji≤Wj∑i=1mtcjxij+fj-1y1j-1,y2j-1,…,ymj-1=Minx1j,x2j,…,xmj≤y1j,y2j,…,ymj∑i=1mCixji≤Wj∑i=1mtcjxij+fj-1y1j-x1j,y2j-x2j,…,ymj-xmj∀j=2,3,…,n.The DP solution algorithm is an efficient solution approach for the cases that the dimensions of the state variables are small. Therefore the selection of the DP approach is actually based on the practical conditions of the case problem which provides some considerations for reducing the state variable dimensions. In addition practical conditions of the case problem provide some other computational aspects which enabled us to find the optimal solution for the relatively large mathematical model of the case problem. In following sections we will present the development of an exact solution algorithm for the proposed problem.


## 4. Development of the Solution Algorithm

The proposed solution algorithm is basically a DP approach. As we know the state space solution of the DP algorithm grows exponentially when solution is progressed in the consecutive stages of the solution process. This exponential growth requires the extensive enumeration efforts in each stage and hence requires unreasonable computational time. We therefore proposed several state reduction mechanisms and integrated them to the DP algorithm for developing an efficient solution algorithm. We also incorporated a powerful bounding mechanism for limiting the growth of the state space solutions in the consecutive stages of the DP algorithm. Before stating the steps of the proposed algorithm, we describe these mechanisms.


### 4.1. The State Space Reduction Mechanisms

To develop an efficient hybrid DP solution algorithm we used the concept of imbedded state solution space. By use of the imbedded state we employed a matrix for recording the state space solutions in which the state variables are enumerated only when the objective function value is varied. We also employed the surrogate constraints concept for reducing the dimension of the state space solutions of the problem. As we know the computational efficiency of the DP approach decreases as the dimensionality of the state variable increases. Therefore if we reduce the state variables dimensionality to a single dimension we can increase the efficiency of the DP solution algorithm substantially. By use of the surrogate constraint we can substitute all the constraints by a single constraint. Through this transformation we reduce the multidimensional state variables of the dynamic programming approach to a single dimension. Through the transformation of the original problem to a surrogate problem, none of the solution points of the original problem are discarded.Therefore we can solve the surrogate problem instead of the original problem and we are assured that by searching through the feasible space of the surrogate problem to obtain the optimal solution of the original problem we are considering all the solution points without losing even a single point. However the surrogated problem may contain solution points which are not feasible to the original problem. But by solving the surrogated problem we can either find the optimal solution of the original problem in case that it is feasible for the original problem or find a very close upper bound to the optimal solution of the original problem.It is very interesting to note that, by solving the surrogate constraint problem, we obtain the optimal return values for the whole range of the state variable values. By recording the return values of the state variables in a matrix, we only need to solve the surrogate problem once. At any stage of the DP solution progress we can use this matrix to obtain the updated upper bound of the optimal solution of the original problem and reduce the growth of the state variables in the succeeding stages of the DP algorithm substantially.


### 4.2. Bounding the State Space Solutions

Bounding is another attempt to reduce the computational requirements for obtaining the optimal solution. A strong upper bound can be obtained through the allocation of vehicles when we consider that there is no limited number in the vehicle’s types. Therefore we incorporated a subroutine in the solution algorithm for finding a strong upper bound in the successive stages of the solution process. The developed subroutine was written such that it can be updated throughout each stage. For initializing this subroutine, we letd
e
p
o
t
=
1. The steps of this subroutine are described as follows.Subroutine BoundStep 1.
Sort vehicles according to their capacity in decreasing order and assign indexi
=
1,2
,
…
,
m to the largest vehicle capacity up to the smallest capacity, respectively, and let i
=
1. Let Y
0
=
0.Step 2.
Letj
=
d
e
p
o
t. If W
j
<
C
i, go to Step 4. Otherwise fully load the vehicle type i. Let Y
0
=
Y
0
+
t
c
j
(
x
i
j
).Step 3.
LetW
j
=
W
j
-
C
i; go to Step 2.Step 4.
Leti
=
i
+
1. If i
=
m, load vehicle type m and Y
0
=
Y
0
+
t
c
j
(
x
i
j
); go to Step 5; otherwise go to Step 2.Step 5.
Ifj
<
n, let j
=
j
+
1; go to Step 2; otherwise let U
B
B
=
Y
0 and stop.


### 4.3. The Solution Algorithm

The solution algorithm is basically DP approach in which the surrogate constraint and bounding routines are incorporated in it for increasing its computational efficiency. To develop the surrogate problem we can either simply use the summation of the constraints or use weighted summation of the constraints. It is obvious that if we can define the proper weighting factors for obtaining the weighted summation of the constraint, we will have a much better surrogated problem with the closer upper bound value. Referring to the fleet vehicle allocation problem, the constraints which define the DP state variables of the recursive equations are those which impose the limitation on the number of vehicles. Considering the capacity of the different vehicles, we can find some proper weighting factors which smoothly balance these capacities and therefore define a single constraint much closer to the actual limitation of the different vehicle’s capacities. For example, if vehicle type 1 has the capacity of carrying 20 tons of products, vehicle 2 has the capacity of carrying 10 tons of products, and vehicle 3 has the capacity of carrying 5 tons of products, we can define the weight factors of 1, 2, and 4, which are assigned according to their capacity ratio, for these vehicles, respectively. Using these weight factors for obtaining the surrogate constraint provides a single constraint which is very closer representative of the original constraints and hence provides a solution which has a smaller duality gap for the original problem.The Steps of the Solution Algorithm
(1)
Determine the properλ
i
∀
i
=
1,2
,
…
,
m and convert the original problem to a surrogate problem, using λ
i.
(2)
Letj
=
1 and D
E
P
O
T
=
1.
(3)
Calculate the optimal solution of the surrogate problem.
(4)
If the optimal solution of the surrogate problem is feasible to the original problem, go to Step10; otherwise, let UBS be the optimal objective function value of the surrogate problem.
(5)
Record the state variables and their associated optimal objective function values, obtained by the surrogated problem, in a matrix “SOS” and vector “SRS,” respectively.
(6)
Call subroutine bound.
(7)
Construct the imbedded state and calculate its associated return values, using the recursive equations of the DP algorithm of the original problem.
(8)
For each state variable calculate the worst case scenario by adding the transportation costs of the cheapest vehicles of depots/cross docksj
+
1 to n. Also for each state variable find its associated optimal return value from SRS and assign it to UBS. Find the state variables associated with the optimal solution of surrogate problem from the imbedded state. If the state variables are feasible to the original problem, then go to Step 10; otherwise, let U
B
=
M
a
x
U
B
B
,
U
B
S. Discard those state variables at which their associated worst scenario is greater than or equal to the UB; then go to 9.
(9)
Ifj
≤
n, let j
=
j
+
1 and D
E
P
O
T
=
j; go to Step 6; otherwise go to Step 9.
(10)
Record the optimal solution and stop.


## 4.1. The State Space Reduction Mechanisms

To develop an efficient hybrid DP solution algorithm we used the concept of imbedded state solution space. By use of the imbedded state we employed a matrix for recording the state space solutions in which the state variables are enumerated only when the objective function value is varied. We also employed the surrogate constraints concept for reducing the dimension of the state space solutions of the problem. As we know the computational efficiency of the DP approach decreases as the dimensionality of the state variable increases. Therefore if we reduce the state variables dimensionality to a single dimension we can increase the efficiency of the DP solution algorithm substantially. By use of the surrogate constraint we can substitute all the constraints by a single constraint. Through this transformation we reduce the multidimensional state variables of the dynamic programming approach to a single dimension. Through the transformation of the original problem to a surrogate problem, none of the solution points of the original problem are discarded.Therefore we can solve the surrogate problem instead of the original problem and we are assured that by searching through the feasible space of the surrogate problem to obtain the optimal solution of the original problem we are considering all the solution points without losing even a single point. However the surrogated problem may contain solution points which are not feasible to the original problem. But by solving the surrogated problem we can either find the optimal solution of the original problem in case that it is feasible for the original problem or find a very close upper bound to the optimal solution of the original problem.It is very interesting to note that, by solving the surrogate constraint problem, we obtain the optimal return values for the whole range of the state variable values. By recording the return values of the state variables in a matrix, we only need to solve the surrogate problem once. At any stage of the DP solution progress we can use this matrix to obtain the updated upper bound of the optimal solution of the original problem and reduce the growth of the state variables in the succeeding stages of the DP algorithm substantially.


## 4.2. Bounding the State Space Solutions

Bounding is another attempt to reduce the computational requirements for obtaining the optimal solution. A strong upper bound can be obtained through the allocation of vehicles when we consider that there is no limited number in the vehicle’s types. Therefore we incorporated a subroutine in the solution algorithm for finding a strong upper bound in the successive stages of the solution process. The developed subroutine was written such that it can be updated throughout each stage. For initializing this subroutine, we letd
e
p
o
t
=
1. The steps of this subroutine are described as follows.Subroutine BoundStep 1.
Sort vehicles according to their capacity in decreasing order and assign indexi
=
1,2
,
…
,
m to the largest vehicle capacity up to the smallest capacity, respectively, and let i
=
1. Let Y
0
=
0.Step 2.
Letj
=
d
e
p
o
t. If W
j
<
C
i, go to Step 4. Otherwise fully load the vehicle type i. Let Y
0
=
Y
0
+
t
c
j
(
x
i
j
).Step 3.
LetW
j
=
W
j
-
C
i; go to Step 2.Step 4.
Leti
=
i
+
1. If i
=
m, load vehicle type m and Y
0
=
Y
0
+
t
c
j
(
x
i
j
); go to Step 5; otherwise go to Step 2.Step 5.
Ifj
<
n, let j
=
j
+
1; go to Step 2; otherwise let U
B
B
=
Y
0 and stop.


## 4.3. The Solution Algorithm

The solution algorithm is basically DP approach in which the surrogate constraint and bounding routines are incorporated in it for increasing its computational efficiency. To develop the surrogate problem we can either simply use the summation of the constraints or use weighted summation of the constraints. It is obvious that if we can define the proper weighting factors for obtaining the weighted summation of the constraint, we will have a much better surrogated problem with the closer upper bound value. Referring to the fleet vehicle allocation problem, the constraints which define the DP state variables of the recursive equations are those which impose the limitation on the number of vehicles. Considering the capacity of the different vehicles, we can find some proper weighting factors which smoothly balance these capacities and therefore define a single constraint much closer to the actual limitation of the different vehicle’s capacities. For example, if vehicle type 1 has the capacity of carrying 20 tons of products, vehicle 2 has the capacity of carrying 10 tons of products, and vehicle 3 has the capacity of carrying 5 tons of products, we can define the weight factors of 1, 2, and 4, which are assigned according to their capacity ratio, for these vehicles, respectively. Using these weight factors for obtaining the surrogate constraint provides a single constraint which is very closer representative of the original constraints and hence provides a solution which has a smaller duality gap for the original problem.The Steps of the Solution Algorithm
(1)
Determine the properλ
i
∀
i
=
1,2
,
…
,
m and convert the original problem to a surrogate problem, using λ
i.
(2)
Letj
=
1 and D
E
P
O
T
=
1.
(3)
Calculate the optimal solution of the surrogate problem.
(4)
If the optimal solution of the surrogate problem is feasible to the original problem, go to Step10; otherwise, let UBS be the optimal objective function value of the surrogate problem.
(5)
Record the state variables and their associated optimal objective function values, obtained by the surrogated problem, in a matrix “SOS” and vector “SRS,” respectively.
(6)
Call subroutine bound.
(7)
Construct the imbedded state and calculate its associated return values, using the recursive equations of the DP algorithm of the original problem.
(8)
For each state variable calculate the worst case scenario by adding the transportation costs of the cheapest vehicles of depots/cross docksj
+
1 to n. Also for each state variable find its associated optimal return value from SRS and assign it to UBS. Find the state variables associated with the optimal solution of surrogate problem from the imbedded state. If the state variables are feasible to the original problem, then go to Step 10; otherwise, let U
B
=
M
a
x
U
B
B
,
U
B
S. Discard those state variables at which their associated worst scenario is greater than or equal to the UB; then go to 9.
(9)
Ifj
≤
n, let j
=
j
+
1 and D
E
P
O
T
=
j; go to Step 6; otherwise go to Step 9.
(10)
Record the optimal solution and stop.


## 5. Case Problem

As we noted earlier, the motivation of the proposed problem comes from a real world case problem. In the following sections, we first describe the scope of the real world case problem. In our case problem, there are some practical aspects by which the proposed mathematical model and its solution algorithm can be adapted more straightly. We then explore these aspects and their benefits we gained for solving our case problem more efficiently.


### 5.1. Case Problem Description

SIG has several food manufacturing plants one of which is a dairy manufacturing plant, named Kalleh Co., producing a vast variety of the dairy products. Products of this manufacturing plant are distributed to its depots/cross docks and cross docks, from which they are distributed to the surrounding retail stores (2154). In SIG’s country host there are few large supermarkets; instead there are a large number of small retailers which are very similar to the western type convenience stores. Therefore distribution of products directly to the retailers is not economically justified. There are 194 depots and cross docks scattered in a vast area throughout the country with a total area of 1,600,000 square kilometers. The vehicles for this distribution system are rented from several firms outside the group. The renting costs of each vehicle are the sum of a fixed cost, depending on the vehicle type with a discount mechanism, and a variable cost depending on the traveling distance. The discount mechanism is applied according to the number of vehicles to be rented. There is a limitation on the number of the vehicles, especially on the larger sized vehicles with the refrigeration room. We found this problem as a challenging one and defined a more general form of the problem in way that may be used for similar manufacturers in the developing countries.Currently the dairy manufacturing plant of this group produces over 2300 tons/day of different dairy products and is planning to increase the production rate to 2700 tons/day. This group has another sales and distribution firm (SDF) which distributes the products of the manufacturing firm throughout the whole nation. The SDF has 85 storage facilities (depots) and 109 cross docks located in major cities of the nation, through which their products are distributed to the designated shops in the same city and to their nearby minor cities. These facilities are acting as sales branches of the SDF and each contains a sales office. As mentioned before, in this nation the majority of shops are small shops which are more similar to the convenience stores of the developed countries. Therefore the need of having these depots/cross docks is realized because their products cannot directly be shipped from the production facility to the designated shops.Although the PF produces massive commodity products, its production system works by ordering system. More specifically every week the sales office of each branch gathers the next week demands of their designated shops and passes the order to the central sales office of the SDF. The central office sums up this order and sends it to the planning department of the production company. The planning department schedules the production plans and executes them to the manufacturing plants. Based on these schedules, products are produced and sent to the storage facilities of the sales supporting department. This department then ships the products to the depots/cross docks throughout the nation.The existing transportation planning, executed by the sales supporting department, suffers from two major deficiencies. First the transportation plan is conducted based on the previous experiences rather than use of any systematic approaches. Second the planning process is conducted based on the daily available vehicles and products rather than weekly basis. Because of these deficiencies the vehicle types are not selected properly and hence they are loaded inefficiently. To demonstrate the inefficiency of the vehicle’s loading, we gathered the data of the past 12 months. Table1 illustrates the usage of the vehicles capacity. In this table the types and number of available vehicles and their nominal capacities are also demonstrated. As it is seen we have limitation on the number of available type 1 and type 2 vehicles. Practically there is no limitation on the number of vehicles of type 3 to type 6.Table 1
The capacity usage of the vehicles.
Vehicle type
Available number of vehicles
Nominal capacity (ton)
Average capacity usage (ton)
Capacity usage %
Vehicle type 1
281
20
15.120
75.6
Vehicle type 2
302
16
12.288
76.8
Vehicle type 3
—
12
9.228
76.9
Vehicle type 4
—
9
6.516
72.4
Vehicle type 5
—
7
5.607
80.1
Vehicle type 6
—
6
4.176
69.6According to the policy of this group, the weekly order is delivered through two shipments. Actually the great distance of more than 1400 kilometers between the manufacturing firm and several depots/cross docks and cross docks practically justifies this policy.Considering this policy, we therefore face the limitation in the number of vehicles of type one and type two as2
∗
281
=
562 and 2
∗
302
=
604 per week, respectively. Assuming that the products weekly order is directly sent to the sales supporting department, we now need to develop a systematic approach for the weekly transportation plan.Referring to Table1, it can be noticed that the capacity usage of the vehicles is not in a satisfactory level. The fact that there are different types of products (milk, cheese, yogurt, ice cream, etc.) with different container and packaging types (bottle, cylindrical shape plastic container, cubic papers, irregular shaped vacuum packing, etc.) and with different densities may justify some percentages of the deficiencies in the capacity usage. However there are some other unjustifiable deficiencies which are due to the improper allocation of product to the vehicle types. Since the transportation charges are according to vehicle’s type and the shipping distances, inefficient loading causes more payment for the total transportation costs. We therefore proposed a mathematical model and a solution algorithm for improving this logistic process. The mathematical programming model was developed to obtain a transportation plan for distributing products to the nationwide depots/cross docks of the sales branches. The measure of performance of this mathematical model is defined as transportation costs which we want to minimize.


### 5.2. Solution of the Case Problem

To solve the case problem, we gathered the required data and information concerning the transportation costs and order volume of the depots/cross docks. We then adjusted the order volume for the production increases by a simple linear extrapolation. For obtaining the surrogate problem we can use equal weight ofλ
i
=
1
/
m. However for obtaining a closer upper bound we need to determine the proper weight by which the surrogated constraint becomes a better representative of vehicles type. To obtain these weights we used the nominal capacities of the vehicles. The original constraints which represent the limitation of the vehicles types are as follows:(6)xi1+xi2+⋯+xin≤Ti∀i=1,2,…,m.The limitations on the number of vehicles are imposed on two types of vehicles, namely, type 1 and type 2, with the nominal capacities of 20 tons and 16 tons, respectively. Based on these nominal capacities, we determined the values for the weights as λ
1
=
3 and λ
2
=
5 for vehicles type 1 and type 2, respectively. The nominal capacities of the vehicles are based on the weight they can carry. However, because the products have different shapes and hence different densities, we modified the nominal capacity by factors shown in Table 1 to obtain a more realistic figure for the weight they can carry. The constraints representing these limitations are modified as follows:(7)x11+x12+⋯+x1,24≤562∗.756≤425x21+x22+⋯+x2,24≤604∗.768≤464.Using the solution algorithm we obtained the optimal allocation of the vehicles for delivering the weekly products order. Comparing the solution obtained through use of the proposed method with the actual costs of the previous year showed a saving of over 8.338 million dollars in one-year transportation costs.


## 5.1. Case Problem Description

SIG has several food manufacturing plants one of which is a dairy manufacturing plant, named Kalleh Co., producing a vast variety of the dairy products. Products of this manufacturing plant are distributed to its depots/cross docks and cross docks, from which they are distributed to the surrounding retail stores (2154). In SIG’s country host there are few large supermarkets; instead there are a large number of small retailers which are very similar to the western type convenience stores. Therefore distribution of products directly to the retailers is not economically justified. There are 194 depots and cross docks scattered in a vast area throughout the country with a total area of 1,600,000 square kilometers. The vehicles for this distribution system are rented from several firms outside the group. The renting costs of each vehicle are the sum of a fixed cost, depending on the vehicle type with a discount mechanism, and a variable cost depending on the traveling distance. The discount mechanism is applied according to the number of vehicles to be rented. There is a limitation on the number of the vehicles, especially on the larger sized vehicles with the refrigeration room. We found this problem as a challenging one and defined a more general form of the problem in way that may be used for similar manufacturers in the developing countries.Currently the dairy manufacturing plant of this group produces over 2300 tons/day of different dairy products and is planning to increase the production rate to 2700 tons/day. This group has another sales and distribution firm (SDF) which distributes the products of the manufacturing firm throughout the whole nation. The SDF has 85 storage facilities (depots) and 109 cross docks located in major cities of the nation, through which their products are distributed to the designated shops in the same city and to their nearby minor cities. These facilities are acting as sales branches of the SDF and each contains a sales office. As mentioned before, in this nation the majority of shops are small shops which are more similar to the convenience stores of the developed countries. Therefore the need of having these depots/cross docks is realized because their products cannot directly be shipped from the production facility to the designated shops.Although the PF produces massive commodity products, its production system works by ordering system. More specifically every week the sales office of each branch gathers the next week demands of their designated shops and passes the order to the central sales office of the SDF. The central office sums up this order and sends it to the planning department of the production company. The planning department schedules the production plans and executes them to the manufacturing plants. Based on these schedules, products are produced and sent to the storage facilities of the sales supporting department. This department then ships the products to the depots/cross docks throughout the nation.The existing transportation planning, executed by the sales supporting department, suffers from two major deficiencies. First the transportation plan is conducted based on the previous experiences rather than use of any systematic approaches. Second the planning process is conducted based on the daily available vehicles and products rather than weekly basis. Because of these deficiencies the vehicle types are not selected properly and hence they are loaded inefficiently. To demonstrate the inefficiency of the vehicle’s loading, we gathered the data of the past 12 months. Table1 illustrates the usage of the vehicles capacity. In this table the types and number of available vehicles and their nominal capacities are also demonstrated. As it is seen we have limitation on the number of available type 1 and type 2 vehicles. Practically there is no limitation on the number of vehicles of type 3 to type 6.Table 1
The capacity usage of the vehicles.
Vehicle type
Available number of vehicles
Nominal capacity (ton)
Average capacity usage (ton)
Capacity usage %
Vehicle type 1
281
20
15.120
75.6
Vehicle type 2
302
16
12.288
76.8
Vehicle type 3
—
12
9.228
76.9
Vehicle type 4
—
9
6.516
72.4
Vehicle type 5
—
7
5.607
80.1
Vehicle type 6
—
6
4.176
69.6According to the policy of this group, the weekly order is delivered through two shipments. Actually the great distance of more than 1400 kilometers between the manufacturing firm and several depots/cross docks and cross docks practically justifies this policy.Considering this policy, we therefore face the limitation in the number of vehicles of type one and type two as2
∗
281
=
562 and 2
∗
302
=
604 per week, respectively. Assuming that the products weekly order is directly sent to the sales supporting department, we now need to develop a systematic approach for the weekly transportation plan.Referring to Table1, it can be noticed that the capacity usage of the vehicles is not in a satisfactory level. The fact that there are different types of products (milk, cheese, yogurt, ice cream, etc.) with different container and packaging types (bottle, cylindrical shape plastic container, cubic papers, irregular shaped vacuum packing, etc.) and with different densities may justify some percentages of the deficiencies in the capacity usage. However there are some other unjustifiable deficiencies which are due to the improper allocation of product to the vehicle types. Since the transportation charges are according to vehicle’s type and the shipping distances, inefficient loading causes more payment for the total transportation costs. We therefore proposed a mathematical model and a solution algorithm for improving this logistic process. The mathematical programming model was developed to obtain a transportation plan for distributing products to the nationwide depots/cross docks of the sales branches. The measure of performance of this mathematical model is defined as transportation costs which we want to minimize.


## 5.2. Solution of the Case Problem

To solve the case problem, we gathered the required data and information concerning the transportation costs and order volume of the depots/cross docks. We then adjusted the order volume for the production increases by a simple linear extrapolation. For obtaining the surrogate problem we can use equal weight ofλ
i
=
1
/
m. However for obtaining a closer upper bound we need to determine the proper weight by which the surrogated constraint becomes a better representative of vehicles type. To obtain these weights we used the nominal capacities of the vehicles. The original constraints which represent the limitation of the vehicles types are as follows:(6)xi1+xi2+⋯+xin≤Ti∀i=1,2,…,m.The limitations on the number of vehicles are imposed on two types of vehicles, namely, type 1 and type 2, with the nominal capacities of 20 tons and 16 tons, respectively. Based on these nominal capacities, we determined the values for the weights as λ
1
=
3 and λ
2
=
5 for vehicles type 1 and type 2, respectively. The nominal capacities of the vehicles are based on the weight they can carry. However, because the products have different shapes and hence different densities, we modified the nominal capacity by factors shown in Table 1 to obtain a more realistic figure for the weight they can carry. The constraints representing these limitations are modified as follows:(7)x11+x12+⋯+x1,24≤562∗.756≤425x21+x22+⋯+x2,24≤604∗.768≤464.Using the solution algorithm we obtained the optimal allocation of the vehicles for delivering the weekly products order. Comparing the solution obtained through use of the proposed method with the actual costs of the previous year showed a saving of over 8.338 million dollars in one-year transportation costs.


## 6. Conclusions

In this paper we considered the heterogeneous fleet vehicle allocation problems in which the number of some vehicles types is limited. The problem is formulated as a discrete nonlinear optimization mathematical programming model. The decomposition nature of the mathematical model encouraged us to select the dynamic programming solution algorithm for solving this optimization problem. Due to the computational complexity of the mathematical program, the computational time grows exponentially as the numbers of decision variables and state variables are increasing. Therefore the proposed problem is categorized as a NP-hard problem. Due to this fact, we developed an efficient solution approach by incorporating several routines in the DP solution algorithm. We incorporated a bounding routine for finding an upper bound for the optimal solution value through relaxing the limitations on the number of vehicles types. We also employed the concept of imbedded state for limiting the enumeration of the objective function values, throughout solution stages of the DP, only on the jumps of the objective function values. We also incorporated the concept of the surrogate constraint and proposed a routine for obtaining another upper bound for the optimal objective function value of the proposed problem. Through use of these upper bounds and by updating mechanism for these bounds we tightened the growth of the state variables in the consecutive stages of the DP solution progress.We then applied the proposed mathematical model and developed solution algorithm for solving a real world case problem. The case problem presents a manufacturer producing a vast variety of dairy products with an existing distribution system consisting of 194 depots and cross docks and 6 types of vehicles for delivering its products. The required vehicles are rented from outside companies. There is a limitation on the number of some larger capacity vehicles to be rented. The transportation costs of a vehicle are the sum of its fixed cost and a variable cost incurred proportionately to the travel distance. A discount mechanism is applied to the fixed cost according to the daily number of vehicles to be rented. The discount is varied by the number of vehicles by means of a step function. The weekly demands of products are known and are determined by an order picking system a week before they must be delivered. It is anticipated to allocate the vehicles to the depots/cross docks route to minimize the total transportation costs. A mathematical programming model in the form of the discrete nonlinear optimization model was proposed for the case problem. The mathematical model was then converted to the recursive equations of a discrete dynamic programming model and solved by a developed solution algorithm. To increase the computational efficiency of the solution algorithm, several concepts and routines, such as the imbedded state routine, surrogate constraint concept, and a bounding mechanism, were incorporated in the dynamic programming solution algorithm. We employed the last 12 months of the transportation costs data for evaluating the solution of the proposed model. The results revealed that the use of the proposed model can provide a considerable saving on the transportation costs.



---

*Source: 8518921-2016-02-22.xml*