Information Technology Reference
In-Depth Information
reduce the overall processing time. A
solution
to the container move allocation prob-
lem is a set of machines, each with a schedule of container moves. Taken collectively,
the moves proposed must correctly unload the ship
4
while respecting the various con-
straints. The overall goal is to reduce the ship turnaround time, and thus the overall
quality of a solution is given by its cost: how much time is taken? This is simply the
completion time of the last machine to complete (i.e. the maximum of the finishing time
over the machines).
The process for deriving a solution has two phases: initial allocation and optimisa-
tion, following the Tabu search meta-heuristic [9]. In the initial allocation phase each
container is considered in turn and is put up for “auction”, with each (relevant
5
) machine
bidding. The container is allocated to the cheapest bidding machine, and is inserted into
its schedule at the end of its schedule. In doing the initial allocation we need to ensure
that each container is unloaded from the ship before it is scheduled to be moved to
the yard. This is done by tracking the time at which a container reaches the apron (its
“minTime”) and ensuring that the Straddle Carrier does not move the container earlier
than its minTime.
The second phase, optimisation, attempts to improve the initial solution by repeat-
edly modifying it. The modifications considered involve selecting a container and con-
sidering (a) moving it to a different position in its machine's schedule; or (b) moving it
to a different machine. The possible reallocations are evaluated based on (an approxi-
mation) of the cost difference, and the cheapest one is chosen and applied to the current
solution, in order to obtain a new solution. In proposing and applying container move
reallocations, we need to ensure that we do not reallocate a container move in a way
that violates the “unload before move” constraint. We also need to ensure that we do
not propose to deal with containers in a non-viable sequence (e.g. unloading C1 before
C2 if C1 is below C2 in the ship).
The process described (briefly) above is performed before machines begin perform-
ing moves, and develops a complete scheduled plan for unloading a ship. A strength of
the approach is that should something go wrong, the schedule can be updated to reflect
necessary changes, and the allocation process re-run in order to deal with the change.
For example, should a Straddle Carrier break down, the solution is updated by removing
the Straddle Carrier in question, and putting its allocated container moves back into the
list of moves to be allocated. The allocation process is then re-run, using the existing
solution as a starting point, to allocate these container moves to other Straddle Carriers.
In order to support this style of usage the solution includes not just a set of machines
(with their associated schedules), but also a list of unallocated container moves, and the
“current time”. The latter is used during the process of container move allocation and
optimisation to ensure that container moves which have already been done (i.e. are in
the past) do not get changed.
We have implemented this negotiation-based approach for container management.
The
(OpenTS
6
).
implementation
makes
use
of
a
Tabu
Search
framework
The
4
We have focused on unloading only in our work so far.
5
A machine is relevant to a container move if it is able to perform that type of move. For
example, a Quay Crane is relevant to a move which involves the apron and a ship.
6
http://www.coin-or.org/Ots
