University of Twente Student Theses


Exploring the world of Container Stacking using Approximate Dynamic Programming

Boschma, R. (2020) Exploring the world of Container Stacking using Approximate Dynamic Programming.

[img] PDF
Abstract:Intermodal shipping containers will be, at one point in their transport, stored at a terminal. In this terminal, containers are usually stacked on top of one another. This approach yields a higher utilization of the area available but leads to unproductive moves when a lower stacked container needs to be retrieved. Such a move is commonly referred to as a reshuffle and preventing them has a financial benefit as it not only avoids the costs of executing the reshuffle but also decreases the time needed to retrieve a container. Most researches consider the problem where all containers need to be removed from a terminal using the least number of reshuffles possible [19]. This problem is commonly referred to as the Container Relocation Problem and is proven to be NP-Hard [3]. It only considers the departure of containers and, usually, it is assumed that the departure time of containers is fully known in advance. In reality, this is often not the case [11]. In addition, no research addresses the stacking restrictions imposed by a reach-stacker, which is most often used in smaller inland terminals. Therefore, in this thesis, a stacking approach, which tries to minimize the number of reshuffles, is proposed. It considers both arrival and departures of containers and includes uncertainty in arrival and departure times. Furthermore, it includes restrictions imposed by the use of reach-stackers. The problem tackled in this thesis is a sequential decision problem that includes uncertainty. Therefore, the problem is modeled using Stochastic Dynamic Programming (SDP). As the number of possibilities to store containers grows exponentially, it is decided to focus in this thesis on Approximate Dynamic Programming (ADP). In this thesis, the data of seven terminals are analyzed. From this analysis, assumptions are drawn from which a model is defined. Different ADP approaches are tested on smaller problem instances. The best-found approach is tested on real-life instances and compared to existing approaches in literature. The real-life instances are generated using data found in the analysis of the terminals. Results show that a basis function approach using the least squares method to update its weight performs best of the tested ADP approaches on the smaller instances. The decision space still proved to be too big to yield results in a reasonable time for real-life instances. Therefore, the decision space was split into smaller decisions and the basis function was used to guide the search of the smaller decisions. This method is referred to as the optimized basis function approach. Still, the optimized basis function proved not to be suitable for real-life instances. In addition to the optimized basis function, a new method is proposed. This method limits the allowed decisions using a corridor. All decisions making use of resources outside the corridor are ignored. This method is referred to as the corridor method and proved to yield compelling results for real-life instances in a reasonable time. It was tested against different terminal sizes where the biggest contained 1000 stacks. It outperformed the compared heuristic found in literature significantly. All data and code used can be found at: 2702/ContainerStacking.
Item Type:Essay (Master)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:54 computer science
Programme:Computer Science MSc (60300)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page