185
Chapter 9
Multi-Load and
Heterogeneous
Vehicle Scheduling:
Hybrid Solutions
When capacity of the vehicles is one container, the problem is a minimum cost ow
model. is model was solved by the highest performance algorithm in Chapter5
through Chapter 8, that is, network simplex algorithm (NSA) and its extensions. If
the capacity of the vehicles increases, the problem is an Non Polynomial (NP) hard
problem. is problem has a huge search space and must be tackled by some heuristic
algorithms. In this chapter, the problem is tackled by the simulated annealing method
(SAM). ree approaches for its initial solution and a neighborhood function to the
search method are implemented. A hybrid of SAM and NSA also is made and applied
to the heterogeneous vehicle scheduling problem in container terminals. Several same
random problems are generated, solved by the hybrid with the proposed approaches,
and the simulation results are compared. e experimental results show that NSA pro-
vides a good initial solution for SAM when the capacity of vehicles is heterogeneous.
9.1 Motivation
In the past few decades, much research has been devoted to technology of auto-
mated guided vehicle (AGV) systems, both in hardware and software (see Qiu and
Hsu 2000a, 2000b, 2001; Qiu et al. 2002). Nowadays, they have been become
popular over the world for automatic material-handling and exible manufacturing
186 ◾ Vehicle Scheduling in Port Automation
systems. ese unmanned vehicles are also increasingly becoming common mode of
container transport in the seaport. In this chapter, we consider a highly automated
seaport container terminal, which consists of a berthing area (quay side), an AGV
area, and a storage area (yard side). Figure9.1 illustrates the layout of one of the
latest seaport container terminals. e berthing area is equipped with quay cranes
for the loading and unloading of vessels. e storage area is divided into blocks,
each of which is serviced by one or more stacking cranes. e transportation of the
containers from the berthing area to the storage area is realized by AGVs, which
can carry up to two 20ft containers or alternatively one 40ft or 45ft container at
a time. In the container terminal considered, AGVs are operated in single-carrier
mode, but shall be used as multi-load carriers in the future.
9.2 Assumptions and Formulation
In this section, the multi-load and heterogeneous AGVs scheduling problem in the
container terminals is dened and formulated.
9.2.1 Assumptions
e major assumptions used here are the same as the assumptions presented in
Chapter 4. In that chapter, we assumed that the AGVs are homogenous with unit
capacity, but here we assume that they are heterogeneous. In formal, we substitute
Assumption 4.5 in Chapter 4 with the following:
Assumption 4.5:
We are given a eet of V={1, 2, …, |V|} vehicles. e vehicles are heterogeneous
and every vehicle transports a few containers. At the start of the process, the vehi-
cles are assumed to be empty.
Storage area
AGV area
Berthing area
Figure 9.1 Layout of a seaport container terminal. (Data from Grunow, M. et al.,
OR Spectrum, 26, 211–235, 2004.)
Multi-Load and Heterogeneous Vehicle Scheduling ◾ 187
9.2.2 Formulation
Assumption 4.5 converts the problem dened in Chapter 4 into an NP-hard problem.
e formulation in the chapter was a minimum cost ow model, whereas the problem
and its formulation, here, are in somewhat dierent. e problem, here, is formulated
as constraint satisfaction and optimization.
A directed graph or network is considered for this transportation system.
Given n for the number of jobs, let node i and node n+i represent the pickup
and delivery location of the ith job in the network, respectively. In this network,
dierent nodes obviously may represent the same physical location in the yard
or berth. By adding node 0 and node 2n+1, as the depot, to the network, the
node set becomes N={0, 1, 2, …, n, n+1, n+2, …, 2n, 2n+1}. e pickup
and delivery points are, respectively, included into two sets P
+
={1, 2, …, n} and
P
−
={n+1, n+2, …2n}. Obviously, P=P
+
U P
−
is the set of nodes other than
the depot node.
e following parameters are known:
AT
j
is the appointment time of the jth job.
TS
vo
is the times at which the vehicle v leaves the depot.
q
v
is the capacity of vehicle v.
TT
ij
is the travel time from the physical location of node i, L
i
, to physical loca-
tion of node j, L
j
(for each pair of i and j in N).
9.2.3 Decision Variable
X
ijv
: is variable indicates the movement of vehicle v from node i to node j. In fact,
this variable is one if vehicle v moves from node i to node j; otherwise, it is zero.
So,its domain is {0, 1}.
9.2.4 Constraints and Objective Function
e constraints and objective function of the problem are formulated in
Equations 9.1 through 9.6. In the formulation, we make a couple auxiliary vari-
ables. e rst one, Y
vi
, is the load of vehicle v when it leaves node i. At the start
of the process Y
v0
=0.
is variable is determined by Equation 9.1. e rst
statement in the equation represents the load of a vehicle when it leaves the rst
pickup point after the depot. e second statement has a similar meaning but
for when each vehicle goes to any pickup or drop-o point after the rst pickup.
If a vehicle goes to any pickup (drop-o) point, its load is increased (decreased)
by one. e second auxiliary variable, TS
vi
, is the time at which the vehicle v
starts service at node i (TS
v0
=0). is variable is determined by the equations
set (9.2).
188 ◾ Vehicle Scheduling in Port Automation
(a) If X
0 jv
=
1
( )
⇒
Y
vj
=
1;v
∈
V, j
∈
P
+
,
( b) If X
ijv
= 1
( )
⇒
Y
vj
= Y
vi
+ 1;v ∈V , j ∈P
+
, i ∈P, i ≠ j
Y
vj
= Y
vi
− 1;v ∈V , j ∈P
−
, i ∈P, i ≠ j
⎧
⎨
⎪
⎩
⎪
⎫
⎬
⎪
⎭
⎪
(9.1)
(a) If X
0 jv
= 1
( )
⇒ TS
vj
= TS
v0
+ TT
L0,Lj
; j ∈P
+
, v ∈V,
(b) If X
ijv
= 1
( )
⇒ TS
vj
= TS
vi
+ TT
Li,Lj
;i, j ∈P, v ∈V
(c) If X
i
2
n+
1
( )
v
= 1
( )
⇒ TS
v
2
n+
1
( )
= TS
vi
+ TT
Li
,
L
2
n+
1
( )
;i ∈P
−
,v ∈V
(9.2)
(a) X
ijv
= 1, i ∈P
+
j∈N
∑
v∈V
∑
( b) X
ijv
− X
jiv
j∈N
∑
= 1, i ∈P, v ∈V
j∈N
∑
( c) X
ijv
− X
j n+i
( )
v
j∈N
∑
= 1, i ∈P
+
, v ∈V
j∈N
∑
(9.3)
(a) X
0 jv
= 1, v ∈V
j∈P
+
∑
( b) X
i 2n+1
( )
= 1, v ∈V
i∈P
−
∑
(9.4)
Y
vi
≤
q
v
,v
∈
V, i
∈
P
(9.5)
Minimum costs =
w
1
X
ijv
⋅ TT
ij
j∈P, j≠i
∑
i∈P
∑
+
w
2
AT
i
− TS
vi
+
i∈P
∑
+ w
3
TS
vi
− AT
i
+
i∈P
∑
⎛
⎝
⎜
⎞
⎠
⎟
jobs on the quay side
∑
⎧
⎨
⎪
⎪
⎪
⎩
⎪
⎪
⎪
⎫
⎬
⎪
⎪
⎪
⎭
⎪
⎪
⎪
v∈V
∑
(9.6)
e rst statement in Equation 9.2 represents leaving the depot, where the vehicles
follow by a pickup point. e second statement in the equation shows that the
vehicles can go to any pickup or delivery point after the rst pickup. e last state-
ment in the equation represents going the depot, where the vehicles have a delivery
before that. To calculate the starting service time at each node, the service time of
the current node and the traveling time between the previous and current nodes
have to be considered.
Multi-Load and Heterogeneous Vehicle Scheduling ◾ 189
Equation 9.3 shows the constraints set on pickup and delivery points of the
vehicles. e rst constraint in the equation ensures that each pickup point is vis-
ited once by one of the vehicles. e second constraint in the equation indicates
that if a vehicle enters a node, it will exit the node. e third constraint in the equa-
tion ensures that if a vehicle visits a pickup node, then it has to visit the associated
delivery node.
Equation 9.4 shows the constraint set on the rst and last visit points of the vehi-
cles. e rst constraint in the equation ensures that the rst visit of every vehicle
is a pickup node. e second constraint in the equation ensures that the last visit of
the vehicles is a delivery node. Equation 9.5 shows the constraint on the capacity of
the vehicles. e load of vehicle v when it leaves node i must not exceed the capac-
ity of the vehicle. Equation 9.6 presents the objective function of the problem. e
rst term in the equation is the sum of traveling time of the vehicles. e second
and third terms in the equation are the cost of waiting of vehicles and the cost of
lateness time to serve the jobs, respectively. ese two terms have impacts on the
objective function provided that they are only positive. Note that w
1
, w
2
, and w
3
are
the weights of those three terms in the objective function.
9.3 Solutions to the Problem
In this section, a couple of solutions for the problem are presented: (a) SAM for
multi-load AGVs and (b) a hybrid of NSA and SAM for heterogeneous capacity of
AGVs. ese solutions are applied to the problems for the rst time.
9.3.1 SAM for the Multi-Load AGVs
e problem has a huge search space and must be tackled by one of the meta-
heuristic search methods. Although, meta-heuristics usually also require relatively
long computation times in order to provide good-quality solutions, in some real-
world applications meta-heuristics such as Tabu search and SAM might prove to
be a good choice of method. is is due to the fact that these methods for the most
part will be able to nd a feasible solution within few seconds (see Qiu et al. 2002;
Rashidi 2010; Rashidi and Tsang 2005).
More research eort were observed recently on the SAM to improve their run-
ning times (see Chiang and Russel 1996; Cave et al. 2002; Czech and Czarnas
2002; Galati, Geng, and Wu 1998; Rashidi 2010). is method could have signi-
cant impact on the speed up and the performance of the solutions. We therefore
restrict ourselves to SAM in this research.
SAM is analogous to the physical annealing process of obtaining a solid mate-
rial in its ground state. A pseudocode for the SAM is demonstrated in Figure9.2.
For a description of the steps in this method and more details on parameters refer
to Czech and Czarnas (2002) and Galati, Geng, and Wu (1998).
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.