离散泊位分配装卸量加权延迟最小化策略

杨 斌，岳宇菲

（上海海事大学物流研究中心，上海201306）

0 引言

近年来，经济的全球化和贸易的国际化给港口企业带来机遇的同时也带来了巨大的挑战。港口企业为了提高服务质量和顾客满意度，尽量缩短船舶的作业时间，使船舶等待作业的时间最短。然而，由于不同的船型及其装载量有明显差别，如果简单地将船舶总的作业时间累加，并不能使港口的作业效率达到最优。对于一些大船，因为其日租金较高，在等待过程中消耗的能耗也较大，其延误一个单位时间所付出的代价要远远超过一艘小船在相同时间内所付出的代价。基于此，决策者在做出决策时，不能将大船和小船视为平级，而要使用大船优先策略，通过对所有船舶的作业延迟时间加权来对不同船舶的等级进行区分。

泊位分配问题在国外已有了深入的研究。文献［1］研究了亚洲商业港口的静态泊位分配问题；文献［2］在此基础上进一步研究了港口的动态泊位分配问题；文献［3］将离散泊位分配问题构建为动态调度问题，借用文献［1－2］所构建的模型，设计了拉格朗日启发式算法用在离散的泊位分配问题中，码头被分为了几个有限的泊位，每个泊位每次只能为一艘船服务。而在连续的泊位分配问题中，码头没有固定的泊位分配，只要有空余的位置，合适的船舶就可以靠泊［4］。在连续性泊位分配方面，文献［5］提出了模拟退火算法；文献［6］提出了梯度优化的方法；文献［7］考虑了空间上的水深和船长度等因素，提出了遗传算法，并通过计算得到了很好的解决方案；文献［8］在文献［1－2］模型的基础上提出了以成本最小化为目标的泊位分配问题，并邻域搜索启发式算法对该问题进行了求解；文献［9］研究了动态泊位的数学规划问题，并通过计算实验对不同的情况进行了比较。

而在国内的相关文献中，文献［10］考虑到船舶动态到达的情况，以及实际操作中码头装卸效率对船舶在港作业时间和船舶优先权的影响，以最小化包括等待时间在内的船舶在港停留时间为目标，建立了基于船舶优先权的连续布置泊位分配模型；文献［11］建立了以最小化船舶在港总停时间为目标函数的数学模型，并用遗传算法进行求解，并指出传统的先到先服务的人工分配方式的低效性；文献［12］考虑了体现码头和船公司双方各自的需求指标，使用一种基于禁忌深度局部搜索的模拟退火混合算法，对船舶动态到达情况下的离散泊位调度问题进行求解；文献［13］将泊位问题抽象为二维装箱问题，建立了同时考虑泊位和桥吊资源的整数规划模型，并给出了求解模型的回溯算法。文献［14］建立了集装箱港口集群下多港口多泊位联合调度的多目标非线性决策模型，并设计了改进的遗传启发式算法。文献［15］充分利用码头的岸桥资源，设计出了一种基于合同网协议（CNP）协商机制的岸桥实时调度模型，有效地降低了不确定因素所带来的影响。

虽然上述文献在泊位分配问题研究中提出了水深、船长等物流条件的限制，但没有考虑到在实际运营过程中人为设置的船舶优先权对泊位分配与港口运作效率的影响。本文在离散泊位的基础上，引入服务优先权的思想，根据船舶的装卸量赋予不同的权重，建立以加权后船舶等待时间最小化为目标的泊位分配方案，对比了传统的仅以最小化船舶等待时间为目标的泊位分配方案，并分析了不同的权重值对泊位分配方案的影响。

1 问题描述

泊位调度是指在船舶到港前或到港后，根据各个泊位的空闲情况和物理条件约束对船舶分配合理的停靠泊位、选择合适的靠泊顺序。本文研究的船舶调度问题目的是确定计划周期内船舶分配的泊位位置及进行装卸作业的次序和时间，目标是使不同服务级别船舶总的作业延迟时间最小。

若不考虑船舶的重要性程度，只是以船舶的作业时间最小化为目标函数，这样得到的泊位分配方案没有太大的意义。不同的船舶由于装卸量的不同，其对于港口企业的重要程度也有很大差别。通常来说，装卸量较小的船舶都是一些小船、非定期常来的船舶，装卸量较大的船舶往往是大船，跟港口企业有长期合作的关系，其日租金也会较高，等待一个单位时间所消耗的成本要比那些小船大。因此，若将不同装卸量的船视为平级，简单地相加所有船舶的作业延迟时间，并将其作为港口泊位分配的目标函数，是不合理的。因此，在实际的泊位分配过程中，港口企业要对不同装卸量的船舶区分开来，对装卸量较大的船舶实施优先调度策略。要想对不同的船舶进行区分，就要分别对船舶进行加权，使每一艘船都有对应的权重值。由于船舶的优先权跟船舶的装卸量相关，因此可以根据船舶的装卸量建立以下的加权函数，并结合不同的权值系数来表示不同程度的重要性，从而得到相应船舶的权重值ωi。

其中，wi为船舶的装卸量；wmax为船舶集合V中装卸最大的船舶装卸量；wmin为船舶集合V中装卸最小的船舶装卸量；q为权重系数，ωi为在权重系数为q的情况下船舶i相对应的权重值，q的取值越大，船舶的优先权越突出。

2 模型的建立

2.1 假设条件

（Ⅰ）每条船必须被服务且仅被服务一次（即不考虑移泊情况）；

（Ⅱ）每个泊位上一次只能停靠一条船；

（Ⅲ）船长不超过泊位长；

（Ⅳ）船舶预计到港时间已知，船舶装卸作业开始时间必须晚于船舶到港时间；

（Ⅴ）一艘船从开始装卸到完成之前，不会离开泊位；

（Ⅵ）船舶的在港时间为船舶在锚地的等待时间加上在泊位上的作业时间。

假设条件（Ⅰ）、（Ⅱ）、（Ⅲ）是泊位分配的基本要求，假设条件（Ⅳ）是船舶到港作业的必要条件，假设条件（Ⅴ）是码头对船舶装卸作业的要求，假设条件（Ⅵ）是为了在不影响求解结果的前提下，使建立的模型相对简单。

2.2 模型建立

基于船舶获得的优先权，建立如下的泊位分配模型：

此模型中，V为到港船舶的集合，i＝（1，2，…，I）∈V；Q为港口泊位的集合，j＝（1，2，…，J）∈Q；O为船舶服务顺序，k＝（1，2，…，I）∈O；Si为船舶i的长度；Lj为船舶j的长度；ai为船舶i总的装卸时间；bi为船舶i的到港时间；ωi为船舶i所对应的权重值；zi为船舶i的最长延迟时间；M表示一个足够大的正数。xijk为0～1变量，若船在i泊位以k顺序开始作业，xijk＝1，否则xijk＝0；yijk为船舶i在泊位j以k顺序开始作业的时间；σijk为0～1变量，若i船被分配到j泊位时σijk＝1，否则σijk＝0。

式（2）表示最小化加权后船舶总的延迟时间定义目标函数；式（3）表示每一艘船舶只能停靠在一个泊位上进行服务；式（4）表示泊位j上的第k时间段最多只能有一艘船舶停靠；式（5）表示靠泊船舶的长度不能超过泊位的长度；式（6）表示船舶的开始作业时间必须迟于船舶的到港时间；式（7）表示仅当船舶被分配在泊位j上以顺序k进行作业时，才存在开始作业时间；式（8）是对xijk的限制，保证xijk的取值；式（9）表示船舶i开始作业时间必须大于0；式（10）表示对船舶作业延迟时间的限制，即将装卸量较大的船的延迟时间尽量缩短；式（11）是防止在同一个泊位上的两条船开始作业的时间重叠。

3 仿真算例

3.1 参数设置

为了验证模型的有效性，本文根据港口实际业务情况，选取了48 h内某港口的作业计划作为实例，选择了5个参与作业的泊位和10条船舶的参数数据，泊位1～泊位5的泊位长度分别为150 m、160 m、260 m、280 m、220 m，船舶数据如表1所示。船舶长度（l）、预计到港时刻（T）、预计装卸时间（t）和船舶装卸量（Q）是随机给出的，根据表1给出的数据，可以根据式（1）计算出在不同权值系数的情况下，10条船所对应的权重值。

表1 船舶数据

由于泊位数量的限制，有的船舶到港后并不能立即进行作业，甚至需要等待很长时间。而船舶的优先权直接决定着船舶的最长延迟时间，上文已根据船舶的装卸量和权重系数得到了船舶i的权重，因此，可以引入一个分段函数式来确定船舶i的最长延迟时间：

式中，zi表示船舶i的最长延迟时间；ωi表示船舶i相对应的权重值；参数r1、r2、r3、r4表示权重范围系数；s1、s2、s3、s4、s5表示船舶i在相对应的权重范围内的最长延迟时间。本文选取参数值r1＝1、r2＝2、r3＝3、r4＝4、s1＝24、s2＝12、s3＝6、s4＝3、s5＝1。即可得到10条船在不同权重下船舶i的最长延迟时间。

分别选取了q＝2、q＝3、q＝4这3种情况，并根据以上公式得出了相应的权重值和船舶最长延迟时间，如表2所示。

表2 不同权重系数下的船舶权重值ωi及最长延迟时间zi

3.2 结果分析

3.2.1 加权对泊位分配的影响

根据表1给出的数据，运用CPLEX软件进行编程求解，以权值系数q＝2，设计了不考虑船舶优先权（试验1）和考虑船舶优先权（试验2）的两组试验，见表3。

由于试验1中没有权值系数及相对应的权重值，因此得不到加权后的延迟时间这组数据。本文考虑把q＝2所对应的权重值ωi与试验1中所得到的船舶i的延迟时间（t1）分别相乘，并求和得到10条船的总的加权后的延迟时间，与试验2进行对比。

表3 泊位分配计划

从表3中的两组试验数据对比中可以发现：若将船舶的总延迟时间最小化作为目标，那么不考虑船舶的优先权的情况下，其目标函数值f＝16 h，考虑船舶优先权的情况下，目标函数值f＝44 h。从总的延迟时间上来看，不考虑船舶优先权可能更为有利，然而，船公司所拥有的客户有大客户和小客户之分，其重要性有很大差异，不同的客户等待一个单位时间所付出的成本是不一样的。所以在做出决策时，要将不同船舶的权重值考虑进去，使大客户的等待时间尽可能少，同时让一部分小客户做出牺牲，延长其等待的时间，从而最小化加权后的总延迟时间。取权值系数q＝2，得到考虑船舶优先权时的加权延迟时间f＝0.682 h，为了便于和加权后的方案比较，将q＝2时相对应的权重ωi代入到不考虑权重时得出的方案当中，得到目标函数值f＝4.212 h，显然，不考虑船舶优先权时的加权延迟时间f远远大于考虑优先权时的加权延迟时间f。

因此，对不同的船区别对待，在不影响港口整体作业的前提下，很大程度的提高客户满意度，为企业带来一定的效益。

3.2.2 不同的权值系数对泊位分配的影响

不同船舶的权重值受到q值的影响，q表示权值系数，权值系数越大，大船的优先程度越高。因此，q值的选取直接影响着泊位分配方案。

本文选取权值系数q＝2、q＝3、q＝4进行了3组试验，分别比较了3种情况下船舶加权后总的作业延迟时间，结果见表4。

表4 船舶在不同权重下作业的总延迟时间及加权后延迟时间

由表4可以发现：在考虑船舶权重的情况下，随着权值系数的逐渐增大，船舶总的作业延迟时间变化不大。然而，由于大船的优先程度越来越高，使小船牺牲的利益也越来越大，从而在整体上导致加权后总的延迟时间逐渐增大。

权值系数的选取会对泊位分配产生很大的影响，决策者在制定决策的过程中，要综合考虑到船舶的重要性程度以及整个港口的作业效率，不能只是考虑船舶的优先权问题而使整个港口的作业效率失衡。

4 结论

本文主要研究了静态离散泊位调度问题，基于船舶的不同装卸量，引入服务优先权的思想，否定了把船舶作业延迟时间简单相加作为目标的泊位分配方式，并在已有的泊位分配模型上进行了相关改进，建立了考虑船舶优先权的泊位分配模型。通过对不考虑权重和考虑权重的两种泊位分配方式的对比分析，可以看出引入服务优先权后泊位分配方式的优越性，并指出不同权重系数对泊位分配方式的影响。该模型和泊位分配策略可以使港口企业从实际角度对泊位进行合理分配，对不同重要性的船舶区分对待，为调度人员提供决策支持，同时有效地提高港口作业效率和总体客户服务水平。

［1］ Ima A，Nagaiwa K，Chan W.Efficient Planning of Berthing Allocation for Container Terminals in Asia［J］.Journal of Advanced Transportation，1997，31：75－94.

［2］ Imai A，Nishimura E，Papadimitriou S.The Dynamic Berth Allocation Problem for a Container Port［J］.Transportation Research Part B，2001，35（4）：401－417.

［3］ Dorigo M，Maniezzo V，Colorni A.Ant System：Optimization by a Colony of Cooperating Agents IEEE Trans［J］.Systems Man Cybernet，1996，26（1）：29－41.

［4］ Lim A.The Berth Planning Problem［J］.Operations Research Letters，1998，25（2／3）：105－110.

［5］ Kim K H，Moon K C.Berth Scheduling by Simulated Annealing［J］.Transportation Research Part B，2003，37（6）：541－560.

［6］ Park K T，Kim K H.Berth Scheduling for Container Terminals by Using a Sub-gradient Optimization Technique［J］.Journalof the Operational Research Society，2002，53（9）：1054－1062.

［7］ Nishimura E，Imai A，Papadimitriou S.Berth Allocation Planning in the Public Berth System by Genetic A lgorithms［J］.European Journal of Operational Research，2001，131（2）：282－292.

［8］ Hansen P，Oguz C，M ladenovic N.Variable Neighborhood Search Form inimum Cost Berth A llocation［J］.European Journal of Operational Research，2008，191（3）：636－649.

［9］ Buhrkal K，Zuglian S，Ropke S，et al.Models for the Discrete Berth Allocation Problem：A Computational Comparison［J］.Transportation Research Part E，2011，47（4）：461－473.

［10］ 童珊.基于船舶优先权的集装箱港口泊位分配问题［J］.交通运输工程与信息学报，2012，10（1）：105－110.

［11］ 王军，李卓荣.基于遗传算法的动态泊位分配问题优化研究［J］.中国水运，2011，11（1）：63－65.

［12］ 韩笑乐，陆志强.具有服务优先级别的动态离散泊位调度优化［J］.上海交通大学学报，2009，43（6）：902－905.

［13］ 韩晓龙，丁以中.集装箱港口泊位配置优化［J］.系统工程理论方法应用，2006，15（3）：275－278.

［14］ 毕娅，李文锋.集装箱港口集群下多港口多泊位联合调度方法［J］.计算机应用，2012，32（2）：448－451.

［15］ 孙彬，孙俊清，陈秋双.基于鲁棒反应式策略的泊位和岸桥联合调度［J］.系统工程理论与实践，2013，33（4）：1076－1083.