原文传递
基于列生成算法的近海平台供应船规划问题研究
| 论文题名： | 基于列生成算法的近海平台供应船规划问题研究 |
| 关键词： | 供应船规划;列生成算法;MLC算法;硬时间窗;周期性运输 |
| 摘要： | 海上油气开采装置的储存空间有限，近海平台供应船通过陆上供应基地为每个海上装置提供周期性的物资供应，以保证其生产活动的持续进行。一般在海上运营的油气开采商需要从其他船舶经纪公司和船东处租赁船舶，供应船总运营成本包括租船成本和航行成本，租船成本是影响供应船总运营成本的主要因素。因此为了降低油气开采商配送后勤物资的总运营成本，需要对供应船制定合理的规划方案。 供应船规划问题包括确定最佳船队组成、为海上油气开采装置提供服务的周期性航线以及船期表。为了制定符合实际情况的供应船规划方案，本文设计了一个新的供应船整数规划模型，在航次模型的基础上添加硬时间窗、船舶均匀出发、航次不重叠、航行周期等限制，使模型更加贴合现实。为了精确求解大规模供应船规划问题，本文采用了全局精确求解算法——列生成算法（ColumnGeneration,CG），打破了启发式算法不能确保解的质量和仅能求取近似满意解的局限。在列生成算法框架下，利用D-W分解原理将供应船整数规划模型分解为基于路径的主问题和带资源约束的最短路子问题。为了提高子问题的求解效率，本文设计了一种新的改进的标号修正算法（ModifiedLabelCorrectingAlgorithm，MLC），并采用多种剪枝策略降低子问题的计算规模；运用CG+MLC算法，在主问题与子问题之间不断迭代符合条件的变量，直至得到全局最优精确解。本文依据求取的所有预生成航次，设计了一个船期表的生成方案，使计划与实际更加契合。 为验证模型与算法的可行性和有效性。在海上装置的不同规模下，将CG+MLC算法、NS算法、直接使用CPLEX求解进行效率对比，并以我国渤海海域海上油气开采装置分布现状为例，将传统的点对点式配送方案与多点式配送方案进行比较，发现运用CG+MLC算法的多点式配送方案能以较少的存储空间、较短的时间、较低的成本生成最佳船队组合（数量和类型）、周期性配送航线以及船期表。通过成本敏感性分析，可知租船成本一直是供应船总运营成本的主要组成部分，随着海上装置规模的不断增加，航行成本所占比重也越来越大。结果表明，列生成算法在大规模近海平台供应船规划问题的求解精度和速度上均有明显优势。 |
| 作者： | 岳美 |
| 专业： | 交通运输工程 |
| 导师： | 钟铭 |
| 授予学位： | 硕士 |
| 授予学位单位： | 大连海事大学 |
| 学位年度： | 2022 |
检索历史
应用推荐
