Information Technology Reference
In-Depth Information
Each optimiser when called is given an ordered list of expected container moves (either
from yard to ship or, as initially implemented, from ship to yard), and the current yard
state, and must answer with a list of the optimal storage locations within the yard for
each container.
Our initial module uses an Evolutionary Algorithm [10]. Given a sequence of ex-
pected container moves and a representation of the current yard state, an Evolutionary
Algorithm (EA) is used to attempt to optimise the location for each container placement
within the yard. Straddle Carriers, such as used within the yard we modelled, can only
place or remove the uppermost container in a stack. Any time a Straddle Carrier needs
to move a container that is part-way down in a stack, it must first remove all the over-
stowed containers to a free location in the yard, and this is obviously expensive. This
implies that the order of operations is important; containers should be loaded in a stack
in the opposite order to which they will be removed. We therefore hypothesised that the
sequence of container moves should be explicitly addressed by each component of the
EA, and so our EA consists of an ordered genome representation, a fitness function that
simulates the sequence of moves when assessing costs, and custom order-preserving
crossover and mutation operators.
Genome Representation: The genome is made up of a sequence of (container id,
yard location) genes, where each gene represents a move of a particular container to
a [lane,bay,tier] location within the yard. Order is significant because the sequence in
which containers are placed onto a stack determines the rehandle costs when they are
extracted for loading onto a vessel. Containers usually appear more than once in the
genome, to capture moves into and out of the yard; any additional entries for a given
container signal potentially costly rehandles, or moves within the yard.
Fitness Function: The fitness of each entity is calculated by simulating the sequence
of moves encoded in the genome to a simplified representation of the container termi-
nal. Each move between yard and ship has a cost equal to the 'Manhattan' distance
of the move. Any genome that encodes an invalid sequence of moves is given a high
penalty cost. Invalid sequences include ones where a required move is missing from the
genome, or falls out of sequence, or a move involves an overstowed container. A binary
tournament is used to select a sample of the best (lowest cost) genomes for the next
generation.
Mutation Operator: Mutation acts only on the location encoded within a specified
proportion of genes in the genome; mutation does not affect the order of container
moves. A random set of genes is selected, and each gene in the set gets its location
adjusted to a random free location in the yard.
Crossover Operator: The order of genes in the genome is significant, so the crossover
operator developed attempts to preserve the order of genes from each parent in the new
child genome. It does this by identifying locations unique to the second parent, and then
switching those for the locations of a random proportion of genes in the first parent, so
leaving the order of moves untouched. This can result in invalid genomes, e.g., where
the crossover results in a container to be in mid-air. Such invalid genomes are repaired
by dropping mid-air containers down the stack to a supported position.
Search WWH ::




Custom Search