英语原文共 17 页，剩余内容已隐藏，支付完成后下载完整资料
集装箱码头最佳泊位布置与动态岸桥
分配和调度优化
欧洲运筹学报
Yavuz B.Tuuml;rkogullarıa, Z.Caner Tacedil;skın, Necati Aras,I. Kuban Altınel
摘要：在过去的三十年里，世界集装箱运输量急剧增加。因此，集装箱码头的有效管理成为一个关键问题。在本项研究中，我们主要致力于海滨综合作业问题，即泊位布置、码头起重机分配和码头起重机调度问题的整合。首先，我们建立了一个混合整数线性规划，其精确解给出了船舶的最佳停泊位置和停泊时间，以及起重机在船舶停靠码头期间的时刻表。然后，我们提出了一种基于分解方案的高效切割平面算法。我们的方法是，在主要问题中处理船舶的停泊位置及其在每个时间段内所分配的起重机数量，并通过求解子问题寻求相应的最优起重机调度。我们证明了起重机调度子问题在一般成本条件下是NP完备的，但在某些特殊情况下可以用多项式时间加以求解。计算研究表明，我们的新公式和所提出的求解方法可以为实例提供最优解。
关键词：整数规划、集装箱码头管理、泊位分配、起重机作业、起重机调度
ABSTRACT：There has been a dramatic increase in worldrsquo;s
container traffic during the last thirty years. As a consequence, the efficient management of container terminals has become a crucial issue. In this work we concentrate on the integrated seaside operations, namely the integration of berth allocation, quay crane assignment and quay crane scheduling problems. First, we formulate a mixed-integer linear program whose exact solution gives optimal berthing positions and berthing times of the vessels, along with their crane schedules during their stay at the quay. Then, we propose an efficient cutting plane algorithm based on a decomposition scheme. Our approach deals with berthing positions of the vessels and their assigned number of cranes in each time period in a master problem, and seeks the corresponding optimal crane schedule by solving a subproblem. We prove that the crane scheduling subproblem is NP-complete under general cost settings, but can be solved in polynomial time for certain special cases. Our computational study shows that our new formulation and proposed solution method yield optimal solutions for realistic-sized instances.
copy; 2016 Elsevier B.V. All rights reserved.
Keywords:Integer programming、Container terminal management、Berth allocation、Crane assignment、Crane scheduling
- 引言
由与运输时间短、运输成本低、可靠性和安全性高以及运输方式多样化等优点，集装箱运输成为了大受欢迎的运输方式。在过去的30年里，集装箱贸易在世界干货物总量中所占的份额有了相当大的增长：从2000年至2010年的增长率为53.3%，其中仅2010年一年就占有11%的份额。由于集装箱运输量的急剧增加，集装箱码头的有效管理已成为一个关键问题，并吸引了包括运筹学在内的各个学科的大量研究工作。这是一项艰巨的任务，因为存在相互依赖的作业方式，可以大致分为海上作业、转运作业和堆场作业。在本项研究中，我们主要研究海滨作业的综合规划，包括泊位分配问题（BAP）、码头起重机分配问题（CAP）和码头起重机调度问题（CSP）。我们将引导任何对转移和堆场作业特别感兴趣, 特别是在集装箱的转运流程以及海滨和堆场之间的相关决策问题感兴趣的读者, 关注由Vacca (2010年) 进行的研究工作。
海滨作业的有效规划直接影响船舶的停留时间（即船舶到达和离开之间的时间，包括等待和装卸的时间之和），这是集装箱码头的主要性能指标之一。主流国际海运港口通常有多个由不同公司经营的集装箱码头。因此，较长的停留时间会对港口和码头运营公司的竞争力产生负面影响。这便解释了研究中关于BAP、CAP、CSP及其结合的研究的存在，即泊位分配和码头起重机分配问题（BACAP）、起重机分配和调度问题（CAP）和泊位分配、码头起重机分配和调度问题（BACASP）。我们的目标是深度综合问题，由Geoffrion（1994年）定义，其中子问题以单一、统一的数学优化框架的形式组合。
一般来说，BAP涉及集装箱码头中船舶最佳停泊时间和位置的确定。另一方面，CSP的重点在于确定码头起重机的最佳船舶装卸计划。Bierwirth和Meisel（2010年、2015年）以及Carlo、Vis和Roodbergen（2015年）对相关作品进行了出色的近期调查，并根据某些特定属性进行了分类。CAP确定了分配给船舶的最佳起重机数量，因此可以视为最佳起重机分配问题的一种特殊形式（Steenken等人研究，2004）。CAP相对简单，因此在实际应用中可以很容易地用直观的推理来解决最优性问题，这使它看起来没有太多研究价值。但实际情况是，起重机数量直接影响船舶的加工时间。因此，相关的决策应该嵌入到BAP或CSP模型中。
据我们所知，最早尝试BACASP的研究是由Rashidi（2006）、Theofanis、Golias和博伊尔（2007），张，郑，张，石，阿姆斯特朗（2010）所做的，他们把BAP、CAP和CSP整合到同一个数学优化模型中，以确定船舶的最佳停泊时间和位置，起重机的数量、种类以及时间表。在刘、万和王（2006）的工作中，BAP方面的整合略显薄弱。他们的BACAP模型确定了最佳的起重机数量和规格，但是最佳的解决方案只包括了船只的停泊时间，而没有任何关于其停泊位置的信息。此外，它们使用预处理方案为每艘船舶和起重机可分配数量生成可能的处理时间，作为其BACASP模型的输入。Meier和Schumann（2007年）、Meisel（2009年）、Meisel和Bierwirth（2013年）以及AK（2008年）也采用了同样的方法。Meier和Schumann（2007）试图通过将其CASP模型与BAP进行功能结合来实现这一点。然而，Meisel（2009年）和Meisel和Bierwirth（2013年）在三个阶段整合了BAP、CAP和CSP。AK（2008）在海边作业的最佳规划工作中，开发了一个混合整数线性规划（milp）模型，该模型包含BAP、CAP和CSP。他的BACASP模型同时计算最佳停泊时间、泊位分配和船舶的起重机数量分配，以及计算的起重机分配的起重机计划。在该公式中，泊位分配限制是基于船舶在时间和空间上的相对位置，起重机调度允许起重机在无交叉的情况下移动，目标是将船舶的总停留时间和晚点船舶造成的损失减至最小。值得注意的是，AK（2008）的目标是加快船舶吞吐量。虽然这一目标试图对所有的船舶一视同仁，但由于起重机空闲而产生的成本并没有考虑在内。Yang（2008）还提出了一个集成BAP、CAP和CSP的MILP公式。在该公式中，起重机的切换大大减少，泊位分配限制是基于将时空网格的矩形（即位置分配）分配给船舶，并将总的装卸时间最小化为目标。但是，起重机重新布置的负面影响没有被考虑到，因为起重机的移动成本被忽略了。此外，两种模型只能在小的情况下精确求解，因此作者提出了求解公式的启发式方法。
关于分配给船舶的起重机的数量和移动，文献中有不同的假设。一些作者认为，起重机的数量可能在起重机的最小和最大数量之间发生动态变化（见Meiselamp;amp;Bierwirth，2009年；Parkamp;amp;Kim，2003年）。张（2010）批评此类模型，指出分配给船舶的码头起重机数量在实践中不能经常改变，因为移动码头起重机需要显著的设置运行和调整时间。他们假设分配给每艘船只的码头起重机数量只能在船只离开前更改一次。这种减少码头起重机重新配置导致的大型安装损失的动机导致T护Trkogullar、Taskn、Aras和Altnel（2014）制定了一个时间不变的模型，在该模型中，码头起重机的相同子集在停泊期间为船舶服务。在这里，每个小矩形代表一艘船舶，其高度等于其长度（按泊位段数测量），宽度等于其停泊时间（按AK（2008年）和Bierwirth和Meisel（2010年）绘制的时期数测量）。TrkoGullar等人（2014）首先提供一个新的位置分配公式，用于时间不变的BACAP，将总成本降至最低，包括从所需泊位靠泊成本、靠泊成本、离港成本和因活动起重机数量变化而产生的成本之和。然后，他们提出了一种高效的切割平面算法，该算法从其BACAP公式的最佳解中获益，从而精确地解决大型BACAP实例。虽然这是一个非常有效的方法，可以解决现实的实例，起重机分配是时间不变的（Bierwirthamp;amp;Meisel，2010年）。这意味着在停泊期间，分配给船只的起重机组及其编号保持不变。在Trkogular、Taskn、Aras和Altnel（2012）中，作者放宽了时间不变性假设，并开发了一个考虑同一问题的时变版本的milp模型，并将因指定起重机数量变化而产生的成本纳入其中。它也是一种位置分配公式，可将总成本降至最低，但包括主动起重机数量可能发生动态变化的灵活性。然而，这种方法仍然受到限制，因为安装成本不被认为是尽可能实际的，并且假设总安装成本与安装数量成比例。换句话说，目标函数中的总设置成本项主要基于活动起重机数量变化的频率，而不关注起重机的行驶时间和行驶距离等问题。然而，这种方法仍然受到限制，因为安装成本不被认为是尽可能实际的，并且假设总安装成本与安装数量成比例。换句话说，目标函数中的总设置成本项主要基于活动起重机数量变化的频率，而不关注起重机的行驶时间和行驶距离等问题。在这项工作中，我们遵循这一研究路线，并引入了一种将BAP、CAP和CSP（BACASP）作为我们的第一项主要贡献进行深入整合的方法。我们的公式允许包含与起重机重新定位相关的实际成本，包括可变成本和固定成本。我们注意到，作为BACASP的一部分，这里所考虑的CSP类似于公共汽车/火车调度，起重机响应公共汽车/火车和停泊船只等待起重机替换公共汽车站/火车站。由于资源的分布，即起重机，随着时间的推移，这也是一个调度问题。然而，它比起重机操作调度简单，因此被Bierwirth和Meisel（2010）命名为CAP（SPecifific）。Bierwirth和Meisel（2010年、2015年）以及Carlo等人确定了起重机运行计划。（2015）作为起重机的总体任务计划。因此，BACASP可以被视为BAP、CAP和CSP的深度整合（即这三个问题以数学优化分解模型的形式在统一的框架内解决），其中CSP确定了起重机到船舶的分配以及停泊时间和位置时的具体时间段。给出了船舶的ONS和分配给船舶的起重机数量。我们还指出，顾客服务提供商的定义以前曾在法律中使用过（AK，2008；Imai、Chen、Nishimura和Papadimitriou，2008；Parkamp;amp;Kim，2003；Yang，2008）。
然而，我们在以下章节中提出的公式能够处理由于起重机重新定位而产生的各种设置成本，如行驶时间和距离，以及可能因起重机规格、船舶规格和位置规格原因而产生的固定成本。我们的第二项主要贡献是一种新的精确求解算法。这是一种有效的切割平面算法，它基于一个装饰位置方案，根据船舶的停泊位置和分配给它们的起重机数量，将起重机方案的确定隔离开来。我们证明了CSP子问题在一般情况下是难以计算的，并讨论了一些很容易解决的特殊情况。我们还开发了一种新的分支定界算法，该算法使用最小成本-流量松弛，并将其性能与动态规划公式的状态网络上的最短路径实现进行比较，其根源在Park和Kim（2003）的早期工作中。
论文的其余部分组织如下。下一节将介绍新模型的制定。在第3节和第4节中，我们分别解释了精确求解BACASP的新分解算法和对最优值给出快速上界的算法。在第5节中，我们主要关注顾客服务提供商，并提出其有效解决方案。在第6节中，我们介绍了增强功能，以提高新方法的效率。第7节报告了证明所提出方法效率的计算结果。最后，总结性发言和未来的研究方向列在第8节中。
- 综合模型的建立
我们提出的综合BACASP配方主要基于以下八个假设：
1.规划范围被划分为等长的时间段。
2.泊位是连续的，由等尺寸的单位泊位段离散。它们和单个起重机一样大，可以在每个起重机上自由运行。
3.每个泊位段在每个时间段内由不超过一艘船占用。
4.已知船舶的
全文共27381字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[426]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
