多停泊基地约束下的港口拖轮调度优化研究开题报告
2020-02-18 07:02
1. 研究目的与意义（文献综述）
| 1.1 研究目的及意义 中国拥有1.8万公里海岸线，11万公里内河航道，承担着9％的国内贸易运输和85％以上的外贸货物运输，沿海沿江有1460多个商港。大部分的外贸货物运输由港口来承担，对外贸易量的不断增长，必然会给许多的港口的发展壮大带来千载难逢的好机会。我国的港口建设与经济，特别是港口物流的发展越来越迅速，港口业的迅速发展又为我国国民经济的迅猛发展提供了很大的动力。港口的这种作用是无法替代的，现代物流的发展也促进了港口的建设，港口物流将越来越显现其强大的生命力与发展力。 港口规模不断扩大，为了维持港口的运营，提升服务水平，在港口作业中起到极为重要的作用的拖轮作业，也需要用更为高效的方法来进行调度。拖轮体积小马力大、反应快速、操作灵活，港口作业从货船进港开始，货船进港后首先在锚地等待办理相关进港手续，船舶到达港口航道时需要拖轮对其辅助作业使其进入预先安排的泊位，然后在码头进行相应的装卸作业，码头作业可能涉及到在多个泊位间作业，由于货轮不能自行在码头间移动，需要拖轮协助作业，即为移泊，码头作业完成后由拖轮辅助货船驶离码头进入航道，最后货船自行离开港口。 在需要拖轮作业的三个主要环节：进港、移泊、出港中，不同的船型所需要的拖轮类型和数量是有差异的，要保证到港船舶能安全地进港、快速靠泊被服务，最后准时地离开码头，控制成本与服务水平，而港口区域的范围和岸线长度有限，如不能有效调度拖轮按时地将待服务船舶拖至合理的泊位接受装卸船服务，会导致船舶在港口停留时间过长，进而造成许多船舶滞港和泊位占用过久的现象发生，拖轮作业调度的好坏将直接影响船舶的作业效率和进出港时间，不合理的拖轮调度会造成资源的浪费也会直接影响服务质量，为了保证港口的日常运营，必须做好港口拖轮的调度工作。 1.2 研究现状分析 对于港口拖轮调度问题，近年来国内外众多学者对这个问题都有相关研究，并通过不同的方法对研究方案进行了优化和改进。 易剑琦[1]等学者运用eM-plant软件分别建立单停泊基地和多停泊基地两种作业模式下的港口拖轮作业系统仿真模型，并限制或允许其交叉作业，对三种拖轮作业模式进行横向比较分析出的其优缺点，相同情况下多停泊基地允许交叉作业最优。 在拖轮调度问题模型建立方面，谈鹏[2]建立了以最小空载距离为目标的拖轮调度优化模型，实现了动态调度；王巍[5]等学者以最大完工时间和总作业油耗最小化为目标建立了多停泊基地和不同作业模式下的拖轮调度模型；刘志雄[6-7]在考虑拖轮最短距离作业的前提下，以最小化最大完工时间为优化目标建立了拖轮作业调度模型，并针对单向航道港口，以拖轮最大作业时间最小化为目标，采用滚动时序的方法构建动态调度模型；周晓光[8]对拖轮调度问题，建立作业时间和成本两个最小化目标；白洁[9]构建了泊位和拖轮协同调度数学模型；HeTao[10]等学者以最小化最大完工时间为目标来建立拖轮调度模型；徐奇[11]等学者构建了以拖轮总作业时间最小化为目标函数、考虑多停泊基地条件下的一体化调度优化模型；徐奇[12-14]等学者将拖轮调度问题归结为一类具有多阶段共用平行机器特征的多处理器任务调度问题，建立了拖轮调度优化模型；闫志超[16]以拖轮作业时间最短为目标函数建模。 |
在解决拖轮调度问题的算法研究方面，谈鹏[2]改进了标准遗传算法，釆取实数编码并运用以时序长度为单位的交叉和变异操作；黄健[3]利用遗传算法的全局搜索能力和非线性规划的局部搜索能力进行求解，结果表明该方法可以以较快的收敛速度达到全局最优。
王巍[5]等学者采用演化策略算法进行计算，提出一种基于轮盘赌概率分配的编、解码方法，计算结果表明了演化策略算法的有效性和可行性；刘志雄[6]采用演化策略算法对拖轮作业调度问题进行优化，提出了一种基于轮盘赌概率分配的编、解码方法，并设计了三点交叉互换的重组算子和个体基因交叉互换的变异算子；刘志雄[7]等学者利用基于3种不同局部搜索策略的混合演化策略算法对模型进行优化求解，其中，基于互换操作的局部搜索策略对算法性能的优化更加理想；周晓光[8]、白洁[9]、HeTao[10]等学者采用进化策略与局部搜索的混合算法来研究拖轮调度问题，通过算例验证了其有效性。
徐奇[11]设计了混合模拟退火算法，以二维实整数的方式作为解的表现形式，在初始解的生成过程中加入首艘可用拖轮的启发式规则，并运用三点交叉的方式产生新解；徐奇[12-14]等学者推导了基于混合流水作业组织的港口拖轮调度优化问题的理论下界值，并设计了启发式规则与模拟退火相结合的混合算法求解；Santos[15]等学者采用模糊模拟退火算法进行并行机调度研究，解决不相关的并行机调度问题。
闫志超[16将拖轮作业分为靠泊、移泊、离泊三阶段，引入人工蜂群算法；刘倩雯[17]探究人工蜂群算法应对不同的优化问题上的特性，并针对作业车间调度问题的特点，提出了一种人工蜂群的改进算法，该算法可以解决包括作业车间调度问题在内的排列和组合优化问题。
| 董良才[19]等学者采用改进后的粒子群算法进行求解，通过对比传统粒子群算法，得出其优越性与可行性；Ezzinbi[20]等学者利用粒子群优化算法求解航空机组调度问题，并将这种求解方法与遗传算法进行了比较；WeiYan[21]等学者提出改进的粒子群优化算法，提出的算法在拖轮上调度得到了成功的应用，并展示了其更快的速度及与标准粒子群算法相比具有更好的收敛性；SuWang[22]等学者提出了一种改进的离散混沌粒子群优化算法，嵌入混沌搜索作为局部搜索方法可以防止过早收敛。 |
2. 研究的基本内容与方案
| 2.1研究的基本内容及目标 （1）介绍研究目的及意义，分析港口作业流程和现状，分析拖轮作业的特点，分析多停泊基地约束下的港口拖轮调度优化问题的国内外研究现状，综述应用的相关算法理论。 （2）假设条件，建立两个停泊基地约束下拖轮调度的数学模型，分为两种情况，允许两个停泊基地交叉作业和限制两个停泊基地交叉作业。 （3）比较遗传算法、人工蜂群算法、模拟退火算法等启发式算法的优缺点，选择遗传算法与非线性规划相结合的函数寻优求解该问题，学习算法的计算原理，并学习MATLAB语言，用以解决该问题。 （4）根据港口资料以及随机数据，设计算例，用选用的算法求解并分析结果，验证算法的有效性和可行性。 2.2研究拟采用的技术方案及措施 |
（1）遗传算法
遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。从随机产生的初始解开始搜索，通过一定的选择、交叉、变异操作逐步迭代以产生新的解。
（2）非线性规划
非线性规划研究一个n元实函数在一组等式或不等式的约束条件下的极值问题，且目标函数和约束条件至少有一个是未知量的非线性函数。采用MATLAB优化工具箱中线性规划函数fmincon进行局部寻优，并把寻到的局部最优值作为新个体染色体继续进化。
（3）数学建模法
假设条件，定义符号，运用符号、函数关系将目标规定下来，并把各参量之间的变化关系通过数学式表达出来，从实际问题中抽象、提炼出数学模型，本文即是将拖轮调度模型用数学符号表示出。
技术路线图如下：
| |
| |
3. 研究计划与安排
| 周次 | 目标任务 |
| 1-4 | 明确任务书内容，查阅相关文献，撰写开题报告； |
| 5 | 完成专业外文文献翻译； |
| 6 | 明确论文思路，撰写提纲； |
| 7 | 撰写论文理论综述部分内容； |
| 8-10 | 建立数学模型并学习算法计算原理和MATLAB； |
| 11-12 | 撰写论文主体部分内容，完成论文初稿； |
| 13-14 | 修改论文，完成终稿并装订； |
| 15 | 制作答辩PPT，完成毕业论文答辩。 |
4. 参考文献（12篇以上）
| |
-
易剑琦,刘志雄,蔡瑞东,黄雪锋,李晗,张桥.面向多停泊基地的港口拖轮作业配置仿真决策[J].物流技术,2015,34(19):105-109.
-
谈鹏. 基于AIS的港作拖轮调度系统研究[D].武汉理工大学,2013.
-
黄健.基于遗传算法和非线性规划的设备预防维修周期优化模型[J].数学理论与应用,2017,37(02):88-96.
-
Hao-Chin Chang,Hung-Te Tsai,Tung-KuanLiu. Application of genetic algorithm to optimize unrelated parallel machinesof flexible job-shop scheduling problem[P]. Control amp;amp; Automation(ICCA), 11th IEEE International Conference on,2014.
-
王巍,赵宏,李强.面向多停泊基地的港口拖轮调度优化研究[J].计算机工程与应用,2013,49(13):8-12 35.
-
刘志雄.考虑最短距离作业的港口拖轮作业调度优化[J].西南交通大学学报,2011,46(05):875-881.
-
刘志雄,李俊,邵正宇,贺晶晶.拖轮动态调度的混合演化策略算法设计[J].计算机工程与设计,2016,37(02):519-524 529.
-
周晓光.基于进化策略算法的港口拖轮调度优化[D].大连海事大学,2014.
-
白洁. 拖轮和泊位的协同调度研究[D].大连海事大学,2013.
-
HeTao,Ye Wenwen. Research of Tugboat operation scheduling problem based on hybridevolutionary strategy[P]. Information Science and Engineering (ICISE), 2010 2ndInternational Conference on,2010.
-
徐奇,边展,陈燕,靳志宏.多停泊基地约束下港口拖轮作业的一体化调度优化[J].上海交通大学学报,2014,48(01):132-139 145.
-
徐奇,邵乾虔,靳志宏.基于混合流水作业组织的港口拖轮调度优化[J].系统工程理论与实践,2014,34(02):485-493.
-
徐奇,李娜,靳志宏.考虑多阶段共用平行机特征的拖轮作业模式优化[J].运筹与管理,2014,23(05):178-186.
-
徐奇. 港口拖轮调度优化及其仿真研究[D].大连海事大学,2012.
-
Santos,A.S.,Varela, M.L.R.,Madureira, A.M.,Ribeiro, R.A.. Parallel machines schedulingwith fuzzy simulated annealing[P]. Nature and Biologically Inspired Computing(NaBIC), 2014 Sixth World Congress on,2014.
-
闫志超. 基于人工蜂群算法的拖轮调度优化[D].大连海事大学,2015.
-
刘倩雯. 人工蜂群算法及其在调度问题中的应用研究[D].北京交通大学,2014.
-
何尧,刘建华,杨荣华.人工蜂群算法研究综述[J].计算机应用研究,2018,35(05):1281-1286.
-
董良才,徐子奇,宓为建.基于遗传算子粒子群算法的拖轮动态调度[J].数学的实践与认识,2012,42(06):122-133.
-
Ezzinbi,O.,Sarhani, M.,El Afia, A.,Benadada, Y.. Particle swarm optimization algorithmfor solving airline crew scheduling problem[P]. Logistics and OperationsManagement (GOL), 2014 International Conference on,2014.
-
WeiYan, Zhicheng Bian, Daofang Chang, Youfang Huang. An improved particle swarmoptimization algorithm for solving dynamic tugboat scheduling problem[P]. PowerElectronics and Intelligent Transportation System (PEITS), 2009 2ndInternational Conference on,2009.
-
SuWang, Kai Zheng, Jun Zheng, Wenxin Hu. An Improved Discrete Particle SwarmOptimization for Tugboat Scheduling Problem in Container Terminal[P].Information Management, Innovation Management and Industrial Engineering(ICIII), 2010 International Conference on,2010.
-
AliAllahverdi,Harun Aydilek. The two stage assembly flowshop scheduling problem tominimize total tardiness[J]. Journal of Intelligent Manufacturing,2015,26(2).
