考虑服务公平性的连续泊位-岸桥集成分配

郝杨杨， 李军军， 黄有方

(1.上海海事大学 物流研究中心， 上海 201306； 2.上海海事大学 商船学院， 上海 201306)



考虑服务公平性的连续泊位-岸桥集成分配

郝杨杨1*， 李军军2， 黄有方1

(1.上海海事大学 物流研究中心， 上海 201306； 2.上海海事大学 商船学院， 上海 201306)

泊位和岸桥是集装箱码头非常最要的资源，合理的分派与调度可以有效地提高作业效率.目前泊位和岸桥的集成调度模型中大多以最小化船舶在港总时间或最小惩罚成本为目标函数，忽略了码头对船舶服务的公平性.为此，通过扩展现有的连续泊位分配模型，兼顾船舶惩罚成本及船舶等待与岸桥分配的公平性，建立多目标的连续泊位分配模型.设计一个三阶式邻域搜索算法， 该启发式算法包括邻域搜索安排船序列、停泊位置搜索和分配调整岸桥3个阶段.实验结果显示，不同的邻域策略取得的最优解不同，通过设置最优的邻域策略可以获取最优的目标函数值.实验表明，该模型与算法可以在接受的时间内取得最优解，相关成果可以为码头对船舶服务的公平性研究提供理论依据.

集装箱码头； 连续泊位； 泊位-岸桥； 公平性； 邻域搜索

作为集装箱码头最重要的资源，泊位和岸桥的合理调度可以有效提高作业效率.实际作业中出于岸桥数量和岸桥成本限制，码头需要在最大限度的岸桥数量和有限泊位岸线下，进行集成资源优化配置来提高运行效率[1-2].

在泊位和岸桥的集成分配问题中，目标函数通常是船舶总在港时间最小、总成本最小或是总等待时间最小.如Imai等[3-4]考虑到船舶服务的优先级，建立了以船舶最小化在港时间为目标的优化模型，提出通过遗传算法求解泊位分配问题.Frank Meisel等[5]采用岸桥的装卸效率代表船舶的处理时间，研究了泊位和岸桥的联合分配问题.梁承姬等[6]将船舶处理时间用岸桥装卸的速度来表示，研究了泊位和岸桥整合分配问题.乐美龙等[7]研究了基于泊位偏好与服务优先级的泊位和岸桥分配问题.将离散泊位连续化可以最大限度的提高泊位利用率，Kim等[8]构建MIP模型研究连续泊位分配问题，并用模拟退火算法和LINDO进行求解.韩晓龙等[9]建立了泊位分配的混合整数规划模型以及桥吊调度的混合整数规划模型，讨论了连续泊位和岸桥的协同分配问题.

以上研究主要是从码头利益的角度考虑问题，最小化船舶在港总时间，提高码头资源利用率，却忽略了码头对船舶服务的公平性.船舶服务的公平性最初体现在船舶的等待时间和停泊顺序上，采用先到先服务(FCFS)的分配策略是最常见的研究领域.童珊[11]考虑到实际操作中码头装卸效率同时影响着船舶在港时间和船舶的优先权，建立了船舶优先权的动态连续泊位分配模型.勾岩[12]研究港口服务的公平与效率，建立以船舶在港总时间和船舶等待时间方差最小为目标的双目标优化模型，并采用基于启发式算法的多目标遗传算法NSGA-II对模型进行求解，实现了公平与效率的统一.以上研究虽然通过对船舶延迟到达、延迟离港、偏离偏好泊位等情况的惩罚成本的分析，然而船舶服务的公平性中将等待靠泊作业的公平性和等待完成作业离开的公平、岸桥分配数量的公平等作为评估标准的研究却很少.

本文通过扩展现有的连续泊位分配模型，考虑等待的公平性与岸桥分配的公平性，建立多目标的连续泊位分配模型.为验证公平性对船舶靠泊计划的影响，设计一个三阶式邻域搜索算法， 该启发式算法包括邻域搜索安排船序列、停泊位置搜索和分配调整岸桥三个阶段.通过邻域生成策略和公平性的成本函数相结合来设计实验方案，检验算法的有效性，分析等待时间对公平性的影响.

1问题描述与假设

通常船舶抵港后，码头调度员将根据相关信息和调度策略将泊位和岸桥分配给船舶.泊位-岸桥的优化分配是指通过分配适当的泊位、选择合适的靠泊顺序并配备合理的岸桥数量，使船舶在港时间较短，以提高船舶的利用率和客户的满意度，并降低码头的运营成本.对船公司而言，希望到港的船舶被分配到理想的偏好泊位、排队等待靠泊的时间最小且处理时间延误最小；对码头管理人员而言，希望计划周期内保持码头的集装箱吞吐量能最大.

当船舶靠泊时，占用泊位的长度取决于其船长，占用泊位的时间取决于岸桥装卸处理的时间.本文考虑的连续泊位-岸桥分配问题，只要船舶满足靠泊的岸线长度，船舶便可沿岸线靠泊，多只船可以同时靠泊接受服务.本文通过对预期到达时间和装卸服务需求量这两个因素核算排序，综合衡量船舶接受港口服务过程的公平性，包括顺序公平、基于服务时间公平和资源配置公平.本文考虑船舶偏好泊位的影响以及船舶到港、离港延迟惩罚的约束，并结合船舶接受服务的公平性，建立的连续泊位和岸桥的集成分配模型将基于以下合理假设：

1) 每条船必须被服务且被服务一次，即不考虑移泊作业；

2) 船舶到港时间不能早于预计到达时间，只能等待靠泊，不能提前到港；

3) 处理时间取决于所在泊位、码头的岸桥数量，与船舶的距离、集装箱运输以及其他因素等无关；

4) 泊位资源视为连续线性的，被划分为尽可能多且相等的微小停泊单元，多只船舶可以同时停靠；

5) 每条船舶设有同时作业的最大岸桥数和最小岸桥数，当可用岸桥数量不小于最小岸桥数时才能开始作业，并且不能大于最大岸桥数；

6) 分散的闲置岸桥不能横跨工作，岸桥只能在岸线固定的位置为靠泊的船进行装卸；

7) 每条船都有一个最优停靠偏好位置，偏离偏好泊位会增加在港时长；

8) 假定泊位计划在零时刻开始，船舶只有到港后才能进行靠泊作业，正常情况下靠泊后即可开展装卸作业.

此外，船舶靠港作业过程中的靠泊时间和离泊时间对于不同船型差异不大，且相对整个在港时间很小，在此忽略不计.

2模型建立

2.1相关概念和符号

本模型的相关概念和符号如表1.

表1 相关概念和符号

续表1

2.2连续泊位岸桥集成分配模型

连续泊位岸桥集成分配模型为

(1)

目标函数中f=f1+f2+f3，fmax和fmin用来作为函数的最大值和最小值，其中ϑmax和ϑmin作为评价公平性的最大和最小值.然后，惩罚成本和公平措施通过方程(1)合成一个独立的目标函数，此时wϑ+wf=1，wϑ≥0且wf≥0.

1)惩罚成本f

泊位与岸桥集成调度的优化目标包含两方面：一是泊位的优化，即停靠泊位应该尽可能的靠近偏好泊位，以减少集装箱从岸桥到后方堆场的移动时间，提高岸桥作业效率，降低作业；二是服务时间的优化，即船舶入港后应尽快靠泊作业，靠泊后尽可能在船公司规定的时间内作业完毕并按时离港.针对这两个目标建立了最小化总惩罚成本的多目标模型，旨在减少靠泊惩罚成本、靠泊等待时间、延迟离港时间.目标函数通过(2)～(5)定义；而约束函数通过式(6)～(30)定义.

Minimize

(2)

(3)

(4)

(5)

s.t :

BLv≥Bv-Sv，∀v，

(6)

BRv≥Sv-Bv，∀v，

(7)

TLv≥Tv-ev，∀v，

(8)

Tv≥ev，∀v，

(9)

DLv≥Cv-dv，∀v，

(10)

(11)

∑vXv，p，t≤1，∀p，t，

(12)

∑vYv，t≤c-Dt，∀t，

(13)

∑tYv，t≥av，∀v，

(14)

Vv，t≤Yv，t，∀v，t，

(15)

Yv，t≤M·Vv，t，∀v，t，

(16)

(17)

Yv t≤uv，∀v，t，

(18)

Vv t≤∑pXv，p，t，∀v，t，

(19)

Vv t·M≥∑pXvpt，∀v，t，

(20)

Uvp≤∑tXvpt，∀v，p，

(21)

Uvp·M≥∑pXvpt，∀v，p，

(22)

(23)

(24)

Vvt≤∑p，τ≤tZvpτ，∀v，t，

(25)

∑p，tZvpt=1，∀v.

(26)

∀v，ρ≥2，ρ≤sps-bv:

(27)

(28)

(29)

(30)

其中,目标函数式(2)为最小化惩罚成本函数，包括船舶停泊的泊位偏移偏好泊位的总成本、船舶延迟靠泊的总惩罚成本，船舶延迟离泊的总惩罚成本，分别通过 (3)～(5)定义.式(7)和(8)约束了船的停泊位置偏离偏好泊位的水平距离.函数(8)界定了船舶推迟停泊的时间差.式(9)约束了船舶到港后才能靠泊.式(10)约束了延迟离泊的时间差.函数式(11)约束了船舶离开时刻必须大于等于集装箱作业完成时间.函数式(12)约束了每一个时空点只能被一条船占用，考虑了前期滚动调度中已被占用的时空点.函数式(13)表示的可供分配的岸桥数受总岸桥数限制，考虑了前期滚动调度结果中每个时刻已被占用的岸桥数目.函数式(14)约束了船的作业时间必须要大于等于总桥时.函数式(15)～(16)反映了作业的持续性，至少有一个岸桥为之服务，即船舶不能中途停止作业.函数式(17)～(18)限制了可以给每条船分配的岸桥数受最大值和最小值限制.函数式(19)～(20)建立了Vk，j与Xk，i，j之间的关系.函数式(21)～(22)建立了Uk，i与Xk，i，j之间的关系.函数式(23)～(25)保证了船舶靠泊后占用时间和泊位上的连续性.式(26)保证了一条船只有一个参考点，即矩形的左下角.式(27)～(30)保证了矩形内的网格取值为1，矩形外的网格取值为0.

2)公平措施

假设船舶是按预期到达时间进行分类，所有船舶从1到svs，则v.船舶v的服务时间是由ψv=Cv-Tv，v∈sv计算取得.根据船舶抵港的顺序，可以讨论基本的顺序公平性.在港口服务系统中船舶接受处理的顺序由π所界定.根据EAT 和 EDT分别对船舶进行πa和πd两种时间的排序，以上两种时间序列可以讨论两种标准化延迟公平性，即迟于EAT与迟于EDT.根据QC分配数量以及泊位是否为偏好泊位，讨论资源配置的公平性，包括4种类型，具体分类见表2.最后，综合讨论以上公平性.

表2 公平性设计

3邻域搜索算法求解

邻域搜索算法的基本思想是在搜索过程中系统地改变邻域结构集来拓展搜索范围，获得局部最优解，然后在基于此局部最优解重新系统地改变邻域结构集拓展搜索范围找到另一个局部最优解的过程.由于邻域搜索算法具有实用性、有效性、时效性及鲁棒性的属性特点，且可以在可容忍的时间内求解NP-Hard问题，因此本文将采用邻域搜索算法求解，实现局部范围内的集成分配优化.该算法具体分为3个阶段(表3):邻域搜索进行排序，生成靠泊位置，调整位置和分配岸桥.

表3 邻域搜索算法过程

4算例实验与分析

本文不考虑水深的影响，以宁波北仑港第二大港作为参考的生成测试数据集，根据以下条件随机产生100艘船的算例数据.

1)码头的长度是1 200m，分为120段的单位段10m.因此，sps=120;

2)岸边总计有16个岸桥;

3)预计到达时间 EAT (ev)是均匀分布在一个星期内，即168h.计划周期设置为180h，分为180段的时间单位.因此，sts=180;

5)预期离港时间EDT(dv)由U(ev+10，ev+15)生成;

图1 实验1Fig.1 Experiment 1

实验1显示(图1)，随着迭代次数的不断增加，目标值不断优化.当迭代至1747次时，目标函数值降到最低为0.279，随后迭代至3 000过程中，目标函数值始终收敛于0.279.

实验2在实验1的基础上，保持其他参数设置不变，修改邻域调整次数md，取值从1、5、10直至100.

实验2显示(图2)，随着邻域调整次数md在[1，100]范围内呈整数倍不断增加，目标函数值整体呈现不断递减的趋势.当邻域调整次数为1时，目标函数值最大为0.35；随着邻域调整次数的增加，目标函数值不断减小，最终减少至0.272.

实验3在实验1的基础上，保持其他参数设置不变，修改邻域结构生成方式为插入方式和交换方式，比较插入方式与交换方式取得的目标函数值.

实验3显示(图3)，插入策略收敛较快，在355次迭代后目标函数值收敛于0.277；而交换策略在迭代1 087次后目标函数值收敛于0.273，可以取得更好的最优解.

图2 实验2Fig.2 Experiment 2

图3 实验3Fig.3 Experiment 3

实验4在实验1的基础上，保持其他参数设置不变，修改相邻两船位置的定位方式为绝对定位和相对定位方式，比较绝对定位与相对定位取得的目标函数值.

图4 实验4Fig.4 Experiment 4

实验4显示(图4)，相对定位取得的最优解明显好于绝对定位方式，绝对定位方式的最优解为0.297，而相对定位的最优解为0.279.

实验5在实验1的基础上，保持其他参数设置不变，修改产生邻域的范围，取值从5、10、15至100，分为普通分布和正态分布.

实验5显示(图5)，在选用范围为10的普通分布情况下，可以取到最优的目标函数值0.271.

图5 实验5Fig.5 Experiment 5

实验6在实验1的基础上，保持其他参数设置不变，根据上述实验选择较好的参数设置，修改邻域调整次数md为100，调整邻域结构生成方式为交换方式，修改相邻两船位置的定位方式为相对定位方式，修改普通分布产生邻域的范围为10.

实验6显示(图6)，当选用较好的参数时，算法在93次迭代之后迅速收敛至最优解0.237，收敛速度与最优解都较实验1有明显改进.

图6 实验6Fig.6 Experiment 6

5结论

本文给出了基于服务公平性的连续泊位-岸桥集成分配模型，通过扩展现有的连续泊位分配模型，考虑船舶惩罚成本、船舶等待公平性与岸桥分配的公平性，建立了多目标的分配模型，并设计了三阶段的邻域搜索算法.实验结果显示，不同的邻域策略取得的最优解不同，通过优化邻域策略可以获取更优的目标函数值.实验表明，该模型与算法可以在接受的时间内取得最优解，相关成果可以为码头对船舶服务的公平性研究提供理论依据.

此外，本文还存在一些不足，如惩罚系数设置的合理性、权重分配的合理性等需要进一步研究.通过细致分析客户对公平性满意度的影响，调整各个公平性的权重值，探讨公平性的权重体系设计对整个船舶靠泊服务公平性的影响是本文以后继续研究的方向.

[1] BARROS V H， COSTA T S， OLIVEIRA A C M， et al. Model and heuristic for berth allocation in tidal bulk ports with stock level constraints[J]. Computers & Industrial Engineering， 2011， 60(4):606-613．

[2] 乐美龙，刘 菲. 基于Memetic算法的泊位和岸桥分配问题[J]. 武汉理工大学学报， 2011， 33(11):66-71．

[3] IMAI A， NISHIMURA E， PAPADIMITRIOU S. Berth allocation with service priority[J]. Transportation Research Part B Methodological， 2003， 37(5):437-457．

[4] IMAI A， SUN X， NISHIMURA E， et al. Berth allocation in a container port: using a continuous location space approach[J]. Transportation Research Part B Methodological， 2005， 39(3):199-221．

[5] MEISEL F， BIERWIRTH C. Integration of berth allocation and crane assignment to improve the resource utilization at a seaport container terminal[J]. Operations Research Proceedings， 2005， 26(4):105-110．

[6] LIANG C， HUANG Y， YANG Y. A quay crane dynamic scheduling problem by hybrid evolutionary algorithm for berth allocation planning[J]. Computers & Industrial Engineering， 2009， 56(3):1021-1028．

[7] 乐美龙， 刘秀玲. 基于泊位偏好与服务优先级的泊位和岸桥分配[J]. 辽宁工程技术大学学报(自然科学版)， 2013， 39(5):709-712.

[8] KIM K H， CHAN K. Berth scheduling by simulated annealing[J]. Transportation Research Part B Methodological， 2003， 37(2):541-560．

[9] 赵坤强， 韩晓龙， 梁承姬. 连续泊位下集装箱港口泊位与桥吊协同调度优化研究[J]. 武汉理工大学学报， 2011， 33(11):60-65．

[10] 童 珊. 基于船舶优先权的集装箱港口泊位分配问题[J]. 交通运输工程与信息学报， 2012， 10(1):105-110．

[11] 勾 岩. 考虑船舶等待时间均衡的泊位岸桥联合分配问题研究[D]. 大连：大连海事大学， 2015.

Integrated allocation of continuous berth and quay crane base on service fairness

HAO Yangyang1， LI Junjun2, HUANG Youfang1

(1.Logistics Research Center, Shanghai Maritime University, Shanghai 201306;2.Merchant Marine College, Shanghai Maritime University, Shanghai 201306)

Berth and quay are the most important resources in container ports, and optimal allocation and scheduling of them under stochastic environment are able to improve work efficiency. At present, most of the integrated scheduling models of berth and quay crane take minimization of the total time or penalty cost of the ship in the port as the objective function, ignoring the fairness of the ship's service. Therefore, the existing continuous berth allocation model is extended to the multi objective continuous berth allocation model based on ship’s penalty cost, fairness of the ship waiting and allocation of the berth and quay crane. A neighborhood search algorithm is designed, consisting of three stages: the sequence of the adjacent search, the search for the position of the berth and the allocation and adjustment of the quay crane. The results of the experiments show that the optimal solution is obtained by different neighborhood strategies, and the optimal value of the objective function is able to be generated by setting the optimal neighborhood strategies. The model and algorithm are found to possess optimal solution in an acceptable time, and the relevant results provide theory for research on ports for ships service fairness.

container terminal; continuous berth; berth-quay crane; fairness; neighborhood search

2016-05-22.

国家自然科学基金项目(71301101)；交通运输部建设科技项目(2015328810160)；上海自然科学基金项目(15ZR1420200)；教育部人文社会科学基金项目(15YJC630059).

1000-1190(2016)06-0860-07

TP18

A

*E-mail: yyhao@shmtu.edu.cn．