基于改进遗传算法的泊位岸桥协调调度优化.docVIP

基于改进遗传算法的泊位岸桥协调调度优化 　　摘 要：针对集装箱码头资源调度不合理造成资源浪费的问题，在考虑岸桥装卸成本的基础上，以在港集装箱船总的作业成本最小为优化目标，建立了基于非线性混合整数规划的泊位岸桥协调调度优化模型。为使模型更加接近码头操作的实际情况，模型假设船舶装卸时间依赖于为其分配的岸桥数。采用基于可拓关联函数的改进遗传算法对模型进行求解。改进算法强调了不可行解的重要性，用可拓关联度来衡量种群中不可行解的优劣程度，通过在种群迭代中始终保持一定数量的不可行解来维持种群多样性，从而克服传统算法局部有哪些信誉好的足球投注网站能力较差的缺陷。数值实验验证了模型和算法的可行性和有效性，与不考虑岸桥装卸成本的模型相比，能够有效减少港口资源的浪费。 　　关键词：集装箱码头；泊位岸桥协调调度；遗传算法；可拓关联函数；非线性混合整数规划 　　中图分类号：TP301.6； U691.3 　　文献标志码：A 　　文章编号：1001-9081（2016）11-3136-05 　　0 引言 　　码头资源调度优化一直是集装箱码头管理的难点问题。泊位和岸桥作为码头的主要稀缺资源，其调度问题是影响码头服务水平的重要因素。合理安排船舶的靠、离港的泊位计划以及装卸计划，有利于提高码头资源的利用率，扩大码头通过能力。在实践中，泊位调度和岸桥调度是两个相互关联的问题。泊位调度计划需要岸桥资源的配合才能顺利完成，反过来岸桥计划要以现有的泊位计划为载体。具体地说，一方面，泊位计划依赖于岸桥的分配，船舶装卸时间与为其分配的岸桥数相关；为船舶分配较多的岸桥能够有效地提高船舶装卸效率，然而岸桥资源有限，若分配不合理有可能导致船舶滞港、压船、压货等现象。另一方面，泊位计划也影响着岸桥的分配，泊位分配不合理有可能导致部分岸桥闲置、资源浪费或者岸桥频繁调度、作业冲突。因此，简单的单独调度很难使泊位和岸桥构成的系统达到整体最优，而泊位岸桥的协调调度问题是将泊位和岸桥资源联系起来进行统筹协调，充分考虑泊位调度和岸桥分配之间相互依赖、相互影响的关系，避免了单独调度的局限性，能够有效地减少船舶在港时间，降低船舶总的服务成本。 　　对泊位岸桥协调调度问题的研究主要在模型建立和算法设计两方面。在建模方面，由于码头调度是一个复杂的系统，集装箱码头作业过程中，需要泊位、岸桥、集卡及堆场等装卸资源协同配合，才能使码头的效率达到最优，因此如何建立一个更接近码头操作实际情况的模型，避免模型过于理想化是建模的重点和难点。在求解算法的设计方面，随着船舶和泊位数量的增加，模型解的有哪些信誉好的足球投注网站空间迅速膨胀，因此设计一个快速高效的算法以获得更优的解也是研究的重点。 　　国内外学者对泊位岸桥协调调度问题已经进行了一定的研究：韩骏等[1]假设船舶装卸时间与停泊位置相关，以所有船舶总在港时间最小为目标建立了协调调度模型，该模型允许服务同一船舶的岸桥在不同时刻开始服务；考虑到调度方案对客户满意度的影响，谭盛强等[2]建立了基于船舶服务优先级的多目标混合整数规划模型，以最小化泊位偏离惩罚、推迟离港惩罚、船舶总在港时间、靠泊等待时间为目标，设置不同的惩罚系数来满足不同客户的满意程度；李明伟等[3]针对离散型泊位，以平均集卡运距和所有船舶平均在港时间最小为目标建立了多目标协调调度模型，并采用混沌粒子群算法进行求解；Meisel等[4]在建模中充分考虑了岸桥间相互干扰导致的生产率损失，并采用吱呀轮优化（Squeaky Wheel Optimization， SWO）算法求解；Zhang等[5]假设在装卸过程中，分配给船舶的岸桥数量以及具体的岸桥均是可变的，提出了基于拉格朗日松弛和次梯度优化的算法对模型求解；He[6]为了促进集装箱码头的节能减排，建立了双目标规划以均衡船舶推迟离港的成本和岸桥能耗；Karam等[7]考虑了码头有限的集卡资源，以最小化船舶平均服务时间为目标对泊位、岸桥和集卡进行了协调调度；Bierwirth等[8]针对集装箱码头泊位岸桥调度问题进行了综述。 　　泊位岸桥调度问题的求解是个NP难题，目前常用的求解方法主要是进化算法和启发式算法，包括遗传算法[9-11]、粒子群算法[3，12]、禁忌有哪些信誉好的足球投注网站算法[13]等。采用进化算法求解能够找到理论最优解，然而有哪些信誉好的足球投注网站空间将随着船舶和泊位数量的增加迅速膨胀，从而出现组合爆炸问题。启发式算法的设计则依赖于具体的问题，容易陷入局部最优。 　　本文主要研究集装箱码头泊位岸桥的协调调度问题，具体是指：针对连续泊位，在一个计划周期内，为动态到港的船舶安排停泊时间和停泊位置，并为每艘船舶分配一定数量的岸桥以完成船舶装卸任务。综合考虑船舶到港后等待停泊的时间成本、远离偏好泊位的距离成本、推迟离港的时间成本以及岸桥装卸成本4个方面建立模型，使得船舶总的服务成本最小；同时克服传统