Transportation Research Part E: Logistics and Transportation Review
Volume 44, Issue 5, September 2008, Pages 900-920
The simultaneous berth and quay crane allocation problem
Author links open overlay panelAkioImaiabHsieh ChiaChenaEtsukoNishimuraaStratosPapadimitriouc
Show more
https://doi.org/10.1016/j.tre.2007.03.003Get rights and content
Abstract
This paper addresses efficient berth and crane allocation scheduling at a multi-user container terminal. First, we introduce a formulation for the simultaneous berth and crane allocation problem. Next, by employing genetic algorithm we develop a heuristic to find an approximate solution for the problem. The fitness value of a chromosome is obtained by crane transfer scheduling across berths, which is determined by a maximum flow problem-based algorithm based on a berth allocation problem solution defined by the chromosome. The results of numerical experiments show that the proposed heuristic is applicable to solve this difficult but essential terminal operation problem.
Keywords
Berth allocation
Crane scheduling
Terminal management
Container transportation
Mathematical programming
1. Introduction
In multi-user container terminals (MUTs) featuring a long quay, efficient berth allocation is a vital factor for successful terminal operations. In the existing literature it has been demonstrated that by employing flexible ship-berth-order allocation without taking into account the First-Come-First-Served rule, high productivity is obtained, where a shiprsquo;s handling time depends on its berthing location.
Quay cranes are one of the key terminal equipment used for container movement. This in turn implies that inefficient quay crane employment could be the bottleneck for fast ship handling operations. For this reason, a terminal is obliged to be able to provide as many cranes as possible to serve a specific ship; however, when there is a fluctuation in ship calling frequency, this turns out to be a very expensive and certainly not a cost-effective investment, especially due to the high crane costs. Therefore, a competitive terminal needs to maximize the operating efficiency of a rather limited number of cranes.
As shown in Fig. 1, container quay cranes are mounted on the same track (or rail) and move from one berth to another on the track. This structural feature does not enable them to bypass each other and consequently they cannot move freely when requested at another berth. This study considers crane allocation (or scheduling), with respect to the decision to be made as to when and how many cranes are to be moved from a specific berth to another berth for fast overall ship handling in the system. From this point of view, the berth allocation and crane allocation are closely related.
Fig. 1. Crane allocation.
Envisage the following situation in which ships can start service only when a predetermined number of cranes have been allocated to them. There are three berths: 1, 2 and 3, located in that order. Berth 1 is serving a ship with the required number of cranes. Also this berth has some extra cranes which are currently not being used for ongoing handling and remain idle. Berth 2, located between berths 1 and 3, is using a number of cranes in serving a ship with a long handling task. Berth 3 is idle with very few cranes available when a ship is arriving at the terminal. The arriving ship can be berthed at berth 3, but in most cases it does not start its handling if the available cranes are much fewer than the ones required. In such a case, if the surplus cranes at berth 1 were able to move to berth 3 through berth 2, the ship at berth 3 would start its service immediately; however this is not practical since the ship at berth 2 utilizes a number of cranes and it is almost impossible to suspend the shiprsquo;s handling by stopping all the cranes
全文共62641字，剩余内容已隐藏，支付完成后下载完整资料
运输研究E部分:物流与运输综述
摘要：本文研究了多用户集装箱码头泊位和起重机的有效调度问题。首先，介绍了泊位与起重机同时分配问题的一种计算方法。其次，利用遗传算法，我们开发了一个启发式算法来寻找问题的近似解。染色体的适应度值通过跨泊位的起重机转移调度得到，该适应度值由基于最大流量问题的算法确定，该算法基于染色体定义的泊位分配问题求解。数值实验结果表明，所提出的启发式算法能够较好地解决这一复杂而又关键的终端操作问题。
关键字：泊位分配 起重机调度 终端管理 集装箱运输 数学规划
1. 介绍：在长码头的多用户集装箱码头(MUTs)中，有效的泊位分配是码头运营成败的重要因素。已有文献表明，在不考虑先到先得规则的情况下，采用灵活的泊位顺序分配，船舶的靠泊时间取决于船舶的靠泊位置，可以获得较高的生产效率。码头起重机是集装箱运输的关键设备之一。这进而意味着码头起重机的使用效率低下可能成为船舶快速装卸作业的瓶颈。因此，一个码头必须能够提供尽可能多的起重机来为一艘特定的船只服务;然而，当船舶呼叫频率出现波动时，这将是一项非常昂贵的投资，当然也不是一项划算的投资，尤其是考虑到起重机的高成本。因此，一个具有竞争力的终端需要最大化数量有限的起重机的运行效率。如图1所示，集装箱码头起重机安装在同一轨道(或轨道)上，并在轨道上从一个泊位移动到另一个泊位。这一结构特点使它们不能互相绕过，因此它们不能在另一个泊位上按要求自由移动。本研究考虑的是起重机的配置(或调度)，即在系统中，为了快速地整体装卸船舶，需要在何时、将多少台起重机从一个特定的泊位移到另一个泊位。从这个角度看，泊位分配与起重机分配密切相关。
图1所示。起重机分配。
设想以下情况:只有预先确定数量的起重机被分配给船舶时，船舶才能开始作业。有三个泊位:1、2和3，按顺序排列。1号泊位正在为一艘船提供所需数量的起重机。此外，这个泊位还有一些额外的起重机，目前没有用于正在进行的处理和保持闲置。2号泊位位于泊位1和泊位3之间，使用多个起重机为船舶提供长时间的装卸作业。当船到达码头时，3号泊位处于闲置状态，可用的起重机很少。到达的船只可以停泊在3号泊位，但在大多数情况下，如果可用的起重机比所需的少得多，它就不会开始装卸。在这种情况下，如果1号泊位的剩余起重机能够通过2号泊位移动到3号泊位，3号泊位的船舶将立即开始作业;然而，这是不现实的，因为停泊在2号泊位的船舶使用了许多起重机，而且几乎不可能通过停止所有与船舶有关的起重机来暂停船舶的操作，以便让一台起重机从1号泊位通过到3号泊位。另一种加快周转速度的方法是让来船等待1号泊位空闲。这个例子说明了泊位和起重机分配之间的密切关系。
同时也注意到集装箱船尺寸的增加趋势，导致了停靠在枢纽的船舶尺寸的巨大差异。因此，不同数量的码头起重机的变化，需要处理一艘船将增加。因此，起重机配置的重要性将变得更加重要。本文提出了一种最小化总服务时间(包括等待和处理时间)的泊位起重机同时分配模型，并提出了一种基于遗传算法的启发式算法。
论文组织如下：下一节将提供关于泊位和起重机分配规划的文献综述。第3节讨论了问题的提法。第4节介绍了一个求解算法，第5节进行了一些计算分析。最后一部分对全文进行了总结。
- 关于泊位和起重机调度的文献综述
随着码头作业效率问题的日益重要，有关泊位分配问题(BAP)和码头起重机分配问题(CAP)的研究也越来越多，但同时对这两个问题进行研究的很少。
Lai和Shih(1992)提出了一种启发式的泊位分配算法，该算法的动机是香港HIT终端更有效的使用终端(实际上是泊位)。他们的问题考虑的是先到先得(FCFS)分配策略，而我们的问题则不是这样。Brown等人，1994年，Brown等人，1997年研究了海军港口的船舶操作。他们确定了最佳的船舶到泊位分配集，最大限度地提高船舶在港口的效益。海军港口泊位规划与商业港口泊位规划有重要区别。在前一种情况下，当为了提供适当的服务，必须将一艘新到的船分配到另一艘船已经在服务的泊位时，就会发生泊位转移。这种处理在商业港口是不可能的。他们的论文考虑了移泊等与商埠无关的因素，使得他们的研究不适用于商埠。
Imai等人(1997)针对商业港口提出了一个BAP。大多数服务队列通常是在FCFS的基础上处理的。他们的结论是，为了获得较高的港口生产力，应该在不考虑FCFS规则的情况下找到一组最优的船舶到泊位分配。然而，这一服务原则可能会导致某些船舶不满意服务秩序。为了处理这两个评价标准，即，泊位性能和对服务顺序的不满意，他们开发了一种启发式方法来寻找一组非劣解，同时最大化前者和最小化后者。他们的研究假设了一种静态的情况，即在计划泊位分配之前，为规划期服务的船只都已到达港口。因此，他们的研究只能应用于非常繁忙的港口。就集装箱运输而言，这样繁忙的港口既没有竞争力，也不现实，因为在港口的交换过程中存在着长时间的延误。在这一背景下，Imai等人，2001,Imai等人，2005a将BAP的静态版本扩展为与静态处理类似的动态处理，但不同的是，一些船只到达时，工作正在进行中。作为这一动态处理的第一步，只有一个目标，泊位性能，被考虑。由于寻找精确解的困难，他们利用拉格朗日弛豫的次梯度法开发了一种启发式算法。他们的研究假设所有泊位的水深相同，而实际上某些港口的泊位水深不同。Nishimura等人(2001)进一步扩展了BAP的多水深配置的动态版本。他们用遗传算法来解决这个问题。在一些实际情况下，码头运营商会给呼叫船只分配不同的优先级。例如，在中国的一个码头，小型支线船拥有优先权，因为与它们相关的处理工作在很短的时间内完成，而大型船舶不需要等待很长时间。另一方面，新加坡的一个码头对大型船舶的优先权更高，因为它们是码头的好客户。Imai et al.(2003)在Imai et al.， 2001, Imai et al.， 2005a中扩展了BAP，以处理具有不同优先级的船舶，并查看扩展的BAP如何根据与船舶相关的服务时间来区分对船舶的处理。Imai等人(2007)提出了将多艘船同时停泊在缩进泊位的BAP，这对于大型集装箱船的快速周转具有潜在的帮助。
还有另一种类型的泊位分配问题，它具有连续的位置索引(称为BAPC)。在上述研究中，整个码头空间被划分为多个部分(或泊位)，并根据划分的泊位空间进行分配。这可能会导致一些泊位空间闲置。在连续定位方法下，船舶可以通过一个连续定位系统，在任何可用的物理空间容纳船舶的地方提供服务。这类问题或多或少类似于库存削减问题，即一套商品以一种有效的方式包装在一些盒子里。船舶在泊位等待和服务可以通过一个矩形显示在一个时空表示或甘特图,因此有效泊位的使用是一种包装“船矩形”berth-time可用性与一些有限的一盒包装方案,不允许船舶矩形旋转。Lim(1998)提出了一个问题，其目标是在任何时候最大限度地减少码头空间的使用，并假设船舶一旦靠泊，在离开码头之前不会沿着码头移动到其他任何地方。他还假定每艘船一到港口就停泊了。另一方面，Li等人(1998)解决了有和没有船舶运动限制的BAPC问题。他们的目标是使完工时间最小化。Guan等人(2002)为BAPC开发了一种启发式方法，其目标是最小化船舶服务的总加权完成时间。Park和Kim(2002)研究了BAPC，其目标是将船舶在港口非最佳系泊位置服务时，由于不需要的服务订单和处理集装箱的额外复杂性而造成的延迟离港成本降至最低。他们的工作比上述的BAPC研究更实际，因为客观评估的因素取决于船只的码头位置。Kim and Moon(2003)处理的BAPC与Park and Kim(2002)处理的相同，但前者采用模拟退火方法，后者采用亚梯度优化方法。注意，上述所有的BAPC研究都认为船舶装卸时间与停泊位置无关。Imai等人(2005b)研究了一个BAPC，但与其他BAPC的主要区别在于，处理时间取决于船舶的停泊位置。在Imai et al.， 2001, Imai et al.， 2005a中，他们与动态BAP的启发式算法合作开发了该问题的启发式算法。他们的研究结论是，在泊位长度为问题所涉及船舶最大长度的离散位置，将最佳近似解与最佳解相结合。这说明离散位置解适用于泊位分配规划的实践，可以从离散位置解中得到改进的解。Cordeau等人(2005)开发了一个禁忌搜索启发式的动态BAP在两个版本的离散和连续位置索引。分析了用CPLEX方法求解精确解的离散位置启发式算法的解质量;然而，应用的问题案例相对较小。对于连续定位版本，通过与解决方案的比较，采用直观的启发式方法来评估解决方案的质量。
目前国内外对集装箱码头码头吊车调度的研究不多，特别是对传统码头吊车调度和集装箱码头吊车调度的研究更是少之又少。码头起重机在码头轨道上移动时，由于不能相互通过而被限制沿泊位移动到另一个位置。Daganzo(1989)最初提出了一种高效的起重机调度启发式算法，该算法将一组起重机最优地分配给多艘正在服役的船舶，使港口船舶周转延迟的总成本最小化。Peterkofsky和Daganzo(1990)在随后的研究中，利用分枝定界技术实现了一种精确的求解方法。Kim和Park(2004)解决了集装箱船舶的起重机调度问题，该问题安排用于处理特定单船(而不是处理任务下的多船)的起重机，以最小化船舶的周转时间。因此，他们的研究是在不同于前两项研究的背景下进行的。
也有一些研究涉及到类似于本研究的船舶的泊位和码头起重机的配置问题。Park and Kim(2003)采用与Park and Kim, 2002, Kim and Moon, 2003所表达的目标相似的起重机配置连续位置指数研究了BAP。Park和Kim(2003)确定了船舶服务和相关系泊位置的最佳启动时间，同时确定了码头起重机对这些船舶的最佳分配。在他们的研究中，某艘船的装卸时间是该船所使用码头起重机数量的函数;然而，装卸时间与船舶的系泊位置无关。其求解过程包括两个阶段:泊位分配阶段和起重机分配阶段。从某种意义上说，他们通过独立求解泊位分配和起重机分配，简单地解决了泊位-起重机分配问题。Lee等人(2005)也处理了泊位和起重机的分配问题。他们利用遗传算法将整个问题分解为BAP和CAP;然而，他们的论文没有提供关于解决程序的详细说明。
- 问题公式化
如前所述，船舶泊位和码头起重机分配问题(Bamp;CAP)包括两个子问题:一个是BAP，另一个是CAP。Bamp;CAP假设船舶和码头起重机分配靠泊位置的离散泊位单元。
对于泊位分配，我们的假设与Imai等人(2001)对DBAP的假设相同。那就是:(a)每个泊位可同时供一艘船使用。(b)没有物理或技术限制，例如船舶吃水和水深。(c)船舶装卸时间取决于指定的泊位。(d)船舶到达后才提供服务。(e)船舶装卸任务一旦开始，就必须不间断地完成。对于起重机调度，做以下假设:(f)船舶装卸需要特定数量的起重机，在有足够数量的起重机之前不会开始。(g)如果其他泊位从事船舶装卸作业，起重机不能通过其他泊位从一个泊位移到另一个泊位。(h)起重机通过一个闲置的泊位，通过推入和拉出程序得到一些起重机。
关于假设(c)，值得注意的是，Bamp;CAP并不意味着在某一特定泊位上的船舶的装卸时间是恒定的，而不论装卸该船舶的起重机数量如何。将看到Bamp;CAP制定的,虽然我们没有明确考虑起重机的数量作为一个因素影响船的处理时间,我们间接地假设处理速度依赖于起重机的数量由规划者在特定泊位服务特定的船,即。，假设(c)，在公式的约束条件中用作参数。
注意，假设(f)可能不实用，因为在实际操作中，船舶处理可以从一些可用的起重机开始，即使数量少于需要的起重机，以便尽量减少港口周转的延误。这个假设是为了促进问题的解决过程。让船舶用更少的起重机开始装卸，然后在装卸过程中增加一些起重机，要求该公式定义船舶装卸时间，不仅取决于分配给船舶的泊位，还取决于船舶所使用的起重机的数量。此外，它要求考虑装卸速度随时间的变化，因为起重机是增加或从正在考虑的船舶装卸中撤出。这种起重机的使用，虽然可能是现实的，但它以复杂的形式(可能是非线性的)转换了公式，并使求解过程相当复杂。认为本文所研究的Bamp;CAP问题解提供了上述所讨论的柔性起重机使用Bamp;CAP问题解的上界。
假设(g)集装箱码头码头起重机基本由多个泊位和船舶共用;因此，在处理有关船舶的作业时，将一些起重机从一个泊位(船)移到另一个泊位(船)是常见的做法。这也与假设(f)有关。事实上，在相邻的两个泊位之间移动起重机在物理上并不困难，即使这些泊位是为船舶服务的。虽然作者不了解集装箱码头码头起重机转运的具体情况，但很容易想象到，通过一些泊位(在装卸任务下)的起重机移动会影响这些中间泊位船舶的顺利装卸。因此，在泊位较多的大型集装箱码头，如5个或5个以上泊位，频繁的吊车移动受到很大限制。如果一个中间泊位使用许多起重机(比如7台)为一艘大型船舶提供服务，那么所有的起重机必须同时停止工作，以便让一台起重机从一个泊位移动到另一个泊位。这导致服务中断，并随后导致处理大型船舶的长时间延迟。根据上述讨论，假设(e)、(f)及(g)未必适用于所有情况，但可被认为适用于大型货柜码头。注意，在本研究中，允许起重机在怠速状态下通过中间泊位移动。
采用遗传算法求解Bamp;CAP问题。Park and Kim(2003)将Bamp;CAP作为两个独立的问题来处理:BAP和CAP。相反，本研究同时确定了这两个独立的决策，而这两个决策过程是在整个GA求解过程的迭代中一个一个构建的。在BAP阶段，确定船到泊位的分配。在这种分配下，起重机通过在所有泊位上按顺序分配船舶处理任务来调度。在问题设置中，如果泊位上可用的起重机数量少于该任务所需的起重机数量，则每个泊位上的船舶处理任务不会启动;因此，任务将被推迟到它得到足够数量的起重机。这意味着在整个特定的计算迭代中，BAP解决方案保持不变。
通过以上讨论，Bamp;CAP的公式可以分为BAP和CAP两部分，在组成Bamp;
全文共9904字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[1119]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
