Container Ship Stowage Unloading Sequence

Container Ship Stowage Unloading Sequence: Multiple Criteria Decision Making. Alex Goussiatiner, P. Eng., M. Sc., Senior Container Terminal and Transportation Specialist, Sandwell Engineering Inc., Vancouver, Canada

An effective ship unloading plan is a crucial element in the successful operation of any marine container terminal. Depending on the current situation at the terminal, the ship planners prioritize all container categories to be unloaded and the computer system instantly provides the unloading sequence for the crane operators. In an ideal unloading sequence, all first priority containers go out first, followed by second priority containers, etc. In reality, an ideal sequence is not always achievable. Containers are randomly stowed in the bays and often in order to retrieve containers with the higher priority it is necessary to retrieve containers with lower priority first. The planning model developed in this paper is based on multiple criteria with lexicographic ordering for sequence evaluation and effective informed search procedure. This model can easily be applied to a variety of inventory tasks related to stowage/stack unloading and in general to any multistep process evaluated by such multiple criteria.

Key words: Sequencing, optimization, multiple criteria, container ship unloading

Introduction Container ships are loaded and unloaded by section (bays) as shown in Fig 1. Ship planners are required to plan the sequence of bays for operations as well as the unloading and loading plans for each bay. The planning model described in this paper makes unloading sequences for bays. Each container in a bay can belong to only one allocation category and each allocation category has a priority level with 1 being the highest, followed by 2, etc. These priorities are identified by a planner depending upon additional information such as train schedules, the yard situation, etc. at the time of unloading. . In reality, an ideal sequence is not always achievable. Containers are randomly stowed in the bays and often in order to retrieve containers with the higher priority it is necessary to retrieve containers with lower priority first. (Figure 1: the category is in the lower right comer of each cell, the sequence number is denoted in each upper left corner). Therefore the planner attempts to make a sequence so as to approximate the ideal.

Figure 1. Unloading Sequence

For now our intention is to describe verbally the optimal sequence in such a way as to allow us the construction of a formal planning model. An optimal sequence should entail the minimum moves necessary to unload the first container of first priority, the minimum moves necessary to unload the next container of first priority, etc. This is the main planning objective, but there are always a number of variants which will achieve this objective. Which sequence is the best? To answer this question, we should obviously take into account containers of second priority, then third priority and so on. Therefore, when defining the optimal sequence, the following conditions are to be taken into account: • • • • •

What are the minimum moves necessary to discharge the first container of first priority? What are the minimum moves necessary to discharge the second container of the first priority? What are the minimum moves necessary to discharge the first container of the second priority? What are the minimum moves necessary to discharge the second container of the second priority? etc.

These conditions are ranked in order of importance; each condition is overwhelmingly more important than all others following.

Multiple Criteria

Definition 1. Unloading Sequence. Vector s = (c1 ,..., ci ,..., cm ) is the unloading sequence ( s ∈ S ) , where:

ci - column number chosen in step i ; m -number of units in the sequence. If m is less than the number of units in the bay n then the sequence is incomplete, otherwise it is complete. First let us compare sequences one pair at a time. For any pair, say s1 and s 2 , one and only one of the following can occur: s1
s2 : s1 is preferred to s2 ;

s1 ≺ s2 : s1 is less preferred than s2 ; s1 ∼ s2 : s1 and s2 are of equal preference; s1 ? s2 : preference between s1 and s2 is unknown Definition 2. Multiple Criteria. Assume that each unloading sequences s is evaluated according to the next multiple criteria vector: Y = (( y11 ,..., ym1 1 ),...,( y1p ,..., y jp ,..., ymp p ),...)

Where y jp - sequential number on s for the j -th container with priority p if the unit has been determined in s otherwise y jp equal #.

m p - number of units with priority p . Definition 3. Preference as operator. Let us consider that the k -th component of Y = ( y1 ,..., yk ,..., yn ) is overwhelmingly more important then the (k + 1) -th component for k ∈ {1,..., n − 1} . (This approach is called lexicographic ordering [1] .)

Assume then that: Y ( s1 ) = ( y1 ( s1 ),... yn ( s1 )) is a vector for s1 and Y ( s2 ) = ( y1 ( s2 ),... yn ( s2 )) is a vector for s2 . A preference as operator can be defined as following:

•

s1
s2 iff ("if and only if") y1 ( s1 ) < y1 ( s2 ) or there is some k ∈ {2,..., n − 1} , so that yk ( s1 ) < yk ( s2 ) and yq ( s1 ) = yq ( s2 ) for q ∈ {1,..., k − 1}

•

s1 ≺ s2 iff y1 ( s1 ) > y1 ( s2 ) or there is some k ∈ {2,..., n} , so that yk ( s1 ) > yk ( s2 ) and yq ( s1 ) = yq ( s2 ) for q ∈ {1,..., k − 1}

•

s1 ∼ s2 iff yq ( s1 ) = yq ( s2 ) for q ∈ {1,..., n − 1} and both s1 and s1 are complete.

•

s1 ? s2 otherwise

Example 1. Let us compare four sequences for the unloading bay in Fig. 2 (the first two sequences are complete, the last two are incomplete) and present multiple criteria for each of them in Fig 3. If we compare the evaluation vectors, we can define preference relations between all of them as shown in Fig. 4.

Figure 2. Bay Stowage

1

2

3

1

2

3

1

1

1

3

Figure 3. Multiple Criteria

s2 = (1,1, 2, 2, 2,3,3) ’vertical from left to right’ (1, 2, 4,7)

s3 = (1,1)

s4 = (1,1, 2,3,3)

y1

s1 = (1, 2,3,1, 2,3, 2) ’horizontal from left to right’ (1, 4,5, 6)

(1, 2, #, #)

(1, 2,5, #)

y2

(2)

(3)

(#)

(3)

y3

(3,7)

(5, 6)

(#, #)

(4, #)

Y

(1, 4,5, 6, 2,3,7)

(1, 2, 4,7,3,5, 6)

(1, 2, #, #, #, #, #)

(1, 2,5, #,3, 4, #)

Figure 4. Preference as operator

s1

s2

s3

s4

s1

∼

≺

≺

s2




s3




∼ ?

≺ ?

s4




≺

∼ ?


? ∼

Definition 4. Preference as a subset. Preference based on




is a subset of S ⊗ S , denoted by P{
}

, so that whenever ( s1 , s2 ) ∈ P{
} , s1
s2 Preference based on ? is a subset of S ⊗ S , denoted by P{?} , so that whenever ( s1 , s2 ) ∈ P{?}, s1 ? s2

Definition 5. Transitive Preference. P{
} is transitive: ( s1 , s2 ) ∈ P{
} and ( s2 , s3 ) ∈ P{
} implies that ( s1 , s3 ) ∈ P{
} , for every ( s1 , s2 , s3 ) ∈ S

Remark 1. As you can see from Example 1, P{
} is transitive, but P{?} is not. For example ( s2 , s3 ) ∈ P{?} and ( s3 , s4 ) ∈ P{?} but ( s2 , s4 ) ∉ P{?}

Definition 6. As discussed before, an ideal sequence occurs when every container goes out according to its priority level. So the ideal sequence for the bay with n containers would be the one which has multiple criteria: Y = (1, 2,3,..., n) .

Obviously this sequence is preferred to any other sequence but it can rarely be realized. For example, it cannot be realized for the bay on Fig. 2 because some first priority containers are covered from above by second and third priority containers.

Definition 7. Goal Sequence. Complete sequence s* ∈ S is a goal sequence iff there is no si ∈ S so that

si
s*

Remark 2. This definition certainly does not prohibit that case where there are a number of equal goal sequences.

Lemma 1. If f is an incomplete sequence and yq ( f ) is determined, then for any complete sequence s developed from f : yq ( s ) = yq ( f ) .

Proof. Simply by definition of multiple criteria (Def. 3), if any member of Y has already been set for the incomplete sequence it will stay unchanged for the complete sequence. Remark 2. If y1 ( f ), y2 ( f ),..., yk ( f ) - first k members for Y ( f ) are determined, then for any complete sequence s developed from f : yq ( s ) = yq ( f ) for q ∈ {1,..., k} Theorem 1. If f1 and f 2 are two incomplete sequences and f1
f 2 , then for any complete sequences s1 and s2 developed from f1 and f 2 respectively s1
s2 Proof. By Def. 3: If f1
f 2 then: (1) y1 ( f1 ) < y1 ( f 2 ) . According to Lemma 1 : y1 ( s1 ) = y1 ( f1 )

y1 ( s1 ) = y1 ( f 2 ) We have thus established: y1 ( s1 ) < y1 ( s2 ) This immediately yields by Def. 3: s1
s2 (2) There is some k ∈ {2,..., r} so that:

•

yq ( f1 ) and yq ( f 2 ) are determined for q ∈ {1,..., k}

•

yq ( f1 ) < yq ( f 2 )

•

yq ( f1 ) = yq ( f 2 ) for q ∈ {1,..., k − 1}

According to Remark 2: yq ( s1 ) = yq ( f1 ) and yq ( s2 ) = yq ( f 2 ) for q ∈ {1,..., k − 1} We have thus established: yk ( s1 ) < yk ( s2 )

yk ( s1 ) = yk ( s2 ) for q ∈ {1,..., k − 1} This immediately yields by Def. 3:

s1
s2

Definition 11 Leader member. Let us call the very first undetermined member of the multiple criteria the leader and denote it with a question mark.

Theorem 2. Let us assume that f is an incomplete sequence with m members and the k -th member of Y ( f ) is a leader member. Then any complete sequence s1 which has the k -th member determined by step m + 1 ( yk ( s ) = m + 1 ) is preferred to any complete sequence s2 developed from f which has the k -th member determined by the later step yk ( s ) > m + 1 . Proof. According to Remark 2: yq ( s1 ) = yq ( f ) for q ∈ {1,..., k − 1} and yq ( s2 ) = yq ( f ) for q ∈ {1,..., k − 1} Thus:

yq ( s1 ) = yq ( s2 ) for q ∈ {1,..., k − 1} As we assumed:

yk ( s1 ) = m + 1; and yk ( s2 ) > m + 1;

Thus we established: yk ( s1 ) < yk ( s2 ) . And finally by Def. 3: s1
s2 .

Remark 6. These theorems are not true exclusively for the evaluation of unloading sequences. In general, they can be used for any multi-step process evaluated by multiple criteria with lexicographic ordering (Def . 3).

Fast Track Search Theorems 1 and 2 allow creation of the effective informed tree search heuristic, which allows finding of the goal sequence s * . Search Tree • An arc presents a fragment of unloading sequence which is being applied to the ancestor node. • A node presents evaluation criteria for that part of the unloading sequence which has been determined in a path from the root node to the node in question. Each node also contains a description for those containers remaining in the bay. This description we will call state. • A terminal node is a node where the sequence is complete (all members of the evaluation criteria have been determined), • A goal node is a terminal node whose corresponding sequence is preferred to that of any other terminal node on the tree.

Control Strategy The strategy which defines the rules for raising the search tree and finding the goal node can be presented as seen in Procedure 1.

Procedure 1. Search on tree begin Create a search tree, G , consisting solely of the node Root Y ( Root ) ::= (#, #,..., #) Put Root on list called Open Barrier ::= Root while Open is not empty do n ::= first member from Open Remove n from Open

if n
Barrier or n ? Barrier then if n can be accumulated then Create node n * Install n * on G else n* ::= n end Barrier ::= n * if n * is not a terminal node then Expand node n * , generating, the set M of its successors and install them as successors of n * in G . while M is not empty do m ::= first member from M Remove m from M if m
Barrier or m ? Barrier then Barrier ::= m Put m on Open end loop end end loop Define Goal as a sequence obtained by tracing a path from Root to Barrier in G . end

There is a set of rules which is used in the procedure to prevent the creation of unnecessary nodes:

•

In every step of the search procedure the barrier node is determined. This node presents a temporary lower level limit for the search because it is preferred to or has unknown preference relations with any other node that has been created thus far. So before we create a new node or expand an existing one, we compare it with the barrier. If the node is not preferred to the barrier, then according to Theorem 1 we can put it aside as it is not a prospect.

•

Before we expand any prospective node, we analyze the state for this node and determine if it is possible to find a container which will immediately define the leader member. As we demonstrated in Theorem 2, all other continuations would be less preferred and can therefore be ignored. We create a new node which accumulates all such containers and then expand this node.

•

When we expand a node, we determine the leader member in the multiple criteria and then search all state columns in order to fill up the leader member. When a

column with such a container is found, we include the container in the sequence and determine the multiple 9 criteria for the prospective node. Finally, we compare the node with the barrier and decide whether to put it into the Open list or to put it aside.

Example 4. In Fig. 5, we presented a search tree for the bay in Figire 2. As you can see, the multiple criteria for the root node (1) contains only undetermined members, and the bay description is the original. When the search procedure creates new nodes, the multiple criteria become more determined, and the number of containers in the bay diminishes. Finally, you can see the goal node (7).

Figure 5

Conclusion With respect to container ship unloading, this approach allows us to provide unloading sequences similar to those manually prepared by ship planners. The search procedure is quite efficient, so ship planners can specify priority and instantly see the results. In general, this search procedure can be used for any multi-step plans that can be evaluated by multiple criteria with lexicographic ordering.

References 1. P. L. Yu (1989) Multiple Criteria Decision Making: Five Basic Concepts, In Optimization 1993 (G. L. Nemhauser, A. H. G. Rinnooy Kan, M. J. Todd Eds.), vol. I, pp.663-699. NHC, North-Holland.