Landscape-Aware Hybrid Metaheuristic for Cross-Dock Door Assignment

The cross-dock door assignment problem (CDAP) is a critical challenge in optimizing cargo transshipment in logistics, where each inbound door serves multiple origins and each outbound door serves multiple destinations, subject to capacity constraints on the volume of goods processed at each door. To address this problem, we propose a novel metaheuristic (LA-HM) that integrates landscape-aware iterated tabu search and large neighborhood search within a unified framework. The proposed algorithm begins with a model-driven procedure to generate a diverse set of initial solutions, which are then refined using an iterated tabu search procedure, enhanced by an innovative landscape-aware detection mechanism. This mechanism dynamically monitors the search landscape at regular intervals to identify plain regions characterized by slow local improvement. Based on the detected plain level, the algorithm adaptively adjusts the interval length in the tabu search and applies targeted perturbations to escape local optima, thereby exploring more promising regions. Additionally, we introduce a reformulation of the original problem, consolidating all trucks at a door into a single “consolidated truck.” This reformulation enables the use of an alternating local search method to further refine solutions efficiently. Evaluated on two widely used data sets, the proposed algorithm sets new best known records for 39 out of 99 benchmark instances, and surpasses the leading algorithms in the literature. Moreover, a comprehensive analysis of the landscape-aware detection mechanism and the large neighborhood search highlights their contributions to solution quality. Notably, the search strategies proposed in this work are generalizable and applicable to a wide range of combinatorial optimization problems, particularly those characterized by flat landscapes where traditional methods often struggle to navigate effectively.

History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms.

Funding: This work was supported by National Natural Science Foundation of China [Grant 72371200]; Spanish government-Ministerio de Ciencia e Innovación [Grants PID2021-125709OB-C21, PID2024-160226OB-C21].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1233) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2025.1233). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.