Conference Agenda

Housekeeping is a key process in terminals, where containers are rearranged during off-peak hours to minimize future reshuffles during retrieval. The classical Container Pre-Marshalling Problem (CPMP) assumes a deterministic retrieval sequence, an assumption that rarely holds in practice, particularly in rail-road terminals where retrieval times of import containers are largely unknown. This paper introduces the Stochastic Container Pre-Marshalling Problem (SCPMP), which explicitly models uncertainty in container retrieval times through pairwise retrieval probabilities.

Unlike existing robust approaches that require non-overlapping time windows or convert the problem back into a deterministic formulation, the SCPMP encodes uncertainty directly at the container level by delivering a more realistic representation of the operations. Pairwise probabilities P(i,j), representing the likelihood that container i is retrieved before container j, are derived from heterogeneous sources including Machine Learning-based dwell time forecasts, truck appointment systems, and train schedules. These probabilities naturally accommodate overlapping retrieval windows and serve as direct input parameters for both the optimization model and the solution algorithm.

We formulate the SCPMP as a binary integer program that minimizes the expected number of badly placed items under a fixed move budget, reflecting the limited crane capacity available during housekeeping periods. A threshold parameter τ controls which blocking probabilities are classified as critical, enabling operators to calibrate the trade-off between reshuffling effort and residual risk.

For the solution approach, we adapt the Iterative Deeping A* (IDA*) algorithm, established as state-of-the-art for the deterministic CPMP, to the stochastic setting. A central contribution is the development of improved heuristic bounds that tighten the search. Beyond the direct lower bound based on τ-classified badly placed items, we introduce a blocking bound (counting well-placed containers that physically obstruct access to badly placed ones) and a destination-deficit bound (identifying badly placed containers lacking any safe target stack). Both bounds are proven admissible and combined via a maximum operator, preserving optimality guarantees while significantly reducing the search space. Computational experiments show a median speedup factor of 2.6× in node expansions compared to the baseline heuristic.

A computational study on synthetic instances calibrated with real operational data from a German intermodal terminal demonstrates that the IDA* approach solves typical terminal configurations (up to 5 stacks, 4 tiers) within seconds. We further compare solution quality against the exact BIP formulation, analyze the impact of uncertainty levels on algorithmic performance, and evaluate final layouts using CV@R-based risk metrics. Results show that probabilistic information significantly reduces expected reshuffles and tail-risk compared to deterministic and robust reference approaches.