分布式决策下的集装箱码头泊位分配研究

张恒 全雄文 徐亚 陈增强

[摘要]为减少船舶废气排放和优化集装箱码头资源配置，建立了分布式决策环境下的泊位和岸桥联合调度模型，将船舶和码头看作相互独立的决策主体，船舶优化航速及抵港时刻，码头则优化自身泊位及岸桥分配。采用多回合组合拍卖方法，将泊位服务时段看作特殊商品，港航双方就泊位分配反复协商达成一致，相比于以码头作为集中决策者的集中式决策方案更易于被船舶方接受。数值实验表明，分布式决策模型求得的分配方案相比于传统固定抵港时问策略能够有效减少船舶燃油消耗及在港等待时问，降低船舶废气排放。

[关键词]水路运输；泊位分配；组合拍卖；集装箱码头；分布式决策

[中图分类号]U656.1+35；N945.12 [文献标识码]A [文章编号]1005-152X（2018）02-0034-07

1 引言

近年来，船舶废气排放问题受到社会广泛关注，这些废气将对港区环境和居民健康产生不利影响。以香港为例，2013年水上运输仍是该市最大的S02、NOx、PM10、PM2.5排放源，排放贡献率分别达到了50%、31%、36%、42%，在所有船舶中，远洋集装箱船是最大排放源。航运减排措施可分为三类：技术手段、运营手段和市场手段，。目前的研究和实践多集中于技术手段，而对后两者的研究还不多。泊位是港口的稀缺资源，泊位分配不仅影响码头自身的运营效率，还影响船期可靠性，因此，泊位分配是港航双方通过协作来推进节能减排的重要契合点。对此，Golias等采用可变抵港时间（Variable ArrivalTime，VAT）策略，将船舶抵港时间视为决策变量，间接考虑了船舶在港期间的废气排放。Lang和Veen-stra等建立了港航合作下的泊位分配模型，使得燃油成本、机会损失和延误惩罚之和最小化。Du等采用更加精确的燃油消耗函数，对燃油消耗量和主要废气排放量做了定量分析。这些研究表明，相比于固定抵港时间（ Constant Arrival Time，CAT）策略，通过优化抵港时间可以降低船舶燃油消耗与废气排放。

但是，这些研究都是以码头作为集中决策者来制定泊位分配方案，其存在两方面的问题：首先，大多数船舶出于商业竞争考虑并不愿意将私有信息传递给码头，如燃油消耗信息；其次，集中式VAT策略要求船舶依照码头所指定的航速航行，忽略了船舶方的自主性，降低了船舶参与合作的积极性，不利于策略的推广实践。

为克服以上两点不足，本文将码头和船舶看作相互独立的决策主体，在分布式决策环境下研究泊位和岸橋联合调度问题。由于每个主体在决策时都从自身利益出发，经常存在相互冲突的情况，所以需要协调以得到可行方案。组合拍卖作为一种有效的市场机制，可以保护好主体的独立性和私有信息，被广泛应用于资源分配问题，如机场跑道分配、分布式火车调度等。针对问题的特点，本文设计了基于多回合组合拍卖的泊位分配机制，船舶无需在每一回合中对所有可能时段组合进行估值，减轻了船舶方的计算负担，包括投标决策、中标决策、价格更新、拍卖流程四个方面的设计。这样更有利于VAT策略应用于实践，丰富节能减排运营手段和市场手段的研究。

2 问题描述

在分布式决策环境下，船舶自主决策航速及抵港时间，码头优化泊位及岸桥分配。船舶决策时主要考虑船期可靠性和航次成本，其中航次成本除去固定成本外主要包括燃油费及港口费用，因此，可将港口费用作为中间量用于双方协商。本文将泊位使用时段（Time Slot）看作一种特殊商品，码头作为资源主体向各船拍卖使用时段并制定中标决策，船舶则竞拍所需时段并支付相应费用（即港口费用）。同时，码头可根据投标情况及时调整时段价格，从而引导船舶避开高峰期。考虑到使用时段的互补性，即船舶需获得一段连续的使用时段，本文采用多回合组合拍卖的方法，双方通过协商达成一致意见。希望通过港航间的这种协商机制来降低船舶燃油消耗和废气排放，提高码头服务水平。

为便于建模，基于以下假设进行研究：

（1）泊位为同质离散泊位，且物理条件满足任一来港船舶停泊要求；

（2）船舶一旦开始装卸作业，不允许中断；

（3）船舶在投标时采用最佳近似投标策略nu；

（4）不考虑船舶对泊位位置的偏好及岸桥移动约束限制。

3 模型建立

3.1 数学符号

对本文中出现的数学符号定义如下：

H—计划期长度；

T一泊位使用时段集合，T={1，2，…，H）；

V-船舶集合，共n艘船，V={1，2，…，n）；

B-泊位集合，共m个泊位，B={1，2，…，m）；

li—初始时刻，船i距离码头的距离，i∈V，单位：海里；

a0i—船i预计抵港时刻，i∈V；

di一船i要求最晚离港时刻，i∈V：

hi—船i装卸作业量，i∈V，单位：岸桥工时；

p—燃油价格，单位：美元/t；

Q—码头可用岸桥总数；

rmini，rmaxi—每时段至少和最多为船i分配的岸桥数，i∈V；

qi一码头每时段为船i预计分配的岸桥数，qi= （rmini+rmaxi）/2，i∈V；v0i—船i计划服务航速，i∈V，单位：节；vmini，vmaxi一船i最小和最大航速，i∈V，单位：节；ai，ai—依离港距离和航速范围计算出的船i最早和最晚抵港时刻，i∈V；Ai—船i可能抵港时刻的集合，i∈V，Ai=

Faii一船i以时刻ai抵港时对应的燃油消耗量，i∈V，ai∈Ai，单位：t；

λit一对船i，第t时段的价格，i∈V，t∈T，单位：美元；

Ci—船i港口费用预算，i∈V，单位：美元；

M—足够大的正数。

3.2 投标决策

基于最佳近似投标策略，船舶在每回合竞拍时选择使自身成本最小的时段组合进行投标。在计算燃油成本时，采用的单位时间燃油消耗函数为：

其中，c0，c1为回归系数，v为航速。考虑到燃油消耗函数非线性带来的求解困难，本文采用离散化方法进行处理，计算出不同抵港时刻对应的燃油消耗量。

对船i，i∈V，其投标决策模型如下：

决策变量：

yi一船i靠泊时刻；

zit—0-1变量，若占用t时段则取1，否则取0，t∈T：

Uaii—0-1变量，若以时刻ai抵港则取1，否则取0，a∈Ai。

辅助决策变量：

ei—船i离港时刻；

其中，目标函数为最小化航行成本（燃油成本和港口费用）与离港延误时间加权和，Ni1和Ni2为标准化因子，用于消除量纲影响，（ei-di）+=max{ei-di，0}；式（4）表示需选择一个抵港时刻；式（5）表示靠泊时刻不得早于抵港时刻；式（6）表示装卸作业完成后才能离港，依预计分配岸桥数来计算；式（7）定义了所需时段的数目；式（8）和（9）要求所占用时段是连续的；式（10）表示所支付港口费用不能超过预算。

求解模型后，船i将（i，yi，hi，si，bi，wi）发给码头进行投标，其中，yi为最早靠泊时刻；hi为装卸作业量；si= max{ei，di}为该标要求最晚装卸完工时间；bi=表示船舶支付的费用；wi为状态变量，若ei≤di则取1，否则取-1。

3.3 中标决策

码头得到本回合所有投标后，通过求解竞胜标模型来确定中标船舶及分配方案。码头可通过调整岸桥分配来影响船舶实际装卸作业时间，可看作一个加工时间可控的调度问题。

决策变量：

θ-0-1变量，若船i中标则取1，否则取0，i∈V：

xy—0-1变量，若船i停靠泊位j则取1，否则取0，i∈V，j∈B；

Rit一在t时段为船i分配的岸桥数，i∈V，v∈T：

σii'—0-1变量，等于1时表示船i'在船i离开后才靠泊，i，i'∈V，i≠i'；yi一由码头决策的船i实际靠泊时刻，i∈V。辅助决策变量：rit—0-1变量，在t时段，若安排岸桥为船i服务则取1，否则取0，i∈V，t∈T；

ei一由码头决策的船i实际离港时刻，i∈V。

其中，目标函数第一项表示最大化港口收益，第二项是为了优化船舶离港时刻，对中标船舶i，若wi=1，则可使e尽量接近si，若wi=-1，则表示若在s，离港将产生延误，因此需尽量早点离港；式（ 14）-式（15）表示仅对中标船舶分配泊位及岸桥；式（16）表示安排在同一泊位的船舶不应有时间冲突；式（17）表示分配的岸桥数不能超过码头所拥有的岸桥数；式（18）表示每时段为船舶分配的岸桥数限制；式（19）—式（21）表示装卸作业不能中断；式（22）表示需完成中标船舶的装卸作业；式（23）—式（24）表示实际靠泊和离港时刻应在船舶所投标的时段区间内；式（25）表示当σ长城ii'=1时，ei≤yi'成立。

3.4 价格更新机制

为促使船舶投标时段分布更加均匀，减少冲突现象发生，码头采用基于拉格朗日松弛算法的价格更新机制来引导船舶投标，具体如下：其中，为第k+1回合船i第t时段的价格，为拍卖开始时船i每时段的保留价格，勾时段t能力约束的次梯度，sk为步长。

其中，α是一个常数，UB和LB分别为第k回合码头目标函数的上下界。

3.5 拍卖机制设计

拍卖机制步骤如下：

Step 1：初始化。码头向将在计划期内抵港船舶公布时段初始价格，由于码头通常会根据船舶大小不同安排不同数量岸桥进行装卸作业，所以初始价格采取了差异化定价方式，并置回合计算器k=0。

Step 2：投标决策。在回合k，每艘船先判断自己在上一回合是否中标，如果中标，则无需投标；否则，根据当前时段价格求解投标模型再次投标。

Step 3：码头决策。码头收集当前回合所有投标，结合上一回合的中标结果，求解竞胜标模型，得到本回合临时分配结果，若所有船舶均中标则拍卖结束；否则，转Step 4。

Step 4：价格更新。依照式（30）更新时段价格，置k=k+l，转Step2。

3.6 CAT策略模型

本文以传统CAT策略为对照组，码头计划人员将抵港时间看作一个常量，以最小化离港延误时间之和为目标制定集中式分配方案。约束条件同式（ 16）-式（21），式（25）-式（28）

4 數值买验

为分析分布式决策模型（ Decentralized Decision-making Model，DDM）性能，进行数值实验。以72h为计划期，单位时间为1h，码头共有4个泊位和12台岸桥，船舶分为Feeder、Medium、Jumbo三种类型，比例为4：5：1。按船舶数目不同，设计了5个测试问题。对每个测试问题，按如下方式随机生成15个实例：（1）基本参数按表1所给区间均匀分布产生；（2）船舶其它参数，a0i～U[1，60]，li=a0iv0i，di=a0i+hi/qi·U[1，1.5]最小航速取经济航速vmini=[c0i//（μi-1））]1/μ，最大航速分别为vmaxi=24，26，28，ai=li/vmaxi，ai=li/vmini；（3）价格参数，Ci=λ0ihi/qi·U[1.5，3]，p=400，对于λ0i，主要考虑装卸费用，假设每台岸桥装卸效率77= 30 TEU/h，集装箱装卸费c= 60 USD/TEU，对于这三种船舶，每时段预计分配岸桥数qi= 1.5，3，5，所以相应λ0i=2700，5 400，9000 USD；（4）其它参数，Ni1=pFa0ii+cηhi，Ni2=1，α=2。

在MATLAB环境下采用YALMIP建模，调用CPLEX 12.6求解，电脑配置为2.93GJHz CPU和4GB内存。

4.1 经济和环境效益分析

为比较DDM策略与CAT策略在经济和环境效益上的表现，将总等待时间、总离港延误时间、船舶总油耗三项主要指标汇总，见表2，表中数值为15个测试实例的平均值。可见，在DDM策略下，（1）经济效益方面，燃油消耗明显下降，可省油14.0%-16.4%，平均每艘船省油20.3-26.Ot，而且在港等待时间减少78%以上；（2）环境效益方面，由于燃油消耗的降低及在港等待时间的减少，船舶航行及在港期间的废气排放可以大大减少；（3）延误时间有所增加，这主要是因为在分布式决策环境下，船舶参与决策，码头不再作为决策主导者拥有所有信息并以总延误时间最小为唯一目标，另外，设置的港口费用预算约束对此也有一定影响。

为进一步分析燃油节省效果，将DDM策略与集中式VAT策略结果对比，如图1所示。在集中式VAT策略下，码头以总燃油消耗和延误时间加权和最小化为目标制定集中式决策。DDM策略下的船舶节油量达到集中式VAT策略下节油量的90%左右，因此，DDM策略的节油效果十分明显。

下面对港航双方收支情况进行分析，如图2所示。相比于CAT策略，在DDM策略下，对船舶而言，一方面燃油费用会有所减少；另一方面由于船舶首次投标时的竞标价约等于CAT策略下的港口费用，随着拍卖的进行，港口费用会有所增加，也就意味着码头收益会增长。不过将两者相减，船舶总成本仍然降低了3.1%-7.3%。这对实际运营有一定指导意义，首先，通过拍卖方式对时段进行定价，可以更好地反映不同时段的市场价格和供求关系；其次，通过制定合适的初始时段价格可以取得双赢的效果，一方面降低船舶总成本，同时增加码头收益，有利于策略的实行。

4.2 拍卖效率分析

图3为拍卖所需回合数的统计，码头可通过优化岸桥分配调节船舶实际装卸所需时问，从而优化配置，使得港航双方能够通过较少回合便得到最终分配方案。

需指出的是，仅通过一同合便结束拍卖并不代表首轮投标没有冲突，而是码头通过优化泊位和岸桥分配予以解决。以实例65为例，该例有20艘船，表3为各船首轮投标情况。统计各时段需求次数，如图4所示，即便不考虑岸桥是否充足，仍有多个时段的需求次数大于码头所拥有的泊位数，因而存在冲突。另外，对于船15，通过求解投标模型，得到离港时刻为23，投标时却取28，这样做的日的除了给予码头更大的自由度外，更主要的原因是船舶自身希望能够在不延误的情况下晚点离港，从而以更低航速航行，进一步节省燃油费用，而不必增加港口费用。

通过求解竞胜标模型，该例分配方案如图5所示。由于模型目标函数第二项所起的作用，船15實际靠泊时刻为16，有利于进一步降低油耗；而对于船11，码头则通过分配使其提前离港，避免了产生延误，这正是船舶所希望得到的。

5 结语

本文研究了分布式决策环境下的集装箱码头泊位和岸桥联合调度问题，将船舶和码头看作相互独立的决策主体，设计了基于多回合组合拍卖的分配机制，这样更有利于VAT策略应用于实践。数值实验表明，相比于CAT策略，DDM策略能够有效降低船舶燃油消耗及在港等待时间，从而降低废气排放。并且，通过拍卖泊位服务时段，在降低船舶运营成本的同时也可以增加码头收入，取得双赢的效果。本文的研究还可进一步深入和完善，第一，对拍卖机制进行改进，研究如何进一步减少离港延误时间；第二，设计相应算法，提高求解速度。