集卡调度与存储分配问题的启发式算法外文翻译资料

 2022-04-08 22:18:50

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

集卡调度与存储分配问题的启发式算法

摘要

集卡调度和仓储配送是影响集装箱码头作业效率的两个重要决策问题。本文提出了一种新方法，将这两个问题整合为一个整体，以尽量减少 请求总延迟和集卡总行程时间的加权总和。由于所提出的问题难以处理，本文设计了混合插入算法用以有效解决这些问题。通过计算实验, 本文研究了所提出的启发式算法的关键因素和性能问题。

关键词：集装箱码头操作；集卡调度；存储分配；启发式算法

第1章 简介

集装箱码头是为水陆联运的枢纽站, 也是多式联运的集散站和中转站。航运业在现代物流中占有75% 以上的市场份额。堆放和运输大量集装箱到岸边的效率对任何集装箱码头都至关重要。

通常情况下，集装箱码头有三种类型的集装箱搬运系统：底盘系统，跨运车系统和动式集装箱吊运车系统。由于在堆场内需要较高的集装箱存储容量，所以动式集装箱吊运车系统在主要码头最受欢迎。对于动式集装箱吊运车系统，有三种类型的装卸设备，即码头起重机，堆场起重机和集卡。码头起重机通常是最昂贵的搬运设备，也可能成为集装箱码头装卸作业的瓶颈。

集装箱在从集装箱货轮卸下后，将被分配到堆场暂时存放。在堆场内，堆场起重机用于在堆场各区域间挑选并堆放集装箱。 集卡在码头和堆场之间搬运集装箱，以满足码头起重机和堆场起重机的时间表。

由于建模和计算的局限性，不太可能分析制定并有效解决完整的集装箱码头运营。识别和解决一系列优化问题是提高集装箱码头作业效率的一种实用方法。一般来说，这些优化问题包括泊位分配问题，码头起重机调度问题，集卡调度问题，堆场起重机调度问题和存储分配问题。

本文着重介绍了集卡调度和存储分配问题。在简介和第2部分的文献综述之后，它描述了集卡车调度和存储分配问题。在第3节中提出了一个混合整数规划（MIP）模型用于解决所提出的问题。在第4节中，为找到有效的问题解决方案，本文开发了启发式求解算法。 第5节介绍了一系列计算实验，以测试问题的一些关键因素和解决方案算法的性能。 最后，第6节总结本文。

第2章 文献综述

在卡车调度问题领域，Kim和Bae提出了一种扩展方法，将自动导引车（AGV）应用于基于网络的MIP模型，用以最小化码头起重机由于AGV未按时到达以及相关的总行程时间而造成的总闲置时间。这种方法假定码头起重机的（卸）装载作业的集装箱的存放位置和时间表已经被给出。

Nishimura等提出了一种集卡分配方法，用于解决集装箱码头的集卡路径问题，在这些集装箱码头内及集卡通常被分配给特定码头起重机直至工作完成。他提出了MIP模型，并开发了遗传算法（GA）来解决这个问题，展示了一个新的动态路径选择方案。 这个方案旨在节省码头操作时间以及集装箱处理成本。

NG等讨论了在集装箱码头如何调度一队集卡以最小化完工时间的问题。集卡必须执行一系列运输作业，其顺序取决于处理时间和不同的准备时间。 他们用GA算法解决了这个问题。

对于存储分配问题，Kim和Kim（1999）考虑了如何为卸载集装箱分配存储空间的问题。 他提出了一种隔离战略，即不允许将新抵达的集装箱堆放在先前抵达的集装箱顶部，并为每艘到达的船只分配空间，以尽量减少预估的重新处理总数。

Kim和Kim（2002）讨论了一种确定最佳存储空间和处理卸载集装箱的传送起重机的最佳数量的方法，提出了一种成本模型，并用启发式算法求解。

Zhang等人（2003）使用滚动时间法模拟了存储分配问题。 对于每个规划层面，问题被分解为两个层次，每个层次都被制定为一个数学规划模型。

码头调度和存储分配问题吸引了大量的研究工作。然而, 这些问题彼此之间有着高度的联系。比什 (2001)的研究是将这两个问题结合起来的第一项研究。Bish等人（2001）假设每个集装箱在堆场里都有许多可能存放的地点。集装箱用一对集卡从船上搬运到堆场内，每个卡车每次可以装载一个集装箱。通过将问题分解为两个独立的步骤来开发启发式算法，其中步骤一在忽略集卡工作时间表的前提下，来确定位置分配，步骤二为步骤一获得位置分配确定车辆时间表。Bish（2003）扩展了这项研究，以检测每个卸货集装箱的存放位置，给集装箱调度车辆，并安排码头起重机的卸货和装货作业的问题，以最大限度地减少服务给定船舶所需的最大时间。该问题表现为NP-hard问题，Bish提出了启发式算法来解决问题。 Bish等人（2005）针对Bish（2003）研究的问题开发了容易实现的启发式算法，并推导出这些启发式算法在绝对和渐近最差情况下的性能比。尽管三项研究综合考虑了卡车调度和存储分配问题，但这两个问题仍然是分开解决的，两者之间没有交互作用。相比之下，本文提出了集成式货场卡车调度和存储分配问题，其目标函数是根据软时间窗口最小化码头卡车总行程费用和总延迟罚分的加权平均值。本文提出的解决方案能够捕获这两个问题之间的相互作用。

Han等（2008）提出了另一种整合集卡调度和存储分配的方式和一种在转运码头分配集装箱存储空间的方法，旨在平衡每个码头区块的工作量，以尽量减少码头卡车造成的交通拥堵。 他用启发式算法建立了数学模型。 这个方法提供了整合集卡调度和存储分配的另一种方式。

Lee等 （2008）提出了集卡调度和进口集装箱存储分配的综合模型。 他将这两个问题作为一个整体考虑来制定MIP模型，目标是尽量减少完成操作的时间。 由于问题的NP难度，他们开发了一个GA算法和一个专用的启发式算法来解决问题。

第3章 问题的制定

在本文中，集装箱从其起点到终点的移动被定义为请求，由i和j表示。 装载集装箱的起点是其存放的堆场地点，其目的地是将集装箱装载到船只上的码头起重机的位置。 对于卸载集装箱，其起点是它被起重机从船上卸下的位置，其目的地是分配给集装箱进行临时存放的堆场位置。 设J 是计划内的加载请求的集合，J-是计划内的卸载请求的集合， n 和n- 分别是它们的基数。 我们还定义了J=J J-和= n。

根据船舶的吨位，到达时间和停泊时间，在船舶抵达前，码头将为每艘集装箱船舶分配一个泊位并在对接后为其将安排一定数量的码头起重机。 码头起重机时间表根据船舶装卸计划确定。 由于码头起重机作业是集装箱码头作业的主要瓶颈之一，其他作业如堆场起重机作业时间表应与码头起重机作业时间同步。

每个请求都有一个软时间窗口用于服务，比如[ai; bi），这个时间窗是由码头/堆场起重机时间表确定的。请求只能在最早的可能时间ai之后提供，ai由请求i起点处的起重机时间表决定。请求i的到达时间,bi,可能会受到惩罚。请求i的处理时间用由ti表示，它在这个问题中可能遇到两种条件。 对于加载请求，服务时间是预先确定的，并作为参数给出，而对于卸载请求，服务时间由存储分配计划确定，这意味着它是一个决策变量。 假设请求i中的服务从wi开始，这是一个决策变量。 该服务将这样完成：=

请求i的延迟是:=max{0,-}

如果同一集卡在完成请求i之后立即响应请求j，则服务请求j的起始时间为：wj =max{wi ti sij,aj},

其中sij（也是决策变量）是集卡从请求i的目的地到请求j的起点的空程时间（建立时间）。

在本文中，我们假设码头卡车的数量是有限的，每个卡车只有一条路线。令R为路线集合,基数为[R]=m，路线由r索引。

实质上，每个车辆路线是一对一的请求分配，如图1所示。我们为每个 路径添加两个虚拟请求， 命名为lr和kr，以表示每个集卡的初始和最终状态。我们进一步将请求集扩展，分别用o i和d i表示请求i的起点和目的地。该组位置由L表示。设p和 q为位置的索引，即。每一对的位置之间的行程表示为tau;pq 。设zeta;k 是存储位置（SL）k的位置索引，其中kK，且K是所有SL的集合。

图1.一对一分路线配的图示

在确定处理时间和空程时间时，有四种可能的状态：

状态1：如图2a所示，集卡在完成一个装载请求后响应另一个装载请求。

状态2：如图2b所示，集卡在完成一个装载请求后响应一个卸载请求。

状态3：如图2c所示，集卡在完成一个卸载请求后响应另一个卸载请求

状态 4：如图2d所示，集卡在完成一个卸载请求后响应一个装载请求。

图2.处理时间和设置时间的计算

处理时间是从请求的起点到目的地的行驶时间，空程时间是集卡从一个请求的目的地到下一个请求的起点的行驶时间。 因此，对于条件1和2，由于请求的目的地和后续请求的来源是确定的，所以处理时间和空程时间都是固定的; 而在条件3和4中，处理时间和空程时间取决于由存储分配确定的请求i的目的地的位置。 请求i的处理时间可以用公式 （4）计算，并且从请求i的目的地到请求j的起点的空程时间可以通过等式（5）计算。

如果请求i是一个装载请 （4）

如果请求i是一个卸载请求并分配给SLk

（5）

如果请求i是一个装载请求

如果请求i是一个卸载请求并分配给SLk

以下是模型制定中需要的其他符号：

u [P1]的目标值

a1 请求总延迟的比重

a2 码头卡车总行程时间的比重

xik 如果集装箱i分配给SL k，则为1；否则为0

yik 如果请求i和请求j在同一路线上，则为1；否则为0

该问题可以表述为以下用于集卡调度和存储分配问题的MIP模型（YTS-SAP）。

这个程序的目标是最小化总延迟惩罚（由函数f1表示）和总行程时间的代价（由函数f2表示）的加权总和，如等式（6）。限制条件（7）保证每个卸货集装箱将被分配一个SL。约束条件（8）意味着每个SL可以存储一个并且只有一个卸载集装箱。约束条件（9）和（10）为每条路线形成一对一的分配。限制条件（11）保证服务只能在最早的可能时间之后才能提供服务。约束（12）计算每个请求的延迟。约束（13）表示相同路由中两个相邻请求的开始时间的关系。约束（14）和（15）等价于方程（4）。约束（16）和（17）等价于方程（5）。公式（18） - （21）是决策变量的定义约束。模型[P1]可以归结为具有时间窗的车辆路径问题（VRPTW），这已被广泛认为是一个NP难题。因此，不可能获得VRPTW的确切解决方案（Toth和Vigo，2002）。在下一节中，本文将开发启发式算法以获得YTS-SAP的近似最优解。

第4章 解决算法

在开发[P1]的启发式算法之前，我们需要引入一个存储分配模型。 该模型制定如下：

其中z是[P2]的目标值，而参数ƛik是分配集装箱到SL k的成本，其中，其中是当前部分路线中的一组卸载请求。 在启发式算法过程中，部分路径仅包含一部分请求。在[P2]中，由于集装箱装载的成本是由起点和目的地预先确定的，因此仅考虑卸载集装箱，这意味着它们不会受存储分配问题的影响。 一旦部分路线确定后，可以通过方程（26）计算成本kik并将其视为[P2]的参数。

模型[P2]与分配问题类似; 因此，它是用拍卖算法解决的。 拍卖算法的细节可以在Bertsimas和Tsitsiklis（1997）的文章中找到。 拍卖算法的计算复杂度为O（n2）。

现在我们可以开发结构化的启发式算法。 结构化启发式算法已被广泛用于求解带时间窗和VRPTW的旅行商问题，参见Gendreau et al（1998年）和坎贝尔和Savelsbergh（2004年）。 结构化启发式可以包含各种不同的成本结构，并有效解决问题。
我们首先为部分路线中的卸货请求定义潜在最优存储（POS）。 部分路线的POS是由模型[P2]确定的每个卸货集装箱的存储位置。 它被称为“潜在”的原因是，这种最优方案适用于当前部分路线，而不适用于完整路线。 这仅仅用于选择最佳的插入点而不是确定卸载集装箱的最终存储位置。 混合插入算法（HIA）可以表述如下：

在这个算法中，一个由（j,r,i）表示的插入，表示“将请求j在第i个插入点插入路线r”。 路线r由一组有序的作业表示。 对于每个插入，我们根据成本结构评估成本。 在每次迭代中，我们选择一个最佳的插入并更新路线。

成本u(j,r,i)由两个部分组成。 第一项是

全文共7840字，剩余内容已隐藏，支付完成后下载完整资料

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

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

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

您可能感兴趣的文章