摘要: 针对群岛泊位分配问题，以船舶总在港时间为优化目标，建立了群岛泊位分配问题模型，并提出了一种混合粒子群算法进行求解。该算法中，在更新粒子状态时加入模拟退火和免疫调节操作，增强了粒子群算法的全局搜索能力。此外，该算法中所发展的分段编码法使得粒子解码后能满足船舶类型约束。最后，以舟山群岛大宗商品泊位分配问题为例，通过实证研究，验证了混合粒子群算法的有效性。

关键词:  群岛泊位分配    混合粒子群算法    模拟退火    人工免疫

一、引言

2011年6月30日， 国务院正式批复同意设立浙江舟山群岛新区。舟山群岛新区将逐步建成中国大宗商品储运中转加工交易中心。群岛泊位分配问题是群岛物流体系建设和发展的焦点问题，科学合理的泊位分配方案能够有效提高港口的作业效率，减少进港船舶的在港时间，从而提高国际物流岛的运营效率和服务质量。

一直以来，泊位分配问题( Berth Allocation Problem，BAP)的研究受到了国内外学者的广泛关注，Steenken 等人对此做了较为全面的总结。日本的著名学者Imai从不同的角度对BAP做了大量的研究: 1997 年，针对亚洲的集装箱港口研究了静态BAP[3]; 2001 年，针对公共泊位系统研究了动态BAP[4]; 2005 年,对比研究了连续型BAP和离散型BAP及其优缺点[5] ; 2008年,针对多用户集装箱码头研究了泊位和起重机联合调度问题[6]。L0kuge等人[7]研究了集装箱港口的自动泊位分配问题，提出应用智能软件系统管理港口的运营。Wang等人[8]将泊位分配问题转化为一个多阶段决策问题，提出了一种随机集束搜索算法寻找有效边界。Seyedalizadeh 等人[9]提出了一种基于遗传算法( GA)的连续型BAP求解方法。Rudinei等人[10] 提出了一种基于模拟退火( SA)的聚类搜索(CS)方法求解BAP。杜玉泉等人从行为运筹学的角度，采用深度集成的方法研究了面向服务的泊位和岸桥联合调度问题。国内外学者在BAP方面的研究都已较为成熟且深入。但是对于多品种大宗商品在群岛环境下的泊位分配 问题 (Archipelago Berth Allocation Problem，ABAP) 的研究，还没有引起关注。

本文研究动态环境下的ABAP，所谓的动态是相对于静态而言(在调度时,所有的船舶都已抵港等待靠泊),指所考虑的船舶可以在其他船舶靠泊后才到达。首先根据ABAP的特点，  考虑港区距离、货物品种、泊位类型与水深、航道水深等因素，以船舶总在港时间为目标函数，构建ABAP模型; 其次，在离散粒子群( DPSO) 的基础上，结合模拟退火法、人工免疫算法，设计了一种适用于求解 ABAP的混合粒子群算法( HPSO) ; 最后，以舟山群岛大宗商品泊位分配问题为例进行实证研究，将本文提出的 HPSO算法与DPSO算法进行对比分析。