# Flow Merging and Hub Route Optimization in Collaborative Transportation

Authors: Kerui Weng; Zi-hao Xu
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

This paper studies the optimal hub routing problem of merged tasks in
collaborative transportation. This problem allows all carriers’ transportation tasks to reach the destinations optionally passing through 0, 1, or 2 hubs within limited distance, while a cost discount on arcs in the hub route could be acquired after paying fixed charges. The problem arises in the application of logistics, postal services, airline transportation, and so forth. We formulate the problem as a mixed-integer programming model, and provide two heuristic approaches, respectively, based on Lagrangian relaxation and Benders decomposition. Computational experiments show that the algorithms work well.


---

## Body

## 1. Introduction

With the rapid growth of manufacturing industry and E-commerce in recent years, logistics industry is constantly expanding. However, many carriers still show small scale and low load ratio in developing countries such as China. At the same time, a number of consignors choose multibatchless-than-truck-loads instead of single-batch full-truck-loads in order to adapt to flexible production plans, which increases logistics costs. One promising way of improvement is a new transportation model called collaborative transportation (CT), which integrates all transportation demands and transportation resources to achieve economies of scale. For example, if transport tasks shown in Figure 1 dealt with a CT program as shown in Figure 2, then routing costs could be reduced by combing several transportation flows on a few arcs. A transportation task from node i to j is called O-D flow i
→
j. The route passing through no more than 2 hubs, such as i
→
k
→
m
→
j, is called hub route. An arc (
k
,
m
) is called hub arc if it carries enough O-D flows and produces a freight cost discount on the arc due to economies of scale, which is the most favourable feature of CT. However, two unfavourable characteristics exist in CT. First, O-D flows may increase touring distance. For instance, the distance of route A–B–E–D is obviously longer than the direct distance of route A–D. Second, to achieve discount, we have to pay a fixed charge to build hub arc, such as building railroad instead of highroad or buying heavy trucks to replace light-vans. Therefore, hub route with merging flows obtains discount on hub arc at the expense of additional transportation range and fixed charge. This encourages us to seek the optimal hub route of merging flows to maximize the profit of CT.Figure 1
Transportation task I.Figure 2
Collaborative transportation.Flow merging and hub routing problem of collaborative transportation exists in many practices. For example, flight courses between small cities can be integrated into hub arcs of big cities, such as hub routesmall city—big city—big city—small city. In road line between two Chinese cities Guangzhou and Hong Kong, a logistics company may quote 2700 yuan, 3000 yuan, 3400 yuan, and 3600 yuan for full-truck-loads of 3 tons, 5 tons, 10 tons, and 12 tons, respectively, and the expenses per ton are 900 yuan, 600 yuan, 340 yuan, and 300 yuan. Petroleum exploitation companies in north China considered whether and where to build a railway to convey merging materials and reduce costs. The above applications indicate that larger vehicles loading larger flows generate cheaper transport costs. In other applications of CT where high response speed is required, we need to consider the distance constraints. For example, in express delivery business, customers require that the total transportation time of O-D flow is less than the promised hour such as 24-hour delivery or 48-hour delivery. But in order to save transportation costs, most O-D flows have to give up the direct paths and select longer hub routes. How to generate the saving-and-fasttransportation plan with distance constraints? To reach this, we research flow merging and hub route problem in collaborative transportation (FMRICT) which finds the optimal hub route of merged flows within limited detouring distance, while hub arc can cut cost from discount if paid a fixed charge.At present study of CT, the optimized route can be categorized into fleet’s route and flow’s hub route. Literatures about multidepot arc routing problem (MDARP) and multidepot pickup and delivery problem (MDPDP) are researches on fleet’s route. A fleet finished a taski
→
j in MDARP if its tour starting and ending a depot directly passed arc (
i
,
j
). But to finish a task i
→
j in MDPDP, fleet needs to find a minimal cost tour while node i is before but not necessary last to node j, which means picking up freight at i and delivering it at j. Obviously, MDPDP can achieve a lower cost than MDARP as shown in Figures 3, 4, and 5. However, MDPDP is more complex and extremely harder to solve large scale instances than MDARP. Most researches on MDPDP are tested on instances with single depot. Reference [1] tries to solve MDARP with 200 tasks by particle swarm optimization but does not provide the benchmark of computational time and solution quality. To the best of our knowledge there are no other efficient approaches with benchmark to large scale MDPDP, while MDARP with more than 1000 tasks can be solved with good benchmark in [2–4]. As shown in Figure 6, a promising innovation is the two-stage CT program which takes full advantage of scale effect and decreases the complexity. The first stage merges the flows, and the second stage obtains the fleet’s tour by solving a MDARP which already has good heuristics. Accordingly, it is an important step to find the optimal hub route of merging flow.Figure 3
Transportation task II.Figure 4
MDARP.Figure 5
MDPDP.Figure 6
Two-stage CT program.Current studies on O-D flow’s hub route of CT focus on the hub-and-spoke network design problem (HASNDP). Assuming that all arcs between hubs have transportation discount and requiring that all the O-D flows have to pass one or two hubs, HASNDP seeks the best selecting of hub and arranges the right hub routes of O-D flows to minimize the total cost. HASNDP was initially proposed by O’Kelly (1988) who built a quadratic programming model and provided two types of heuristic algorithms. In recent years, many studies are devoted to improve the model and the solution [5–8], while some scholars concentrate on the extension problem of HASNDP [9–16]. HASNDP and hub location problem have gained much attention. However, there still exist two defects. Firstly, requiring all the O-D flows passing hubs may cause lots of detouring. For instance, in the conclusion of Weng [7], Xi’an was chosen as hub in Chinese airline Lhasa → Xi’ning according to the result of HASNDP, which is obviously not right due to over detouring. Secondly, current researches of HASNDP emphasize on nodes’ cost while neglect arcs’ cost and the demand of incremental flows. HASNDP assumes that all arcs between hubs can automatically obtain economies of scale as long as hub costs are paid and O-D flows pass one or two hubs, which conflicts some practice. For example, tasks shown in Figure 7 will be designed as hub-and-spoke network shown in Figure 8. Nodes H, I, and J are chosen as hubs and all arcs between them enjoy discount of transportation costs. However, as we can see from Figure 8, no incremental flows pass through arc (
H
,
I
) and it should not be given the transportation discount. In fact, the economies of scale for hub arcs need other two conditions including the incremental flows and the fixed charge to build more economic transport facilities. Researches [17–20] also find that some hub arcs do not have quantity strength after paying the hub costs while they still require tasks passing hubs and neglect the detouring distance limitation, which are distinguished from our work.Figure 7
Transportation task III.Figure 8
HASNDP.This paper is organized as follows. In Section2, we formulate the mixed-integer programming model for FMRICT. Sections 3 and 4 provide two heuristic approaches, respectively, based on Lagrangian relaxation and Benders decomposition. Section 5 shows test performance of the algorithms.


## 2. Formulation

Consider a connected networkG
(
N
,
A
), where A is the set of edges and N
=
{
1,2
,
…
,
n
} is the set of nodes. For all i
≠
j, let h
i
j denote the O-D flow from i to j. D
i
j is the limited detouring distance of flow i
→
j. c
k
m is the unit flow cost of arc (
k
,
m
), and f
k
m is the fixed cost when arc (
k
,
m
) is selected as a hub arc. a
(
0
<
a
<
1
) denotes the transportation cost discount of hub arcs. Binary decision variable Y
k
m
=
1 if arc (
k
,
m
) is selected as a hub arc and 0 otherwise. X
i
j
k
m is the quantity of flow i
→
j on non-hub-arc (
k
,
m
). W
i
j
k
m is the quantity of flow i
→
j on hub arc (
k
,
m
). Binary variable Z
i
j
k
m
=
1 if flow i
→
j chooses route i
→
k
→
m
→
j and 0 otherwise. FMRICT model could be formulated as (
P
1
),
(1)
(
P
1
)
min
⁡
⁡
∑
i
‍
∑
j
‍
∑
k
‍
∑
m
‍
(
X
i
j
k
m
c
k
m
+
a
W
i
j
k
m
c
k
m
)
+
∑
k
‍
∑
m
‍
f
k
m
Y
k
m
,
(2)
S.T.
∑
k
∉
i
,
j
‍
∑
m
∉
i
,
j
‍
(
X
i
j
k
m
+
W
i
j
k
m
)
+
X
i
j
i
j
+
W
i
j
i
j
=
h
i
j
hhhhh
∀
i
,
j
∈
N
;
i
≠
j
,
(3)
∑
m
∉
i
,
j
(
X
i
j
k
m
+
W
i
j
k
m
)
=
X
i
j
i
k
+
W
i
j
i
k
∀
i
,
j
,
k
∈
N
;
i
≠
j
;
k
∉
i
,
j
,
(4)
∑
m
∉
i
,
j
‍
(
X
i
j
k
m
+
W
i
j
k
m
=
X
i
j
m
j
+
W
i
j
m
j
)
∀
i
,
j
,
m
∈
N
;
i
≠
j
;
m
∉
i
,
j
,
(5)
h
h
h
w
i
j
k
m
≤
Y
k
m
h
i
j
∀
i
,
j
,
k
,
m
∈
N
;
i
≠
j
;
k
≠
j
;
m
≠
i
,
(6)
Z
i
j
i
k
c
i
k
+
Z
i
j
k
m
c
k
m
+
Z
i
j
m
j
c
m
j
-
D
i
j
≤
0
hh
∀
i
≠
j
;
k
≠
j
;
m
≠
i
,
(7)
hh
X
i
j
k
m
+
W
i
j
k
m
=
Z
i
j
k
m
h
i
j
∀
i
,
j
,
k
,
m
∈
N
;
i
≤
j
;
k
≤
j
;
m
≤
i
,
(8)
h
h
W
i
j
k
m
,
X
i
j
k
m
≥
0
;
Z
i
j
k
m
,
Y
i
j
=
0,1
∀
i
,
j
,
k
,
m
∈
N
,
k
≤
j
;
m
≤
i
.In (P1), objective function (1) accounts for the minimization of total routing costs plus fixed costs. Constraint (2) requires all tasks be finished. Constraint (3) and constraint (4) ensure the flow balance. If flow i
→
j goes through the hub k
(
k
∉
{
i
,
j
}
), then the flow going in k must equal the flow going out of k. Constraint (5) restricts W
i
j
k
m to be 0 if arc (
k
,
m
) is not selected as hub arc. k
≠
j and m
≠
i in constraints (5) and (6) are to avoid roundabout transportation. For instance, route i
→
j
→
i
→
j and route i
→
j
→
k
→
j are not acceptable. Constraint (6) controls the route distance, and constraint (7) is to define Z
i
j
k
m.Compared to HASNDP which neglects detouring distance, (P1) makes tasks choose detour routes instead of direct routes if only they are more saving and control the distance by constraint (6). (P1) also helps the incremental flows of hub arcs by importing fixed charge as shown in Lemma 1. Define Z
k
m
=
∑
i
‍
∑
j
‍
(
X
i
j
k
m
+
W
i
j
k
m
) as the total flow on arc (
k
,
m
).Lemma 1.
In optimal solution of FMRICT, if(
k
,
m
) is selected as a hub arc, then Z
k
m
≥
f
k
m
/
(
1
-
a
)
c
k
m.Proof.
WhenY
k
m
=
1, we can decrease the transportation costs of (
1
-
a
)
Z
k
m
c
k
m but increase fixed charge of f
k
m. For every selected hub arc (
k
,
m
), it is optimal only if (
1
-
a
)
Z
k
m
c
k
m
≥
f
k
m; otherwise we can decrease costs by set Y
k
m
=
0 and it is a contradiction to optimal solution. Therefore, the optimal flow on hub arc must satisfy Z
k
m
≥
f
k
m
/
(
1
-
a
)
c
k
m.


## 3. Heuristic Algorithm Based on Lagrange Relaxation

(
P
1
) is a complicated mixed-integer programming model that possesses about 3
n
4
+
n
2 variables and 5
n
4
+
2
n
3
+
n
2 constraints. The decision variables and constraints would be more than 50 thousands only if 10 nodes are included. FMRICT can be proven NP hard since it is an extension of fixed charge multicommodity network flow problem. Therefore, heuristic is needed for large scaled FMRICT. This section proposes a heuristic procedure based on Lagrange relaxation. The procedure uses the idea of relaxing parts of constraints by bringing them into the objective function with associated vector λ called the Lagrange multiplier and builds relaxed problem called Lagrangian dual problem which is relatively easily solved. A lower bound can be obtained from the solution of the Lagrangian dual problem, and an upper bound was found by refining the solution to a feasible solution of the original problem. The heuristic iteratively reduces the gap between upper bound and lower bound by updating the Lagrange multiplier. The main algorithm elements include the way of building relaxed problem called Lagrange dual problem, the way of constructing feasible solution, and the way of updating Lagrangian multipliers.If we relax constraint (5) in (
P
1
) and define λ
i
j
k
m as the Lagrangian multiplier of corresponding constraint, then the Lagrange dual problem (
P
2
) can be obtained as follows:
(9)
(
P
2
)
min
⁡
∑
i
‍
∑
j
‍
∑
k
‍
∑
m
‍
X
i
j
k
m
c
k
m
+
∑
i
‍
∑
j
‍
∑
k
‍
∑
m
‍
W
i
j
k
m
(
α
c
k
m
+
λ
i
j
k
m
)
+
∑
k
‍
∑
m
Y
k
m
(
f
k
m
-
∑
i
‍
∑
j
‍
λ
i
j
k
m
h
i
j
)
S
.
T
.
Constraints
(
2
)
–
(
4
)
,
(
6
)
–
(
8
)
.Givenλ
i
j
k
m, we can easily minimize the objective of (P2). For fixed costs, if f
k
m
-
∑
i
‍
∑
j
‍
λ
i
j
k
m
h
i
j
<
0, then Y
k
m
=
1, and 0 otherwise. For transportation costs, O-D flow will select the shortest hub route. Let isarc
i
j
k
m
=
1 if flow i
→
j going through hub arc (
k
,
m
), and isarc
i
j
k
m
=
0 otherwise. Let l
k be the objective of (P2). The approaching procedure can be constructed as Algorithm 2.The first step is to calculate the cost of arc(
k
,
m
) for flow i
→
j. The second step is to find the optimal hub route i
→
k
*
→
m
*
→
j that satisfies distance constraints and to determine W
k
m
i
j. The last step is to find hub arcs. l
k is the optimal solution of (P2) and also becomes the lower bound of (P1). In this heuristic, we will augment lower bound to approach optimal value by subgradient optimization.Algorithm 2 (solving the relaxed problem).
(
1
) For ∀
i
,
j
,
k
,
m that satisfy i
≠
j, k
≠
j and m
≠
i, let C
i
j
k
m
=
min
⁡
(
c
k
m
,
α
c
k
m
+
λ
i
j
k
m
), and
(10)
isarc
i
j
k
m
=
{
1
if
C
i
j
k
m
=
α
c
k
m
+
λ
i
j
k
m
0
else;
l
k
=
0, W
i
j
k
m
=
0.
(
2
) For ∀
i
≠
j: find (
k
*
,
m
*
)
=
arg
min
⁡
{
C
i
j
i
k
+
C
i
j
k
m
+
C
i
j
m
j
∣
c
i
k
+
c
k
m
+
c
m
j
≤
D
i
j
,
k
≠
j
,
m
≠
i
}; let l
k
=
l
k
+
C
i
j
i
k
*
+
C
i
j
k
*
m
*
+
C
i
j
m
*
j; if isarc
i
j
i
k
*
=
1,  then W
i
j
i
k
*
=
h
i
j; if isarc
i
j
k
*
m
*
=
1,   then W
i
j
k
*
m
*
=
h
i
j; if isarc
i
j
m
*
j
=
1,   then W
i
j
m
*
j
=
h
i
j.
(
3
) For ∀
k
≠
m, if f
k
m
-
∑
i
‍
∑
j
‍
λ
i
j
k
m
h
i
j
<
0, then Y
k
m
=
1, l
k
=
l
k
+
f
k
m
-
∑
i
‍
∑
j
‍
λ
i
j
k
m
h
i
j, else Y
k
m
=
0.Algorithm 3 (construct feasible solution).
(
1
)    u
k
=
0, W
^
i
j
k
m
=
0, X
^
i
j
k
m
=
0, F
^
i
j
k
m
=
0.
(
2
) For ∀
k
≠
m, let Y
^
k
m
=
Y
k
m while Y
k
m is the result of step (
3
) of Algorithm 2. If Y
^
k
m
=
1, then u
k
=
u
k
+
f
k
m.
(
3
) For ∀
i
,
j
,
k
,
m having k
≠
j, m
≠
i, let
(11)
C
i
j
k
m
=
{
a
c
k
m
if
Y
^
k
m
=
1
c
k
m
else.
(
4
) For ∀
i
≠
j, find (
k
*
,
m
*
)
=
argmin
{
C
i
j
i
k
+
C
i
j
k
m
+
C
i
j
m
j
∣
c
i
k
+
c
k
m
+
c
m
j
≤
D
i
j
,
k
≠
j
,
m
≠
i
}; let F
i
j
i
k
*
=
h
i
j, F
i
j
k
*
m
*
=
h
i
j, F
i
j
m
*
j
=
h
i
j, u
k
=
u
k
+
C
i
j
i
k
+
C
i
j
k
m
+
C
i
j
m
j.However, the optimal solution of(
P
2
) may not be feasible to FMRICT by violating constraint (5) such as W
i
j
k
m
>
Y
k
m
h
i
j. Consequently, solution of (
P
2
) will be adapted to feasible solution of the original problem. Let X
^
i
j
k
m, W
^
i
j
k
m, and Y
^
k
m be the feasible solution of X
i
j
k
m, W
i
j
k
m, and Y
k
m, respectively. Let F
i
j
k
m denote the quantity of flow i
→
j going through arc (
k
,
m
). The definition means that W
^
i
j
k
m
=
F
i
j
k
m and X
^
i
j
k
m
=
0 if (
k
,
m
) is hub arc; else W
^
i
j
k
m
=
0 and X
^
i
j
k
m
=
F
i
j
k
m. Let u
k be the objective value of feasible solution. Algorithm 3 is the procedure of obtaining feasible solution. After initialization in the first step, the second step is to determine the hub arc and to count fixed costs. The third step is to calculate the transportation costs of tasks in all arcs, and the last step is to make O-D flow select the shortest hub route.For given Lagrangian multiplierλ
i
j
k
m, both upper bound u
k and lower bound l
k could be obtained from Algorithms 2 and 3. Updating Lagrangian multiplier is to adjust the value of λ
i
j
k
m so that the upper bound and the lower bound would be more and more closer to the optimal value. Subgradient algorithm is such a method to update λ
i
j
k
m.Letl
t be the step length of iteration t and be computed as
(12)
l
t
=
α
t
(
UB
-
l
k
)
∑
i
∑
j
∑
k
∑
m
(
Y
k
m
h
i
j
-
W
i
j
k
m
)
2
.In (12), α
t is the step length parameter at iteration t, and α
1 is usually initialized by 2. Let UB be the current best upper bound and let Y
k
m and W
i
j
k
m be solutions of the relaxed problem at current iteration. Lagrangian multiplier is updated as formula (13) to heighten the lower bound,
(13)
λ
i
j
k
m
=
max
⁡
{
0
,
λ
i
j
k
m
-
l
t
(
Y
k
m
h
i
j
-
W
i
j
k
m
)
}
.The main program of Lagrangian relaxation algorithm for solving FMRICT is as follows.Algorithm 4 (Lagrangian relaxation algorithm for solving FMRICT).
(
1
) Initialize the parameters. Let t
=
1, λ
i
j
k
m
=
c
k
m, α
t
=
2, and UB
=
∞. Set the current optimal lower bound LB
=
-
∞.
(
2
) Solve Lagrangian relaxation problem with Algorithm 2 to get W
i
j
k
m, Y
i
j
k, and l
k. Update LB
=
max
⁡
(
LB
,
l
k
).
(
3
) According to Algorithm 3, acquire the feasible solution Y
^
i
j
k and F
i
j
k
m and compute objective function (1) to get u
k. Update UB
=
max
⁡
(
UB
,
u
k
).
(
4
) Update step length parameter α
k. If LB is not improved within 65 steps, then let α
k
+
1
=
α
k
/
2.
(
5
) Update Lagrangian multiplier according to (12) and (13).
(
6
) Determine if it has reached the termination criterion. End algorithm if any one of the following three criterions is established to be true: (
1
)  UB
-
LB
≤
0.1, (
2
)  l
t
≤
0.0001, and (
3
)  t
=
1000.
(
7
) Update iteration numbers t
=
t
+
1 and return to step (
2
).


## 4. Heuristic Algorithm Based on Benders Decomposition

This section approaches FMRICT with another method based on Benders decomposition to compare performance with Algorithm4. By fixing some variables of the original problem, Benders decomposition partitions the original problem into master problem and subproblem which are easy to solve. Solve the subproblem to produce the upper bound and increase Benders’ cut to the master problem based on the solution of dual variable of the subproblem, and then solve the master problem to acquire the lower bound. The algorithm will iteratively reduce the gap between upper bound and lower bound.For model(
P
1
), fix all Y
k
m to Y
¯
k
m at the iteration t; then the subproblem is shown as in (
P
3
),
(14)
(
P
3
)
min
⁡
∑
i
,
j
,
k
,
m
‍
X
i
j
k
m
c
k
m
+
∑
i
,
j
,
k
,
m
‍
a
W
i
j
k
m
c
k
m
+
∑
k
,
m
‍
f
k
m
Y
¯
k
m
,
(15)
S.T.
-
w
i
j
k
m
⩾
-
Y
¯
k
m
h
i
j
∀
i
≠
j
;
k
≠
j
;
m
≠
i
,
(16)
Constraints
(
2
)
–
(
4
)
,
(
6
)
–
(
8
)
W
i
j
k
m
,
X
i
j
k
m
,
Z
i
j
k
m
⩾
0
∀
k
≠
j
;
m
≠
i
.(
P
3
) is easy to solve, and we only need to make all O-D flows select the minimum cost hub route within distance limitations. Let U
i
j
k
m
t and v
i
j
t be the dual variables of constraints (15) and (2) of (
P
3
) at the iteration t.Feasible solution ofU
i
j
k
m
t and v
i
j
t could be obtained according to duality theory, as shown in (17),
(17)
V
i
j
t
=
min
⁡
∀
k
≠
j
,
m
≠
i
(
R
i
k
+
R
k
m
+
R
m
j
d
i
j
k
m
≤
D
i
j
)
,
U
i
j
k
m
t
=
{
max
⁡
[
0
,
V
i
j
-
min
⁡
m
(
a
d
i
k
+
R
k
m
+
R
m
j
∣
d
i
j
k
m
≤
D
i
j
)
]
if
k
=
i
max
⁡
[
0
,
V
i
j
-
min
⁡
k
(
R
i
k
+
R
k
m
+
a
d
m
j
∣
d
i
j
k
m
≤
D
i
j
)
]
if
m
=
j
max
⁡
[
0
,
V
i
j
-
R
i
k
-
R
m
j
-
a
d
m
k
∣
d
i
j
k
m
≤
D
i
j
]
if
k
≠
i
,
m
≠
j
0
otherwise.
In (17),
(18)
R
k
m
=
{
a
d
k
m
if
Y
^
k
m
=
1
d
k
m
if
Y
^
k
m
=
0
,
d
i
j
k
m
=
d
i
k
+
d
k
m
+
d
m
j. The economic meaning of V
i
j
t is the incremental costs for adding one unit flow i
→
j. And U
i
j
k
m
t denotes the cutting route costs for unit flow i
→
j when (
k
,
m
) is selected as hub arc.Benders’ cut at iterationt is β
t
(
Y
)
=
∑
i
,
j
‍
V
i
j
t
+
∑
i
,
j
,
k
,
m
‍
(
f
k
m
-
U
i
j
k
m
t
)
Y
k
m. And the master problem at iteration k can be designed as model (
P
4
),
(19)
(
P
4
)
min
⁡
z
(20)
s
.
t
.
z
≥
∑
i
,
j
‍
V
i
j
t
+
∑
i
,
j
,
k
,
m
‍
(
f
k
m
-
U
i
j
k
m
t
)
Y
k
m
hhhh
∀
t
∈
1,2
,
…
,
T
,
(21)
Y
k
m
=
0,1
;
z
>
0
.In the iterative process, Benders decomposition gradually increases Benders’ cut by constraints (20), rather than considering all constraints at once, so that the algorithm efficiency is improved. Solving the master problem (
P
4
) gives us the updated variables {
Y
¯
k
m
} to try out for the next iteration, while solving the subproblem of (
P
3
) provides us new trying schemes. Let l
k, u
k be the objective value of (
P
4
) and (
P
3
) at iteration t. And let LB, UB be the current best lower bound and upper bound. The procedure is designed as in Algorithm 5.Algorithm 5 (Benders decomposition method for solving FMRICT).
(
1
) Initialize parameters, UB
=
∞, LB
=
-
∞, and t
=
1. Initialize hub arcs, and let Y
¯
k
m
=
0 for ∀
(
k
,
m
), which means that no hub arcs are selected at iteration 1. Initialize constraints in model (
P
4
) by setting constraint (20) to be empty at first.
(
2
) Calculate the dual variables of model (
P
3
) according to (17). Compute u
k
=
∑
i
j
‍
V
i
j
t
+
∑
k
‍
∑
m
‍
∑
i
‍
∑
j
‍
(
f
-
k
m
-
U
i
j
k
m
t
)
Y
¯
k
m. If u
k
<
UB, then UB
=
u
k.
(
3
) Add Benders cut constraint z
≥
∑
i
j
‍
V
i
j
t
+
∑
k
‍
∑
m
‍
∑
i
‍
∑
j
‍
(
f
-
k
m
-
U
i
j
k
m
t
)
Y
k
m to model (
P
4
) and solve (
P
4
) to get the lower bound l
k. If l
k
>
LB, then LB
=
l
k. If there is no solution to (
P
4
), then the original problem is unsolvable and the algorithm is terminated.
(
4
) Determine if it has reached the termination criterions. End algorithm if any one of the following two criterions is true: (
1
)   UB
-
l
b
≤
0.01, (
2
)   t
=
20.
(
5
) Update {
Y
¯
k
m
} according to the solution of model (
P
4
). Update t
=
t
+
1 and return to step two.


## 5. Computational Experiments

We code the algorithms in c♯ based on the VS2008 and run them on ThinkPad x60 notebook computer which is equipped with 2.1 GHZ Core2 CPU. In the procedure of Algorithm 5, we call Gurobi to solve model (
P
3
). The test instances are from AP data package that can be downloaded from http://people.brunel.ac.uk/mastjjb and includes postal flow data and distances data of 200 cities in Australia. With data about h
i
j, c
i
j, and so forth, AP data package has become a very famous algorithm testing platform for hub-and-spoke network design, while still lacking data about f
k
m and D
i
j. In our experiments, we let f
k
m
=
2
h
k
m
c
k
m
(
1
-
a
) so that flow quantity of hub arcs is at least twice as much as directed flow quantity according to Lemma 1. Let D
i
j
=
1.2
d
i
j, which means that the length of hub route is no more than 20 percent of the directed route. Moreover, the first 10, 15, 20, 25, and 30 nodes were taken as instances in the AP data package, and the discount number a is set by 0
.
6, 0.7, or 0.8. At first, we apply Gurobi’s B
r
a
n
c
h & C
u
t algorithm to obtain the exact solution of test cases, as shown in Table 1. We find that decision variables and constraints in the mixed-integer programming model (
P
1
) would exceed 1510 thousands when n
≥
25, which is too large to solve by B
r
a
n
c
h & C
u
t algorithm on Gurobi. Then all the cases are tested with Algorithms 4 and 5. The result is shown in Table 2, in which the gap between upper bound and lower bound is defined by gap
⁡
=
100
(
UB
-
LB
)
/
LB.Table 1
Problem parameters of AP data package and computational result ofBranch & Cut algorithm.
Problem parameters
Branch & Cut algorithm
Problem
a
n
Number of transportation tasks
Optimal solution
Time (s)
AP10-6
0.6
10
90
251524
2.55
AP15-6
0.6
15
210
337655
62.59
AP20-6
0.6
20
380
1214739
255.85
AP25-6
0.6
25
600
—
—
AP30-6
0.6
30
870
—
—
AP10-7
0.7
10
90
281348
2.43
AP15-7
0.7
15
210
379664
24.82
AP20-7
0.7
20
380
1384638
86.78
AP25-7
0.7
25
600
—
—
AP30-7
0.7
30
870
—
—
AP10-8
0.8
10
90
311134
1.05
AP15-8
0.8
15
210
421537
5.27
AP20-8
0.8
20
380
1553251
21.62
AP25-8
0.8
25
600
—
—
AP30-8
0.8
30
870
—
—Table 2
Computational result of Algorithms4 and 5 for AP data package.
Instance
Algorithm4
Algorithm5
UB
LB
Gap
Time (s)
UB
LB
Gap
Time (s)
AP10-6
254741
251370
1.34
2.45
251524
250711
0.32
3.26
AP15-6
343625
334800
2.63
12.50
338031
334540
1.03
16.19
AP20-6
1243835
1197288
3.88
51.21
1221368
1204513
1.38
53.80
AP25-6
1588608
1487350
6.80
40.17
1557496
1522760
2.23
185.26
AP30-6
2607031
2457319
6.09
15.49
2581828
2477115
4.05
283.75
AP10-7
281812
278790
1.08
2.18
281348
280792
0.20
3.51
AP15-7
384132
377457
1.76
15.21
380079
377841
0.58
15.78
AP20-7
1412754
1370593
3.07
50.01
1390699
1375812
1.07
53.28
AP25-7
1795345
1720306
4.36
20.91
1767833
1745691
1.25
128.3
AP30-7
2950418
2830074
4.25
15.1
2926752
2847984
2.69
292.95
AP10-8
311723
311068
0.21
2.30
311128
310799
0.11
3.32
AP15-8
425198
420009
1.23
13.4
422749
420408
0.55
17.28
AP20-8
1574894
1548196
1.72
17.08
1556208
1545625
0.68
52.4
AP25-8
1998599
1959522
1.99
7.3
1980503
1965095
0.77
132.11
AP30-8
3274275
3219604
1.69
14.01
3267612
3213814
1.64
283.20The experiment indicates that Algorithms4 and 5, compared to Branch & Cut algorithm on Gurobi, are much more time-saving and capable of solving large scaled instances with more than 25 nodes. Upper bounds obtained from Algorithm 5 have already reached the optimal solution in most instances. For all tested instances, maximum gaps obtained from Algorithms 4 and 5 are 6.8% and 4.05
%, averagely 2.86
% and 1.24
%, respectively. It is clear that both Benders decomposition method and Lagrangian relaxation algorithm possess pretty good performances on solving FMRICT problems.As shown in Table2, for small scaled instances with less than 15 nodes, Benders decomposition method could give the gap between upper bound and lower bound that is no more than 2.7
% within 16 seconds, while Lagrangian relaxation algorithm no more than 1.03
% within 63 seconds. For larger scaled problems with more than 20 nodes, Benders decomposition method gives the gap that is no more than 6.9
% within 52 seconds, while Lagrangian relaxation algorithm no more than 4.05
% within 293 seconds. It implies that Algorithm 4 solves FMRICT problem faster, while Algorithm 5 gives better solutions.


## 6. Conclusion

The current collaborative transportation researches mainly consider the nodes cost of hubs, while ignore detouring cost, hub arcs cost, or incremental flows. FMRICT seeks a way of cutting down detouring route and building infrastructure or conveyances for hub arc and at the same time satisfies the demand of incremental flows by charge costs of building hub arc according to Lemma1. All of them are very important in practice and are foundations of achieving economies of scale in collaborative transportation. We build a mixed-integer programming model of FMRICT and then construct Lagrangian relaxation algorithm and Benders decomposition method to solve FMRICT. The experiments indicate that both algorithms have pretty good computational performance. However, FMRICT considers only one discount rate. In many cases, flow quantity and transportation cost show a piecewise linear relationship, so that different scales of flow quantity and transportation tools produce different discount rates. Therefore, collaborative transportation routing problem with piecewise linear relationship between flow quantity and transportation costs is prospective for the next research.



---

*Source: 621487-2014-03-04.xml*