广东酷记海运拼箱公司

集装箱装船挨次优化模子2.1集装箱装船挨次对运输....其操作流程可见图1:图1...方针函数(7)是求集装箱在 起点口岸由堆场运出所需倒箱次数以及目标地口岸在船埠... 优化,流程 集装箱装船挨次对运输... 煽贫龋顺辉集装箱装船挨次优化模子及算法研究榴睹彰 本论文提出了一个用于集装箱装船挨次优化的动态整数规划模子。模子同时兼顾了集装箱在堆场中和在船上的摆放，并把集装箱在分歧口岸的装卸功课作为一个全体。在实现装船挨次最优化的同时该模子还可船 只在分歧荷载分布下的不变性。模子的求解是一个离散的 NP-hard 问题，论文给出了用遗传算决该问题的算法 框架，并通过正交因子试验切磋了算法参数的显著性和交互效应，从而大大缩短了算法在处理该问题时的运算时间。 环节词 集装箱运输，装卸优化，倒箱，遗传算法 Modeling and Algorithm Study for Optimizing Container Loading Planning for Containership Abstract In this , mathematicalmodel is proposed for developing plans for loading containers on containerships. The mathematical model is formulated as dynamicinteger programming problem. The model integrates many ctors, such as the storage policies, container ship stowage and the transfers at different terminals. As weight is one of the critical ctors that the model deals with, the best solution can also satisfy the meta-centric height restriction of the container ship. Since the problem is known to be NP-hard, GA is chosen due to the relatively good results in reasonable time. Unique coding method, evaluation function, genetic crossover and mutation operators are designed aimed at this problem and the significance and interactive effect of different parameters settings used during operation are analyzed. The shows that by using orthogonal fractional experimental designs, goodGA structure can be achieved to solve large,computationally intensive schedule problem. Key words: Container Transfers, Loading-unloading Optimization, Setup Arrangement, Genetic Algorithms 引言近年来，全球集装箱的运输量增加迅猛。1990 10年间，全球及中国地域的集装箱吞吐 量年平均递增率别离为6.4%和12.7%。为了获得规模 经济的劣势，各航运公司也不竭采用越来越大的集装 箱运输船舶。当前营运中的最大集装箱船舶可载箱 6000~7000TEU，船面上的载箱列数为17 列。而设想 中的超大型集装箱船舶更达到了载箱 18000TEU，列 数跨越 20 列的规模。跟着船舶装卸集装箱数量的增 加，其在口岸逗留的时间也越来越长，往往一艘船在 其运输收集中的一个节点就要装卸上千个集装箱，服 务时间长达5、6 个小时，甚至一天。 按照查询拜访表白，在集装箱装卸的过程中，因为港 口的平面安插，设备配备，船舶属性都是固定的，“倒 箱”次数的几多将是影响装卸办事时间的决定性要素。 为了提高堆场的储存能力，堆场中的集装箱往往要堆 层高，而船舶上的集装箱往往也分6、7层摆放。 若是要装卸的集装箱不是放在最上层，倒箱操作就在 所不免。虽然倒箱一次的时间相对于整个搬运时间来 说很短，但跟着规模经济的成长，堆场和船只中集装 箱堆放数量将会不竭添加，且堆放形式将更为紧凑， 这就使得累积的由于倒箱而花费的时间达到不成轻忽 的程度。假设每个集装箱倒箱一次需要额外破费 2.5 分钟，现有500 只集装箱要装船，而此中30%需要倒 箱的话，其额外功课时间就长达6 个小时，这对于航 运公司和口岸来说都将是一笔不小的丧失。所以本论 文的研究目标就在于若何最大限度的削减倒箱次数， 集装箱装船挨次优化模子2.1 集装箱装船挨次对运输效率的影响 我国集装箱船埠工艺安插与国际上保守的轮胎式 集装箱龙门起重机体例根基不异。船舶在口岸的装卸 过程凡是由几个子过程形成，此中装船过程尤为复杂， 起首由龙门起重机将要装的集装箱运至堆场旁的输送 点（这个过程要颠末若干次倒箱的操作），然后由集装 箱拖挂车运至船埠后用集装箱装卸桥装船(在装船的 同时，因为考虑到下一个口岸的卸货以及船的配载要 求，又要颠末若干次的倒箱操作)。其操作流程可见图 集装箱船装卸过程而从集装箱流动的角度来看，假设第n 个集装箱 要从i 地运往j 地，它起首要在i 地的堆场内存放，然 后由场内吊车运至输送点，通过集装箱拖挂车运至码 头，再由装卸桥装船。颠末一段航行后在 地的船埠卸下运至堆场内。本论文所建的模子就是考虑集装箱 在起点口岸由堆场运出至目标地口岸在船埠卸下这一 个典型的运输过程。该运输过程所花费的时间包罗堆 场功课时间T ，以及集装箱在j地的卸船时间T timeTravel 因为在固定的船舶类型，装卸设备和口岸工艺安插的环境下T 都是固定的值，而且在i地堆场集 装箱搬运挨次必然的环境下，T 也是固定的值，所以集装箱在 地堆场的搬运挨次将是决定该运输过程所需时间的环节要素。由于分歧的搬运挨次决定了 分歧的装船挨次，同时也导致了鄙人一个口岸卸船顺 序的分歧。 2.2 倒箱操作的定义 吊车挪动集装箱的时间是由两部门构成的，一是 将集装箱挪动到目标地的时间，记作T move ；一是吊车 锁住集装箱以及铺开集装箱的时间，这两个时间我们 能够假设它们是相等的，记作T lock 。若是再把集装箱 的层数记作z 代表第i只集装箱，z 是一个大于或等于1 的正整数），则第i 个集装箱的倒箱时间能够用 下面的式子暗示： lockmove lock move Setuptime if Setuptime -1。2.3 集装箱船配载的方式和稳性要求 集装箱船装载集装箱后，船舶重心提高，受风面 积增大会严峻影响船舶稳性。因而必需选择适度的稳 性和合理的集装箱分量分布。 在本课题的研究中，因为装载的总分量是必然的， 则集装箱的装载挨次成为集装箱船分量分布的环节影 响要素。往往为了获得一个好的分量分布，需要颠末 若干次的倒箱操作，为了尽量削减这些操作，能够在 装载的挨次长进行事后的放置。因为装载时必需达到 集装箱船的初稳性要求，所以在成立模子时必需把初 稳性作为不成行束缚前提。 合重心 KMGM 对初稳性最低要求的校核集装箱船的稳性凡是操纵船舶材料供给的“极限 重心高度KG 曲线”进行校核。要求经液面批改后的GM或KG 合适 下列前提之一： GMGM KGKG 2.4模子的假设 影响装卸时间的要素良多，若是全数考虑，模子 将变得十分复杂，难以表现出问题的素质。所以忽略 一些次要要素，做一些假设是有需要的： 在本论文考虑的问题中，集装箱船在首发口岸是空载，而且只考虑从首发口岸装货到下一口岸卸货 的过程。因为集装箱船在起点装载的集装箱是运往网 络中的各个口岸，其鄙人一口岸卸载的只是起点装载 的一部门。这个子过程的优化是整个运输收集优化的 根本； 在模子中，方针函数就是倒箱的次数。吊车的挪动相对于集装箱倒箱来说所花费的价值要小得多， 能够忽略不计； 的集装箱。这是本模子最次要的假设。但集装箱的分量各不不异； 集装箱船在起点所装载的集装箱中，不包含冷藏箱、箱和动物箱等特殊箱。由于这些集装箱在 船上存放的都有特殊的要求，如冷藏箱因为其箱 位附近要设置外接电源插座和插座，因而一般位 于舱面第一层。而且特殊箱需要提前装载； 装船时无集装箱的缓冲区；2.5 模子的成立 起首定义0-1 变量 idek 堆场的第处于 需要装载的集装箱 集装箱船的第被分派至 需要卸载的集装箱 集装箱船的第被分派至 需要装载的集装箱 定义idek 为装载集装箱i时所需的倒箱次数，同 理定义 为卸载集装箱j时所需的倒箱次数。 方针函数： idekidek (13)min GM GM idek(15) jd(16) idekidek if ,, (18)此中， ：集装箱i的分量（以吨为单元）； ：装载集装箱i时所需的倒箱次数； 时所需的倒箱次数；该模子为一个纯整数的线性规划模子。其最优解 可暗示为n 个集装箱装箱挨次的一个全陈列。 方针函数（7）是求集装箱在起点口岸由堆场运出 所需倒箱次数以及目标地口岸在船埠卸载时倒箱次数 之和的最小值。按照前面的阐发，这是集装箱运输的 一个典型过程，而且该过程的倒箱次数的几多决定了 整个过程集装箱处置时间的长短。所以该模子便是要 处理集装箱装卸时间的最优化问题。 束缚前提（8）了堆场中待装载的集装箱的位 置编码的独一性。束缚前提（9）了已装载的集装 箱在船上的编码的独一性。束缚前提（10）暗示 待装载的集装箱分量的总和必需小于集装箱船的排水 量，也即装载的分量总和不克不及跨越集装箱船的总容量。 束缚前提（11）～（13）给定了集装箱在船上的 配载挨次。式（11）暗示对于集装箱船的肆意行和任 意列，其基层的箱位都要比上层的箱位先填满。也就 是说，在装箱时，老是先装满一层后再装上一层；同 理可得，这三个束缚前提限制了集装箱在由装卸桥装 载到船上时，是按照装满一列再装下一列，装满一行 再装下一行，装满一层再装下一层的挨次摆放的。前 面已经会商过，如许的摆放挨次有良多长处，比若有 助于统一目标地的集装箱分布相对集中，以及在装船 的过程中连结较平均的分量分布等等。 式（14）是一个否认性束缚，即集装箱配载完之 后的初稳性高度必然要大于极限初稳性高度，不然该 配载方案则是无效或者不的。 式（15）～（18）描述了某个集装箱在装载和卸 载时对其他集装箱摆放的影响。集装箱所处的层 数在整个装卸过程中并不是固定不变的，而且叠放在 它的集装箱数量也在不断的变化。所以挪动该集 装箱所需的倒箱次数是一个动态变化的值。式（15）、 （16）设定初始形态每个集装箱所需倒箱次数为其所 在层数减一。如，最上层的集装箱地点层数为 所需的倒箱次数为0；而处于第二层的集装箱在搬运 时所需的倒箱次数则为 1，依此类推。当两个集装箱 处于统一行统一列的分歧层时，若是的集装箱先 被搬走，则基层的集装箱所需倒箱次数减一。若是一 个放在第二层的集装箱，当其上层的集装箱被搬走时， 其本身所处的层数天然变为最上层。这是一个很主要 的必需考虑的环境。 模子的算法研究现实的集装箱运输过程中，从集装箱船上装卸的 集装箱的数量是很大的。本章试图用该模子来处理一 个接近实在环境的问题，并会商遗传算法在处理大规 模问题时的机能。 现以1000TEU 摆布的全集装箱船为例，该轮某航 次由上海开往日本，在上海口岸起始形态船为空载， 而且在其下一个目标地日本口岸卸载其在上海口岸装 载的集装箱的一部门。该船船面上共9 行，每行可装 87＝504个集装箱装载单位。按照模子的前提， 假设该轮只装载尺寸不异的40 尺集装箱。该类型集装 箱的配货毛重约22 吨，空箱分量小于5 吨，体积68m 因为集装箱有时并非装满货色，则可设定每个集装箱的分量在5～25 吨范畴内。 上海口岸的集装箱堆场内共有500个40尺集装箱待装。这500 个集装箱在装载前处于离船埠较近的两 个相邻的区内。每个区可堆放8 列10 层的集装箱。集装箱在这两个区内的分布形态为随机发生。遗传算 法的初始参数设置如表1 所示： 遗传算法的初始参数参数名称 参数值 初始种群大小 50 轮回终止前提 30 0.5算法中所用到的交叉算子和遗传算子如表2 所示： 基于挨次问题的交叉和变异算子交叉算子（crossovers） 遗传算子（mutations） 首字母缩写 描述 首字母缩写 描述 PMX 部门映照交叉 AM 反改变异 LOX 线性挨次交叉 SFM 插入变异 SPX 单点交叉 2SM 交换变异 OOX 基于挨次的交叉 3SM 三交换变异 CX 轮回交叉 UX 平均交叉 算法采用的选择机制为“指数排序选择” (Exponential Ranking Methods) 其根基思惟为：将染色 体从好到坏进行排序，按照它们在挨次中的而不 是原适值指定选择概率。与凡是所用的转轮式选择相 比，它的劣势是可使染色体之间连结合理的差距，阻 止某些超等染色体太快的独霸遗传过程，以满足晚期 合作、晚期激励合作的需要。其选择概率P 按照下式计较： (19)此中， q＝最好染色体的选择概率； r＝染色体在排序中的，最好染色体的r 为种群的规模。(20) 在集装箱装卸优化的问题中，船舶的定倾核心高 度对方针函数的束缚其实是一个否认性束缚，即不满 足临界初稳性高度的染色体即为不成行染色体。但正 如前面会商的，不成行解有可能离最优解很近，赐与 过大赏罚晦气于从不成行域的标的目的获得最优解，所以 考虑带有自顺应项的乘法形式的评估函数： 赏罚函数形成如下： (22)此中，α 是用来调理赏罚峻厉性的参数； 为束缚的违反量。在不考虑集装箱船初稳性的环境下，本法式运转 了20 次，每次运转时间25 分钟，得出的成果如图2： 680 700 720 740 760 780 1113 15 17 运转次数 倒箱次数平均值 总平均值 仿真1运转成果 由图能够看出，每次法式运转的成果并不不异， 其倒箱次数在710～770 之间波动。平均最优倒箱次数 为737 次。此中最小值为715 次，最大值为765 尺度差12.97。因而，在初始种群大小为 50，并运转 30 代的环境下，并不克不及获得最优解，但根基上已 经接近最优解。 当改变初始种群数为100，运转50 679～739之间波动。平均最优倒箱次数为 707 次，此中最小值为679 次，尺度差14.75。 在考虑了集装箱船的初稳性的环境下，倒箱次 数有所添加，但不是很较着。 三种分歧初始种群、运转代数和方针函数设置下 的运转成果比力如表32 650700 750 800 850 900 950 1113 15 17 设置1 设置2 设置3 随机均值 仿真成果对比仿真 号码 种群数/运转代 均值最优解 尺度差 765715 12.97 707679 14.75 795766 15.44 由的图表能够看出，在处置大规模问题时， 遗传算法具有必然的坚苦，运转的时间较长（对于500 个集装箱的问题，在第二次仿真时运转时间为3 时摆布），并且并不克不及每次都达到最优解。但即便如许，该较好的解679 与随机搬运时的倒箱次数均值 864 比拟仍是削减了 20%的倒箱次数，这对于集装箱 运输系统的效率将会是很大的提高。 通过对三种分歧设置的比力能够得出以下结论： 种群数越大，运转的代数越多，遗传算法获得的成果越好。但该结果需要通过计较时间而获得； 在考虑了集装箱船的初稳性高度时，最优解的值较着增大，但和随机搬运时的倒箱次数比拟，仍然 削减了12%摆布。因为在该算法中采用的否认性 赏罚函数，最终解受赏罚函数的参数α 的影响较大。 按照多次运算的经验，α 0.5时能够获得较好的结 算法的优化遗传算法是一种用来处理需要搜刮复杂解空间的 问题的式算法。它凡是包含了一系列的参数。如 交叉运算和变异运算的参数，种群的大小以及运转次 数等等。不只如斯，还具有着良多分歧的交叉和变异 的算子。跟着这些要素的分歧，遗传算法的布局也在 发生变化。所以，若何按照现实的优化问题找到响应 的遗传算法的最佳布局将常主要的研究标的目的。因 为若是在处理大规模问题时算法运转的时间过长，耗 费的资本过多，即便能够获得最优解，也将得到其实 际使用的意义。 合适表4 参数设置的遗传算法布局优化问题即为 三因子二程度试验问题。为了有足够的度来估量 参数，而又不致进行太多次的试验，我们能够按 试验参数设置参数 分歧程度设置和代码 程度个数种群大小/运转 代数（P/G） 20:60 60:20 仿真试验成果阐发表试验 PMCM 67.6000 63.80 68.350 -3.8000 1.200 -1.2000 1.050 -2.6500 0.250 0.7500 排序 试验数据的方差阐发表方差来历 平方和 度 57.7625.671 5.762.560 4.411.960 PC11.52 5.762.560 PM 56.18 28.0912.484 CM 0.5 0.250.111 随机误差 4.5 的正交因子试验成果的阐发，能够得出以下结论： 初始种群的规模相对于其它参数来说显得最为主要。特别是大规模问题，必然要初始种群的 数量，以便供给足够的采样点。虽然每一代的运转时 间变长了，但能够大大节流运转的代数，从而节流整 个算法的运算时间； 在不高顺应值染色体布局的环境下，而且在运算时间答应的范畴内，应恰当提高交叉和变异运 算的频次，从而在全局和局部搜刮中都能够敏捷的达 到或接近最优解； 对于小规模的问题，不克不及将变异运算频次设置得太高，如许会导致算法变成随机性搜刮而很难； 在大规模问题上，添加变异频次比添加交叉频次显得更为无效，次要表示为得更快，运算成果 更好，而且的价格——运算时间更小。 论文次要结论及对此后研究的论文成立了用于集装箱装船挨次优化的多阶段动 态整数规划模子。该模子分歧于以往将堆场装卸，集 装箱船装卸以及集装箱在分歧口岸装卸的过程分隔来 研究的做法，而是将这些过程整合到一个模子中进行 优化，从而使模子在宏观上更具合和优胜性。模 型还同时兼顾了集装箱船配载后的稳性要求，使得优 化后的方案同时具有更好的可行性和适用性。在实例 阐发中，该模子的使用使倒箱次数平均削减了12％， 这对于集装箱运输系统的效率将会是很大的提高；论 文还给出了集装箱装卸优化模子的遗传算决。设 计了针对该模子的编码策略、选择机制、赏罚策略和 交叉、变异算子。该算法在大规模问题的处理上比以 往的优化方式计较时间大大缩短了，而且在处理现实 问题时取得了较好的结果，从而显示了式算法在 处理组合优化问题时的庞大潜力； 但该模子假设集装箱在堆场中已定，而现实 上装卸前都要对堆场内的集装箱进行调整。因而 能够开辟堆场堆放策略的优化模子，两者相连系，模 型的输出成果能够互为输入参数，颠末若干次的迭代 运算达到均衡，从而实现集装箱运输过程的全体最优 化；而且本论文的模子仅考虑了两个口岸之间的集装 箱流动，此后的研究能够考虑n 个节点之间的集装箱 装卸优化问题，将该模子推广至整个物流运输收集。 AliHaghani, Evangelos modelfor designing container loading plans for containerships. Transportation Research Board. Jan.2001 E.Kozan.Optimising container transfers at multimodal terminals. Mathematical and Computer Modeling. 2000, 31:235-243 ErhanKozan, Peter Preston. Genetic algorithms to schedule container transfers at multimodal terminals. Intl.Trans. in Op. Res. 1999, 6:311-329 Houck,Jeffery Joines,Michael geneticalgorithm for function optimization: matlabimplementation. NCSU-IE TR 1995, 1995-09 D.J.Stewardson,C.Hicks, P.Pongcharoen, S.Y.Coleman. Overcoming complexity via statistical thinking: optimizing genetic algorithms for use in complex scheduling problems via designed experiments. Proceeding of the meeting at Downing College, Cambridge, UK: Tackling Industrial Complexity: the ideas that make difference,9-10 April 2002 臼限凯婴幅娩祸章禁妇集装箱装船挨次优化模子及算法研 集装箱装船挨次对运输... 是求集装箱在起点口岸由堆场运出所需倒箱次数以及目标地口岸在船埠.