集装箱船舶装箱排序问题的两阶段算法

集装箱船舶装箱排序问题综合集装箱装船顺序与船舶贝内排箱,是一类典型的组合优化问题.考虑堆场发箱顺序和船舶配载之间的关联,构建集装箱船舶装箱排序问题的数学模型.针对构建的优化模型,鉴于已有方法难以直接对其进行求解,基于两阶段分层求解思想设计SWO-HES两阶段算法.算法第1阶段利用吱呀轮算法(SWO)大邻域导向式搜索的特点优化集装箱装船顺序问题;第2阶段将SWO的结果作为输入,基于启发式规则和演化策略算法(ES)构造混合演化策略算法(HES)优化船舶贝内排箱问题.最后,通过不同规模算例的研究,将SWO-HES与常见智能算法、基于实际装船规则的启发式算法进行对比分析,验证模型与算法的有效性.

Two-phase Algorithm for Containership Sequencing and Bin Packing Problem

Sequencing and bin packing problem (SBPP) is a kind of typical combinatorial optimization problem including containership loading sequence problem (CLSP) and slot plan problem (SPP). The mathematical model of SBPP is established considering the relationship between CLSP and SPP. As the existing methods are hardly used to optimize SBPP, SWO-HES two-phase algorithm is designed based on the two-phase hierarchical solving method. CLSP is optimized based on the large neighborhood guiding search characteristic of squeaky wheel algorithm (SWO). Then the heuristic evolutionary strategy algorithm (HES) is designed based on evolutionary strategy (ES) and heuristic rules to optimize SPP with the result of SWO as input. Finally, through the research of different scale examples, SWO-HES is contrasted with common optimization algorithm and heuristic algorithm based on actual loading rule to verify the model and algorithm.