英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料

---

多船岸桥分配和调度问题：制定和启发式解决方案的方法

摘要：

本文提出了一种新的方法来分析集成岸桥分配和调度问题（QCASP）。这个问题决定了岸桥对船队分配任务可以通过每个码头起重机同时处理，并且占重要的考虑如岸吊（QCS），排序条件和船舶优先权之间的安全边际。此外，只要任务完成，QCs就可以从一只船运行到另一只船上。集成的问题由于其复杂性很难用准确的方法来解决。因此，遗传算法（GA）被提出用来解决集QCASP。

1.引言：

国际贸易在全球经济中发挥着至关重要的作用，而且在很大程度上依赖于海上运输，其中海上运输占全球贸易运输的90％左右（国际商会航运，2014年）。海上运输的持续增长导致了货物的集装箱化，这有促进了这个部门的发展，使之成为国际贸易的一个更为重要的组成部分。港口和集装箱码头是这个网络中至关重要的的节点，因为它们能够容纳转运品，然后将它们连接到传输网络的其余部分。图1显示，如今的全球集装箱运输流量，在20英尺当量单位（标准箱）测量，已超出了2001至2010年之间的一倍。

图1：集装箱码头吞吐量（The World Bank,2014）

港口操作涉及的一系列活动需要精心的策划和执行，以确保最大的集装箱吞吐量。当船只一到达港口，船只就会被分配到停泊位置，该位置用于集装箱的装卸作业。在泊位分配之后，船只上的集装箱就会根据工作计划安排被指定的岸桥所卸下并运输到堆场其中的某个存放区，然后由码头内的运输车运送到卡车和列车装货的地区，最后这些集装箱被装载到卡车和/或列车上，运送到期望的目的地。在集装箱到达存放堆场之前所进行的操作称为码头操作，因为这些操作是在集装箱码头岸边进行的。在堆场内进行的操作，即堆叠和存储集装箱，被称为堆场操作。

泊位建设和操作设备（比如QCs）的成本是非常高的。因此，论文研究的一个主要重点放在了与泊位和QCs的利用率有关的三个码头操作问题的优化上。第一个问题是码头空间和船舶服务时间的分配，即泊位分配问题（BAP）；第二是岸桥分配问题（QCAP），这就决定了对船只所进行的岸桥分配。在一般情况下，分配到一只船的QC的数量决定了船只处理时间。分配到船只的QC数目越少，处理一只船的时间就越多。最后一个问题是码头起重机调度问题（QCSP），其决定集装箱被每个起重机所处理的顺序，这可以最小化总的船舶处理时间。

码头作业的建模方法因不同假设而变化：（1）船舶到港时间：静态泊位分配问题认为当泊位计划指定完成时，所有船只已抵达达码头，而动态泊位分配问题允许船只在规划期间内到达 (Imai,Nishimura, amp;Papadimitriou, 2001)；（2）码头布局：具有离散布局的码头有固定的泊位数目，在同一时间每个泊位能最多可容纳一艘船(Imai, Chen, Nishimura,amp; Papadimitriou, 2008a; Imai, Nishimura, amp; Papadimitriou,2008b)，对于连续布局的码头，船只会沿着码头边，在只要空间允许的位置进行停泊。因此连续码头布局对于空间利用更有效，但也更难以解决最优靠泊计划(Meisel amp; Bierwirth,2009)；（3）船舶装卸时间：静态处理时间模型假定处理时间是固定的并事先已知的，而动态处理时间模型认为处理时间是船舶停泊位置、分配给船只的起重机数目和起重机的工作时间安排的函数。

综合码头运作模式已经被提出用来提高码头操作的整体效率，Park and Kim(2005), 和 Meisel and Bierwirth (2009)研究的BAP和QCAP集成模型。 Tavakkoli-Moghaddam, Makui, Salahi,Bazzazi, 和Taheri (2009)）提出一个模型，研究了岸桥分配和调度问题（QCASP）我们都知道当船舶处理时间是动态时，BAP需要与QCAP一起被解决，因为分配给船只的岸桥数量需要在泊位分配规划阶段加以考虑，如果问题是独立解决的，例如决定停泊时间时不考虑服务船只的QC数量，那意味着实际船只装卸时间将与给定的停泊时间不同，这也将导致泊位空闲或延迟接受新船。由于QC分配影响QC的排序，所以当QCAP和QCSP被同时考虑时QC可以被更好的利用。

在本文中，我们开发了一个模型来整合岸桥分配和调度问题，然后用一个遗传算法来确定给定问题的近似最优解。通过开发一个新的规划来对复杂问题进行综合建模和提出定制的遗传算法，本文也因此将对有效的解决已提出规划做出贡献。

本文的结构安排如下：第2部分回顾文献；第3部分给出了模型的规划；第4部分介绍并解释解决的办法；第5部分显示了一个模型的实验分析；最后，第6节总结这项研究的结果，并讨论了未来潜在的研究方向。

2.文献回顾

数个在QCAP和QCSP上研究已被用来指导完善集装箱码头操作的性能。QCSP首先在Daganzo（1989）被讨论，在文章中一个集装箱组被定义为一个任务。该问题被制定成混合整数规划（MIP）模型，船舶的总加权离岸时间也被最小化。Daganzo对任务定义与本文不同，本文对一个任务定义是单个集装箱的装载或卸载操作，而不是一个器集装箱。

Kim and Park (2004)提出了一个QCSP 的MIP模型，文中的作者门定义同一个组中的相邻集装箱的集合为一个集群，然后，他们在规划中将对每个集群所进行的转载或卸载操作定义为一个任务，集群之间的优先关系也被考虑在内，分枝定界（B＆B）的方法也随后被提出用来解决 QCSP。本文在B＆B法和启发式搜索算法基础上提出了一个类似物，即贪婪随机自适应搜索程序（GRASP）。

干扰限制在Bierwirth and Meisel (2009)的论文中被介绍到，为了试图合并更多现实的假设，作者考虑了QC非交叉的限制和约束的间隙（即安全边际相邻的QC之间），该问题也被配制为MIP模型并被基于树搜索启发式程序所解决。集装箱群组的QCSP优化解决方案可以在一个非单向时间表中找到。根据在某个预先定义的时间窗口内每个QC被限制以服务某个特定船，Meisel(2011)介绍了QCSP的时间窗的概念。QC总是从高优先级的船到低高优先级的船进行卸货。

Park and Kim (2005)首次通过两阶段的过程将泊位分配和起重机调度问题结合起来。在第一阶段他们确定每个船只的停泊时间和位置以及将被分配到所指定船舶中起重机的数量，第一阶段的目标是使集装箱装卸成本和由于未准时停泊所引起的罚款最小化；在第二阶段，它们在第一阶段结果对个别岸桥进行任务安排。

为了改善Park and Kim (2005)提出的方法，Meisel and Bierwirth（2009）提出一个模型，将QC间干扰所造成的影响以及水平运输的工作量对码头效率的影响考虑在内。吱吱轮优化启发式由作者提出，以产生解，相比于由Park and Kim （2005）提出的拉格朗日启发式，他们报告总是获得更好的结果。

Tavakkoli-Moghaddam等（2009年）将Kim and Park (2004)提出模型扩展到一系列并行的船只上。 这个论文制定针对综合QCSAP的MIP模型。 在动态规划周期内，一个QC在完成当前船只的所有任务后会从当前船只分配到下一个船只上。遗传算法被提出用来获得对于这种复杂和大规模问题的近最优解。

Choo, Klabjan, and Simchi-Levi (2009)提出了在QCSP里的多船问题。码头拥堵限制被认为连接船只。间隙约束也包括在论文中。作者通过重新制定一个MIP模型作为广义集合覆盖制定来解决单舰案，而多舰案用松弛拉格朗日的精神来分解。这两种情况之后是都用B＆P解决了。

最近Diabat amp; Theodorou, （2014）的研究介绍了一个新新的算法类型，，这实际上是将综合分配和调度问题转换成QC在海湾的分配问题。这种方法本质上允许消除时间指数，并且可以有效地使用GA求解。由于消除了时间因素，作者用较低的计算时间和较低复杂性这两个主要优势取得了非常好的汇报效果。

对QC操作问题的研究是广泛的，但由于不同阶段的相互关系，港口动力学和物理约束这些因素，如泊位的可用性，岸桥的数量，和岸桥的非交叉约束，使得已有的模型都很复杂。 这些问题大多数是NP级别难度，这就是为什么当解决这些问题和这些问题的任何扩展的时候，启发式是首选方案。 Park and Kim (2005)，Choo等（2009），以及与关，杨，周（2010）针对他们的模型提出了拉格朗日启发式TavakkoliMoghaddam 等（2009年），Kavoshgar，Huynh, 和Rahimian(2012), Chung and Choy (2012)和Diabat and Theodorou (2014)提出了QCSP模型的遗传算法。

3.数学计算

这一部分提供了码头起重机的分配和调度问题（QCASP）的详细描述。然后，用数学公式呈现。

3.1问题描述

QCSP的目标是通过确定由每个QC执行装载/卸载操作的顺序使每个船舶完工时间最小。表1提供2只分别具有3个和4个托架的船舶的负载信息表作为一个例子，在这例子中，岸桥在他们的的日程安排确定之前就被分配。图2展示了一个具有3个起重机的例子的解决方法，在这个方法中，船舶1被分配到给QC1，船舶2被分配到的QC2和QC3。正如图 3所示，如果QC2在其日程安排开始时就分配到船舶1，总的处理时间可能回减少。这个实例表明，当QCAP和QCSP同时被考虑时，QC可以被更有效地利用，因为在任何有必要的时候，岸桥可以可以被分配给不同的船。

图2：一个解决案例

图3：最优解的案例

图4：一个规划期的例子

依据Choo等 （2009年），每个船舶的停泊时间和地点被认为已给定。货柜码头操作人都有每个船舶的负荷曲线的信息，之后的目标就是在一个规划周期内确定的QC的分配以及装卸操作顺序，使完工时间可以被最小化。图4显示了一个规划期，当船舶所需的装卸时间来实成后，其工作完成标志被设置为1。因此想要减少集装箱码头的完工时间，就要求在一个给定的规划期内使完成工作的标志数目最大。

3.2模型假设和公式

该模型是建立在以下假设：

（i）岸桥可以从一个船舶移动到另一个，并且服务它。

（ii）每个岸桥有相同的工作效率。

(iii) 双向岸桥运动是允许的。

(iv) 岸桥被定位在单一的轨道；因此，它们是升序是从左至右。

(v) 考虑岸桥之间的安全边际。

(vi) 船舶停泊位置给定。

(vii) 不同的船有不同的优先级。

(viii) 岸桥的运动时间不考虑。

表1:负载分布一个例子

表2：负载分布一个例子

用于简化问题的符号如下所示：

定义：

K船舶k

Jk 船舶 k上的托架j

Q 岸桥q:

q 是岸桥数字，从左到右进行递增排序

T 时间段 t

参数：

lkj船k上托架j的位置

m 安全边际

pkj 在船k托架Ĵ上完成工作 Unit : QC ---时间段

ck 船k的单位操作时间成本

结果变量：

如果岸桥q为t时刻分配给船k的托架j

否则

如果船k的托架j的在时间t内完全处理

否则

如果船k被在时间t内充分处理

否则

以下是此模式的IP公式：

推出

目标函数(1)的目的是最大限度地提高的总和加权工作完成标志。约束(2)和(3)分别确保岸桥在任何时间段只能在定位在单个托架上以及在任何时候仅一个QC可定位于托架上。约束(4)强调在任何时间服务的QC的总数不能超过总的可使用QC数。约束(5)强调通过以递增顺序对QC从左到右排序定位。

它还强调定位QC的过关条件至少是m托架远。约束(6)限制所有的集装箱分配要在规划期内完成，在托架工作的起重机时间段的总和必须超过所有集装箱处理时间。约束(7)为每个托架定义工作完成标志，船舶k的托架J上所有集装箱被处理后，fkjt被置为1。约束(8)确保船上每个托架任务完成完成后整只船的任务也完成。约束(9)确保变量x，f和r都是二进制的。

4.解决方法

由于在每个时间单元为每个QC分配一只船和一个托架是很复杂的决策，所以解决QCASP是一个挑战性的问题。当精确的解决方法不能够解决这样的问题时大而复杂问题，本文将采用遗传算法来解决这样。这一部分呈现的是遗传算法的一般概念，接着是介绍所提出的遗传算法。

4.1遗传算法

遗传算法（GA）是通过模仿自然的进化过程而进行优化问题的其启发式搜索。 图5阐释了遗传算法的过程。首先，有一个初始群体，从这个人群中，每个个体将进行适应值评价，具有良好适应值的个体被选择作为父母用于繁殖下一代。 然后通过遗传操作产生新的个体，并将其插入到人群中以取代不太适合的个体(Chipperfield, Fleming, Pohlheim, amp; Fonseca, 1994)。

图5：遗传算法过程

4.2 遗传算法的发展

4.2.1 染色体表示

染色体表示是在遗传算法执行的第一个步骤，所有船卸载需要的各时段代表染色体的一个基因。在染

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[152372]，资料为PDF文档或Word文档，PDF文档可免费转换为Word