6. Algorithmic Analysis Based on the Problem Decomposability

Based on the considerations about the large-scale model structure and its solvability in the previous chapter, a solution method for the core model is developed, formally described and numerically studied. The aim is to reduce the model size in order to enable an analysis of interaction effects of container handling problems in single yard block operations. By this approach, the solution of lager instances is promoted providing an improved basis for the theoretical examination and numerical evaluation. For this purpose, a Benders decomposition approach is developed where the Master and the Sub-problem are solved as linear programs to reduce computational time. Integrality of the Master is obtained by randomised rounding based on a Fix-and-Relax procedure which enables the algorithm to escape local optima. In this process, feasibility is constructed by calling stacking rules which underlie the specific problem structure. Based on the obtained integer input to the Sub-problem from the Master, integrability of the Sub-problem is supported by a polynomial number of facet-defining valid inequalities. Within the specified runtime limit, CPLEX finds only feasible solutions for the 30% smallest test instances while the proposed algorithm generates feasibility in close to 90% of the cases including the largest ones. Moreover, the benefits of the hybrid algorithmic framework are illustrated by a numerical comparison with the original Benders decomposition and a random draw from the solution space with the help of the heuristic stacking rules. Hence, the research questions about the theoretical foundations are addressed within this chapter.