集装箱码头泊位分配与码头起重机调度问题综述外文翻译资料

 2022-08-02 14:00:23

A survey of berth allocation and quay crane scheduling problems in container terminals

Abstract

Due to the variety of technical equipments and terminal layouts, research has produced a multitude of optimization models for seaside operations planning in container terminals. To provide a support in modeling problem characteristics and in suggesting applicable algorithms this paper reviews the relevant literature. For this purpose new classification schemes for berth allocation problems and quay crane scheduling problems are developed. Particular focus is put on integrated solution approaches which receive increasing importance for the terminal management.

Keywords:Container terminal operations、Berth allocation、Quay crane assignment

Quay crane scheduling、Problem classification、Integrated planning

1. Introduction

In recent years, OR methods have received considerable importance for the operations management in container terminals (CTs). Comprehensive overviews on applications and optimization models in this field are given by Meersmans and Dekker, 2001, Vis and de Koster, 2003, Steenken et al., 2004, Vacca et al., 2007, Stahlbock and Voszlig;, 2008. A significant amount of papers dealing with the application of OR methods addresses the planning of the seaside transshipment operations. Fig. 1 shows important relations of the strategic planning and the operations planning at the seaside area, the yard, and the landside area.

One issue of seaside operations planning is the assignment of quay space and service time to vessels that have to be unloaded and loaded at a terminal. This problem is commonly referred to as the berth allocation problem (BAP). The transshipment of containers between a vessel and the quay is generally performed by specialized cranes, which are mounted on rail tracks alongside the quay. The assignment of these quay cranes (QCs) to vessels and the determination of work plans for the cranes addresses two further problems, namely the quay crane assignment problem (QCAP) and the quay crane scheduling problem (QCSP). Solutions to these problems must respect the berth layout and the used equipment, whereas they impact the yard operations and the workforce planning, see Fig. 1.

Due to the variety of technical equipments and terminal layouts, research has produced a multitude of optimization models for the BAP, the QCAP, and the QCSP. Moreover, a trend towards an integrated solution of these problems is observed in the recent literature. The large number of available models and proposed solution methods prevents an easy choice of a suitable approach in a specific situation. To provide a support in modeling problem characteristics and in suggesting applicable algorithms this paper develops classification schemes for BAPs, QCSPs, and integrated approaches.

The paper is organized as follows. In Section 2 the focused operational planning problems are described in detail against the background of different terminal properties and objectives. A literature survey of BAP and QCAP formulations is presented in Section 3 which is derived from a new classification scheme for these problems. Accordingly, a classification scheme and a literature survey are presented for QCSP formulations in Section 4. Since future advances in the field are expected from integrated solution approaches, Section 5 provides a literature review of the state-of-the-art integration concepts. The paper is summarized in Section 6.

2. Planning of seaside operations

2.1. Berth allocation problem

In the BAP we are given the berth layout of a CT together with a set of vessels that have to be served within the planning horizon. For each vessel additional data like the vesselrsquo;s length including clearance, its draft, the expected time of arrival, and the projected handling time can be given. All vessels must be moored within the boundaries of the quay. They are not allowed to occupy the same quay space at a time. The problem is to assign a berthing position and a berthing time to each vessel, such that a given objective function is optimized. An example for the graphical representation of a berth plan with five vessels is shown in Fig. 2a. Berth planning has been shown to be an NP -hard problem by relating it to the set partitioning problem (集装箱码头泊位分配与码头起重机调度问题综述

由于技术装备和码头布局的多样性,研究建立了多种集装箱码头临海作业规划优化模型。为了在建模问题特征和提出适用算法方面提供支持,本文回顾了相关文献。为此,提出了新的泊位分配问题和码头起重机调度问题的分类方案。特别关注的是集成解决方案方法,这些方法对于终端管理越来越重要

一、介绍

海上作业计划的一个问题是,将码头空间和服务时间分配给必须在码头卸货和装货的船舶。这个问题通常被称为泊位分配问题(BAP)。集装箱在船舶和码头之间的转运通常由安装在码头旁边轨道上的专用起重机进行。将这些码头起重机(QCs)分配给船舶和确定起重机的工作计划解决了另外两个问题,即码头起重机分配问题(QCAP)和码头起重机调度问题(QCSP)。这些问题的解决方案必须尊重泊位布局和使用的设备,但它们会影响堆场作业和劳动力规划,见图1。

论文的结构如下。在第二节中,针对不同的终端属性和目标,详细描述了重点作战计划问题。第3节介绍了BAP和QCAP公式的文献综述,这些公式是从一个新的分类方案中导出的。因此,第4节给出了QCSP配方的分类方案和文献综述。由于集成解决方案方法有望在该领域取得未来的进展,第5节提供了最新集成概念的文献综述。本文在第6节中进行了总结。

2.1泊位分配问题

在泊位分配中可能会有进一步的限制,这会导致许多BAP公式。空间约束根据码头预设的泊位划分来限制船舶的可行停泊位置。据Imai等人说。(2005)区分下列情况:

(2)连续布局:码头没有分隔,即船只可以在码头边界内的任意位置停泊(图3c)。对于连续布局,泊位规划比离散布局更为复杂,其优点是能更好地利用码头空间。

在吃水限制的情况下,进一步的空间限制必须确保船舶停泊在足够水深的位置。为避免延长装卸时间,集装箱船在整个服务期间通常停留在指定的停泊位置。相反,允许船舶在海军港口和一般货物码头重新定位,见e.g.Brown等人,1994年,Brown等人,1997年,Lee和Chen,2008年。

(2)动态到达:船舶的到达时间是固定的,因此,船舶不能在预期到达时间之前停泊。

在绝大多数已发表的BAP模型中,船舶装卸时间被假定为确定性的。然而,文献以不同的方式论述船舶装卸时间:

(2)它们取决于船只的停泊位置。

(4)它们取决于指定起重机的工作时间表。

泊位规划的总目标是为船舶提供快速可靠的服务。这在文学作品中体现为各种客观功能。将船舶等待和装卸时间(即港口停留时间)之和最小化的模型明显占优势。进一步的目标是,例如,尽量减少码头资源的工作量,尽量减少拒绝在码头服务的船只的数量。泊位计划的绩效通常是根据成本来衡量的,这允许在一个总体成本函数中结合不同的目标。

在QCAP中,我们给出了一个可行的泊位计划和一组相同的QCs,它们可供使用。对于泊位计划中包含的每艘船舶,已知要装载和卸载的集装箱体积以及允许同时使用的最大起重机数量。起重机应该沿着码头排成一排。它们可以移动到每一艘船上,但不能相互通过。问题是将起重机分配给船舶,以便能够完成所有要求的集装箱转运,见图2b。起重机分配给船舶有时被称为起重机分离,参见Steenken等人。(2004年)。QCAP和BAP基本上是相互关联的,因为QCAP的求解会对船舶的装卸时间产生很大的影响。只有在离散泊位布局的情况下,如果每个泊位都有一组专用起重机,则无需将起重机明确分配给船舶。

(1)一艘船上有许多起重机或一组特定的起重机。

(3)可规定在整个装卸期间为船舶服务的起重机的最少数量。这个号码通常是船舶经营人和CT经营人之间合同的一部分。

在实践中,如果用经验法则来解决QCAP问题,就不会发现它是一个难题。因此,这一问题在学术研究中几乎没有得到应有的重视。然而,由于对船舶装卸时间的深刻影响,在一些先进的泊位规划模型中涉及到起重机的分配决策。

在QCSP中,我们考虑一组代表船只转运操作的任务和一组指定的QCs。可以给出任务之间的优先关系,以确保卸货先于装货,并表示积载计划中定义的集装箱堆叠。每个任务必须由QC处理一次(通常没有抢占权),而QC一次最多只能处理一个任务。这个问题的解决方案称为QC计划,它定义了起重机上每个任务的开始时间。通常,质量控制计划的完工时间最小化是因为它代表了所考虑船舶的装卸时间。到目前为止,所描述的问题对应于具有并行相同机器和优先约束的最小makespan调度问题。这个问题是众所周知的 多台起重机在意义上是困难的,只要有两台以上的机器(起重机),就可以给出非抢占或非均匀的处理时间(Pinedo,2002)。

在QCSP上计划的任务描述了在QCSP模型中考虑船只工作负载的粒度。任务可以基于间隔区域或单个间隔(图4a)或基于容器堆栈、容器组或单个容器(图4b)定义:

(2)间隔:任务由间隔中的所有加载和卸载操作组成。

(4)组:任务是指存储在间隔相邻插槽中的一组容器。分组容器通常有一个共同的目的地等。

将船舶的工作量划分为湾区的想法是,由一名质量控制人员专门为每个湾区提供服务。如果间隔区域不重叠,则完全避免起重机干扰。然而,起重机之间的工作负荷分配往往不可能达到充分的平衡。在案例(2)中,可能可以实现更好的工作负载分布,但由于所需的非交叉约束,解决该问题变得更加复杂。由于任务的数量受容器大小的限制,因此问题的复杂性仍然是中等的。进一步降低粒度可以改善起重机调度,但会增加问题的复杂性。在病例(5)中观察到的大血管有成百上千的任务,相应的QCSP可能变得难以处理。

(2)时间窗口:对于每台起重机,可以使用一个或多个时间窗口来指定起重机可以为所考虑的船舶服务的时间跨度。这些时间窗通常是时间起重机分配变量的结果。 (3)位置:起重机的初始和最终位置是规定的。

2.4问题整合方法

通过在整体优化问题中考虑海边作业计划,有望得到补救。然而,在实际环境中,这样的模型太大,根本无法求解。因此,最近的研究集中在设计合适的问题集成方法上。根据Geoffrion(1999)的观点,问题的集成可以通过深度集成或功能集成来完成。Muhanna和Pick,1988,Dolk和Kottemann,1993以不同的术语提出了类似的概念。

功能集成是通过一个计算议程来实现的,该计算议程定义了一个用于解决子问题的序列以及底层和顶层之间的数据交换。这两个问题是功能上的集成,要么通过一个反馈环结构,要么通过一个预处理阶段。在反馈回路结构(图6a)中,顶层问题指示底层问题,并且在顶层中使用底层反应来修改指令。一旦达到稳定状态,此循环即终止。例如,在涉及QCAP和QCSP的回路中,QCAP确定同时服务的船舶的起重机分配。对于每个容器,都会有一个单独的QCSP实例结果,该结果在基础级别求解。在顶层,使用返回的起重机计划表检查船舶是否分配了足够的起重机容量。通过预处理的功能集成(图6b)开始解决底层问题,以便为顶层问题生成更详细的输入数据。之后,这两个问题都以共同的方式依次解决。例如,给定一个有前途的起重机分配,求解一组相应的QCSP实例。在泊位规划阶段,将在预处理过程中生成的起重机时刻表的最短时间作为船舶的装卸时间。

三。泊位分配和码头起重机分配

为了显示现有泊位分配模型的相同点和不同点,在下面开发了一个分类方案。专注于码头起重机分配的研究,要么以特定类型的BAP为前提,要么在泊位规划过程中整合码头起重机分配决策。因此,QCAP方法也被分类方案捕获。问题按四个属性分类。空间属性涉及泊位布局和水深限制。t

资料编号:[240837],资料为PDF文档或Word文档,PDF文档可免费转换为Word

原文和译文剩余内容已隐藏,您需要先支付 30元 才能查看原文和译文全部内容!立即支付

以上是毕业论文外文翻译,课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。