Diploma and Master Theses (authored and supervised):
"Heuristic solution approaches for the two dimensional pre-marshalling problem.";
Supervisor: G. Raidl, A. Rendl;
Institut für Computergrafik und Algorithmen,
Today´s shipping industry heavily relies on intermodal containers for quick and easy cargo manipulation. Container terminals are used as temporary storage for containers between two forms of transportation where containers are stacked into container stacks and those stacks are then ordered next to each other to form a container bay. To achieve high efficiency, all containers in a container bay have to be preordered in such a way that at pickup time all containers belonging to the current shipment are directly accessible by cranes.
A problem of reshuffling a container bay to achieve a layout where each container is accessible by a gantry crane at pickup time, using a minimal number of container relocations, is called the Pre-Marshalling Problem(PMP). A gantry crane can reach any container that is located on top of a stack. This work considers a new extension of the classical PMP in which we assume that the containers will be picked up by a reach stacker. A container is accessible by a so-called reach stacker if it is located on top of the left- or right-most stack of a container bay. This implies additional constraints that are discussed in this master thesis. We call our extension the Two Dimensional Pre-Marshalling Problem(2D-PMP).
We solve the 2D-PMP with two main approaches. First, we adapt a PMP strategic heuristic, the Least Priority First Heuristic(LPFH). Since the pickup order is predefined, we assign priority values to all containers (the ones with lowest priority value are picked up first). LPFH selects the container with the greatest priority value and positions it so that it can remain in its new position in the final container bay layout. For each container move, an origin and destination stack are chosen according to predefined rules. After that, intermediate moves are made to free up the selected container and destination slot allowing the selected container to be moved. Second, we use a metaheuristic, the Max-Min Ant System(MMAS). MMAS requires the problem to be represented as a path construction problem. Our initial container bay layout corresponds to the initial node and each move is an edge and each subsequent layout is a new node. The path length reflects the number of moves. Furthermore, we investigate simpler greedy and randomized construction heuristics, a PILOT method, and a local search procedure.
All algorithms are experimentally evaluated on benchmark instances. MMAS and 2D-LPFH are able to solve almost all instances. Among instances that both algorithms solved, results show that MMAS clearly outperforms 2D-LPFH as MMAS´s solutions usually require less move-
pre-marshalling problem, reach stacker, PILOT method, ant colony optimization, max-min ant system, least priority first heuristic, container terminal
Electronic version of the publication:
Created from the Publication Database of the Vienna University of Technology.