原文传递
堆场龙门吊调运问题——带拓扑优先级的一维非对称TSP问题
| 论文题名： | 堆场龙门吊调运问题——带拓扑优先级的一维非对称TSP问题 |
| 关键词： | 集装箱码头;堆场龙门吊;调运管理;旅行商问题;拓扑排序;动态规划;剩余点插入策略 |
| 摘要： | 近年来，集装箱码头在进出口贸易发展的带动下高速发展起来的，而航运作为进出口贸易运输的重要一环，也随之出现复苏。堆场作为集装箱码头的一个作业单元，在整个集装箱码头的运作中也扮演着重要的角色，而在堆场中，最重要的就是龙门吊的调运问题。所以，本文以单个堆场龙门吊为研究对象，意在找到一种好的方法来解决堆场龙门吊的调运问题，能够找一条路径，龙门吊所走的路程最短，并用程序语言实现。 本文从单个堆场的龙门吊出发，研究其调运问题与一般TSP问题的联系。为建模方便，将龙门吊在三维空间的运动简化为一维，并考虑到在实际问题中会存在指令的紧急问题，并且不同的优先级约束里可能会出现重复的指令，加入了拓扑优先级的约束。最后，由于龙门吊调运分为存入和取出两个不同的指令，而不同的指令组合对于龙门吊又有不同的调运路线，故又将该问题转换成非对称的TSP问题。综上，堆场龙门吊调运问题，我们可以模型化为带拓扑优先级的一维非对称TSP问题，简称为OA-TSP-TPC问题。 为了解决该问题，我们引入拓扑排序的方法，将拓扑优先级线性化，得到多个线性的优先级约束，在程序中，给每个节点赋入度值，每次循环寻找目标节点并删除相应的入度;再用基于动态规划方法的算法，根据动态规划的特性，每一个状态都是由它的前一个可达状态通过状态转移方程转移过来的，那么我们可以列出所有可能出现的状态，在每种可能性下求最小的路程，直至访问完所有的节点，在最后的状态下最小的路程是全局最优，再倒过去寻找这个最小路程所对应的访问次序，试图找到最优路径，这样就将多个优先级约束转化为一条最优的访问路径，在程序中，我们只考虑了对称的情况;在这种一般的TSP问题中，优先级约束里一般没有包括所有的节点，当将所有优先级约束转换为最优的访问次序后，可以运用剩余点插入策略，将剩余的点插入到次序中，试图以更简便的方法得到包括所有节点的访问次序。最后，在一组数值试验中对比了该文的动态规划和贪婪插入算法的效率，并验证了该方法的鲁棒性。 总的来说，本文通过研究堆场龙门吊调运问题，将其与运筹学中经典的TSP问题联系起来，构建了OA-TSP-TPC问题模型，再运用拓扑排序和动态规划两种不同的方法解决该问题的两个部分，并针对一般TSP问题加入了剩余点插入策略，最终达到解决全部问题的目的，并用程序语言实现。最后的数值实验表明，该方法有良好的性质。 |
| 作者： | 杨然 |
| 专业： | 企业管理 |
| 导师： | 徐亮 |
| 授予学位： | 硕士 |
| 授予学位单位： | 西南财经大学 |
| 学位年度： | 2016 |
| 正文语种： | 中文 |
检索历史
应用推荐
