《出口集装箱倍分配模型及算法研究.doc》由会员分享，可在线阅读，更多相关《出口集装箱倍分配模型及算法研究.doc（7页珍藏版）》请在三一文库上搜索。
1、出口集装箱堆场倍分配模型与算法研究摘要：针对集装箱码头中出口箱堆场分配中的倍分配问题，以场桥大车移动距离最短、装船时发箱连续性为目标，构建了一种多目标规划的出口箱倍分配模型，以达到提高装船效率和降低成本等要求。并且采用了分布式遗传算法和启发式算法相结合的混合算法来求解构建的出口箱倍分配模型。关键字：出口箱；倍分配；目标规划；启发式算法；分布式遗传算法1 引言集装箱码头物流是海洋运输的起点与终点，是海陆货物运输的重要节点，在整个运输链中是货物最大的集散地。随着全球集装箱运量的增加，对集装箱码头的生产组织运营能力的要求也越来越高。堆场分配在集装箱码头生产组织各环节中处于核心地位，其分配结果是否合理
2、，将关系到整个码头的装卸效率和服务质量等。因此，出口集装箱的箱位分配是否合理也就显得尤为重要。近年来，国内外的学者在出口箱堆场分配方面进行了不少的研究。堆场分配通常包括堆场箱区的计划分配和具体箱位的合理选择两个层次，多数学者都致力于研究堆场箱区计划分配的优化问题，采用的优化方法主要包括整数规划、动态规划、二次规划等数学规划技术，但由于求解算法的规模限制，这些方法经常遇到困难。Kim K H和Bae J W1 以最小化装船时翻箱次数为目标，给出了相应的出口箱箱位分配数学规划模型。Kim H K和Lee J S2将约束满足技术应用到出口箱堆场分配问题中，给出了4种变量排序规则，2种值排序规则，并对
3、不同的规则从计算时间角度进行了评价。Taleb-I B M, Castilho B D和Daganzo C F3以最小化堆存空间为目标，描述了根据空箱位数量和实际装卸次数来为出口箱分配箱位。Chen P, Fu Z H和Adrew L4提出用多种算法解决该问题，包括禁忌搜索方法和“squeaky wheel”优化方法的混合方法来求解堆场分配问题。杨淑琴、张云杰和王志强5以取箱时翻箱率最小为目标，建立了不同重量级的集装箱按一定顺序到达的箱位分配模型和对应的启发式算法。沈剑峰6建立了基于知识工程的集装箱箱位分配模型和相应的知识库。本文重点研究了堆场分配中出口箱倍分配计划的优化问题，在充分考虑场桥大
4、车移动距离最短、装船时发箱的连续性等目标的基础上，建立了多目标规划的出口箱倍分配模型。同时，针对该模型，采用了分布式遗传算法和启发式算法相结合的混合算法来进行求解。2 出口箱倍分配数学模型在将决策周期内各时段每一船出口箱集港的箱区分配完成后，这时就需要根据当前时段内为每条船分配箱区的实际情况，决策各船在各箱区内倍的计划。倍分配模型是以以下的分配策略规则来建模的：倍内的集港箱属同一尺寸，同一船舶，同一个卸货港（或同一作业线相邻卸货港），排内只有一个重量级按照“尺寸船名卸货港重量级”对集装箱进行分类，尺寸相同，同属一条船和一个卸货港（或相邻卸货港）的集装箱堆放在同一倍（或堆放在多个箱区，每个箱区内
5、堆放在同一倍），同一重量级堆放在倍内的同一排。该模型主要是根据当前时段内各船出口箱分配到各箱区的箱量，来确定各箱区应该计划的具体的倍。2.1 建模假设(1) 决策天内到港船舶停靠泊位、靠、离泊时间已知； (2) 各船舶装卸箱量、箱型、重量分布可根据对历史统计规律进行预测；(3) 每条船舶预投入作业线数可以估计；(4) 计划天内集港和客户提箱量、提箱时间和历史统计规律吻合；(5) 各类箱区大小划分合理；(6) 集港和装船时对应箱区有可用的场桥。2.2 符号说明Q_allv：当前时段分配给船舶v的出口箱区集合；NBi： 箱区i内空倍的集合；倍分配时只能分配空的倍（空倍是指当该船的出口箱集港时，该倍
6、是空的，且未计划给别的船）；Lijk： 箱区i内第j倍和第k倍之间的距离；Dis： 一个倍的宽度；N40iv： 箱区i内计划船v的40尺的箱量；N20iv： 箱区i内计划船v的20尺的箱量；Rowi： 箱区i内允许堆放的排数；Tieri： 箱区i内允许堆放的层数；Bnoj： 箱区i内第j倍的倍号；Blsniv： 箱区i内分配给船舶v的左边界倍的倍号；Breniv： 箱区i内分配给船舶v的右边界倍的倍号；Bblsniv：箱区i内之前分配给船舶v的左边界倍的倍号；Bbreniv：箱区i内之前分配给船舶v的右边界倍的倍号；Bvalliv：箱区i内分配给船舶v的倍集合；OPij： 判断箱区i内第j倍与
7、其相邻倍是否属于同一条作业线；Badniv：箱区i中给船v计划的倍中连续倍的块集合，块为一个箱区中连续相邻的几个倍组合而成；Bnbiv： 箱区i中给船v计划的块b的倍数；Sadij： 箱区i内第j倍相邻倍的作业开始时间；（指装船或卸船的开始时间）Eadij： 箱区i内第j倍相邻倍的作业结束时间；（指装船或卸船的开始时间）Sij： 箱区i内第j倍的装船开始时间；Eij： 箱区i内第j倍的装船结束时间；： 倍分配时的宽泛系数；2.3 决策变量2.4 数学模型 该数学模型的目标函数有两个子目标，当前时段内每一条船集港时大车移动距离最短，即让各箱区中计划给每一条船的倍与倍之间的距离最短；如果计划的箱区
8、与已经给该船的箱区重复，则当前时段计划的和之前计划的所有倍之间距离最短。对于目标可用计划的倍之间的距离和最小来表示，因为集港时同一箱区内每个出口箱分配到计划的每个倍的几率是一样的，所以场桥大车在倍与倍之间来回移动的次数基本一致，因此虽然集港时大车移动的距离较计划的倍与倍之间的距离大很多，但只要能够保证倍与倍之间的距离最小，就基本能保证集港时大车移动距离最小。对于目标可用之前计划的倍的边界倍与当前时段计划倍的边界倍之间的距离来表示。目标函数： (1)(2) (3)约束条件： (4) (5) (6)其中 (7)(8) (9) (10)Lijk0，Dis 0 (11)式(1)保证集港时大车移动距离最
9、短，也即所有集港的倍之间距离最短。如图1所示，如果船舶在该箱区i中需要计划3个倍，从图中的空倍分布看出，可有多种方案选择3个空倍，以方案1和方案2为例，方案1的3个倍距离之和为5个倍，方案2的3个倍的距离之和为6个倍，因此方案1较方案2更好。图1 出口箱集港倍分配示意图式(4)保证了当前时段内的任意船舶v计划的倍都在分配的箱区中，且属于各箱区的空倍；式(5)保证了当前时段内的任意船舶v计划的箱区内分配的箱位足够堆放该船计划在该箱区的出口箱；式(6)考虑到一个箱区内最多能允许两台场桥同时作业，因此任意船舶v计划的箱区内分配的倍集合中，其左边界倍和右边界倍之间必须有2个相邻的倍未计划给该船，式(6
10、)中(1-Fijv)*(1-Fi(j+1)v)用于判断是否存在两个相邻倍都未计划给该船，如图2所示，箱区i内计划9个倍，分两部分，左边部分为0311倍，右边部分为1723倍，其边界11倍和17倍的倍号差为6，这样可以保证有两台场桥能够同时作业。式(7)保证了相邻倍如果属于不同的作业线，则作业时间不能交叉，任意相邻倍如果属于不同作业线，其作业时间不能交叉，因为相邻倍不能有两台场桥同时作业。式(8)保证了当前时段内的任意船舶v所分配的倍中，以两个相邻倍为大倍的大倍数可以足够堆存该船40尺的集装箱，因为每个40尺的集装箱要占两个相邻的倍，则所有计划的倍中以每两个相邻倍为一个大倍，则大倍总数不能小于4
11、0尺箱所需要的大倍数。式2-4-2-9)保证了当前时段内的任意船舶v计划的块集合与倍集合是一致的。式(10)为倍计划时宽泛系数要大于1。式(11)为倍与倍之间的距离、倍的宽度大于0。图2 箱区内计划的倍分两部分示意图3 出口箱倍分配模型算法出口箱倍分配模型算法主要是求解当前计划时段内，各船舶的所有出口箱在分配的箱区内应计划的具体倍，并计算各船在分配的各箱区内计划的倍之间的距离和。该算法首先采用模型中的各种约束条件和启发式规则，设计出口箱倍分配模型可行解启发式算法，用于缩小模型的可行解范围，然后再用分布式遗传算法对可行解进行全局优化，从而得出最优的倍分配结果。3.1 出口箱倍分配模型可行解算法3
12、.1.1 算法内涉及的符号定义VSeti： 当前时段箱区i内计划的船舶集合, VSeti = V1i , V2i , Vvi , Vni；VNi： 当前时段箱区i内计划的船舶数量；N40iv： 箱区i内计划船v的40尺的箱量；N20iv： 箱区i内计划船v的20尺的箱量；NBSeti： 计划箱区i内的空倍集合, NBSeti = Bay1 , Bay2 , Bayj , Bayn ；NBay20iv：船v在计划箱区i内的所需的20尺倍的数量；NBay40iv：船v在计划箱区i内的所需的40尺倍的数量；RBSetiv： 箱区i内实际分配给船舶v的倍集合；RBaySetj = RB1 , RBj
13、, RBn RBN20iv：箱区i内实际分配给船舶v的20尺倍数量；RBN40iv：箱区i内实际分配给船舶v的40尺倍数量；Bnoijv： 船v计划箱区i内实际计划倍的倍号；3.1.2 算法中的判断条件条件1： 其中，该条件保证了相邻倍属于不同作业线时作业时间不能交叉；条件2：RBN20ij NBay20ij ，该条件用于保证计划的20尺倍充足；条件3：RBN40ij NBay40ij ，该条件用于保证计划的40尺倍充足；条件4：，该条件用于保证分配的倍的集合中，其倍号差值之和应大于或等于6，从而达到允许两台场桥同时作业时不发生碰撞。3.1.3 算法流程如图3所示。图3 出口箱倍分配模型可行解
14、算法流程3.2 出口箱倍分配模型的分布式遗传算法实施Step1: 编码形式。由于集装箱码头倍编号都是整数，所以该算法的编码形式采用整数编码，个体编码中每2位为一个基因，代表箱区中的倍号，其中偶数号为40尺倍，如“01 03 05 07 10 14 18”，代表为20英尺箱计划的倍为01、03、05、07倍，为40英尺箱计划的倍为10、14、18倍。Step 2: 种群规模。根据倍分配可行解算法随机产生各个处理器上的第一代种群。种群规模确定为50-100，处理器为2，各子群体规模为25-50。Step 3: 进化代数的确定。一般，进化代数确定为20-50。Step 4: 适应度评价。在遗传算法的
15、后段采用线性尺度变换，则第k个父代个体的适应度值F(k)为：F(k) = a f(k) +b其中当时：；否则：，其中fmax，fave，fmin、分别表示当前代适应度值的最大值、平均值和最小值。其中c=2.0，适应度函数为2.4节中目标函数式(3) 的倒数，即；对于个体评价时是否可行，可采用出口箱区分配模型可行解算法中的判断条件1、2、3、4来进行判断，不可行解的适应值给一个很小的值代替，如-1000。Step 5: 选种。用赌盘轮算法来选择进入交配池的上一代父代个体，保留各子群体的最优个体，直接进入交配池（mating pool），另外的N -1个体采用赌盘轮算法随机选取，形成第一代交配池群
16、体，执行步骤为： 对子群体中的所有个体n的适应值求和，n为子群体规模。 确定个体的选择概率。 确定个体的累积概率4、产生一个 0 到1之间的随机数：RM。 从子群体中第一个个体开始，依次判断其累积概率是否等于或大于 RM，则 判断到的第一个符合条件的个体入选。Step 6: 各子群体分别独立采用 Steady-State 遗传算法进行选择、交叉、变异操作，交叉操作采用单点交叉，交叉的基因要选择被交叉个体中不存在的基因；变异操作采用高斯变异，其中变异范围是箱区内的空倍集合；替换百分比取 25。Step 7: 移民操作。根据指定的移民数目、移民频率及子群体之间的通讯拓扑关系进行移民操作。子群体之间
17、的通讯拓扑关系采用环状结构，交换频率取14，移民数目取25。如进行移民操作，则移民后重新构成新一代的子群体个体，作为下代父代群体。Step 8: 算法终止准则。遗传算法是一种反复迭代的搜索算法，通过多次进化逐渐逼近最优解。因此需要确定停止运行的准则。采用的终止条件是规定迭代的最大代数目。当遗传算法停止执行时，就把历代中最好的个体指定为遗传算法的结果7。4 结论本文首先构建了一种多目标规划的出口箱堆场倍分配模型，该模型是建立在场桥大车移动距离最短、装船时发箱的连续性等目标的基础上的。同时，采用了分布式遗传算法和启发式算法相结合的混合算法来对出口箱倍分配模型进行求解。参考文献1 Kim K H,
18、Bae J W. Re-marshalling export containers in port container terminals. Computers and Industrial Engineering, 1998, 35(3-4): 655-658.2 Kim H K, Lee J S. Satisfying Constraints for Locating Export Containers in Port Container Terminals.ICCSA 2006, LNCS 3982: 564-573.3 Taleb-I B M, Castilho B D, Daganz
19、o C F. Storage space vs handling work in container terminals. Transportation Research, 1993, 27B(1): 13-32.4 Chen P, Fu Z H, Adrew L. The yard allocation problem. Eighteenth national conference on artificial intelligence, 2002, 56- 65.5 杨淑琴、张云杰、王志强. 集装箱堆场问题的一个模型及其算法. 大连海事大学学报，2002, 28(S1): 115-117.6 沈剑峰. 基于知识与仿真的集装箱堆场作业计划研究. 硕士学位论文. 大连: 大连理工大学, 2006.7 蔡芸. 港口集装箱物流系统仿真和优化方法的研究及应用. 博士学位论文.武汉: 武汉理工大学, 2005.7 / 7文档可自由编辑打印