Information Technology Reference
In-Depth Information
4.1 Rolling Horizon Planning Framework
Figure 1 illustratively shows the rolling horizon planning framework. The entire
time horizon is divided into a series of planning periods. All planning periods
have the same length
τ
. We use index
p
to denote the planning periods,
p
=
0
,
1
,
2
,...,
. At the beginning time point
t
0
= 0, an initial plan
Π
1
for the first
planning horizon including
H
following planning periods, i.e., planning periods
p
=1
,
2
,...,H
, is constructed. The plan for the first planning period is fixed.
The plan for the next planning periods
p
=2
,...,H
, however, will be actualized
in the forthcoming plans as a result of the dynamically released new requests
during the execution of planned routes. After that, at the end of each planning
period
p−
1, i.e., at the planning time
t
p−
1
=(
p−
1)
τ
,
p
=2
,
3
,...,∞
, a new plan
Π
p
for the next planning horizon ranging from planning periods
p
to
p
+
H −
1
will be made based on the updated status. Again, the partial plan constructed
for planning period
p
will be fixed while the rest part will be kept as changeable.
Figure 1 shows the case when
H
is set to 3.
∞
planning time
a planning horizon
t
2
afixed
planning period
a planning period
t
1
a changeable
planning period
t
0
time
t
0
t
1
t
2
t
3
t
4
t
5
Fig. 1.
Framework of rolling horizon planning
, each vehicle can be assigned some
new customer requests after they have finished all the requests that have been
planned fixed in its route in the previous planning periods. In case that a vehicle
has already finished serving all assigned requests, it waits at the location of the
last customer until new orders are assigned.
Let
R
p,a
i
At each planning time
t
p
,
p
=0
,
1
,
2
,...,
∞
denote the set of all active requests of carrier
i
at the planning time
t
p−
1
=(
p
. An active request at a specific time point is a
released yet not executed request that has not been fixed planned in previous
planning periods. The requests in
R
p,
i
can be further differentiated into two
subsets according to their urgency. The most urgent requests are labeled as
due
requests
that must be fixed planned for the next planning period
p
, while the
remaining part of requests are called
non-due requests
that will be planned in
the afterwards planning periods
p
+1to
p
+
H
−
1)
τ
,
p
=1
,
2
,...,
∞
i
and
R
p,
i
to
denote the sets of due requests and non-due requests, respectively, and we have
1. We use
R
p,d
−
