The stochastic container relocation problem with flexible service policies

This paper investigates the Stochastic Container Relocation Problem in which a flexible service policy is adopted in the import container retrieval process. The flexible policy allows the terminal operators to determine the container retrieval sequence to some extent, which provides more opportunity for reducing the number of relocations and the truck waiting times. A more general probabilistic model that captures customers’ arrival preference is presented to describe the randomness for external truck arrivals within their appointed time windows. Being a multi-stage stochastic sequential decision-making problem, it is first formulated into a stochastic dynamic programming (SDP) model to minimize the expected number of relocations. Then, the SDP model is extended considering a secondary objective representing the truck waiting times. Tree search-based algorithms are adapted to solve the two models to their optimality. Heuristic algorithms are designed to seek high-quality solutions efficiently for larger problems. A discrete-event simulation model is developed to evaluate the optimal solutions and the heuristic solutions respectively on two performance metrics. Extensive computational experiments are performed based on instances from literature to verify the effectiveness of the proposed models and algorithms