金波：集装箱翻箱问题的迭代加深分支定界算法设计

数据魔术师
运筹优化及人工智能系列讲座第35期

活动信息

题目：集装箱翻箱问题的迭代加深分支定界算法设计
Title: An Iterative Deepening Branch-and-bound Algorithm for the Container Relocation Problem

主 讲 人：金波 深圳大学管理学院助理教授
主 持 人：秦虎 华中科技大学管理学院教授
讲座语言：中文
活动时间：2022年6月18日  下午15:00 – 18:00
主办单位：华中科技大学管理学院，数据魔术师

直播平台：通过数据魔术师粉丝群发布腾讯会议号及密码，入群方式见文末

主讲人简介

金波，2015年博士毕业于香港城市大学管理科学专业。本科期间曾获第34届国际大学生程序设计竞赛亚洲区域赛金牌（总排名第3），博士毕业后曾于阿里巴巴、华为、南科大等企事业单位从事科研工作，2020年加入深圳大学任助理教授，主要从事港口与航运管理、物流与供应链管理等领域的研究，已有多项研究成果发表于European Journal of Operational Research、Omega、Computers & Operations Research等期刊。

报告摘要

集装箱翻箱问题（Container Relocation Problem）是港口码头中重要的运作优化问题之一。该问题考虑一组出口集装箱，通过最小化取箱过程中的翻箱次数，以提升堆场整体装卸效率及减少船舶停泊时间，对提升港口的集装箱吞吐量有着重要意义。本次报告将以集装箱翻箱问题为例，详细介绍一种求解NP难组合优化问题的精确算法设计，包括搜索框架、上界函数、下界函数、支配规则等关键技术的设计思路及应用心得。最后，报告将解读求解集装箱翻箱问题的迭代加深分支定界算法的源代码。

The container relocation problem, also known as the block(s)relocation problem, is one of the most studied optimization problems incontainer terminals. The problem aims at minimizing the total number ofrelocations for retrieving containers from a storage yard according to aspecific order. The purpose of this study is to develop an efficient iterativedeepening branch-and-bound algorithm for exactly solving one of the mostpractical variants of the problem, namely the unrestricted container relocationproblem with duplicate priorities, which has received less attention in theliterature. To improve the search efficiency of the proposed algorithm, wedesign two new lower bounds that can be computed quickly to incorporate theminto the branch-and-bound algorithm. We also present a set of mutuallyconsistent dominance rules to reduce the search space while avoidingover-pruning. The performance of the proposed algorithm is evaluated byextensive computational experiments on three commonly used benchmark datasets.The results show that the proposed algorithm outperforms the state-of-the-artexact algorithm for the unrestricted container relocation problem with distinctpriorities, although our algorithm is applicable to a more general variant ofthe problem. Moreover, it can still provide competitive results for small- andmedium-sized instances under a strict time limit of one second in comparison toexisting metaheuristic approaches.

对学生听众的建议：参加报告之前先预习掌握深度优先搜索、广度优先搜索，以及最短路问题的Dijkstra算法、A*算法、IDA*算法等知识。

加入会议方式

欢迎大家加入数据魔术师粉丝群，我们的活动将会通过粉丝群优先发布， 学习资料将通过粉丝群分享。
欲入群，请扫描下方二维码联系数据魔术师小助手.