求解动态停泊计划问题的拉格朗日松弛算法

刘 悦，谢 谢

1.辽宁信息职业技术学院 软件工程系，辽宁 辽阳 111000 2.沈阳大学 制造集成自动化重点实验室，沈阳 110044

求解动态停泊计划问题的拉格朗日松弛算法

刘 悦1，谢 谢2

1.辽宁信息职业技术学院 软件工程系，辽宁 辽阳 111000 2.沈阳大学 制造集成自动化重点实验室，沈阳 110044

1 引言

作为中国最重要的钢铁制造商，宝钢每年拥有超过上千万吨的原材料。其中大约95%的原材料由水路运输至宝钢原料码头进行卸载，之后由码头皮带运输机连接岸上的皮带运输机将它们运至指定料场。伴随着年钢产量的迅速增加，宝钢所需的原材料也迅猛增长，因此使得宝钢原料码头上最昂贵的泊位资源显得十分有限。这就迫切需要制定一个有效的进港原料船停泊计划来提高整个码头的生产率。原料码头的整个海岸线长度通常会被划分为几个泊位，但是由于进港原料船之间差别很大，所以在实际操作中在码头进行卸载的原料船经常会出现跨越原有泊位边界的情况。为了与实际停泊计划的要求相一致，本文将一个可同时停靠多条原料船的连续泊位空间看作一个泊位。目标为最小化总权重服务时间为目标函数来为进港原料船分配泊位空间，其中服务时间包括原料船到港后等待靠泊的时间和卸料时间。

近年来，关于停泊计划问题已引起了一些学者的关注，然而与现有文献相比，本文所提出的问题有如下几个特点：（1）与Park and Kim[1-2]，Imai等学者[3-4]研究只有一个连续泊位的停泊计划问题不同，本文研究有多个连续泊位的停泊计划问题。（2）区别于Imai等学者[5-6]，Nishimura和Imai[7]，将码头上的离散停泊区域看作一个“泊位”，本文把整个连续的位置空间称作一个“泊位”。由于本文所研究的停泊计划问题只为原料船指定停泊位置但并不同时考虑卸船机的分配问题，所以主原料码头上的多台卸船机认为是相同的。如图1所示，主原料码头和副原料码头构成了两个连续泊位。（3）按照本文所提出方法制定的停泊计划为每一艘进港船指定停泊泊位、在选定泊位上的具体停泊位置和开始卸料时间。（4）在计划展望期开始时不是所有的进港原料船都已经到港。在计划展望期开始时每一个泊位上仅部分泊位长度是可利用的，即在泊位上存在上一个计划展望期未完成全部卸载操作而遗留到当前计划展望期继续进行卸载的原料船。

图1 宝钢的连续泊位

大部分关于连续泊位停泊计划问题的研究都假定在计划展望期开始时，不存在上一个展望期内未卸载完而延续到下一个计划展望期继续卸载的进港船。本文所考虑的计划展望期开始时在每一个连续泊位上并非所有的泊位长度都可利用的停泊计划问题是更接近于实际停泊计划的一类问题。

本文所研究的停泊计划问题可以用几何方法在图2所示的两个泊位-时间平面上表示出来。每一个泊位-时间平面与主原料码头或副原料码头相对应。横轴对应泊位的物理长度，纵轴对应计划展望期。进港原料船的泊位安排通过相应泊位-时间平面上的矩形来表示。矩形的横边表示船的物理长度，它的纵边表示船在相应泊位上的卸载时间。从上一个计划展望期遗留下来的船用灰色的矩形表示，这些矩形的横边仍然表示船的长度，而其纵边表示该船在当前计划展望期上所剩余的卸料时间。

2 问题描述

图2 动态停泊计划举例

本文所研究的问题主要是对在泊位时间平面中代表进港原料船的矩形进行调度，其目的是在保证每个矩形都不与同一平面上的其他矩形相重叠的前提下使得目标函数最小。本章为所研究的问题建立一个数学模型，该模型的特点是首先把连续泊位长度和计划展望期划分为许多个长度或时间段，使得整个泊位-时间平面被分割成许多方格。该模型通过确保每个方格最多只能被一艘船占用来避免重叠。该问题的建模方式可以被视为与Guan et al.[8]相似的多处理器任务调度问题[9-11]。这里船是工件，而经过划分后的每一个泊位长度段可以看作是处理器。

2.1 问题假设

在给出模型前，先对问题做以下假设。

（1）假设原料船只有在完成卸载操作后才可以移动，即在开始卸载后不允许变更泊位。在实际原料码头的卸船过程中，除非有优先级很高的船急需泊位（如已经延误的外轮或运送生产紧缺原料的船到港）否则一般不会对正在卸载的船更换泊位。这是因为任何对卸载过程的干扰都会造成由相关原料船的额外等待时间和卸船机的调整时间而引起的高额费用，所以该假设是合理的。

（2）不允许叠放停靠。这种停泊方式通常在海军基地发生，但在钢铁企业原料码头却不允许出现。

（3）每艘进港船的卸载时间依赖于它所停靠的泊位。尽管在同一个泊位上的卸船机卸载能力是相同的，但是不同泊位上所配备的卸船机卸载能力是不同的。因此第三个假设适用于可以在多个泊位上进行卸载操作的原料船。

（4）假设整个计划展望期和每个泊位的总长度被划分为许多小的时间或长度段，这样每个泊位-时间平面就可以被分割成许多个方格。

2.2 数学模型

下面给出用于定义问题的参数和决策变量。

Ω：在整个计划展望期内将要到达的进港原料船集合。该集合可以被划分成三个子集：Ω1={1，2，…，N1}是只能在主原料码头进行卸载的原料船集合；Ω2= {1，2，…，N2}是只能在副原料进行卸载的原料船集合；Ω3={1，2，…，N3}是那些既可在主原料码头又可在副原料码头进行卸载的原料船集合。基于以上的定义，可得Ω= {1，2，…，N}=Ω1∪Ω2∪Ω3，其中 N=N1+N2+N3是进港原料船的总数。

Ψ：泊位集。该集合可以分成两个子集：Ψ1={1，2，…，B1}是与主原料码头相对应的泊位集；Ψ2={1，2，…，B2}是与副原料码头相对应的泊位集。因此得到Ψ={1，2，…，B}= Ψ1∪Ψ2，其中B=B1+B2是泊位总数。

P：时间段集，P={1，2，…，T}，其中T是整个计划展望期所分成的时间段总数。

Φj：泊位j上的泊位长度段集，Φj={1，2，…，Qj}，其中Qj是泊位j上泊位长度段总数。

pij：船i在泊位j上所需的卸载时间。

li：船i的长度（包括水平安全距离）。

ai：船i的到达时间。

M：一个很大的数。

Ω′：遗留船集。Ω′={1，2，…，N′}，其中 N′是遗留船总数。

bkj：泊位j上的遗留船k的起始停泊位置。

rjm：泊位j上的长度段m的可利用时间。

决策变量：

ci：船i的离港时间。

原料船的卸载时间和等待靠泊的时间之和形成了原料船的总服务时间，由于这个总服务时间是评价码头利用率的一个重要依据，因此本文以最小化进港原料船的总权重服务时间为目标函数。则模型可表示为：

约束式（2）确保每艘原料船必须被安排在一个泊位上进行卸载。约束式（3）保证分配到某一泊位的各船必须在一个不间断的时间段内进行卸载操作且占用与船的长度相对应的连续泊位长度段。约束式（4）指明某一泊位-时间平面上的任意一个方格最多只能被一艘船占用。该约束保证在同一个泊位-时间平面内没有相互重叠的原料船。约束式（5）说明只有在船到达了原料码头后，并且该船所占用的连续泊位长度段都可利用的时候，该船才可以开始卸载操作。约束式（6）表明船的离港时间是其开始卸载时间和卸载时间之和。约束式（7）表明了两个决策变量zijkt和 yij之间的关系。根据定义，如果zijkt=1，那么 yij=1;类似地，如果 yij=0，那么zijkt=0。约束式（8）和（9）限定某些有固定泊位要求的船必须停靠在相应的泊位上。约束式（10）是决策变量约束。

3 拉格朗日松弛

如前所述，本文所研究的问题可以看作是以最小化总权重服务时间为目标函数的多处理器任务调度问题。尽管已有文献针对连续泊位停泊计划问题提出定理或拉格朗日松弛算法给出了其所研究问题的下界[8，12]，然而由于问题特性的不同，这些下界不能扩展应用到本文的问题上。因此本文提出了适合求解本文所研究问题的拉格朗日松弛算法。

3.1 松弛问题的模型

从模型的结构可以看出，只有约束式（4）包含了不同原料船。如果将该约束松弛掉，那么原问题就可以被分解为每个对应一艘船的多个子问题。引入非负的拉格朗日乘子{ujmn}将约束式（4）松弛到目标函数中形成松弛问题，表示如下：

满足约束式（2）～（3），式（5）～（10），且 ujmn≥0，∀j∈Ψ，m∈Φj，n∈P。

那么拉格朗日对偶问题为：

满足约束式（2）～（3），式（5）～（10），且 ujmn≥0，∀j∈Ψ，m∈Φj，n∈P。

在忽略掉常数项后，该问题可以被分解成每个对应一艘原料船的多个子问题。则对应于船i，i∈Ω的子问题表示如下：

(LRi)Minimize ZLi≡

满足约束式（2）～（3），式（5）～（10），且 ujmn≥0，∀j∈Ψ，m∈Φj，n∈P。

3.2 求解子问题

对应于船i的子问题可以按如下步骤求得最优解。将式（6）代入式（13），可得：

满足约束式（2）～（3），（5），（7）～（10），且ujmn≥0，∀j∈Ψ，m∈Φj，n∈P。

下面来研究约束式（2），（7）～（9）之间的关系。当zijkt=1时，可从约束式（7）推出 yij=1。考虑式（7）～（9），并令Ψi= {1，2，…，Bi}表示可以卸载船i的泊位集合，则对应于船i的子问题变形为：

满足约束式（2）～（3），（5），（10），且ujmn≥0，∀j∈Ψ，m∈Φj，n∈P。

在忽略最后一个常数项后，对应于船i的子问题等价于：

满足约束式（2）～（3），（5），（10），且ujmn≥0，∀j∈Ψ，m∈Φj，n∈P。

那么式（16）就等价于：

满足约束式（2），（5），（10），且ujmn≥0，∀j∈Ψ，m∈Φj，n∈P。约 束 式（5）表 明 如 果 zijkt=1，那 么 t≥max{ai，m=k，k+m1，a…x，k+l-1(rjm)}。因此子问题被表述为：

i

满足约束式（2），（10）且ujmn≥0，∀j∈Ψ，m∈Φj，n∈P。

因此，令zij*k*t*=1，找到使得下式成立的组合：

就得到对应于船i的子问题最优解。

如图3所示，对于每艘船i，搜索(j*，k*，t*)的过程是在逐个扫描各泊位-时间平面内的可能组合来实现的。在泊位-时间平面j内，搜索过程从时间段1所对应的第1行上长度段1开始，到长度段Qj–li+1结束。在完成对第1行上全部可能组合的搜索后，开始进行对应于时间段2的第2行上可能组合的搜索。依此类推，直至完成第T–pij+1行上全部可能组合的搜索后，对泊位-时间平面j的搜索结束，转到下一个泊位-时间平面继续进行，直到将所有可卸载船i的泊位-时间平面上的组合都搜索完毕即可找到(j*，k*，t*)。

图3 求解子问题搜索过程示意图

性质1在拉格朗日松弛算法第一次迭代过程中，对于每艘船i(i∈Ω)其所对应的最优组合(j*，k*，t*)=argmj，ki，nt(wit+ wipij)，这里 j∈Ψi，k∈{1，τhj|Chj–1–t≥0}，t∈{ai，C1j，C2j，…，Cgj}且t≥m=k，k+m1，a…x，k+l-1(rjm)，其中Chj等于泊位j上的遗留

i原料船h的离港时间加1，τhj等于船h在泊位j上的末尾停泊长度段加1，h=1，2，…，g，这里g为泊位j上的遗留船总数。

证明 由于在拉格朗日松弛算法第一次迭代过程中，对于任意的 j∈Ψi，m∈Φj，n∈P，所有的拉格朗日乘子ujmn=0，所以问题简化为寻找使得 wit+wipij最小的组合(j*，k*，t*)。

在带有遗留船的泊位j上，船i所有可能的开始时间只能是ai，C1j，C2j，…，Cgj中的一个，并且船i可能停靠的起点位置是1或者是遗留船h的末尾位置加1。但是，在这其中只需考虑那些船i在时刻t停靠在泊位j上后，此时在该泊位上依然没有离港的所有遗留船。

最后，所选的组合(j*，k*，t*)必须保证船i不能与泊位j*上的遗留船重叠。如上所述，可得结论。

性质2令A*ijt′为针对船i的搜索过程进行至泊位-时间平面j上第t′行时所得到的 Aijkt中的最小值。如果存在A*ijt′≤wi(t′+1+pij)，则对于同一平面j内 t＞t′并且 k=1， 2，…，Qj的搜索过程可以被省去。

证明 对于给定的i和 j，wi(t′+1+pij)是泊位-时间平面j上尚未搜索的T-t′+1行所有组合对应的Aijkt中的最小值的下界。如果此时有该下界wi(t′+1+pij)＞A*ijt′，则不必再进行同一平面上剩余的搜索过程。

3.3 寻找可行解

对约束式（4）的松弛很容易导致子问题的解不可行。这种不可行性具体表现为在同一个泊位-时间平面上的船互相重叠。为了寻找可行解，本节提出了一种启发式算法。该启发式的主要任务就是为子问题的解中互相重叠的船重新分配停泊位置。在给出这个启发式之前，先给出一个性质来指出等待泊位分配的原料船所对应的矩形其左下端点可能占用的所有方格。

性质3如果任意未被安排泊位的船i可以停靠在泊位j，则其对应的矩形左下端点可占用泊位-时间平面j上以下范围内的方格：k∈{1，τhj|Chj–1–t≥0}，t∈{ai，C1j，C2j，…，Cgj}且t≥m=k，k+m1，a…x，k+l-1(rjm)。其中Chj是泊位j上已安排泊位

i的船h的离港时间加1，τhj是泊位j上已安排泊位船h的末尾停靠长度段加1，h=1，2，…，g+fj，这里g为泊位j上遗留船总数，fj为泊位j上所有已安排泊位的可行船总数。

证明 该性质的证明类似于性质1的证明。不同点在于除了要考虑泊位j上的遗留船外，还要考虑已安排泊位的可行船。

性质3指出了在泊位-时间平面j上所有可能改进目标函数的长度段k和时间段t的组合。由于其他的一些组合不可能改进目标函数值，因此不再进行对它们的搜索。

在以下启发式算法中只包含性质3中指定的组合。令I和Ij代表不可行船集和子问题中分配至泊位j的不可行船集。令Fj代表泊位j上已安排泊位的可行船集。令I=Ф，Ij=Ф，Fj=Ф且 j=0。该启发式算法步骤如下：

步骤1 j=j+1。如果 j＞B，转到步骤4。否则，i=0且令Ij=Ф。将子问题中分配到泊位j的船将其按照到达时间的升序排列。

步骤2i=i+1。在给定遗留船和Fj中可行船的情况下，检验子问题所给出的第i艘船泊位安排是否满足约束式（4）。如果第i艘船的当前泊位安排不违反约束式（4），则将其加入到Fj中；否则将其加入到Ij中。重复此步骤，直到泊位j上所有船都被加到Fj或Ij中为止。

步骤3选择Ij中第一艘船作为当前船。将其对应矩形的左下端点安排在性质3所指定的泊位-时间平面j上的每一个方格(k，t)以找到在不与Fj和泊位j上遗留船相重叠的条件下使得目标函数值最小的可行解。如果为当前船找到了可行解，则将当前船从Ij中删除并将其加入到Fj中；如果在泊位j不存在当前船的可行泊位安排，则将其加入到I中。重复这一步骤直到Ij为空时为止。转到步骤1。

步骤4如果I为空，停止。否则，选择在I中第一艘船作为当前船，并且在每个可以卸载当前船的泊位上执行步骤3中的类似步骤，但对于在子问题的解中已经被分配给该船的泊位则不执行此步骤。

3.4 更新拉格朗日乘子

本文使用次梯度方法来获得拉格朗日乘子{ujmn}的值。令urjmn为迭代至第r代的乘子，ZUB为最小总权重服务时间的上界，该上界用3.3节中提到的启发式算法求得。在用3.2节中的方法求解松弛问题后，所得解ZLB作为目标函数的下界。令λr的初始值设为2，当连续进行5次迭代而未改进下界时，λr减半。通过以下的递推公式用来确定乘子：

在如下性质4中的三种情况下，所用到的拉格朗日乘子在各次迭代中均未改变。因此在更新乘子的过程中，可以不必更新这些乘子。

性质4令amin为可以在泊位j上进行卸载操作的船所具有的最早到达时间，asmin为可以在泊位j上进行卸载操作的船所具有的次最早到达时间，则在以下三种情况ujmn=0：

（1）对应于被遗留船所占用方格的乘子。

（2）对应于泊位j上每一个 m∈{1，2，…，Qj}，n∈{1，2，…，amin–1}的方格的乘子。

（3）对应于泊位j上每一个m∈{1，2，…，Qj}，n∈amin，…，asmin–1}的方格的乘子。

证明 根据ujmn≥0的情况下拉格朗日松弛算法原理，如果泊位j上的方格(m，n)在任何时刻总是被至多一艘船占用的话，则ujmn=0。由于对应于情况（1）中乘子的方格总是只被一艘遗留原料船占用。情况（2）中乘子对应的方格由于在时刻n没有船到达而不被任何船所占用。而对于情况（3）中乘子对应的方格，如果可在泊位j上进行卸载的船中具有最小到达时间的那艘船被安排在该泊位上，则这些方格就被该船占用，否则将不被任何船占用。因此，以上结论得证。

4 计算实验

本文使用50个实际问题来测试拉格朗日松弛算法的性能。所提出的算法用C++语言编码，在PC（CPU：Inter Core2 2.93 GHz，内存：2 GB）上进行性能测试。

本章使用宝钢原料管制中心提供的一些实际停泊计划来测试算法性能。为了与实际原料码头的原料船停泊情况相对应，每艘船的长度和卸载时间应包含分别为20 m 和1 h的安全水平距离和相邻两艘进港船的间隔时间。泊位长度分别是640 m和400 m。表1显示了3天计划展望期内共有15艘进港船和3艘遗留船情况下的一系列参数。

宝钢原料码头的进港船是在原料日课作业计划的指导下入港停靠的。该计划实际上是基于滚动计划展望期的方法制定的，即每天都要由计划员来制定一个3天的原料船停泊计划，但只为第一天到港的原料船分配泊位。第二天计划员再制定下一个基于3天计划展望期的停泊计划，依此循环往复。在宝钢实际泊位停泊计划的最小时间单位是1 h，因此设定T为72对应于一个3天的计划展望期。这样与主原料码头和副原料码头相对应的泊位-时间平面分别被分割成64×72和40×72个方格。每个泊位-时间平面内的一个方格所代表的实际含义是10 m-1 h。本章通过从2011年6月到8月期间的日课作业计划中所挑选的50个实例来测试所提出的拉格朗日松弛算法的性能。船数从8到15之间取值以便包含不同的码头资源占用情况。本章所测试的拉格朗日松弛算法包括未改进算法和使用4个性质进行加速的改进算法。

表1 （a）15艘进港船参数举例

表1 （b）3艘遗留船的参数举例

对偶间隙是最常用于评价拉格朗日松弛算法性能的重要指标，它通常可表示为（（上界—下界）/下界）×100%。由于最优解一定处于上界和下界之间，因此对偶间隙表示了由拉格朗日松弛算法所求得的最终目标函数值偏离最优解的程度。当算法执行500次或者对偶间隙小于0.005时，拉格朗日松弛算法停止。

表2给出了所有50个实例的结果。从实验结果中可以得出以下结论：

（1）在3天的计划展望期内原料船的平均到港数是11.16。

（2）平均来看，拉格朗日松弛算法求解实际问题所花费的计算时间和所求得的对偶间隙都比较理想。以上50个例子对偶间隙的平均值为14.62%。尽管以通常的标准来看，该平均对偶间隙有些偏大，但是从以拉格朗日松弛算法研究连续泊位停泊计划的实验结果来看，本文所求得的对偶间隙属于正常范围。

（3）未改进的拉格朗日松弛算法求解50个实例所需的运行时间从19.16 s到39.25 s之间不等，而其平均运行时间是26.78 s。而改进拉格朗日松弛算法的运行时间则显著减少，平均降至3.56 s。这表明改进拉格朗日松弛算法对宝钢实际停泊计划可以在较短的运行时间内求得近优解。

5 结论

本文以最小化总权重服务时间为目标函数研究了钢铁企业原料码头具有多个连续泊位的动态停泊计划问题。该问题的特点是有两个或两个以上连续泊位且在计划开始执行时每一泊位上仅有部分泊位长度可利用。本文为该问题建立了一个数学模型来充分表述宝钢实际停泊计划问题的特性。提出了一种改进拉格朗日松弛算法来求解该问题，该算法用到了4个性质分别删除子问题求解、获得可行解和更新乘子等步骤中的不必要搜索过程从而大幅度地减少算法运行时间。实验结果表明改进的拉格朗日松弛算法能在半分钟内求得问题近优解。

表2 50个宝钢真实停泊计划问题计算结果

[1]Park K，Kim K.Berth scheduling for container terminals by using a sub-gradientoptimization technique[J].Journalof the Operational Research Society，2002，53（9）：1054-1062.

[2]Park K，Kim K.A scheduling method for berth and quay cranes[J].OR Spectrum，2003，25（1）：1-23.

[3]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，2005，39（3）：199-221.

[4]Imai A，Chen H C，Nishimura E，et al.The simultaneous berth and quay crane allocation problem[J].Transportation Research Part E，2008，44（5）：900-920.

[5]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.

[6]Imai A，Nishimura E，Hattori，M，et al.Berth allocation at indented berths for mega-containerships[J].European Journal of Operational Research，2007，179（2）：579-593.

[7]Nishimura E，Imai A，Papadimitriou S.Berth allocation planning in the public berth system by genetic algorithms[J]. European Journal of Operational Research，2001，131（2）：282-292.

[8]Guan Y，Xiao W Q，Cheung R，et al.A multiprocessor task scheduling model for berth allocation：heuristic and worstcase analysis[J].Operations Research Letters，2002，30（5）：343-350.

[9]Chen J，Lee C Y.General multiprocessor task scheduling[J]. Naval Research Logistics，1999，46（1）：57-74.

[10]Manaa A，Chu C B.Scheduling multiprocessor tasks to minimise the makespan on two dedicated processors[J].European Journal of Industrial Engineering，2010，4（3）：265-279.

[11]Lee C Y，Cai X.Scheduling one and two-processor tasks on two parallel processors[J].IIE Transactions，1999，31（5）：445-455.

[12]Guan Y，Cheung R.The berth allocation problem：models and solution methods[J].OR Spectrum，2004，26（1）：75-92.

LIU Yue1,XIE Xie2

1.Department of Software Engineering,Liaoning Information Vocational Technical College,Liaoyang,Liaoning 111000,China
2.Key Laboratory of Manufacturing and Integrated Automation,Shenyang University,Shenyang 110044,China

A dynamic berth planning problem encountered in the iron and steel industry is investigated.The dynamic features reflect that the docks have two or more berths with continuous berth sections and the berth sections on the same berth are not simultaneously available at the planning start time period.This problem is formulated as a 0-1 hybrid mathematical model.An improved Lagrangian relaxation algorithm is presented for the solution in a reasonable running time by introducing four properties to speed up the procedures of solving the sub-problems,updating Lagrangian multipliers and obtaining feasible solutions, respectively.Computational results including 50 real-size problems show that the improved algorithm can reduce more than 80%of the running time of unimproved heuristics.

raw material logistics;berth planning;Lagrangian relaxation

研究钢铁企业原料码头动态停泊计划问题，其动态特征主要体现在原料船动态到达并有两个或两个以上连续泊位且在停泊计划开始执行时每一泊位上仅有部分泊位长度可利用。针对这个问题，建立了一个数学模型并设计了改进拉格朗日算法在很短的时间内求得了近优解。在改进算法中使用了所提出的四个性质来分别加速求解子问题、乘子更新和获得可行解的过程。通过包含50个实际规模问题的算法性能实验表明改进的拉格朗日松弛算法相比未改进算法减少了80%的运行时间。

原料物流；停泊计划；拉格朗日松弛

A

TP13

10.3778/j.issn.1002-8331.1207-0398

LIU Yue,XIE Xie.Lagrangian relaxation algorithm for dynamic berth planning problem.Computer Engineering and Applications,2013,49（5）：241-247.

刘悦（1979—），女，讲师，研究领域为复杂网络、智能计算；谢谢（1981—），女，博士，讲师，研究领域为生产作业优化管理。E-mail：liaoyangliuyue@163.com

2012-07-25

2012-09-25

1002-8331（2013）05-0241-07

CNKI出版日期：2012-10-23 http://www.cnki.net/kcms/detail/11.2127.TP.20121023.1539.001.html