原文传递
船舶作业调度的数学模型及其算法研究
| 论文题名： | 船舶作业调度的数学模型及其算法研究 |
| 关键词： | 船舶作业;作业调度;数学模型;改进启发式算法;调度问题;混合遗传算法;组合最优化;子路径;旅行商问题;个体;质量;优化问题;求解;费用最小;作业船;种群;上海港;航行;服务;二叉树 |
| 摘要： | 本文着重研究的是船舶作业调度问题的数学模型及其算法。这是来自于上海港 的一个实际的组合最优化问题。有一队作业船为抵达或离开上海港的大型运输船舶 提供港口作业服务，问如何安排这些作业船的服务对象、航行路线及作业时间，在 确保准时服务的前提下，使总航行费用最小。 本文从各个方面对船舶作业调度问题作了详尽的分析，并将它与几个相关的经 典组合最优化问题作了全面的比较。在此基础上，建立了船舶作业调度问题的数学 模型，以简洁的数学语言正确地描述一个复杂的实际问题，为问题的求解奠定了基 础。随后对该问题的算法复杂性从理论上作了分析，结论是，本论文提出的船舶作 业调度问题属于NP很难类，没有有效算法。 本文提出了求解船舶作业调度问题的启发式算法。算法的整个过程分为三个步 骤。首先按航行费用最小的原则，生成初始子路径。然后尽可能地将子路径合并以 减少子路径数量，由此生成可行子路径。最后，采用路径改进启发式算法，进行局 部搜索，以提高解的质量。 本文对与船舶作业调度问题的有密切关系的旅行商问题(TSP)提出了两种独 特的算法。 第一种方法是基于二叉树的TSP描述及其求解的启发式算法。其基本特征是从 大处着眼、从小处着手。以此法求解著名的中国31城市TSP问题获得了目前已知 的最好解，而且对大规模TSP也有优异的效果。在这一启发式算法的基础上，本文 还提出了培养算子的概念和方法，以进一步改善解的质量。 第二种方法是种群性状保持的遗传算法。这一算法基于一种假说：在同一种群 中的个体具有相近的性状，由其中的母代个体通过交叉生成的两个子代个体，应具 有与它们的母代个体相近的性状。根据这一假说设计的遗传算法，产生低质量子代 个体机会显著下降，从而提高遗传算法的效率。 另外，将本文提出的基于二叉树描述的启发式算法与种群形状保持的遗传算法 相结合，构成混合遗传算法，解的质量可进一步提高。 关键词 组合最优化；船舶作业调度问题；旅行商问题；启发式算法；遗传算法 |
| 作者： | 徐伯庆 |
| 专业： | 模式识别与智能系统 |
| 导师： | 宣国荣 |
| 授予学位： | 博士 |
| 授予学位单位： | 同济大学信息学院 |
| 学位年度： | 2003 |
| 正文语种： | 中文 |
检索历史
应用推荐
