From a Container Pre-Marshalling Problem towards a Real-World Application

Beschreibung

Containers are stored in container bays that consist of w stacks of at most h containers, from which containers are retrieved in a particular order. Before accessing a container, all overlying, blocking containers in the stack need to be re-placed, which is typically performed by a gantry crane that accesses the top most container of each stack. To prevent so-called idle strokes, i.e. additional, time-consuming re-placements during vessel stowage, all blocking containers need to be re-placed beforehand. Thus, the container pre-marshalling problem (PMP), as commonly de ned in (academic) literature, aims at nding a minimal length work-plan of container replacements such that the resulting container bay contains no more blocking containers. Although the PMP frequently arises in container terminals|especially in those employing semi/full-automatic gantry crane systems|many terminals are facing an even more complex problem: First, container terminals need to concurrently process outbound as well as inbound containers. Second, in real-world applications, some information, such as arrival or shipment time of containers, is volatile or even not available. Finally, two types of container lifting vehicles are typically in operation at container terminals: gantry cranes for performing intra-bay operations (moving containers within a bay) and reach stackers for inter-bay operations (moving containers within di erent bays). Within our work, we plan to extend the classical PMP to sup- port all three of these extensions, i.e. inter-bay operations, uncertain information on container arrival and shipment times, and di erent lifting vehicle types. So far, we have developed two exact approaches for the classical PMP: a novel dynamic programming approach (capable of solving medium-sized instances) and a novel constraint programming approach. First, we plan to extend the exact approaches to inter-bay operations. In a second step, we plan to embed inter- and intra-bay solution methods in a metaheuristic framework for solving the more complex real-world application. For this purpose, we consider to employ a population based metaheuristic as surrounding procedure with speci cally designed recombination operations such that promising parts of the individual work-plans (e.g. the gantry crane plan from one solution and the reach stacker plan of another solution) can be further improved and combined with each other. In summary, we will develop a fully hybrid approach for optimizing real-world container management operations being able to provide intra as well as inter bay plans by means of dynamic programming and constraint programming while overall optimization is controlled by a metaheuristic part.

Zeitraum	7 Dez. 2012
Ereignistitel	Austrian Workshop on Metaheuristics 8
Veranstaltungstyp	Sonstiges
Bekanntheitsgrad	National