共计 1877 个字符，预计需要花费 5 分钟才能阅读完成。
摘要：针对集装箱港口提箱过程中的翻箱问题，以最小化翻箱次数为指标，构建基于状态结点的网络图模型，将翻箱问题转化为最短门路问题，并采纳最短门路算法进行求解，最初给出一组计算样例。
1. 集装箱堆场翻箱问题
在集装箱码头作业过程中，因为船舶抵港工夫具备不确定性，可能呈现集装箱提箱程序与初始堆放地位不齐全相符的状况，导致须要较早离场集装箱被压在后续离场集装箱上层景象。所以提箱过程中不可避免须要进行翻箱，甚至当被翻箱落箱地位选取不当，会造成后续提箱的二次翻箱；翻箱过程存在如下定义：
（1）指标箱：某一堆存状态下，预最先发箱的集装箱为该堆存状态下的指标箱;
（2）必翻箱：若某集装箱下方存在比其优先取箱的箱子，则该集装箱为相应堆存状态下的必翻箱；
（3）阻塞箱：间断堆存在某集装箱上方的必翻箱，为相应堆存状态下该集装箱的阻塞箱；
如图 1 所示为某一贝位内的堆存状态（6* 6 的贝位，且均为 20FT 集装箱，底部横轴为栈编号，左侧纵轴为层编号）；当提箱程序为 C21->C15->C12 时，可知以后堆存状态的指标箱位 C21，C12 处于栈顶，不存在阻塞箱，可间接收回；而 C15 作为后续堆存状态的指标箱，其上方还有其余集装箱；此时，定义 C12,C13,C14 为指标箱 C15 的阻塞箱，同时 C12,C13,C14 称为以后堆存状态的必翻箱；
图 1 堆存状态
2. 基于状态结点的网络图模型
（1）堆存状态：指某堆存范畴内集装箱的堆存状况，如图 1 所示，即为栈 6 -11 的一组堆存状态；翻箱过程中可行的堆存状态应具备如下特点：
a）：集装箱不能悬空搁置；
b）：不思考轻压重等分量准则；
c）：不容许超过堆存区域既定的最大堆高；
d）：集装箱地位不能超过作业机械所能达到的最大堆高；
（2）状态结点：每一个可行的堆存状态即可作为一个状态结点；
（3）结点可达：针对某一指标箱，若状态结点 A 中的某一集装箱通过翻箱操作后失去的堆存状态与状态结点 B 统一，则称结点 A 可达结点 B；
（4）权重取值: 且若结点 A 可达结点 B，那么结点 A、B 间存在方向 A ->B, 且可计算 A ->B 的翻箱次数，并将其作为连贯权重；
（5）网络图构建原理：以初始堆存状态作为根节点，将指标箱作为层级划分的标识。同时，将提箱过程中各层可能的堆存状态作为该层的叶子节点，实现提箱操作的堆存状态作为完结节点；结构形如图 2 所示的树状网络图构造，并减少虚构完结节点：
图 2 状态结点树状网络图
（4）网络图性质：剖析可知，上述结构的堆存状态树状网络图具备以下特色：
特色 0： 完结状态层中，不存在待提集装箱，此时堆存状态可能为空，也可能包含非待提箱；
特色 1 ：图中入度为 0 的点和出度为 0 的点有且仅有一个（别离为根节点和虚构完结节点）；其余节点的出度、入度均大于等于 1；
特色 2 ：虚构节点作为后续节点与所有完结节点相连，且权重均等于 0；
特色 3 ：上一层的指标箱在以后堆存状态肯定处于栈顶或已被提箱离场；
特色 4 ：因为提箱程序有优先级要求，联合特色 3，因而不存在跨层节点连贯；
特色 5 ：因为不波及预翻箱作业，则中间层每层至多存在一个状态叶子节点，且两两状态之间不可达；
特色 6 ：联合特色 4 和特色 5 可知，网络图为有向无环图；
至此，通过构建具备上述特色的树状网络图，可将翻箱问题转化为寻找从根节点到虚构完结节点的最短门路问题，并采纳最短门路问题算法进行准确求解。
3. 计算样例
（1）初始堆存状态 Node0；
（2）结构树型网络图构造
结点信息如下：
（3）最短门路问题求解
以后最短门路反对 Dijkstra’s 算法（正权有向图）、Floyd 算法、0- 1 整数布局等形式求解；此外，进一步联合特色 6 可知，上述构建的最短门路问题为有向无环图，因而可采纳更为高效的基于拓扑排序的疾速求解算法求解；最终失去翻箱计划如下，翻箱次数为 1 次；
参考文档
- da Silva Firmino A, de Abreu Silva R M, Times V C. An exact approach for the container retrieval problem to reduce crane’s trajectory[C]//2016 IEEE 19th international conference on intelligent transportation systems (ITSC). IEEE, 2016: 933-938.
- https://bbs.huaweicloud.com/blogs/211445- 有向无环图最短门路问题及其变种问题的疾速求解算法.
本文分享自华为云社区《集装箱港口翻箱问题的最短门路求解算法》，原文作者：CKW@10270。
点击关注，第一工夫理解华为云陈腐技术~
