الگوریتم های هیوریستیک برای ظرف مسائل از پیش آماده شده

A container pre-marshalling problem is to find a sequence of container movements to reach final container layout satisfying certain conditions. Two container pre-marshalling problems that are denoted as problem Type-A and Type-B are defined in this paper. Two labelling algorithms, which denote as Heuristic-A and Heuristic-B, are proposed to solve these two container pre-marshalling problems, respectively. Experiments retrieved from past literature and generated by computer program are used to verify the performance of the two algorithms. According to the output results, these proposed algorithms are able to yield a competitive solution in comparison with other methods. Computational results and model variations are discussed.

Most cargo is transported in containers through major seaports today. Thus, berthing time has become one of the most important measures for terminal performances (Imai et al., 2008 and Imai et al., 2006). Among all operations, loading and unloading containers from the containership or container-yard are critical ones which affect berthing time significantly (Kim & Bae, 1998). Because of disordered arrival of the containers or lack of accurate information from time to time, the container that is supposed to be handle earlier may be buried in the container stacks beneath other containers that would be handled later. In order to reach the correct container, the containers on its top have to be removed first. This operation is called a “re-handle.” It is a non-productive operation to dig a container out from the bottom of a stack. Hence, this container-shuffling operation results in long loading and unloading time, which incurs long berthing time. Pre-marshalling is an effective action to utilize the loading/unloading operations. It sorts containers according to certain priorities in advance so that the actual processing times of loading/unloading operations can be decreased. However, there are not many research results about optimizing the pre-marshalling process in a container yard. Kim (1997) proposed a methodology to estimate the expected number of rehandles to pick up an arbitrary container and the total number of rehandles to pick up all the containers in a bay for a given initial stacking configuration. Kim, Park, and Ryu (2000) considered the configuration of the container stack and the weight distribution of containers in the yard-bay and proposed a methodology to determine the storage location of an arriving export container. These two researches related to the container arrangement but not exactly the container pre-marshalling problem. Besides, Kim and Kim (1997) discussed how to route transfer crane during loading operation of export containers in port container terminal. The objective is to minimize the total container handling time of the transfer crane including the set-up time at each yard-bay and the travel time between consecutive yard-bays. They also proposed an algorithm to determine the working route of a transfer crane for a similar loading operation later on Kim and Kim (1999). The most relevant research to our topic is Lee and Hsu (2007), which deals with the container pre-marshalling optimization. They model the problem as an integer programming which was a multi-commodity network flow problem embedded within. The optimization goal is to minimize the number of container movements during pre-marshalling. In addition, Lee and Chao (2009) proposed another method – neighborhood search process – to solve the per-marshalling problem. The heuristic takes a neighborhood search approach by starting from a feasible solution and improving the solution through iterations. Our research is basically an extension of Lee’s research. Two different pre-marshalling problems are described and two simple heuristic algorithms are provided to solve the problems. The remainder of this paper is organized as follows. Section 2 states the definition and assumptions to identify the two types of pre-marshalling problems. The heuristics are described in Section 3 and the experiments are provided in Section 4. Section 5 discusses the analysis and a brief conclusion is presented.

Yard operation is one of the most important factors of measuring the efficiency of a container terminal system. Container pre-marshalling is an essential action to deal with container rehandles. The container pre-marshalling problem is to figure out an efficient sequence of container movements that results in a desirable final layout. This paper defined two different situations for container pre-marshalling problems, which are labelled as problem Type-A and Type-B. Accordingly, two heuristic algorithms are proposed to solve these two problems. These two algorithms use basically labelling process to decide next move step by step until the containers reach a desirable layout. Algorithm Heuristic-A is tested on the experiments retrieved from the literature and the output results suggest that Heuristic-A is able to provide better performance than other methods using very short running time. On the other hand, algorithm Heuristic-B is tested on the experiments generated from computer program and the output results indicate that the method is capable of providing near-optimal solution in very short running time. The results indicate that the buffer ratio can affect the solution quality significantly especially when the buffer ratio is getting small. This model may be extended in some directions. For example, the containers in the yard are assumed to be in the same dimensions in current problem. However, it is possible to have containers with different dimensions mixed in one yard. This case is realistic and complicates the pre-marshalling problem. Moreover, these two problems can be combined as a multiple-ship loading problem. Containers for one specific ship are piled up in one zone with which each container has its loading priority.