Information Technology Reference
In-Depth Information
Method 3: Repairing dock infeasibility. The solution delivered after ap-
plying the previous methods may not satisfy all dock capacity constraints.
In that case, this method attempts to repair this possible infeasibility by
making the necessary time shift adjustments. To perform this task, we de-
fine J ( h,i )=
as the set of vehicles that arrive at node i
during time index h (measured in hours). We now can determine the set of
conflict nodes, that is, those nodes where the dock capacity constraints are
violated at time h ,as Ψ ( h )=
{
k
K :
s ik / 60
}
.
The method works as follows. Starting from the lowest value of h for which
there are conflicts, we first choose one conflicting node i . Now, for this node
we must determine what is the least critical vehicle, that is, the vehicle that
possesses the largest amount of time adjustment flexibility. To do this, we
compute for each vehicle the maximum amount of time that can be added
to this vehicle without violating the future time window constraints in the
remainder of its route ( i,...,k ) as follows
{
i
V : f ih <
|
J ( h,i )
|}
Υ ( i,k )= min
u
( i,...,k ) {
b u
s uk }
.
Then the vehicle with the largest possible value of Υ ( i,k ) is chosen and
its future arrival times at every node in its remaining route are updated.
By doing this, we guarantee that no more conflicting nodes for any time
earlier than h arise, and this time adjustment may bring the current vehicle
k at node i back into feasibility. The method is depicted in Procedure 5. If
no vehicle can be found, the current iteration stops reporting an infeasible
solution.
Procedure 5. repairDocks()
1: for h =0 ,...,|H| do
2:
while ( Ψ ( h ) = ) do
3:
i ← choose one element of Ψ ( h ) arbitrarily
4:
while ( |J ( h, i ) | >f ih ) do
k arg max
k∈J ( h,i ) ( i, k ) }
6: for all ( u ∈ [ i,..., n ]) do
7: s uk = s uk +60 ( s ik 60 ·s ik / 60 )
8: end for
9: end while
10: end while
11: end for
12: return
5:
4 Empirical Results
The procedures were implemented in C# on Visual Studio 2010 environment.
All experiments were performed on an Intel Core i7 computer running the Win-
dows 7 operating system. CPLEX 12.1 was used for solving the transportation
 
Search WWH ::




Custom Search