史　立，管明静，郭金鑫

(上海海事大学 科学研究院物流研究中心，上海 201306)

0　引　言

在经济全球化的背景下，运输物流正在快速发展。集装箱运输业已成为运输和物流的支柱，集装箱码头在多式联运网络中扮演着不可或缺的角色。特别是随着过去20年世界贸易的快速发展，集装箱码头的服务需求在不断的增加，这样就需要更高效率完成作业，以减少船舶在码头的逗留时间，从而获得与其邻近港口的竞争优势。这种竞争优势将有助于客户的增加，从而获得利润。随着过去几十年里集装箱化的发展，对集装箱港口码头的研究问题也应运而生，泊位和岸桥的集成分配是目前港口优化领域研究的热点问题。

国内外很多学者对泊位分配问题(berth allocation problem，BAP)和岸桥分配问题(QCAP)进行了研究。ZHANG Canrong等[1]最早尝试研究BA-CASP(berth allocation，quay crane assignment and scheduling problem)，即在数学优化模型中整合BAP，CAP(quay crane assignment problem)和CSP(quay crane scheduling problem)以确定船舶的最佳停泊时间和位置以及岸桥的数量和调度方案，C. BIERWIRTH等[2]对相关论文根据一些特定属性进行很好的调查分类。Y. M. PARK等[3]建立了一个动态到达的连续的BACAP数学模型，提出了将模型分为两个阶段解决方案，在第1阶段，确定船舶的靠泊时间、位置及分配给每艘船舶的岸桥数量，运用拉格朗日松弛问题使用子梯度优化技术分解成几个独立的子问题；在第2阶段，使用动态规划确定分配给每艘船舶1组具体的岸桥。蒋大培等[4]基于偏好泊位的泊位和岸桥联合分配问题建立0-1混合整数规划模型，并运用了CPLEX 软件进行编程求解。HAN Xiaolong等[5]将泊位岸桥调度问题分为两个阶段，第1个阶段，根据船舶之间的时空关系，建立1个连续泊位分配模型；第2阶段，即岸桥分配阶段，用到多目标规划，考虑到了岸桥的最小最大覆盖范围，同时还考虑了岸桥移动的成本，运用PSO和CPLEX进行求解和比较。

在港口业务的实践中，对BAP和QCAP集成优化研究上会忽略泊位的水深对限制船舶停泊的限制，因此为了避免船舶搁浅，其停泊位置的水深必须满足船舶的吃水深度要求。泊位水深通常受现实环境中潮汐的影响，从而使船舶停泊位置的水深随时间变化而变化。如果船舶在低水位时到达港口且水深不满足船舶吃水的情况下，则需要在锚地等待下一个高水位的来临，那么由潮汐引起的等待将会进一步降低码头的生产率。孙少文等[6]考虑到潮水水位变化对靠泊计划的影响，根据潮汐的运动规律，建立了船舶总在港时间最小的离散泊位分配模型。A. KARAM等[7]在假设船舶停泊位置不受船的吃水影响条件下，建立了船舶动态到达的连续泊位分配模型。T. QIN等[8]考虑到在泊位分配中，受潮汐的影响水深会随时间变化，对整数规划(IP)和约束规划(CP)两种模型进行比较。Y. DU等[9]研究了船舶进出港口时，量化了潮汐对集装箱港口海边作业的影响，为了减少燃料消耗和污染物排放，建立了采用虚拟到达策略的泊位分配模型，运用了二阶锥规划方法。A. SHEIKHOLESLAMI等[10]建立了潮汐海港连续动态泊位分配模型，考虑到不同泊位的水深也不同，并使用了遗传算法结合模式搜索算法进行求解。D. XU等[11]提出了一种集装箱码头的离散泊位分配模型，其中船舶的泊位分配受水深和潮汐条件的限制。在该模型中，时间窗分为两个时段，即低水位和高水位，并且这两个时段中的处理集是不同的。V. H. BARROS等[12]通过引入潮汐时间窗(即高潮时期)来建立和分析泊位分配模型，其中船舶只能在这个时间窗内才能被服务。这个模型主要讲述的是潮汐散货港口和海运集装箱码头(MCT)管理。

通过上述关于泊位和岸桥调度问题的研究可以看出，在泊位分配和岸桥调度过程中考虑潮汐因素局限在离散泊位。在文中不是将潮汐条件分类为两个或更多，而是将准确的潮汐数据应用在连续的泊位分配问题。

1　问题描述

集装箱港口使用大量的资源和设备为进港船舶提供服务。泊位和岸桥是集装箱码头最为稀有和最昂贵的资源，集装箱港口岸边操作如图1，因为要提高这两种资源的生产力需要大量的投资。 因此，通过规划实现这两种资源的最大利用对于实现整个码头总体的最大生产率是至关重要的。

因此出现两个重要的规划问题，即泊位分配问题(BAP)和岸桥分配问题(QCAP)。在泊位分配中，确定在给定的规划范围内待服务的每艘船舶在码头的停泊时间和停靠位置。在岸桥分配中，分配一组具体的岸桥来为在港船舶服务。在确定船舶靠泊位置时受很多不同的约束，如沿着岸线的水深、岸桥覆盖范围等。

图1　集装箱港口岸边操作示意Fig. 1　Diagram of quayside operation of container port

笔者研究连续泊位及岸桥集成分配问题，同时考虑随着时间变化的水深对船舶靠泊计划的影响，建立了混合整数规划模型，优化船舶的停靠时间、离港时间和所分配的具体岸桥。

图2　潮汐规律示意Fig. 2　Diagram of tidal regularity

2　模型建立

基本假设条件为：① 岸桥在服务过程中不能发生中断；② 每艘船可分配的岸桥数量都有一定的范围；③ 岸线上的任意位置至少被一个岸桥覆盖；④ 船舶左端船头为船舶的靠泊位置。

2.1　参数定义

2.2　决策变量

1)ai表示船舶i的停泊时间；di表示船舶i的离开时间；

2)bi表示船舶i的开始靠泊位置；

3)xikt表示0～1变量，船舶i的左端船头在t时段停在k位置时等于1，否则等于0；

4)φitρ表示0～1变量，ρ个岸桥在第t时间为船舶i服务时等于1，否则等于0；

5)rqit表示0～1变量，岸桥q在第t时间段服务船舶i时等于1，否则等于0；

6)rit表示0～1变量，在第t时间段有岸桥为船舶i服务时等于1，否则等于0；

7)zij表示0～1变量，船舶i任务结束后船舶j任务开始时等于1，否则等于0；

8)μij表示0～1变量，船舶i的位置在船舶j的下面时等于1，否则等于0。

2.3　目标函数及约束条件

目标函数：

(1)

约束条件：

(2)

(3)

(4)

(t+1)·rit≤di∀i∈V，t∈T

(5)

t·rit+M·(1-rit)≥ai∀i∈V，t∈T

(6)

(7)

(8)

bi+li≤bj+M(1-μij)∀i，j∈V，i≠j

(9)

di≤aj+M(1-zij)∀i，j∈V，i≠j

(10)

μij+μji+zij+zji≥1∀i，j∈V，i≠j

(11)

(12)

Di·xikt≤bkt∀i∈V，k∈L，t∈T

(13)

(14)

rq，it+rqjt≤1+μij∀q，q′∈Q且q

i，j∈V，t∈T

(15)

xkit，φitρ，rqit，rit，zij，μij∈{0，1}∀i，j∈V，

q∈Q，t∈T，k∈L，ρ=1，2，…，Ri

(16)

上述模型的目标函数为时间成本及岸桥使用成本最小化，通过式(1)～式(16) 定义目标函数和约束条件。式(1)表示总目标函数，最小化船舶延迟到港成本、延迟离港处罚成本、岸桥使用成本；式(2)表示任意时刻分配给船的岸桥数量不能超过码头岸桥总数；式(3)确保变量φitρ和rit的一致性；式(4)确保船舶服务不能中断。船舶在码头停泊，装卸操作必须完成才能离开码头；式(5)为船舶的某一作业时间与离港时间关系；式(6)表示船舶到港后才能被服务；式(7)表示某一时刻分配给船舶的岸桥数量与服务船舶的岸桥数量的关系；式(8)表示任意时刻一个岸桥最多只能为一艘船服务；式(9)～式(11) 保证船舶在时间和空间上不冲突；式(12)表示服务某一艘船的岸桥数量范围；式(13)表示船舶作业期间停泊位置的水深必须满足船舶的吃水深度；式(14)表示任意一艘船舶只有一个停泊位置；式(15)表示岸桥之间不能穿越；式(16)表示对决策变量的约束。

3　试验算例

算例(N=6)即6艘船，原始数据见表1。

表1　6艘船的原始数据Table 1　Original data of 6 ships

3.1　算例分析

在忽略潮汐影响的条件下，表1计算的结果整理后如图3。其中，横坐标表示时间段，纵坐标表示岸线。不同的矩阵表示不同的船舶，矩阵的长表示船舶占用的岸线长度；矩阵的宽表示船舶作业时间；矩阵中的数字表示每个时间段分配给船的岸桥，这个岸桥数量是随着时间段而变化的。从图3也可以看到，进港的船舶基本能保证船舶在最迟离港时间之前离港。在第1～5时间段船1和船2分别都是有3台岸桥服务，船3在第5时间段进港后使得岸桥资源变得紧张，从而分配给船1和船2的岸桥数量减少，岸桥资源紧张。到第12时间段船1和船2作业完成，使得船4能有更多的岸桥可以使用。从到第13时间段开始，船5、船6的到来使得船4所分配的岸桥数量由3台减少为2台。到第20时间段，船4的作业完成，船5和船6所分配到岸桥资源也随之增加，由原来的2台岸桥增加到3台。从图3也可以看出，服务船舶的岸桥的数量也在可行的范围内。这种岸桥的动态分配使港口有限的岸桥资源更能充分利用，提高港口的运营效率。同时可以看到在船1、船2、船3进港靠泊后，泊位资源也变得紧张，所以船4实际进港的时间延迟了1个时间段，船5实际到港时间延迟2个时间段。

3.2　受潮汐干扰的算例分析

在港口的实际作业中，潮汐规律通常会对船舶的靠泊计划产生影响，考虑到船舶吃水与停泊位置水深的关系，由表1计算的结果整理后如图4。

从图4中可以看出，由于船1、船2、船3、船5的吃水不受潮汐影响，所以这3艘船的靠泊计划不变；根据图2中的潮汐规律图可以看出，在第12时间段水深为7.6 m，不满足船4的8 m的吃水，直到第14时间段船4才能进行靠泊作业，因此船4需延迟2个时间段，同时岸桥资源也需要重新分配，船3和船5有了更多的可用岸桥；第14时间段的水深也不满足船6的吃水，船6也需要延迟一个时间段到港。因此在集装箱码头的作业计划中，考虑到潮汐因素可以使作业计划更符合实际。也可从图4看出，因为岸桥的移动是在一定范围内，在第12时间段到第14时间段之间，船4受潮汐影响需延迟两个时间段，因此在第14时间段就没有船舶进行作业，为了使码头资源得到充分的利用，在空闲时段可以安排不受潮汐影响的小型船舶(如船7、船8)进行作业。这样将进一步提高码头资源的利用率，降低运作成本，同时使文中的模型更加符合港口的实际情况。

表2　算例惩罚费用Table 2　Penalty costs of case studies

由表2中的惩罚费用所知，船舶在受潮汐因素影响的情况下，船4、船5、船6均没有在期望到达时间到达，各产生了9、8、5的惩罚费用，同时船舶离港时间及岸桥服务数量也受到了影响。例如船6应在第21时间段离港，最终在第24时间段延迟离港，在第22、23时间段岸桥数量由原来分配的3台减少为2台，船6总的延误费用为11.8；且船4、船5的延迟离港也产生一部分惩罚费用。

模型中考虑到连续泊位可以使泊位资源得到更加充分地利用；岸桥分配过程中考虑到岸桥的覆盖范围，同时在潮汐因素的约束下研究泊位岸桥集成分配问题，更符合码头的实际情况，可以减少因船舶吃水条件不满足而产生的等待时间进而减少船舶总的时间，降低运营商的运作成本，充分利用码头资源，从而提高客户的满意度。

4　结　语

通过构造连续泊位-岸桥联合分配模型，建立了一个混合整数模型，将连续型泊位与岸桥分配结合在一起。在泊位计划中，考虑船舶进出港受到潮汐的影响，以24 h为一个周期，根据潮汐规律在不同的时间段设置了不同水深；在岸桥分配过程中，考虑到岸桥覆盖范围对岸桥分配的影响，并设置不同的惩罚系数，从而达到时间延迟成本及岸桥使用成本最低的优化目标，到港船舶的停泊位置与进港离港时间及各船舶的具体岸桥分配也比不考虑潮汐因素更符合码头的实际情况。

但是，笔者没有考虑到岸桥移动对总成本的影响以及一些码头在同一时间不同位置水深也不同对泊位分配的影响，从而进一步提高港口的服务水平及码头资源的利用率。因此，可以使用其他方法完善连续泊位和岸桥分配模型。

参考文献(References)：

[1]ZHANG Canrong，ZHENG Li，ZHANG Zhihai，et al.The allocation of berths and quay cranes by using a sub-gradient optimization technique[J].Computers&IndustrialEngineering，2010，58(1)：40-50.

[2]BIERWIRTH C，MEISEL F，MEISEL F.：A survey of berth allocation and quay crane scheduling problems in container terminals.[J].EuropeanJournalofOperationalResearch，2010，202(3)：615-627.

[3]PARK Y M，KIM K H.A scheduling method for Berth and Quay cranes[J].OrSpectrum，2003，25(1)：1-23.

[4]蒋大培，胡志华，胡少龙.考虑偏好泊位的泊位和岸桥集成分派问题[J].广西大学学报(自然科学版)，2014(3)：663-672.

JIANG Dapei，HU Zhihua，HU Shaolong.Considered berths and quay berths integrated dispatch issue preference[J].GuangxiUniversity(NaturalScience)，2014(3)：663-672.

[5]HAN Xiaolong.A new continuous berth allocation and quay crane assignment model in container terminal[J].Computers&IndustrialEngineering，2015，89(C)：15-22.

[6]孙少文，杨斌，胡志华.潮汐影响下的港口离散泊位分配问题研究[J].合肥工业大学学报(自然科学版)，2014，37(4)：486-492.

SUN Shaowen，YANG Bin，HU Zhihua.Research on the Dispatch of Discrete Berths under the Influence of Tide[J].JournalofHefeiUniversityofTechnology(NaturalScience)，2014，37(4)：486-492.

[7]KARAM A，ELTAWIL A B.Functional integration approach for the berth allocation，quay crane assignment and specific quay crane assignment problems[J].Computers&IndustrialEngineering，2016.

[8]QIN T，DU Y，SHA M.Evaluating the solution performance of IP and CP for berth allocation with time-varying water depth[J].TransportationResearchPartE，2016，87：167-185.

[9]DU Y，CHEN Q，LAM J S L，et al.Modeling the impacts of tides and the virtual arrival policy in berth allocation[J].TransportationScience，2015，49(4)：939-956.

[10]SHEIKHOLESLAMI A，ILATI G，KOBARI M.The continuous dynamic berth allocation problem at a marine container terminal with tidal constraints in the access channel[J].InternationalJournalofCivilEngineering，2014，12(3)：344-353.

[11]XU D，LI C L，LEUNG Y T.Berth allocation with time-dependent physical limitations on vessels[J].EuropeanJournalofOperationalResearch，2012，216(1)：47-56.

[12]BARROS V H，COSTA T，SOUZA S，et al.Model and heuristic for berth allocation in tidal bulk ports with stock level constraints[J].Computers&IndustrialEngineering，2011，60(4)：606-613.