基于分布式混合遗传算法的动态泊位分配策略与仿真何军良,宓为建,谢尘,严伟(上海海事大学物流工程学院,上海200135)摘要:针对集装箱码头的泊位分配问题,提出滚动式优化决策策略,建立基于整数规划的动态泊位分配模型,以连续岸壁线泊位分配为基础,使模型更加接近实际.同时,在该模型的基础上建立码头前沿的泊位仿真模型,采用分布式遗传算法和启发式算法相结合的分布式混合遗传算法求解泊位分配模型.通过对某集装箱码头的案例分析,说明该泊位分配模型和算法的有效性与实用性.关键词:连续岸壁线;泊位;动态分配;整数规划;分布式混合遗传算法;集装箱码头中图分类号:U656.135;N945.12文献标志码:AStrategyandsimulationonberthallocationbasedondistributedhybridgeneticalgorHEJunliang,MIWeijian,XIEChen,YANWei(SchoolofLogisticsEng.,ShanghaiMaritimeUniv.,Shanghai200135,China)Abstract:Totheproblemofberthallocation,arolling2horizonapproachisproposed.Accordingtothisapproach,adynamicallocationmodelisinitiallydevelopedbasedontheintegerprogrammingforberthallocation,whichismoreclosedtorealityastheresultofbasingcontinuumquayside.Atthesametime,asimulationmodelisdevelopedbasedontheberthallocationmodel,andadistributedhybridgenetical2gorithmisemployedforsolvingthemodel,whichcombinesdistributedhybridgeneticalgorithmandheu2risticalgorithm.Acaseapplyingthisapproachonacertaincontainerterminalshowsthevalidityanduse2fulnessofthemodelandalgorithm.要标志之一.泊位是非常重要的港口资源,船舶靠岸前都需要给其预先安排泊船时间和泊位.一般根据每条船舶靠泊该港口的历史数据决定其预靠泊位,再根据预靠泊位进行堆场计划,将要装船的货物靠0引言现代港口作为国际物流供应链的重要环节,能否提供快速、可靠、灵活的综合物流经营服务是其重收稿日期:2007211226修回日期:2008203206基金项目:上海市曙光计划项目(07SG52);上海市能力建设项目(071705107);上海市教育委员会支出预算项目(2008085)作者简介:何军良(1984—),男,四川剑阁人,硕士研究生,研究方向为现代工业工程,(E2mail)soldierlianglian@163.第2期何军良,等:基于分布式混合遗传算法的动态泊位分配策略与仿真53近该泊位通道的箱区中.因此,船舶在靠泊时要尽可能靠近预靠泊位,这样就能缩短装卸船所需时间,即减少船舶在港时间、提高顾客满意度及港口通过率和运作效率,从而使港口获得较高的利润.国内外学者在泊位分配方面进行过一定的研究.IMAI等[1]针对大船和驳船混合靠泊问题,以大船和驳船装卸时间最短为目标,构建线性规划模型并采用遗传算法作为求解算法;CHEN等[2]提出可选择性的网络图(NetworkPattern),并建立考虑到时间和地点的泊位分配网络模型;GUAN等[3]将二叉树和启发式算法结合解决泊位分配这类大规模问题,使完成任务所花的时间最小化.BROWN等[4,5]研究军事港的泊位安排问题,假设泊位是离散的,采用混合整数规划模型描述泊位安排问题.韩晓龙等[6]将泊位分配问题抽象为二维装箱问题,建立同时考虑泊位和桥吊资源的整数规划模型,并给出求解模型的回溯算法.WANG等[7]构建多阶泊位分配决策模型,采用随机定向搜索算法求解该模型.本文提出滚动式优化决策策略,建立基于整数规划的动态泊位分配模型,并在此基础上建立码头前沿的须尽量靠近预靠泊位,否则,在集装箱装船时,势必造成集卡移动的水平距离变长,增加作业时间,延长船舶在港时间,降低码头运作效率,不利于港口企业发展.所以,有必要建立1个模型使船舶靠泊的位置接近预靠泊位.3模型建立假设图1为某港口的前沿情况.图中粗线代表港口前沿的岸壁线,以最小单位1m进行划分,根据岸壁线长度平均分为多段,从左到右、从小到大为岸壁线段编号,然后创建1张岸壁线分段占用表,以确定岸壁线的哪些段被占用、哪些段空闲.图1港口前沿情况3.1建模假设本模型的建立基于以下假设:(1)船舶的停靠方向为朝向左;(2)船舶间不会碰撞;(3)船舶不会停到岸壁线之外.3.2泊位分配模型由于船舶到港信息的不确定性特征,在决策周期已确定的情况下,研究采取滚动式决策策略,决策计划综合考虑近...