Heuristic solution approaches for the two dimensional pre-marshalling problem

Abstract

Ein wesentliches Element der modernen Frachtindustrie ist der 20-Fuß-Container. Beim Wechsel des Transportmittels, beispielsweise von Bahn auf Schiff, werden diese in Container Terminals in Stapeln zwischengelagert. Solche Stapel werden nebeneinander angeordnet und bilden eine Container Bay. Um höchste Effizienz zu erreichen, müssen alle Container einer Bay so angeordnet sein, dass der Kran jeweils alle Container, die zu einer Lieferung gehören, zum Verladezeitpunkt direkt erreichen kann. Das Problem der Neuanordnung einer Container Bay sodass jeder Container für einen Brück-enkran zugänglich wird, wobei die Minimalanzahl an Containerbewegungen vorgenommen werden soll, ist als Pre-Marshalling Problem (PMP) bekannt. Ein Brückenkran kann einen Container erreichen, wenn dieser oben auf seinem Stapel liegt. In der vorliegenden Arbeit wird eine neue Erweiterung des PMP vorgestellt, für das die Benutzung eines Greifstaplers angenommen wird. Ein Greifstapler erreicht nur Container, die oben auf dem Stapel am äußersten rechten oder linken Rand der Container Bay liegen. Daraus ergeben sich zusätzliche Einschränkungen, die in dieser Arbeit erörtert werden. Wir nennen unsere Erweiterung das Zweidimensionale Pre-Marshalling Problem (2D-PMP). Zwei Ansätze werden zur Lösung des 2D-PMP herangezogen. Erstens wird eine strategische PMP-Heuristik angepasst, die Least Priority First Heuristic (LPFH). Da die Abholreihenfolge vordefiniert ist, können allen Containern Prioritätswerte zugewiesen werden (diejenigen mit der geringsten Priorität werden zuerst abgeholt). LPFH wählt den Container mit dem höchsten Prioritätswert und positioniert ihn so, dass er an dieser Position bleiben kann. Für jede Containerbewegung wird ein Herkunfts- und ein Zielstapel nach vorher festgelegten Regeln ausgewählt. Danach werden die nötigen Containerbewegungen durchgeführt, die den Container und dessen Zielposition erreichbar machen, sodass der Container schließlich bewegt werden kann. Zweitens verwenden wir eine Metaheuristik, das Max-Min Ant System (MMAS). Dieses erfordert, dass das Problem als Pfadkonstruktionsproblem repräsentiert wird. Hier entspricht die ursprüngliche Konfiguration der Container Bay dem Startknoten, jede Containerbewegung einer Kante und jede weitere Konfiguration der Container Bay einem weiteren Knoten. Die Pfadlänge entspricht der Anzahl der Containerbewegungen. Zusätzlich untersuchen wir einfachere greedy und randomisierte Konstruktionsheuristiken, eine PILOT-Methode und eine Prozedur zur lokalen Suche. Um sinnvolle Kontrollparameter zu finden werden alle Algorithmen experimentell an einer vordefinierten Menge von Testfällen evaluiert. MMAS und 2D-LPFH lösen fast alle Benchmarkfälle. An den Fällen, die von beiden Algorithmen gelöst werden können, zeigt sich, dass MMAS deutlich besser ist als 2D-LPFH da MMAS meistens Lösungen mit weniger Container-Verschiebungen findet. Schlüsselworter: PMP, PILOT method, ACO, MMAS, LPFH

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 movements. Keywords pre-marshalling problem, reach stacker, PILOT method, ant colony optimization, max-min ant system, least priority first heuristic, container terminal