文摘

本文研究的问题积载计划在多个港口的船湾交通路线,旨在最小化总容器转移费用。由于访问容器是自上而下的顺序为每个堆栈,重组操作发生在当一个目标目的地卸货港集装箱不是安放在堆栈的顶部。每个容器转移通过码头起重机产生一个单位的转移费用取决于当地的集装箱港口的收费政策。先前的研究假设每个容器转移一个统一的成本消耗所有端口,从而专注于减少的总数变化或船的周转时间。出于非均匀的观察到不同的港口费用每个容器的转变,我们提出一个混合整数规划问题(MIP)模型来产生一个最优的积载计划与最低总费用转移工作。此外,由于考虑的问题是np难的np困难的对应统一的单位转移费用,我们提出一种改进的遗传算法来解决这个问题。该算法的效率是通过数值实验证明的。

1。介绍

在世界海运贸易,大部分商品是由集装箱船运输。集装箱船海上运输占据了绝大多数的海上运输行业,其中集装箱贸易已经成为增长最快的货运段(见[1])。

一个高效的积载计划是最重要的因素之一,在拯救航运公司的运输成本。一个容器可能访问几个集装箱港口航行期间,和容器被加载到容器从上游港口和后卸船的下游端口。如果目标容器被卸载的船不是安放在堆栈的顶部,它产生重组操作作为访问容器遵循自上而下的顺序栈。所有相关集装箱堆积在目标一必须暂时删除,之后重新加载后回堆栈目标容器已卸载。涉及的卸载/重载操作不属预定目标的容器造成额外的费用和时间消耗转移。一个有效解决船舶积载可能大大减少这种转移费用在运输路线。

大多数以前的研究的目标是最小化的总数变化不属预定目标的容器在每个集装箱港口,因此减少船的周转时间。通过现场调查,然而,我们观察到转移费用也是一个重要的考虑因素,和一个关键点是,单位转移在不同的集装箱港口费用变化很大。例如,单位转移费用一个容器将在宁波舟山港是49.5元,虽然在广州港100元。观察激励我们探讨积载计划问题的总转移费用以外的总数变化在多个港口船最小化运输路线。作为容器的容器在每个湾分别处理每个端口,我们考虑在船舶积载计划内湾。我们声称以来积载计划正在考虑的问题是np难的对应统一的单位转移费用,也就是说,问题最小化的数量变化,(已经赋权2]。我们还没有找到任何相关工作总费用最小化的情况下转移与非均匀单元转移费用。针对这个问题,我们建立一个MIP模型和设计一个高效的算法产生良好的积载计划解决方案。

接下来的工作是组织如下。部分2简要文献综述相关的作品,部分3描述了正式考虑问题。节4,我们现在的MIP的数学公式,在部分5我们提出这个问题的遗传算法。数值结果给出了部分6,最后我们总结论文部分7。

2。文献综述

近几十年来,集装箱船积载计划的问题进行了广泛的调查(3- - - - - -6]。

2.1。积载计划在单独的端口

Delgado et al。7]研究装载规划问题,提出一种方法,生成一个接近最优规划大型集装箱船在几分钟内。在两个步骤的方法解决了问题。在第一步分解船进入主隔间和分配容器到主隔间。在第二步中,在每个主容器湾湾的进一步分配给特定的插槽。

摩纳哥et al。8)参与的问题确定最优位置的容器存放容器。他们认为这艘船停泊在码头由一个槽数和提出一个二进制整数程序和一个两步启发式算法获得积载计划问题的有效解决方案。

Ambrosino et al。9]研究主湾计划问题(MBPP)和禁忌搜索算法提出一个metaheuristic方法寻找全球船舶稳定的总体积载计划。提出了禁忌搜索算法可以提高规划管理可视化的积载计划在软件支持系统。也表现良好在一些现实生活中的测试用例相关的终端位于热那亚港口,意大利。

刘等人。10internal-reshuffling]调查码头起重机双周期问题操作,提出一个多项式时间的启发式算法来减少集装箱船的海湾。通过比较他们与先进的启发式算法,证明他们的模型可以更有效地解决比提出Meisel和Wichmann11]。

2.2。积载计划在多个端口

Avriel et al。2)办理集装箱船积载计划减少的数量变化,首先提出一个二进制线性规划公式为积载计划找到最优的解决方案。由于许多二进制变量和约束,他们开发所谓的悬启发式程序。

Araujo et al。12)考虑一个三维的集装箱船积载计划问题。他们建立一个数学模型的目标最小化容器的数量和船不稳定。提出了一种混合方法解决模型和帕累托前获得一个好的近似。计算结果表明,该方法比monoobjective模拟退火算法提供了更好的解决方案。

丁和周13)考虑充填规划问题,船顺序访问一系列的港口。他们开发一个启发式算法生成与合理数量的集装箱积载计划变化,表明该算法执行比悬启发式程序提出了Avriel et al。2]。

Ambrosino et al。4]扩展MBPP多端口主湾计划问题(MP-MBPP),并提出一种启发式算法基于一个精确的MIP模型以最小化总船的靠泊时间。提出有效的启发式算法可以找到好的解决方案整个旅行计划。

上述文献分析广泛和多端口集装箱装卸场景。更多结果充填规划问题,请参阅王(14和拉莫斯等。15]。所有这些作品关注最低重组或周转时间的路线;那就是,他们都认为每个容器转变是相同的成本在所有的港口。一些作者也为各自的问题[建立线性规划模型2,12]。然而,正如我们前面所提到的,不同的端口通常是不均匀的运营成本和单位在实践中一个容器的转移费。因此我们建立一个混合整数规划模型与非均匀单元转移费用与负载平衡需求在这工作。我们所知,还没有相关的研究文献,考虑nonuniform-shifting费的情况,旨在最小化总成本转移容器的路线。

3所示。问题描述

我们考虑积载计划问题在多个港口和集装箱船关注容器转移操作在一个港湾的船。湾包含一个数字集装箱列或堆栈可能有最多的地方在每个垂直堆栈容器存放。每个容器占据一层的堆栈或同样的位置。我们假设所有的容器都是集装箱(二十英尺等量单位)。图1是一个二维坐标图,有一个侧面和鸟瞰容器的容器。更详细的描述容器港湾的船被Ambrosino et al。3]。每个容器的插槽位置在海湾用列和索引层的结合,也就是说,插槽 在哪里 , 。

这艘船离开港口 和顺序访问端口 。最初,没有集装箱装载在第一个出发前湾港。注意,没有集装箱转变 港口因为只有装载容器。同样,在最终的港口 ,所有剩下的集装箱船是卸船,和存在没有容器转移。

在海湾,有完全目标容器加载,然后卸载的港口。每个容器与重量装载港然后卸货港口 。任何堆栈中存放的容器的一种方式,这样重的容器在低层和轻容器在更高的层次。考虑任何目标容器港这样一个不属预定目标的容器上面是收藏在相同的堆栈。作为 、集装箱被称为屏蔽容器,它必须重组一次卸载目标容器 。的重组导致一个单位转移费用在港口。自从单位转移费用变化在不同的港口,积载计划正在考虑的问题是产生一个可行的重组计划,这样的总转移费用港口是最小化。这意味着这些端口的数量变化与最高单位转移费用应当最小化。此外,由于负载平衡要求整个容器,它需要负载平衡在不同列的海湾,相应地,我们假设有一个上限的重量每个堆栈。

4所示。数学公式

在本节中,我们首先给出基本的符号,然后现在MIP模型的目标函数和约束。

4.1。符号

指数 :该指数的港口 , :指数的容器 :容器列的索引或栈在海湾 :指标层, ,分别为最高和最低层

输入参数 :港口的数量 :容器的总数在加载/卸载港口 :列或堆栈的数量在海湾 :层的数量在每个堆栈 :集装箱的重量 :出发的港口装载容器 :目的港的卸货集装箱 :目标的设置集装箱港 ,也就是说, :不属预定目标的集装箱港的集合 ,也就是说, :单位转移费用在港口 :集装箱的最大允许重量在每个栈存放 :一个足够大的正整数

决策变量 := 1,如果容器位于槽 当船到达港口 ,0,否则 := 1,如果容器位于槽 当船离开港口 ,0,否则 := 1,如果容器重组一次槽吗 港 ,0,否则

4.2。MIP配方

4.2.1。准备目标函数

屏蔽容器在海湾的每个转变生产一个单位的转移费用港 ,和目标是最小化总费用的转变港口:

4.2.2。模型约束

容器不能在任何位置存放 前海湾要么离开港口或目的港后 :

集装箱的总重量在每个堆栈不能超过上限在任何港口 :

毕业后在任何港口装卸操作 ,不超过在每个堆栈或列容器收藏:

在任何堆栈更重的容器上面不允许被放置较轻的容器在任何港口:

每一个槽 湾是收藏的最多一个容器,每个容器装进一个槽在其运输:

如果容器不是装进栈的底部,那么一定存在另一个容器存放下:

容器在海湾的插槽位置可能会改变只有在港口装卸业务,但不是任何两个港口之间的路上。即槽状态时该船时留下一些港口是一样的船到达下一个港口。特别是在最后一个端口 ,所有剩下的容器在海湾卸载:

如果不属预定目标的容器改变槽位置在海湾港 ,然后它必须改变曾经在港口:

如果不属预定目标的容器加载目标容器的顶部吗在同一个栈港 。完成加载/卸载操作后,容器不会改变它的位置,但容器吗必须转港:

不属预定目标的容器加载不属预定目标的容器的顶部吗在一个堆栈港 。完成加载/卸载操作后,虽然容器没有改变它的位置,它必须改变曾经在港口:

4.2.3。变量的范围

给出了决策变量的范围如下:

5。解决方案的过程

5.1。最佳的解决方案,最大化策略为小型实例

在本节中,我们首先考虑一个小实例的湾由四层三列。也就是说,有完全 槽充填最多12容器在海湾。该船访问四个港口 按顺序。每个集装箱的重量范围从1到3,更多意味着一个更重的重量。重的容器是收藏在一个较低的层的堆栈。最大可装载集装箱的重量在每个堆栈是8。注意,没有集装箱在装货前湾操作在端口1,和所有其余的容器在海湾港4卸载。这意味着没有发生转移的费用在第一个港口或港口,虽然容器变化可能发生在端口2和3。单位转移费用是15 - 40在端口2和3,分别。

在实例中,完全有20个目标容器加载和卸载在4端口。集装箱的详细数据,包括指标,权重,离开,和目的地港口,表中列出1。例如,集装箱1重量1在端口1加载和卸载港3。

我们解决上面的小实例12.6最大化策略求解和计算结果如图2这说明了装载前三个集装箱的港口。有四个矩形的每一列代表每个堆栈的四层,每个矩形内的数字表示容器指数。例如,在端口1,有12个集装箱装载和收藏在不同时段根据他们的相对权重和卸货港序列。在航行中,只有三个集装箱1,3,和14转移在端口2和3,分别。它导致的总转移费 。

稍大的实例有五列的六层在海湾,55目标容器参与四个港口。求解器的计算时间就会成指数级增长作为输入大小增加。一起考虑的np困难问题,我们提出一个遗传算法来解决更大的实例。

5.2。遗传算法

正如我们知道的,遗传算法已广泛地应用于各种应用程序由于其高效的性能。其基本过程如图3。在本文中,我们采用了遗传算法来解决大型积载计划问题的实例。我们在下面详细描述。

5.2.1。染色体表示

我们确定染色体基因片段端口的数量不包括最后一个端口的所有剩余的集装箱卸货,没有费用发生转移。也就是说,有 基因片段。每个染色体都是积载计划的解决方案。

每个基因片段的长度代表的容器加载相应的端口。每个基因的基因段表示堆栈的位置一个容器内的一个值 ,0表示没有容器被加载。例如,第三个基因的基因段= 2,代表第三个集装箱装载在堆栈在端口1(请参见图24)。因为每个集装箱重量的不同,其层相应位置是由排名的重量堆栈。通过这种方式,集装箱的装载计划。

5.2.2。种群初始化和个人的可行性

我们提出一个分布机制,保证每一个生成的解决方案是可行的。如下描述的机制。个人可行性验证通过容器的重量限制在每个堆栈和高度约束的堆栈。我们不断地产生大量的个人和丢弃它们之间的不可行个体直到可行个体的数量满足所需的具体规模。

5.2.3。健康评估

我们计算每个个体的适应度值基于目标函数的值。最小化的目标,目标函数值越小,越健康,它更有可能被选择作为父母。健身价值的计算是基于以下的插槽位置容器在海湾。

5.2.4。交叉和变异

有几种典型方法的交叉操作如单点交叉、两点交叉,多点交叉和均匀交叉。在这项工作中,我们采用两点交叉的交叉操作如下。首先两个不同的分频点是随机生成的两条染色体的基因段选择交叉操作和分频点的值没有超过染色体的长度。之间的数字交叉分两条染色体的交换,同时保持每个染色体的其他部分不变。交换后两个新染色体(参见图生成5插图)。

每个染色体的变异操作发生随机有一个预先确定的概率,这叫做突变率。两个突变的突变,染色体的位置随机选择和交换的两个对应的数字,生成新的染色体。新的染色体的可行性验证算法的下一步。

5.2.5。可行性验证

交叉和变异的操作可能导致不可行解或染色体。因此有必要验证和证明。基本验证规则如下:每个堆栈的总重量不超过 ; 有最多容器在每个堆栈;每个容器必须保管在海湾在离开前离开港口和目的港;在任何堆栈更重的容器上面不允许被放置较轻的容器在任何港口。在每一代,我们不断生成新的染色体,然后识别和丢弃的违反任何上述规定,直到后代的数量满足人口规模的要求。

5.3。一种改进的遗传算法

5.3.1。新的染色体表示

我们反复产生可行的个人,直到他们满足所需的约束,但是第一个算法的染色体长度太长,cross-mutation操作的效果提高初始种群的健康受到影响。主要结果是来自解决方案生成的初始种群。在本节中,根据原遗传算法,我们提出一种改进的遗传算法。我们称为原始算法,改进GAII之一。

改进后的染色体组成的 基因段,每个段的长度不再是容器的总数的路线,但容器盒在海湾的总数。改进后的染色体结构如图6。的染色体,有四个容器盒在海湾,第三个集装箱装载在端口1第四集装箱箱。的染色体,第三个集装箱是卸货港2。注意,如果没有集装箱装载在集装箱箱,染色体基因值等于0。在每个基因片段,容器将加载根据自己的体重在每个堆栈。我们反复产生可行的个人,直到满足所需的规模。此外,适应度函数和cross-mutation操作是一样的在丐。

5.3.2。可行性验证

cross-mutation操作后,测试规则如下:没有重复数字在每个染色体片段中,除了数字0;每个堆栈的总重量不超过 ; 每个容器必须收藏在海湾离开之前离开港口和目的港。cross-mutation操作后,如果染色体不满足所有测试规则,那么它就会被丢弃。

6。数值实验

6.1。时至今日,GAII的性能比较

正如我们在前一节描述的,配载图可以由最大化策略在小规模的实例。为了测量解决方案质量通过丐帮和GAII,我们首先解决这个问题通过最大化策略在小规模的实例。GA仿真设置多达100人口和100代的极限,执行编码与Matlab语言在计算机上(国米Core i5处理器,3.00 GHz;记忆,4 G)。在实验中使用的实例是随机生成的。我们假设航运包含8端口和单位转移费用在每个港口30,15日,40岁,50岁,80年,50岁,70,25(元),分别。与不同能力的海湾 和装载容器的数量的路线,我们测试这两个小型和大型实例。总费用转移和CPU运行时间以秒为单位的解决方案由最大化策略,盖和GAII,分别在表中所示的实例2。

从数值结果表2,最大化策略可以有效地解决小实例,多达147个集装箱大但不能输出解决方案实例有196或更多的容器(用“/”)。丐可以解决大规模实例,而低质量的解决方案。GAII可以取得更好的负载规划,特别是获得一个最优的解决方案实例与196个集装箱。它可以有效地解决这类装载问题在短时间内,这有助于节省运营成本的航运公司在路线。

6.2。之间的性能比较GAII例均匀和非均匀转移费用

如前所述,将活动在不同的集装箱港口导致不同的成本。此外,减少数量的容器是一个特例的变化最小化转移费用。为了显示对积载计划转移费用的影响,我们设计了数值实验对GA和解决他们的问题。我们假设航运包含8端口,再一次在实验中使用的所有实例都是随机生成的。对于非均匀转移费用的情况,我们假设单位转移8港口的费用等于30日,15日,45岁,60岁,100年,50岁,70,20(元),分别。对于均匀转移费用的情况,不失一般性,我们设置它的单位转移费用的平均费用超过8端口;即统一单位转移费用在每个端口是48.75(元)。结果GAII上述两种情况的实例表所示3。“统一移动金额”和“统一移动费”代表总转移数量和转移费用,分别在统一单位转移费用情况。“非均匀量”和“非均匀费”表示,分别把总额和转移费用的非均匀单元转移费用情况。

由表3,因为这两种情况下均匀和非均匀单元转移费用,GAII最佳解决第一个四个实例最多147个集装箱。对所有其余四个实例有196或更多的容器,我们观察到的解决方案与非均匀单元转移费用对应于较小的客观统一的单位值比其他情况转移费用。这意味着在非均匀单元转移费用的情况下,大多数将活动分配给这些端口与最便宜的转移费用,尽管它可能会导致一些变化重组容器。例如,在过去的实例与385个集装箱, 但更多的变化调整容器 元少转移费用在非均匀单元转移费用的情况下,相比于统一单位转移费用情况。因此,我们得出这样的结论:当转移在不同的港口费用是不均匀的,为了避免产生大量的港口的费用昂贵的费用转移,转移转移活动可能发生在一些前港口转移费用便宜。尽管这种调整可能导致更多的容器转移,转移可以将容器的总成本降低。

7所示。结论

在本文中,我们研究一个海湾的积载计划多个集装箱港口,船的关注nonuniform-shifting费用的情况,建立混合整数规划模型。提出了遗传算法和改进遗传算法求解该模型。实验结果表明了该模型的有效性和提出的遗传算法。更重要的是,通过比较与非均匀变化之间的积载计划费用和制服费用转移的情况,我们认为积载计划在前一种情况下可能会导致更多的容器转移但不如在后一种情况下转移费用。自负载平衡转移容器也很重要的活动,它可以受到几个因素的影响,如船的严重性和容器类型。考虑各种约束条件对积载计划是下一个研究的焦点。

的利益冲突

作者宣称没有利益冲突。

确认

这项工作是由美国国家科学基金会支持的中国(71428002,71428002,71428002,71771048,71571134,,71571135)。基础研究基金支持的工作也为中央大学、上海浦江计划(17 pjc046), MOE(中国教育部)项目的人文和社会科学(12 yjc630284),并在东华大学非线性科学研究所。