An enhanced variable neighborhood search method for refrigerated container stacking and relocation problem with duplicate priorities

Due to the stringent timeliness requirements of temperature-controlled cargoes and distinctive storage operations of refrigerated container (RC), it is imperative to optimize the storage process of RCs in terms of reducing relocations and delays. Aiming to manage RC storage more efficiently, this paper addresses an integrated problem of refrigerated container stacking and relocation problem (RCSRP) with unique characteristics, including various storage modes (i.e., RC block and cold storage), concurrent stacking and retrieving tasks, and duplicate handling priorities. A new virtual stack concept is introduced to develop a new binary formulation of RC block configuration, enabling simultaneous handling of stacking and retrieving tasks. Based on the new binary formulation, a mixed integer programming (MIP) model is developed and incorporates novel constraints related to RC operations and duplicate handling priorities. To improve solvability, a decomposition strategy is proposed to make it possible to solve large-scale problems. An enhanced variable neighborhood search (EVNS) algorithm is developed to solve the decomposed model iteratively. A handling sequence and stacking and relocation scheduling (HSSRS) heuristic is designed to solve sub-problems. With the implementation of the decomposition strategy and tailored EVNS framework, both the solvability and solving efficiency of the original integrated MIP model are significantly improved. The decomposed model can be optimally solved by CPLEX under the EVNS on small-scale instances. On medium-scale instances, the proposed approach can also obtain extreme high-quality solutions with an average gap of less than 0.1%, while the solving efficiency is increased more than 30%. On large-scale instances, the decomposed model is still worked, while the original MIP model cannot be solved. Besides, by applying the HSSRS, the EVNS can also optimally solve small-scale instances, and yields satisfactory solutions with an average gap below 3.2% on medium and large-scale instances. Meanwhile, the computing efficiency is significantly higher than CPLEX and general genetic algorithm. The computational experiments results indicate that, the proposed decomposition strategy can effectively improve the solvability of the original MIP integrated model. Benefit from the unique characteristic of the RCSRP, the tailored EVNS framework and HSSRS heuristic significantly improve the solving efficiency of the decomposed model, while ensuring the solution quality and convergence. The proposed approach can help port operators to manage RC storage in a more effective manner. Under specific scales and workloads, the proposed model and algorithm could also help managers to determine the equipment configuration in RC storage yards.