通过模拟退火进行泊位调度
Kap Hwan Kim *, Kyung Chan Moon 1
韩国釜山市Kumjeong-ku，Changanon-dong，釜山国立大学工业工程系，韩国釜山609-735
2001年3月21日收到;以2002年3月18日修订的形式收到;2002年3月28日接受
摘要
泊位调度问题的目的是确定港口集装箱码头中的集装箱船的停泊时间和位置。每个容器在码头中需要特定量的空间预定的时间长度以卸载和装载容器。在这项研究中，为泊位调度问题制定了混合整数线性规划（MIP）模型。将模拟退火算法应用于泊位调度问题，寻找近似最优解。实验结果表明，模拟退火算法获得的解决方案与MIP模型找到的最优解相似。
copy; 2003 Elsevier Science Ltd.保留所有权利。
关键词：泊位调度;集装箱码头;混合整数编程;模拟退火
- 介绍
许多集装箱码头的管理人员试图通过有效利用资源来降低成本，包括人力资源，泊位，集装箱堆场，集装箱起重机和各种堆场设备。在所有资源中，泊位是最重要的资源，泊位的良好时间表提高了客户满意度，提高了港口吞吐量，从而带来了更高的港口收入。港口管理人员通常通过计划系统中的计划板或图形用户界面支持的直观的反复试验方法来安排泊位的使用。本文试图通过使用分析方法最大限度地利用码头并满足停泊集装箱船的各种限制。
*通讯作者。电话： 82-51-510-2419;传真： 82-51-512-7603。
电子邮件地址：kapkim@pusan.ac.kr (KH Kim),kcmoon@pusan.ac.kr （KC Moon）。
1电话： 82-51-510-1483;传真： 82-51-512-7603。
0191-2615 / 03 / $ - 见前面的内容copy; 2003 Elsevier Science Ltd.保留所有权利。doi:10.1016/S0191-2615(02)00027-9
在安排泊位使用时，必须确定每艘船的停泊时间和位置。在该过程中，必须考虑几个因素，包括每个容器的长度，每个容器的到达时间，用于卸载和装载的容器的数量，以及要装载到相应容器上的出站容器的存储位置。
图1示出了港口集装箱码头中的泊位时间表的示例。横轴表示码头上的位置，而垂直轴表示时间轴。每个矩形表示相应船只的时间表。船舶的矩形的水平位置对应于船舶的靠泊位置，而矩形的垂直位置表示相应船舶的船舶操作时间。
泊位安排的目的是最大限度地减少由于船舶离港延误而导致的罚款成本以及由于码头中船舶的非最佳位置而导致的额外处理成本。承运人通常会告知码头运营商预计的到达时间和船舶的要求出发时间。根据该信息，终端运营商试图满足所有船舶的要求出发时间。但是，当船舶的到达率很高或出现意外到达时，可能无法按要求的出发时间完成所有船舶的服务。因此，一些船只的离港可能会延迟。此外，码头运营商通常对不同类型的船舶具有不同的优先级。可以通过将优先级转换为目标函数中船只的惩罚成本的成本系数来考虑优先级。
由于以下原因，靠泊位置也是一个重要的决策变量。在船舶到达港口前几天，船只的集装箱通常开始到达码头。因此，如果船舶停靠在要装载到船上的集装箱的存储位置附近的位置，则由货车或跨运车运输的集装箱的运输成本可以
最小化。在这种情况下，船舶的最低成本靠泊位置是码头上的位置，船舶中心与已经到达船厂并将装载到船上的出境集装箱的平均坐标重合。此外，由于长期合同规定了与承运人泊位的使用，船舶所需的最低吃水深度，根据码头位置的不同波浪等因素，一些停泊位置可能优于其他位置。
关于提高港口集装箱码头的船舶运营效率已经进行了大量研究。这些研究包括Cho（1982），Cojeen和Dyke（1976），Gifford（1981），Kim和Kim（1999）的负载排序问题，以及Daganzo（1989）和Perterkofsky和Daganzo的起重机调度问题。 （1990）。布朗等人。（1994），Imai等。（2001），Lai和Shih（1992），Li等。（1998）和Lim（1998）处理了泊位调度问题，这是本文的主题。
通过模拟实验，Lai和Shih（1992）比较了集装箱船的三个泊位分配规则。他们假设一个可以表示为连续线的码头可以划分成几个部分，每个部分只能在特定时间分配一个船只。泊位分配规则考虑了以下因素：码头的可用部分，每个可用部分的船舶的预期完工时间，以及每艘船的大小和到达时间。
通过考虑各种实际约束，布朗等人。（1994）制定了整数规划模型，用于将码头的可用部分分配给船只。他们假设一个码头是一系列离散的靠泊部分。Lim（1998）首先将码头视为连续空间而不是分区部分的集合，并且泊位调度问题被公式化为二维打包问题。但是，他认为所有船只的停泊时间都是固定的。他提出了一种启发式方法，用于最小化船舶所占码头的总长度。
李等人。（1998）将泊位调度问题制定为具有单个处理器的调度问题，通过该处理器可以同时处理多个作业。该问题假设所有船只已经到达，并且基于该假设尝试最小化制造。他们提出了一个先适合减少的启发式规则，进行了数值实验。他们还讨论了允许重新安置船只的情况。但是，他们没有提出获得最佳解决方案的方法。
Imai等人。（2001）也假设一个码头是一个离散的靠泊部分的集合。他们试图最大限度地减少船只的等待时间，并提供了一种混合整数规划模型，用于为船只分配靠泊段。他们还提供了一个基于拉格朗日松弛原始问题的启发式程序。
本文所述的研究在以下三个方面是独一无二的：首先，与Lim的研究（1998）不同，本研究试图同时确定停泊时间和靠泊位置。第二，与布朗等人的研究不同。（1994），Imai等。（2001），Lai和Shih（1992），码头被认为是一个连续的空间，而不是一个分区的集合。第三，与Lai和Shih（1992）和Li等人的研究不同。（1998）提出了启发式规则，本研究提出了一种优化方法。
在设施布局方面，可以在Heragu和Kusiak（1991）以及Tompkins等人中找到与我们类似的有用配方。（1996）。布局的公式试图在一个大矩形中定位代表部门的小矩形，代表一个建造。设施布局问题的目的是最小化材料流量的总和乘以相应矩形之间的距离。二维切割库存
问题也类似于泊位调度问题。然而，切割库存问题的目的是最大限度地减少废料数量，因此在平面上切口的位置 - 这对泊位调度问题很重要 - 与目标无关功能。
最小化总体早期和迟到惩罚的单机调度问题（Fry等，1987）是泊位调度问题的一个特例。
由于前一个问题仅确定作业的起始时间，因此它是泊位调度问题的一维版本，其中必须确定停泊位置以及靠泊时间。下一节将介绍泊位调度问题的数学公式。部分图3介绍了最优解的几个属性。第4节提出了一种启发式算法和一种用于泊位调度问题的模拟退火算法。最后，第5节提出了结论性意见。
- 问题的表述
本节介绍了泊位调度问题的数学公式。配方使用以下符号：
N 船舶总数。
L 码头的长度。
pi 船舶i的成本最低的靠泊位置。该位置由容器最左端的x坐标表示，并且通过考虑先前到达的容器的分布或特定容器的指定位置来确定位置。x坐标的参考点是码头的最左边界。
xi 船舶i的靠泊位置（决策变量）。
yi 船舶i的停泊时间（决策变量）。
ai 船舶i的预计到达时间。
di 船舶i要求的出发时间。
bi 船舶运营所需的时间i。该值包括船舶离港和另一艘船舶停泊之间的时间限制。
c1i 用于输送容器i的容器的每单位距离的额外行程成本，由相对于最低成本点的非最佳靠泊位置导致。
c2i 船舶i每单位时间的罚款成本，由于出发延迟超过要求的到期时间。当一艘船的离开时间推迟到她的时间表后，她必须加快她的航行，赶上下一个港口的时间表，这将导致额外的燃料消耗。罚款成本c2i 可以从预期的额外燃料消耗估算。
li 船只的长度i。该值包括相邻船舶之间所要求的间隙。
{
{
1：如果船舶i在船舶j之前及时停泊;
0：否则：
图2显示了码头时间空间和几种符号。然后，目标函数了
泊位调度问题可写成如下：
其中 (1)
目标函数的第一项表示非最佳靠泊位置产生的成本，第二项是由船舶离港延迟产生的罚款成本。当时，取。当，取；，取，否则取。然后，泊位调度问题可以如下形成：
(2)
受制于
,对于所有的i (3)
，对于所有的i (4)
，对于所有的i (5)
，对于所有的i和j，ine;j,和一个很大的正数M （6）
，对于所有的i和j，ine;j,和一个很大的正数M （7）
，对于所有的i和j，ine;j (8)
,对于所有的i (9)
,对于所有的i (10)
,对于所有的i和j，ine;j (11)
约束条件（3）和（4）与i的定义有关;一个约束（5）意味着船舶i的最右端的位置受到码头长度的限制。约束（6）或（7）仅在等于1时有效。约束（8）排除了两个案例船只在停泊时间和靠泊位置方面相互冲突。也就是说，约束（8）排除了情况在这种情况下矩形代表反对船只i和j重叠的时间表。约束（9）意味着船只在到达港口之前不能停泊。本研究中描述的模型的简化版本，其中所有船舶的停泊时间是固定的，已知是NP-hard（Lim，1998）。由于使用商业软件（LINDOreg;）超过七个容器解决公式（2） - （11）的计算时间超过了合理的限制，实际问题中的容器数量约为20，模拟退火算法在第3节和第4节中提出。
- 最优解的性质
在本文中，解决方案由一系列船只编码，以将模拟退火算法应用于泊位调度问题。为了将一系列血管解码成溶液，必须能够从给定的血管序列获得时间 - 码头平面中血管矩形的近似最佳位置。本节讨论最佳解决方案的几个有用属性。
以下介绍解释稳定性概念所必需的几个定义。
定义1. x-cluster定义为一组矩形（容器），其垂直边彼此接触。此外，y簇被定义为一组矩形（容器），其水平边彼此接触。
定义2.如果通过向正或负方向移动集群无法减少集群中船只的总成本，则称一组船只是“稳定的”。
性质1.制剂（2） - （11）的最佳溶液中的团簇是稳定的。
证明。该属性由群集稳定性的定义决定。
属性2.当x-cluster稳定时，以下两个条件之一成立：（1）x-cluster中的一个或多个矩形位于x轴上的最低成本点;（2）簇中至少一个矩形的一侧位于码头的右边界或左边界。
证明。让集群中最左边的矩形称为集群的“参考矩形”。设x是簇的参考矩形左侧的水平坐标。
另外，令ri 是从关联簇的参考矩形的左侧起的矩形i的左侧的相对水平坐标。然后，第i个矩形的成本可以表示为。因此，总成本可以由 表示，其中ck 是第k个x-簇中的一组矩形。这个问题等同于直线距离测量下单个设施的minisum问题。在总成本的表达式中，可以被认为是第i个现有设施的位置。也就是说，通过应用中值条件的性质可以找到x*（Francis等，1992）。在这种情况下，一个或多个矩形必须位于其成本最低的位置，以使群集稳定。然而，当群集中的矩形与码头的两个边界中的任何一个接触时，没有矩形可以位于其最低成本位置。因此，结论成立。
性质3.当y-簇稳定时，以下两个条件中的任何一个都成立：（1）y-簇中所有容器的停泊时间位于[ai,di-bi];（2）集群中一艘或多艘船舶的停泊时间为其到达时间（ai）或零。
证明。与物业2的证明相似。
当为给定的血管序列提供血管矩形布局时，我们可以通过检查群集的稳定性和稳定不稳定群集来改善布局，这可以通过仅将群集移动到将降低成本的方向来完成。根据属性2和3，在该过程中，仅考虑x轴或y轴上的几个离散点作为簇的候选位置就足够了。此改进过程将用于解码下一节中的解决方案。
- 应用模拟退火方法
为了描述模拟退火算法，必须首先定义解的编码和解码方法。
-
- 解码的编码和解码
解决方案由一系列容器编码。为了将一系列容器解码成溶液，将容器的矩形逐个添加到时间码头平面中。对于时间码头平面中给定的矩形布局，右/上角，如果存在另一个角，则称矩形的占主导地位，使得和 和两个不等式中的任何一个严格成立。通过使用一组非支配的右/上角，可以构造向下的楼梯，如图3（ii）中的粗线所示。在以下描
全文共12763字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[1116]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
