基于启发式算法的散货码头排船问题研究

柴佳祺，李 锋，宓为建，杨小明，沈一帆

（上海振华重工（集团）股份有限公司，上海 200125；上海海事大学 物流工程学院 上海 201306）

在港口码头的各类系统中，通常将矿石、煤炭、散粮、散装水泥等专业化泊位称为散货码头.散货码头的核心资源有泊位、装卸机械、装卸堆场等，其中泊位是指在港内为了进行装卸给船舶停泊靠岸并有一定长度岸壁的地方.船舶在靠、离泊时，所需的岸壁线长度要大于船舶长度.泊位属于码头的稀缺资源，近年来不断增长的散货流量给码头提出了更高的要求，而排船计划的质量是关系到码头生产作业质量的重要因素，因此如何更好地利用有限的岸线空间、提高煤炭运输量和运输效率、减少船舶的在港时间一直都是研究的热点与难点.

针对码头泊位分配问题很多国内外学者进行了相关研究.KIM等［1］运用混合整数模型来描述泊位分配问题，以船舶延迟离港和船舶偏离最优位置产生的额外费用最小化为目标，并应用模拟退火算法（SA）求得该模型的近似最优解.IMAI等［2］为解决集装箱船舶大型化和码头岸线资源有限的问题，建立了锯齿形岸线的泊位调度模型，提高了泊位的利用率.LEE等［3］建立了混合整数规划模型，利用遗传算法获取最优解.BIERWIRTH等［4］针对泊位安排和岸桥调度的联合问题进行了研究.EDUARDO等［5］提出了禁忌搜索方法，并结合混合启发式算法讨论了动态泊位的分配问题.LIM等［6］以任意时刻下岸线空闲长度的最小化为目标，提出了连续型泊位的调度问题.假设到港船舶无须等待，可立即靠泊作业，并且在离港之前不存在移泊现象.PARK等［7－8］综合计算了船舶延迟离港和未停泊在最优位置所产生的额外费用.IMAI等［9］对于离散型的泊位调度问题，按最大靠泊船舶的长度对岸壁线进行了划分，运用启发式算法求解模型.国内学者张煜等［10］将岸线连续化，建立了泊位动态调度模型，通过仿真将连续型泊位调度与离散化泊位调度进行了分析和比较.王红湘等［11］按照岸线有限的泊位分配原则，建立了动态泊位分配的数学模型，并采用启发式算法对该策略进行了模拟和优化.何军良等［12］按照滚动式计划模式，建立了基于整数规划的动态泊位调度模型，并采用分布式遗传算法和启发式算法相结合的分布式混合算法求解了泊位调度问题.CHANG Daofang等［13］采用滚动式计划模式建立了泊位－岸桥联合调度模型，然后利用遗传算法和启发式算法相结合的混合算法求解模型.

以上研究大多是针对集装箱码头的泊位分配问题，构建数学模型并通过合理的算法解决相关问题的.然而对于散货码头的连续性泊位分配问题，很少有人通过相应算法进行求解，也未给出详细的计划编制表供调度人员参考.因此本文采用启发式算法求解连续性泊位的船舶靠泊计划问题，计算并验证该算法应用于实际生产作业的效果，以提高码头的生产效率及服务水平.

1 排船问题描述

国内大部分散货码头在做船舶靠泊计划时，首先考虑船舶吃水和码头水深的关系，在确保安全靠离的前提下遵循“先外贸再内贸”、“先干线后支线”、“先到锚地先靠”的原则，同时兼顾堆场、靠泊位置和各装卸机械的所在位置，对船舶的靠泊位置与离泊时间做统筹安排.随着船舶大型化的发展，越来越多的散货码头开始关注优化散货船的可装载量以及在港时间，以求获得更大的经济收益.

目前港口码头按照实际作业情况，将整个码头岸线均匀地分为若干个小单位.在考虑安全距离的前提下，根据到港船的船长，停靠在相应若干个小单位组成的泊位区段上，这样可以有效增加泊位岸线的利用率.

散货码头的泊位沿线有一定数量的缆绳桩，每当船舶靠泊时，船舶上的缆绳将会被固定于缆桩，以完成靠泊作业.船舶占用的泊位长度可以通过该船映射的缆绳桩头尾之间的距离来确定，并将此长度反映为缆绳桩间距的整数倍.在实际操作中，一个桩位只可作用于一艘船，即使相邻桩位间留有一定距离，甚至可以容纳一条船，也不能将相邻船舶系在同一根缆桩上.实际排船的二维图形如图1所示.

图1 排船分配的二维示意图Fig.1 Two－dimensional diagram of berth allocation for vessels

图1中横坐标表示码头泊位岸线，最右端的数值代表岸线总长度，所有船舶的停靠位置都不能超过横坐标的范围；纵坐标表示码头生产管理的时间维度.所有船舶的靠泊作业都可用一个矩形框表示.其中，矩形的横边（Ei－Si）表示所占用的泊位岸线长度（其中包含了为避免船体碰撞所预留的安全距离），矩形的纵边（Eti－Bti）表示在泊作业时间.矩形左下角坐标（Si，Bti）和（Sj，Btj）分别为靠泊船头位置和靠泊时间，同理：（Ei，Eti）和（Ej，Etj）分别为靠泊船尾位置和离泊时间.

这样，排船问题就转化成了上述约束条件下的矩形排列问题，所有矩形框的集合就是调度人员排船的规划方案.在实际的生产实践中，有经验的调度人员在绝大多数情况下会针对性地选择多种排位顺序作为辅助参考，以优化作业总量和船舶在泊时间为前提，做出有效合理的安排与调整，提升散货码头的整体生产作业质量.

2 排船数学模型

2.1 模型假设

数学模型的建立基于下列假设：① 每艘船根据自身条件、货物配载量及到港时间配置以较优的靠泊位置，考虑船舶都在计划好的靠泊时间准时到港，并且都是空船到达码头，等待靠泊并进行装船作业.② 装卸机械足够，且船舶装卸效率沿码头岸线固定.③ 船舶之间预留安全净距离，可互不影响地进行作业.④ 靠泊位置始末决定了所占用的岸线长度，靠泊时间始末决定了在港作业的总时间.⑤考虑在计划开始时刻泊位岸线皆为空闲状态.⑥ 在港作业时间包含从锚地到泊位的行驶时间与从泊位驶离港口的时间，即船舶到港时泊位岸线上若有空闲位置，认定该船到港时刻为船舶靠泊时间，亦即无延迟靠泊，靠泊结束时刻为离港时间.⑦散货船舶按计划次序沿着岸壁线从左至右编排.

2.2 模型描述

2.2.1 目标函数

目标函数1：单位岸线长度装船容量最大化.

式中：L为岸线长度，即泊位总长度；s为规定排船周期（如日泊位计划24h）到港船集合（i＝1，2，3…s）；i，j指任意船舶，i，j∈（1，2，3…s）；Xi为决策变量，若船舶i靠泊，则Xi＝1，否则Xi＝0；Ci为船舶i的载重量，i∈s（i＝1，2，3…s）.

目标函数2：单船延迟靠泊时间最小化.

式中：Bti为船舶i的靠泊时间；Ati为船舶i的到港时间.

总目标函数：

式中：w1，w2为权重.由于两个子目标的计算量纲不同，因此要对目标函数做出转换，如式（4）—（6）所示.

式中：Ti为船舶i的装卸作业时间.

2.2.2 约束条件

（1）保证船舶的靠泊位置在岸线范围以内

式中：Pi为船舶i的中心位置，i∈s（i＝1，2，3，…，s）；Li为船舶i长度，i∈s（i＝1，2，3，…，s）.

（2）船舶i靠泊后装卸作业的开始时间不能早于船舶的到港时间.

（3）在港船舶i接受装卸处理的结束时间要早于船舶i的离港时间.

（4）要求泊位的空闲长度要大于船舶的自身长度.

（5）对于停靠在泊位上的所有船只，占用的装卸设备不能超过码头所能提供的机械总量.

式中：Qi为分配给船舶i的机械数量，i∈s（i＝1，2，3…s）；q为机械设备数量.

（6）要求靠泊船舶在时间维度交叉冲突的情况下空间位置不重叠.

式中：Ei，Ej为船舶i，j的靠泊止位置，即船尾位置；Si，Sj为船舶i，j的靠泊始位置，即船头位置.Sij为决策变量，若船舶i和j到港时间交叉，则Sij＝1，否则Sij＝0.

（7）要求靠泊船舶空间维度不交叉冲突（此约束下，无论时间维度是否重叠，都不会发生船舶碰撞）.

式中：Eti，Etj为船舶i，j的离泊时间；Pij为决策变量，若船舶i和j靠泊位置交叉，则Pij＝1，否则Pij＝0.

（8）保证岸线上任意位置及任意时刻最多被1条船占用.

3 排船算法

港务码头公司对排船的实施控制具有主动性，事先通过船代公司获得每艘船的数据信息，并根据这些信息制定船舶的靠泊、装卸等作业计划［14］.船舶在泊生产作业的时间和单船作业量对港口的经济收益有重要影响，是排船问题中的关键因素.

本文运用启发式排船算法，在保证求解速度的前提下能获取最优解.该算法的流程如图2所示.

图2 启发式算法流程示意图Fig.2 Flowchart of the proposed heuristic algorithm

步骤1 选择符合计划期的船舶初始信息，根据配载量从大到小进行排序，总量为s.

步骤2 从i＝1开始循环，给到港船舶进行泊位分配.

步骤3 根据船舶i的进港时间及配载量计算船舶的装卸作业时间，由此得到靠泊的时间范围.

步骤4 安排船舶靠泊位置的规则是沿着岸线从左向右排列，即第1艘船的靠泊始位置为码头最左端，依据占用的泊位长度计算出靠泊末位置.根据靠泊始末位置计算得出对应的缆桩始末位置.

步骤5 预先做出该时刻码头岸线有无空闲泊位的判断.若有空闲泊位，继续分析当前计划的船舶p与已排船舶t在作业时间上有无冲突.若冲突，进入（1）；若不冲突，则进入（2）.若船舶p到港时无空闲泊位，则进入（3）.

（1）把船p的矩形框排放在t的右边（遵循从左往右排的规则，直到超出长度范围为止），即缆桩的起始位置紧邻船t所在缆桩的末端位置.

（2）将当前船p排放在码头最左端.

（3）对该船进行延时装卸作业，相应的靠泊时间段要做延后调整，同时排船规则依旧遵从（1），（2）.

步骤6i＝i＋1，若出现下述两种情况，计算终止.

（1）如果i大于总船舶数s；

（2）现有的时间、空间范围已无空闲区域可供船舶靠泊.

否则，重复算法步骤3—5.

上述过程中，在完成一艘船的配载任务后，随即对现有船信息进行更新，表示该船已做好排船计划，同时进入安排下一条船的预备状态.此算法保证了码头的装船总量最大，根据到港时间、配载量和所占用的泊位长度，尽量多地往二维图中排放矩形框，直到无可放空间为止.

4 案例分析

各类散货在码头的装卸作业具有一定的共性，本文以出口型散货煤码头为研究对象，码头的基本配置以出口为前提条件，所构建的模型和算法求解同样适用于其他类型的散货码头.

选取国内某港煤码头2011年10月11日16∶00至12日16∶00所有的到港船舶作为实际研究案例，共30艘船.其主要内容包括：船舶代码、占用的泊位长度、配载量和到港时间，如表1所示.案例所讨论的是日泊位计划，目的是将足够多的船舶编制排入24小时的排船计划中.需要说明的是，这些船舶都是空船到港，靠泊后进行装船作业，而且不管任务是否做完，都算入当日装船总量.

采用Power Builder11.5构建排船辅助系统，其中启发式算法的计算模块如图3所示.

计算说明：划分桩位，设定25m为一个小单位的泊位长度，煤码头岸线总长度为1 000m，则缆桩数为1 000／25＋1＝41个.从“占用的泊位长度”一栏，可以用对应的数值除以25，向上取整后得到缆桩与缆桩间共占用几小段.例如，若长度为168m，则占用7小段，即从B1至B7，是该船的停靠位置，其他船在此时刻就不予停靠在与其有交叉的位置上.为方便计算，假设单位为1 000t的作业时间需要20min.如一艘船的装载量为4 000t，其靠泊时间就是80min.因此船舶i的靠泊时间段为［进锚地时间，进锚地时间目标函数中的权重w1和w2都设为1（可根据实际作业情况作相应调整），求解结果如图4和表2所示.

表1 煤码头初始数据表（30条船）Tab.1 Initial datasheet for the coal terminal

图3 启发式算法模块Fig.3 Heuristic algorithm module

图4 启发式算法二维效果图Fig.4 Two－dimensional result by heuristic algorithm

表2 煤码头排船计划编制表Tab.2 Table showing the vessel scheduling at coal terminal

续表2

煤码头的常规排船策略是运用“先到锚地，先安排泊位”的方法，即FCFS.在此综合比较两组求解结果，如表3所示.

表3 排船结果比较Tab.3 Comparison of scheduling results

从表3可以发现：在装船量和延迟靠泊时间这两个评价指标上，启发式算法有一定的优势，能多排入一艘船，装船量相比多了9 000t.比较后面两个指标，发现传统排船方法的延迟情况比较严重，单船平均延迟靠泊时间大于30min，采用启发式排船策略则可将单船延迟靠泊时间降低到22.06min.

上述分析表明，启发式算法对于求解现有散货码头的排船问题有现实意义，对于提高码头的经济效益有积极作用.码头调度人员也能很直观地参考二维图制定规划，针对码头的实际作业情况进行调整，得到较为科学可靠的结果.

另外，从船舶的初始数据信息可以看出，配载量较大的船舶有时会集中进港.如果不及时对装载量较大的船舶进行靠泊，则会在船舶数量很多、来不及作业的情况下，无法排入当天的排船计划，出现压港或者延迟靠泊的现象.所以启发式算法的好处在于为配载量大的船舶先安排靠泊，与之相比，“先到先靠”的传统方法，没有考虑船舶配载量，只按照进港秩序进行编排，这样的运行模式缺乏一定的经济合理性.

5 结语

本文针对散货码头泊位分配的具体现状，深入研究排船策略.根据码头生产管理的相应原则，构建综合考虑装船容量和延迟靠泊时间的优化数学模型，在模型基础上利用启发式算法进行求解.实例验证表明，该模型和算法能在一定程度上增加配载总量及降低船舶延迟靠泊时间，对提高散货码头的生产作业效率和服务水平有一定的指导意义，证明该排船计划模型和启发式算法的有效性和实用性.

［1］KIM K H，KIM H B.The optimal determination of the space requirement and the number of transfercranes for import containers［J］.Computers and Industrial Engineering，1998，35（3）：427－430.

［2］IMAI A，NISHIMURA E，PAPADIMITRIOU S.Berth allocation at indented berths for mega－containerships ［J］.European Journal of Operational Research，2007，179（2）：579－593.

［3］LEE D H，HUI Q W.Integrated discrete berth allocation and quay crane scheduling in port container terminals ［J］.Engineering Optimization，2010，42（8）：747－761.

［4］BIERWIRTH C，MEISEL F.A survey of berth allocation and quay crane scheduling problems in container terminals［J］.European Journal of Operational Research，2010，202（3）：615－627.

［5］EDUARDO L R，BELEN M B，MARCOS M V.Artificial intelligence hybrid heuristic based on tabu search for the dynamic berth allocation problem ［J］.Engineering Applications of Artificial Intelligence，2012，25：1132－1141.

［6］LIM A.The berth planning problem ［J］.Operations Research Letters，1998，22：105－110.

［7］PARK K T，KIM K H.Berth scheduling for container terminals by using a sub－gradient optimization technique［J］.Journal of the Operational Research Society，2002，53：1054－1062.

［8］PARK Y M，KIM K H.A scheduling method for berth and quay cranes［J］.OR Spectrum，2003，25：1－23.

［9］IMAI A，NISHIMURA E，PAPADIMITRIOU S.Berth allocation in a container port：using a continuous location space approach ［J］.Transportation Research：Part B，2005，39：199－221.

［10］张煜，王少梅.基于遗传算法的泊位连续化动态调度研究［J］.系统仿真学报，2007，19（10）：2161－2164.ZHANG Yu，WANG Shaomei.Dynamic scheduling of continuous berth based on genetic algorithm ［J］.Journal of System Simulation，2007，19（10）：2161－2164.

［11］王红湘，严伟.基于启发式算法和仿真优化的岸壁线长度泊位分配策略 ［J］.上海海事大学学报.2008，29（1）：19－22.WANG Hongxiang，YAN Wei.Quay－length－based berth allocation strategy on heuristic algorithm and simulation optimization［J］.Journal of Shanghai Maritime University，2008，29（1）：19－22.

［12］何军良，宓为建，谢尘，等.基于分布式混合遗传算法的动态泊位分配策略与仿真 ［J］.上海海事大学学报，2008，29（2）：52－57.HE Junliang，MI Weijian，XIE Chen，et al.Strategy and simulation on dynamic berth allocation based on distributed hybrid genetic algorithm ［J］.Journal of Shanghai Maritime University，2008，29（2）：52－57.

［13］CHANG Daofang，JIANG Zuhua.Integratin berth allocation and quay crane assignments［J］.Transportation Research：Part E，2010，46：975－990.

［14］邓恢华，欧凡.港口运行机制与排船决策影响因素分析 ［J］.商场现代化，2008（4）：156－158.DENG Huihua，OU Fan.The analysis of port operational mechanism and influential factors for vessel scheduling［J］.Market Modernization，2008（4）：156－158.