装箱算法（共7篇）
装箱算法 篇1
摘要：装箱问题 (bin packing problem) 是一个著名的NP难解问题, 其在工业生产及日常生活中有广泛的用途, 具有重要的研究价值。本文首先对装箱问题进行了简要的介绍, 然后描述了下次适应算法和调和装箱算法这两种一维装箱问题的近似算法及其并行化。
关键词：装箱问题,并行算法,近似算法
1．引言
装箱问题就是把一定数量的物品放入容量相同的一些箱子中，使得每个箱子中的物品大小之和不超过箱子容量并使所用的箱子数目最少。装箱问题具有重要的研究价值，实际生活中的货物装运、服装裁剪，以及计算机科学中的存储分配、共享资源调度、文件存储等都是装箱问题在实际应用中的体现。最早被研究的是经典一维装箱问题（Bin Packing Problem，简称BPP），其定义如下：
经典一维装箱问题：给定n个物品的序列Ln=（a1, a2, …, an），物品ai (1≤i≤n）的大小s (ai) ∈ (0, 1]，要求将这些物品装入最小数量的单位容量的箱子中。例如，把ai (1≤i≤n）分别放入箱子序列B1, B2, …, Bm中，使得每个箱子中的物品大小之和不超过1，即s (ai) ≤1, 1≤j≤m，且使所用的箱子数目m最小。
装箱问题是经典的N P难解问题，不存在多项式时间内求得精确解的算法（如果P≠N P），因此，装箱问题算法研究的对象是其近似算法。目前，已经提出了装箱问题的大量近似算法，如下次适应（Next Fit）、首次适应（First Fit）、最佳适应（B e s tF i t）、调和（Harmonic-K）算法等。这些串行算法已经具有比较好的性能，其重要性能指标的比较见表1[1]。
随着研究的深入，人们发现实际生活中更多存在的是一些带约束的装箱问题，因此也就抽象化出了二维装箱问题（条形装箱问题、剪裁问题）、三维装箱问题、变容装箱问题、有色装箱问题、对偶装箱问题等等一系列的带约束的装箱问题。但是由于这些问题所与生俱来的复杂性，虽然已经有一些研究成果发表了，但是其研究还是相当的困难。本文主要讨论一维装箱问题。
2. 下次适应算法及其并行化
2.1 下次适应算法
下次适应算法是最早提出、最简单的一个在线算法，其时间复杂度为O (n) ，最坏情况性能比为2，平均情况性能比为4/3。下次适应算法同一时间内只有一个箱子是打开的，当物品到达时，检查该物品能否放入这个当前打开的箱子中，若能则放入；否则把此箱子关上，打开一个新的箱子，把物品放入此新的箱子中。其串行算法如下：
算法1 Next-Fit串行算法
由算法易知，同一时刻只打开一个箱子，所以需要O (1) 的辅助存储，算法的时间复杂度为O (n) 。根据算法定义可知，任何两个相邻箱子中物品大小之和一定大于1，即s (Bi) +s (Bi+1) >1。对所有i，把该不等式求和，并注意到一个明显的事实OPT (L) ≥s (L) ，OPT (L) 即最少所必须使用的箱子数，s (L) 即输入序列中所有物品大小之和。可以得到下次适应算法的性能不等式NF (L) ≤2OPT (L) -1；且存在任意长输入物品序列使该不等式等号成立L= (1/2, 1/2N, 1/2, 1/2N, ……, 1/2, 1/2N) 。因此下次适应算法的最坏情况性能比值为2。
下次适应算法是最早被进行平均性能分析的近似装箱算法。1977年Shapiro给出了它在指数分布下的平均性能比，而算法在 (0, 1]均匀分布下的平均情况性能是Coffman等人首先给出的。他们利用概率分析方法证明，如果输入物品满足 (0, 1]均匀分布，则使用下次适应算法后，各箱子中物品大小之和（最后一个箱子除外）满足分布V (x) =x3，均值为3/4，从而该算法的平均情况性能比是4/3[1]。
2.2 下次适应算法的并行化
下次适应算法的并行算法的主要思想是结合平衡二叉数、倍增技术等并行化技巧对下次适应算法进行并行化。该算法分为以下四步：
(1) 利用前缀和算法建立一个链表簇，令A (i) 为输入物品序列中第i个物品的大小, 如果链表指针由A (j) 指向A (k) ，则表示A (j) +A (j+1) +…+A (k) >1且A (j) +A (j+1) +…+A (k-1) ≤1;
(2) 利用倍增技术计算以A (1) 为头的链表的长度，我们会在后面解释以A (1) 为头的链表的长度, 即是下次适应算法所使用的箱子数目；
(3) 利用在上一步骤中产生的中间数据反向建立一棵二叉树，使该二叉树的叶节点恰好是下次适应算法在各箱子中放入的第一个物品的序号；
(4) 根据各箱子中放入的第一个物品的序号，使用二分法确定各物品所放入的箱子的序号。
其具体算法如下：
算法2下次适应算法在S I M D-C R E W模型上的并行化
该算法的装箱方案与串行下次适应算法的方案相同，对任意输入物品序列L，它使用的处理器数目为O (n) ，时间复杂度为O (l o g n) 。该算法的总运算量为O (nlogn) ，明显大于串行算法O (n) 的运算量，所以该算法不是成本最优的。
3. 调和装箱算法及其并行化
3.1 调和装箱算法
带参数K的调和算法，在1985年由C.C.Lee和D.T.Lee提出[2]。其基本思想是将原始装箱问题划分为K个具有相同类型物品的子装箱问题，然后对每个子问题调用下次适应的策略。其中的参数K为常数，是指把区间（0, 1]划分为K个子区间], 大小处于区间Ik的物品为第k类物品, 同时箱子也相应地被划分为k类, 规定第k类箱子中只能装入第k类的物品。由于参数K的引入, 下次适应等算法中存在的前面箱子的剩余空间不可再用的矛盾得到了一定程度的缓解。K调和算法对于物品大小参差不齐的物品序列能很好的减小空间资源的浪费, 从而很好的提高了算法的性能。其算法的时间复杂度为O (n) , 最坏情况性能比为1.69103..., 较之下次适应算法其最坏情况比有了很大的提高。由于K的引入其平均情况性能比与K相关, 在K无穷大且在 (0, 1]均匀分布的情况下, 其平均情况性能比为1.28987...[3]。
3.2 调和装箱算法的并行化
由于调和装箱算法中每个子问题采用下次适应算法，所以可以在下次适应算法的并行算法的基础之上对其并行化。调和算法的并行化算法如下：
算法3调和算法在SIMD-CREW模型上的并行化
该并行化算法使用的处理器数目为O (n) ，时间复杂度为O (logn) ，该算法很好的保持了原调和装箱算法的在线性。
4. 结论
本文首先研究了下次适应算法的串行算法性能及它的一个并行算法，然后研究了K调和算法性能及它的一个并行化算法。装箱问题的并行化是一个很好研究课题，本文所介绍的只是众多装箱问题近似算法中的两种的并行化方法，且其性能未达到最优。对于该问题的研究还有待进一步深入。
参考文献
[1]E.G.Coffman, Jr., M.R.Garey and D.S.Johnson.Approximation Algorithms for Bin Packing:A Survey.Approximation algorithms for NP-hard problems.pages:46-93, 1996
[2]C.C.Lee and D.T.Lee.A simple on-line packing algorithm.Journal of the ACM, 1985.32 (3) :562-572.
[3]顾晓东, 许胤龙, 陈国良, 顾钧.调和装箱算法的平均性能分析.计算机学报.2001, 24 (5) :548-552.
装箱算法 篇2
颁布文号：海船舶[2007]531号
发布机构：海事局
发布日期：2007年10月25日
第一章
总 则
第一条 为加强船舶载运危险货物的安全管理，提高海运危险货物的通关效率，便利危险货物的运输，依据《中华人民共和国船舶载运危险货物安全监督管理规定》、《国际海运危险货物规则》等规定，制定本办法。
第二条 本办法适用于在中华人民共和国境内从事海运危险货物申报和集装箱装箱单位及其人员的管理。
第三条 海事管理机构根据职责分工，负责对船舶载运危险货物相关申报单位和装箱单位及其人员实施诚信管理制度。
诚信管理工作坚持依法、公正、公开的原则，按照统一的内容、标准、方法和程序进行。
第四条 诚信评定以遵守国内法律、法规、规范和履行国际公约、规则情况为主要依据，通过评审确定信誉类别。
第二章
信誉类别评定
第五条 申报单位和装箱单位的资质应符合国家相关法律、法规的规定，并持有相应的证书或文书。
申报单位和装箱单位应当配备合格的申报员和装箱员。申报员、装箱员应掌握海运危险货物及相关安全知识，通过专项培训或评估，取得相应的培训合格证书，并定期进行知识更新。
第六条 海事管理机构对申报单位采用备案管理方式。办理备案手续时申报单位应提交以下资料：
（一）备案情况报告；
（二）从事经营活动所在地工商管理部门颁发的营业执照；
（三）从事国际航行船舶申报的，应提交《国际船舶代理经营资格登记证》；
（四）从事国际贸易货物运输代理申报的，应提交无船承运人证明或相关货代证明文件；
（五）危险货物申报内部工作程序和制度；
（六）申报员持证情况；
（七）安全诚信承诺。
海事管理机构对上述资料审核无误后，应予备案。
第七条 海事管理机构对装箱单位采用备案方式。办理备案手续时，装箱单位应提交以下资料：
（一）备案情况报告；
（二）从事经营活动所在地工商管理部门颁发的营业执照；
（三）装箱单位所在地相关部门签发的相关危险货物安全生产许可证；
（四）装箱单位所在地消防部门签发的消防证书；
（五）危险货物装箱作业内部工作程序和制度；
（六）装箱员持证情况；
（七）安全诚信承诺。
海事管理机构对上述资料审核无误后，应予备案。
第八条 对已经备案的申报单位和装箱单位，海事管理机构应将其纳入信誉类别评定管理，并按照本办法为其进行信誉类别评定。
信誉类别分为A、B、C三类。
第九条 信誉类别评定的依据主要包括：
（一）上一的违规记录；
（二）发生事故的情况；
（三）涉及危险货物违法案件情况；
（四）从事船舶载运危险货物申报或装箱的单位和人员被举报并经查实情况等。
第十条 信誉类别评定采用当累计扣分制，每年的1月1日至12月31日为一个信誉类别评定。
第十一条 经评定信誉类别的单位，每年二月底前向海事管理机构提交书面材料，办理信誉类别确认或变更。
备案单位初次评定时，上两无不良记录的备案单位，备案后直接按A类单位管理；上两有不良记录的备案单位，备案后按B类单位管理；上两有重大不良记录的备案单位，备案后按C类单位管理。
第十二条 危险货物申报单位存在以下行为的应予扣分：
（一）发生危险货物谎报、瞒报行为的；
（二）申报员被海事管理机构吊销、暂扣培训合格证书或有违章记录在案的；
（三）未按规定办理申报的；
（四）未按规定履行审核职责的
（五）发生违章行为不按规定进行整改纠正的；
（六）备案情况不实或未及时变更的；
（七）有阻挠、拖延等不配合海事管理机构实施现场检查的。
第十三条 危险货物装箱单位存在以下行为的应予扣分：
（一）发生危险货物谎报、瞒报行为的；
（二）因装箱质量问题，导致危险货物在装卸、运输和储存过程中发生事故的；
（三）发生违章行为不按规定进行整改纠正的；
（四）装箱员被海事管理机构吊销培训、暂扣合格证书或违章记录在案的；
（五）应报告或提交的装箱信息或档案（包括照片、资料等）不符合要求的；
（六）未按规定履行审核职责的；
（七）备案情况不实或未及时变更的；
（八）有阻挠、拖延等不配合海事管理机构实施现场检查的。
第十四条 海事管理机构按各单位扣分累计扣满情况，即时调整其信誉类别。A类或B类的申报单位、装箱单位有下列行为的，可随时对其信誉类别进行调整，按照C类进行管理。
（一）有谎报、瞒报危险货物行为的；
（二）由于申报或装箱的过失导致严重后果的。
第三章
分类管理措施
第十五条 海事管理机构对A类申报单位、装箱单位给予以下便利措施：
（一）优先办理远程电子申报；
（二）在履行法定程序的前提下，申报审批事项，可通过“绿色”快速通道办理；
（三）接受相关担保证明；
（四）免除集装箱开箱检查，但专项、专案检查除外。
第十六条 海事管理机构对B类申报单位、装箱单位实施以下管理：
（一）除实施常规监管外，重点对其进行培训和指导，帮助其提高业务素质和安全意识，提升信誉类别。
（二）不接受相关担保证明，除高危险性货物外，可提供相关资料的复印件。
（三）海事管理机构对其装箱的集装箱实施一定比例的开箱抽查。第十七条 海事管理机构对C类申报单位、装箱单位实施以下管理：
（一）办理手续时，应提交相应正本书面材料。
（二）海事管理机构对其货物状况和装箱质量进行查验后，办理申报审批手续。
（三）装箱单位在办理申报审批时应按照装箱标准附送3张反映装箱情况的照片，海事管理机构对其装箱的集装箱实施经常性开箱抽查。
第四章
申报员及装箱员管理
第十八条 危险货物申报员发生下列行为的，海事管理机构应记录在案并予以扣分：
（一）有谎报、瞒报危险货物行为的；
（二）所申报的危险货物在包装、标记、申报材料等方面存在缺陷的；
（三）不按规定要求填写申报单证或报送申报信息的。
（四）有错报、漏报危险货物行为的；
（五）由于在申报中存在过失，而导致危险货物在装卸、运输和储存过程中产生严重后果的。
第十九条 危险货物装箱员发生下列行为的，海事管理机构应记录在案并予以扣分：
（一）未按规定签署《装箱证明书》的；
（二）危险货物集装箱无CSC标牌、箱体严重变形或集装箱超载的；
（三）集装箱内危险货物与申报内容不符、危险货物包装不符合规定要求的；
（四）集装箱内危险货物在积载、隔离、衬垫、加固、标志、标记等方面存在问题的。
（五）有阻挠、拖延海事管理机构开箱查验的。
第二十条 申报员、装箱员扣分达到相应的扣分量，应对其采取暂扣培训合格证书、吊销其培训合格证书等限制性措施，经培训或评估后，可再允许其从事申报、装箱工作。
第二十一条 申报员、装箱员发生下列行为的将吊销培训合格证书，且二年内不再对其签发新证书：
（一）有谎报、瞒报危险货物行为的；
（二）未到现场检查就签署装箱证明书的；
（三）对海事管理机构提出的整改要求置之不理，或隐瞒事实采取欺骗手段对存在安全隐患的危险货物集装箱不进行纠正的；
（四）由于在申报或装箱中存在过失，而导致危险货物在装卸、运输和储存过程中产生严重后果的。
第五章
附则
第二十二条 装箱单位应按照《海运危险货物集装箱装箱安全技术要求》（JT672-2006）的规定从事危险货物集装箱装箱工作。
罐式集装箱可参照集装箱的有关管理要求执行。
第二十三条 各直属海事局和各省（自治区、直辖市）地方海事局可根据本办法，结合辖区实际制定实施细则，明确各信誉类别累计扣分值、人员证书限制性措施扣分值及各项具体行为的扣分值，并报中国海事局备案。
装箱算法 篇3
摘要：
为完善解决轴辐式网络下的集装箱甩挂运输调度问题，针对轴辐式甩挂运输网络中的不同任务类型，考虑挂车中心数量、位置及任务时间窗，构建甩挂运输车辆调度优化数学模型；设计基于任务紧迫度函数、惩罚函数和距离函数的三阶段启发式算法，分别调度紧急任务、普通任务和超期任务.通过对经典算例求解，分别针对牵引车、挂车、挂车中心和紧急任务等数量的变化等进行敏感性分析，显示不同因素变化对整体调度方案的影响.该方法可为甩挂运输企业调度决策者提供相关的决策支持.
关键词：
甩挂运输； 轴辐式网络； 挂车中心； 时间窗； 启发式算法
中图分类号： U169.71；U492.22
文献标志码： A
0 引 言
轴辐式网络是道路运输的常见形式，胡志华等[1]对该物流网络进行过枢纽重配置优化研究.甩挂运输集汽车列车运输与装卸甩挂作业技术于一体，是一种集约、高效的运输组织模式.常见的甩挂模式有：一线两点，两端甩挂；循环甩挂；一线多点，沿途甩挂；多线一点，轮流拖带[2].
现有文献中有关带有挂车的车辆路径问题（Vehicle Routing Problem， VRP）的研究主要分为两类.一类问题可以被描述为：一辆货车配备一辆或者若干辆可以与之接挂或分离的挂车组成汽车列车.针对这类问题展开的研究主要有：SEMET等[3]首次讨论了“公路列车”（拖带一辆或多辆挂车的货车）的VRP；GERDESSEN[4]提出了VRPT（Vehicle Routing Problem with Trailers）的两种现实情境；CHAO[5]将带有挂车的VRP定义为TTRP（Truck and Trailer Routing Problem），并首次为该问题建立数学模型而不是描述性模型；SCHEUERER[6]、LIN等[79]和VILLEGAS等[1011]分别设计启发式算法、模拟退火算法和超启发式算法求解TTRP；DERIGS等[12]对TTRP的变形问题进行研究；胡志华[13]为该问题建立子回路分割模型.
另一类问题则是对目前国内所推广的“甩挂运输”的研究.该类问题与前述问题的区别在于：（1）甩挂运输问题中牵引车仅提供动力部分，没有装货的空间，而前述问题中的货车车头既是动力引擎又提供装货空间；（2）与前述问题拖挂分离的目的不同，甩挂运输中拖挂分离的目的是为了提高牵引车的利用率.虽然两类问题都存在其现实意义与研究价值，但是本文的研究内容主要集中在对第二类问题即甩挂运输问题的研究.
在甩挂运输相关文献中，HALL等[14]运用基于预测路径生产率的控制规则判断在循环甩挂中何时释放牵引车.SMILOWITZ[15]运用嵌入列生成的分支定界法对带有柔性任务的多资源路径规划问题进行求解.FRANCIS等[16]对SMILOWITZ[15]的模型及算法进行了改进，得到了更好的解.ZHANG等[17]对同一问题[1516]进行动态调度研究，运用两阶段算法对问题进行求解，目标是使运输成本最小.TAN等[18]在LEE等[19]模型的基础上加入挂车约束，首次建立了甩挂运输问题的数学模型，运用混合多目标进化算法得到问题的帕累托最优解.胡志华等[20]研究集装箱集散环境下空重箱循环甩挂的调度问题，建立混合整数规划模型，运用两阶段优化方法求解该问题.继而，胡志华[21]将该方法应用于集装箱码头间互拖的集卡甩挂运输调度问题.LI等[22]研究单车场牵引车与半挂车路径问题（tractor and semitrailer routing problem），运用启发式算法得到牵引车数量和每辆牵引车的路径，但文章缺乏对该问题的数学建模.袁野等[23]对单一客户点甩挂运输的建模进行了分析.
分析文献可以看出，现有文献集中在对循环甩挂和多线一点、轮流拖带这两种甩挂模式的研究上.在问题描述方面，对多线一点、轮流拖带的轴辐式网络结构缺乏明确的定义.在建模方面，对甩挂运输问题的数学建模，尤其是针对不同甩挂运输模式的特色建模，还处于研究初期，需要进一步完善.在算法方面，除文献[1517]运用分支定界法对问题进行求解外，其余文献主要集中在启发式算法上.本文基于已有的研究成果，运用启发式算法求解轴辐式网络下的集装箱甩挂运输调度问题，对该种模式的问题提取和模型建立进行深入研究.
本文对轴辐式网络下的集装箱整箱运输牵引车调度问题进行研究，研究贡献集中在：（1）对轴辐式集装箱甩挂运输的网络进行明确的定义及阐述；（2）提出三阶段启发式算法迅速给出调度方案，保证甩挂企业实际应用的时效性；（3）对牵引车数量，挂车中心数量、位置，挂车数量、分布，以及紧急任务数量等重要参数进行敏感性分析，为甩挂企业经营人进行合理的资源配置提供参考.
1 问题描述
如图1所示，椭圆中的轴辐式网络由中央集散中心（或港口）与分布在周围的客户点、挂车中心（TrailerCenter，TC）和连接各点的弧构成.牵引车的路径闭合，即从集散中心出发，最终回到集散中心.
出口集装箱甩挂运输操作流程为：牵引车从集散中心出发，先到TC挂一辆空挂车，再回到集散中
心的堆场取空箱运至客户点处，并将载有空箱的挂车甩下，然后从客户点返回集散中心或者驶向下一任务的开始节点.甩下的空挂车停留在客户点处进行装箱作业.待客户点处装箱完毕后，牵引车将从客户点将重挂取回至集散中心，重箱与挂车分离，落至堆场等待干线运输.需要说明的是，为客户点送空挂的牵引车和取重挂的牵引车可以不是同一辆.进口集装箱甩挂运输操作流程则与之相反.
根据集装箱流向和客户的需求，将牵引车的任务类型分为4种：取空箱、送空箱、取重箱、送重箱.4种任务类型两两组合可以形成16种任务子序列，当某个任务子序列为两个送箱任务相连时，牵引车需要在两任务中间访问TC取空挂车；当相连任务为取箱任务时，牵引车需要访问TC还空挂车.本文根据调度的不同阶段，将任务分为紧急任务、普通任务和超期任务.紧急任务被定义为：在本规划期的牵引车路径规划完成后，企业接到的新任务或任何需要优先于其他任务完成的任务.普通任务被定义为：本规划期内不需要被优先完成的任务.超期任务被定义为：已经接受客户申请，但因公司资源条件限制，无法在本规划期内完成的任务.加入对紧急任务的处理是本文的创新点之一.
为了日常调度的实用性和时效性，启发式算法在解决VRP中被大量应用.本文采用三阶段启发式算法对问题进行求解，三阶段算法分别调度紧急任务、普通任务以及超期任务.在80个客户点、100项任务、不同资源配置下的50项实验中，该算法均能在5 s之内给出调度方案，极大地满足企业在实际调度工作中对时效性的需求.
2 数学模型
在文献[18]和[23]的基础上进行扩展，建立如下数学模型.
2.1 模型假设
一辆牵引车仅能挂一辆挂车；牵引车与挂车在各任务节点的挂/甩挂车时间已知且不变；所有挂车均载有40英尺的集装箱.
2.2 参数和变量
2.2.1 参数
G=V，D为运输网络；V=0，1，…，i，…，I为节点集合，其中节点0表示集散中心，其他节点表示客户点及TC；D为节点之间弧的集合，Dij为两节点i与j之间的路网距离；Ck为牵引车k的每千米油耗；K为牵引车总数；M为任务总数；Ma为紧急任务数；Mb为普通任务数；ma为紧急任务序号；mb为普通任务序号；
T为牵引车在规划期内能够完成的任务数上限；Tma，2为所有紧急任务的结束时间；Tmb，1为第一个普通任务的开始时间；Thpm为牵引车从紧前任务h终点到挂车中心p，再到紧后任务m起点的行驶时间；Thm为牵引车从紧前任务h终点到紧后任务m起点的行驶时间；Tm为牵引车从任务m起点到终点的行驶时间；Hm，1为任务m在起点的操作时间；Hm，2为任务m在终点的操作时间；Tk，1为牵引车k开始工作的时间；Tk，2为牵引车k结束工作的时间；TEm为任务m的最早开始执行时间；TLm为任务m的最晚开始执行时间；NSK为送空箱任务集合；NSZ为送重箱任务集合；NQK为取空箱任务集合；NQZ为取重箱任务集合.
2.2.2 决策变量
2.3 数学模型
式（1）为优化目标，即方案总成本最小；式（2）表示每个任务仅被执行一次；式（3）保证所有牵引车的任务分配有序；式（4）表示所有普通任务要在紧急任务之后被完成；式（5）～（8）表示每项任务的时间序列，其中式（5）是同一牵引车执行前后两项任务的时间递推；式（9）表示每辆牵引车的工作时间均在规划期内；式（10）保证满足任务的时间窗要求；式（11）和（12）保证每辆牵引车的路线是闭合的；式（13）～（15）表示对TC的访问约束，式（13）中当牵引车执行第一项任务时，只有涉及送挂车时才会产生访问TC取挂车的情况，执行其他任务时前后两项任务均需送挂车才会产生访问TC取挂车的情况.
3 三阶段启发式算法
设计启发式算法进行求解.根据任务的待执行紧迫程度，将其分为紧急任务、普通任务和超期任务等3种，而任务性质的划分则依赖于决策函数（紧迫度函数、惩罚函数和距离函数）.
任务的紧迫度越高，紧迫度函数值越大；任务执行方案对其时间窗违反程度越高，惩罚函数值越大；距离函数则是执行该任务所需行驶的总距离.
3.1 三阶段启发式算法总体流程
算法总体思路为优先分配紧急任务，然后分配普通任务，最后推迟或外包超期任务，具体见图2.
3.2 三阶段启发式算法具体步骤
3.2.1 分配紧急任务
紧急任务的紧迫度函数值相同，因此当同时出现多个紧急任务时，分别计算各任务的惩罚函数值后再进行分配.具体流程见图3.
3.2.2 分配普通任务
紧急任务分配结束后，以任务的紧迫程度和子序列的惩罚函数值为标准进行普通任务的分配，具体流程见图4.
3.2.3 外包或推迟超期任务
当存在超出规划期的任务时，将这些超期任务推迟至下一规划期或外包，具体见图5.
4 算例实验
通过改进文献[18]中的算例，本文分别从牵引车数量、TC数量、挂车数量和紧急任务数量这4个方面验证算法的有效性，并分析各因素对整体调度方案的影响.
轴辐式网络由一个集散中心、若干个TC以及80个客户点组成.TC和客户点的位置随机分布在100×100的网格上，集散中心位于网格中心.任意两点之间采用欧氏距离.另外，本文的规划期为早8：00到晚8：00（1天内）.牵引车行驶速度为60 km/h，单位挂/甩挂车时间为30 min.违反时间窗的惩罚因数a=b=1.
4.1 牵引车数量
本例共有11项实验，牵引车数量从15辆逐一变化至25辆，任务数量均为100个，TC有5个，均匀分布在网络中.每个TC的可用挂车均为6辆.
由图6可以看出，牵引车的数量能够直接影响任务的完成情况.当牵引车数量上升至19辆时，未完成的任务数下降至0，说明该系统内牵引车最低保有数量为19辆.牵引车从15辆逐渐增多，迟到惩罚成本降幅超过提前惩罚成本的涨幅；当牵引车数量超过20辆并继续增多时，提前惩罚成本大幅上升，并且覆盖了迟到惩罚成本的减少，造成总惩罚成本曲线呈“U”型.
4.2 TC数量
为研究TC的地理分布对调度方案总成本的影响，设置TC数量不同的算例，共8项实验，TC数量有1，3和5个等3种情况.TC分布方式有：TC1～TC5均匀分布，仅设TC1，仅设TC2，仅设TC3，仅设TC4，仅设TC5，设置TC1，TC3和TC5，设置TC1，TC2和TC4等8种.挂车在TC均匀分布，总数均为30辆.
由图7可以看出，TC的数量和分布方式会直接影响任务的完成情况和系统整体调度方案.总体而言，TC数量越多，分布越均匀，牵引车行驶的总里程及方案的总惩罚成本越小.当仅设置单一TC，且TC分布在1，3，4，5等4个位置时，出现了未完成任务.而当TC位于2位置时，总里程和总惩罚成本较其他算例更优，证明TC的选址也会影响经营成本.
图7 TC数量不同时的算例运算结果
4.3 挂车数量
该算例包括5组25项实验，TC数量均为1个，分布方式分别为TC1，TC2，TC3，TC4和TC5.每项实验任务数量均为100个，牵引车数量为20辆，每组实验TC的挂车数量（NT）从23辆逐渐增至27辆.
由表1可见，在各TC的挂车数量增加的过程中，当挂车数量为23辆和24辆时以及第3组和第5组中当挂车数量为25辆时，因挂车数量难以满足需要未能给出规划结果.挂车数量不仅影响经营成本，还会直接影响经营质量：挂车数量过少无法完成既定的任务，而过多又会增加公司经济负担和管理成本.
4.4 紧急任务数量
设置紧急任务数量不同的6项实验，任务数均为100个，牵引车数量均为20辆，TC可用挂车数均为30辆，5个TC均匀分配挂车，紧急任务的数量从0逐渐增长到5个.
由图8可以看出，初期随着紧急任务数量的增加，提前惩罚成本和迟到惩罚成本均逐渐下降，优先处理紧急任务可以使整体方案违反时间窗的程度降低；当紧急任务数量上升至5个时，迟到惩罚成本仍保持下降趋势，但提前惩罚成本增加，导致总惩罚成本上升幅度较大.这说明紧急任务的数量较多时，为尽快完成任务，对时间窗上限的违反程度较高.
图8 紧急任务数量不同时的算例运算结果
5 结束语
本文建立了轴辐式网络中甩挂运输车辆调度问题的模型，提出了基于启发式规则的三阶段调度算法.基于牵引车数量不同、挂车中心数量不同、可用挂车数量有限和紧急任务数量不同等4个类型的算例实验，提出了配置牵引车和挂车数量以及优化挂车中心地理位置的具体方法，并阐述了紧急任务数量对调度计划的影响.全面剖析了甩挂运输系统调度时各因素的影响，为营运者提供一定的决策借鉴.
未来的研究将考虑甩挂运输新模式下的调度优化问题，例如牵引车对开、相遇后司机折返等.
参考文献：
[1]胡志华， 洪雯婷， 胡青蜜. 轴辐式物流网络扩张的枢纽重配置优化[J]. 上海海事大学学报， 2015， 36（1）： 1924.
[2]高洪涛， 李红启. 道路甩挂运输组织理论与实践[M]. 北京： 人民交通出版社， 2010： 1819.
[3]SEMET F， TAILLARD E. Solving reallife vehicle routing problems efficiently using tabu search[J]. Annals of Operations Research， 1993， 41（4）： 469488.
[4]GERDESSEN J C. Vehicle routing problem with trailers[J]. European Journal of Operational Research， 1996， 93（1）： 135147.
[5]CHAO I M. A tabu search method for the truck and trailer routing problem[J]. Computers & Operations Research， 2002， 29（1）： 2251.
[6]SCHEUERER S. A tabu search heuristic for the truck and trailer routing problem[J]. Computers & Operations Research， 2006， 33（4）： 894909.
[7]LIN S W. Solving the truck and trailer routing problem based on a simulated annealing heuristic[J]. Computers & Operations Research， 2009， 36（5）： 16831692.
[8]LIN S W， YU V F， CHOU S Y. A note on the truck and trailer routing problem[J]. Expert Systems with Applications， 2010， 37（1）： 899903.
[9]LIN S W， YU V F， LU C C. A simulated annealing heuristic for the truck and trailer routing problem with time windows[J]. Expert Systems with Applications， 2011， 38（12）： 1524415252.
[10]VILLEGAS J G， PRINS C， PRODHON C. GRASP/VND and multistart evolutionary local search for the single truck and trailer routing problem with satellite depots[J]. Engineering Applications of Artificial Intelligence， 2010， 23（5）： 780794.
[11]VILLEGAS J G， PRINS C， PRODHON C. A GRASP with evolutionary path relinking for the truck and trailer routing problem[J]. Computers & Operations Research， 2011， 38（9）： 13191334.
[12]DERIGS U， PULLMANN M， VOGEL U. Truck and trailer routing problems， heuristics and computational experience[J]. Computers & Operations Research， 2013， 40（2）： 536546.
[13]胡志华. 基于混合进化算法的甩挂配送问题[J]. 公路交通科技， 2013， 30（5）： 147152.
[14]HALL R W， SABNANI V C. Control of vehicle dispatching on a cyclic route serving trucking terminals[J]. Transportation Research Part A： Policy and Practice， 2002， 36（3）： 257276.
[15]SMILOWITZ K. Multiresource routing with flexible tasks： an application in drayage operations[J]. IIE Transaction， 2006， 38（7）： 555568.
[16]FRANCIS P， ZHANG G， SMILOWITZ K. Improved modeling and solution methods for the multiresource routing problem[J]. European Journal of Operational Research， 2007， 180（3）： 10451059.
[17]ZHANG G， SMILOWITZ K， ERERA A. Dynamic planning for urban drayage operations[J]. Transportation Research Part E： Logistics and Transportation Review， 2011， 47（5）： 764777.
[18]TAN K C， CHEW Y H， LEE L H. A hybrid multiobjective evolutionary algorithm for solving truck and trailer vehicle routing problems[J]. European Journal of Operational Research， 2006， 172（3）： 855885.
[19]LEE L H， TAN K C， OU K. Vehicle capacity planning system： a case study on vehicle routing problem with time windows[J]. IEEE Transactions on Systems Man and Cybernetics Part A Systems and Humans， 2003， 33（2）： 169178.
[20]胡志华， 曹杨， 王云霞. 集装箱集散的空重箱循环甩挂调度方法[J]. 武汉理工大学学报， 2012， 34（10）： 6873.
[21]胡志华. 集装箱码头间互拖的集卡甩挂运输调度问题[J]. 重庆交通大学学报（自然科学版）， 2013， 32（2）： 313317.
[22]LI Hongqi， LU Yue， ZHANG Jun， et al. Solving the tractor and semitrailer routing problem based on a heuristic approach[J]. Mathematical Problems in Engineering， 2012. DOI：10.1155/2012/182584.
[23]袁野， 徐家旺， 方云龙. 集装箱甩挂运输模型与应用[J]. 沈阳航空航天大学学报， 2014， 31（1）： 9296.
一种求解装箱问题的混合算法 篇4
装箱问题(Bin Packing Problem,BPP)是一类重要的组合优化问题,在现实生活中有着广泛的应用背景,特别在现代物流中,许多问题都抽象化为装箱问题或其变形,如货物如何装载,才能提高运载器具的利用率,从而降低运输成本;物流任务应如何调度,才能提高运行效率,等等。但在理论上,装箱问题是一个NP难题[1],很难精确求解。因此对其求解进行研究具有重要的理论价值和实际意义。
到目前为止,针对该问题人们提出了许多算法,但都有其局限性:枚举法和分支定界等精确算法在箱子数目稍大时,会出现“组合爆炸”;一些近似算法如下次适应NF、首次适应FF、降序首次适应FFD、最佳适应BF等,在解决复杂的装箱问题时结果与物品的体积数据有较大关系,在极端情况下很不理想;遗传算法能在合理的时间内求得最优解或满意解,但易陷入局部最优。
本文针对以上算法的不足,提出一种混合算法,该算法结合遗传算法良好的全局搜索能力和禁忌搜索具有记忆能力的全局逐步优化特性,增强全局和局部意义下的搜索能力和效率。实例证明,在求解装箱问题时,该算法性能明显优于单纯遗传算法。
1 问题描述
装箱问题是指将重量分别为w1,w2,…,wnwj,>0,j=1,2,…,n,的n个物体装入许多个同种大小的箱子(最多n个),且每个箱子有重量限制c c,>w j,。问题是寻找最优的装箱方案,即在保证每个物体都被装入且重量之和不超过箱子的容量限制情况下,使用的箱子数量最少。
数学模型表示如下:
式(1)是装箱问题的目标函数;式(2)保证装入箱子的物体重量之和不超过其容量限制;式(3)保证每个物体都被放入箱子中;式(4)与式(5)是决策变量的整数约束。
2 遗传禁忌混合策略
遗传算法(Genetic Algorithm,GA)是Holland教授于20世纪60年代受生物进化论的启发而提出的一种基于生存遗传和进化机制的随机优化方法。它将问题的求解表示成染色体适者生存的过程,通过染色体群的一代代不断进化,包括复制、交叉和变异等操作,最终收敛到最适应环境的个体,从而求得问题的最优解或满意解[2]。遗传算法开创了在解空间中从多出发点搜索问题的先河[4],能从概率的意义上以随机的方式寻求到问题的最优解,具有并行性,很强的通用性,良好的全局性和鲁棒性等特点。但是,在实际应用中,由于受选择压力、交叉和变异操作等因素的影响,容易出现早熟现象,局部搜索能力差。
禁忌搜索(Tabu Search,TS)最早是由Glover提出的,是对局部邻域搜索的一种扩展,通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索,并通过藐视准则来赦免一些被禁忌的优良状态,进而保证多样化的有效探索以最终实现全局优化。但禁忌搜索时搜索效率低,并且禁忌搜索对初始解具有较强的依赖性[3]。
鉴于以上两种算法各自的优缺点,本文设计了一种混合算法,将遗传算法和禁忌搜索结合起来,相互取长补短,这样混合算法具有遗传算法多出发点和禁忌搜索的记忆功能及爬山能力强的特点[4]。混合算法结构如图1所示,具体来讲,就是将禁忌搜索作为遗传算法的变异算子,初始群体经过选择、交叉操作后产生的新个体作为禁忌搜索的初始解,然后禁忌搜索每一个参与变异的个体,搜索后的新个体与未变异的个体形成新的种群,再对新种群中的个体进行上述混合操作,直至算法终止。
3 遗传禁忌混合算法设计
3.1 算法步骤
步骤1给定初始参数,包括最大迭代次数T,群体规模m,交叉概率Pc和最大变异概率Pm,令当前代数t=0。
步骤2确定初始群体,随机产生n个箱子的m个全排列作为初始染色体xt1,…,xtm。
步骤3计算群体中每个个体的适应度值f（xt1）,…,f （xtm））
步骤4按轮盘赌方式从群体中选择m个个体作为父代,个体被选择的概率为,i=1,2,…,m。选择过程中使用
最优个体保留策略。
步骤5按照交叉概率Pc,对群体中的个体进行交叉操作。
步骤6按照变异概率Pm,采用禁忌算法作为变异算子,把一个要变异的染色体作为禁忌搜索的输入,把禁忌搜索得到的解作为变异的新个体。
步骤7如果t<T,令t=t+1,转步骤3,否则转步骤8。
步骤8输出最优解,终止算法。
禁忌搜索算法操作步骤如下:
(1)按照变异概率从当前代中随机选择部分个体进入禁忌搜索集合,给定算法参数。
(2)从禁忌搜索中随机选取一个个体作为当前解,置禁忌表为空。
(3)利用当前解的邻域函数产生所有(或若干)邻域解,并从中选择部分候选解。
(4)对候选解判断藐视准则是否满足?若是,则用满足藐视准则的最佳状态y代替x成为新的当前解,即x=y,并用与y对应的禁忌对象替换最早进入禁忌表的禁忌对象,修改禁忌表中各禁忌对象的任期,同时用y替换“best so far”状态,然后转步骤(6);否则,继续以下步骤。
(5)判断候选解对应的各对象的禁忌属性。将候选解集中非禁忌对象对应的最佳状态作为新的当前解,同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象,并修改禁忌表中各禁忌对象的任期。
(6)判断对该解的禁忌搜索是否满足终止条件,若是,则结束搜索,转步骤(7);否则返回步骤(3)。
(7)判断禁忌搜索集合中的每个解是否都搜索完毕,若是结束该过程;否则转步骤(2)。
3.2 参数设计
(1)编码方案。本文采用自然数编码。把所有物体按顺序进行编号,随机生成一个序列,从而组成一个染色体。例如有5个物体需要装箱,生成的染色体可能有(1,2,3,4,5)和(2,5,4,1,3)等。用这种编码方法,没有把箱子编入染色体中,染色体的结构仅和物体有关[5]。
(2)适应度函数。因为本文中研究的装箱问题,是以所用箱子数最少为目标函数,即目标函数是求问题的最小解。假设某一染色体对应的箱子数是Fx,则适应度函数可表示为fx=K-Fx,其中K是一足够大的正数。
F xF F由下次适应法NFFF确定。具体步骤是依次从每个随机生成的染色体中按顺序取出每个基因(即物体)放入一个箱子中,如果该箱子放满了,则放入下一个箱子,直到所有物品放完为止,此时所用的箱子数即为F xF F。
(3)选择算子。在这里使用轮盘赌选择算子,也叫比例选择算子,即个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比。同时,在选择的过程中引入最优保存策略,用上一代适应值最大的染色体代替新一代适应值最低的染色体,可保证当前的最优个体不会被破坏,加速算法向最优解收敛。
(4)交叉算子。交叉是指对两个相互配对的染色体以某种方式相互交换部分基因,从而形成两个新的个体。本文选择最基本两点交叉算子,其具体执行过程如下:(1)群体中的个体进行两两配对。(2)对每一对相互配对的个体,随机设置两个位置为交叉点。(3)对每一对相互配对的个体,依设定的交叉概率的交叉点相互交换两个交叉点之间的染色体,从而产生出两个新的个体。
(5)变异算子。采用禁忌搜索算法作为变异算子,把一个要变异的染色体作为禁忌搜索的输入,把禁忌搜索得到的解作为变异的新个体,在这里以染色体本身为禁忌对象,采用两点互换操作构造邻域并从中选择部分个体作为候选解,以目标函数值作为藐视准则。
4 仿真试验
4.1 算例一
采用以上算法步骤,作者试算了文献[5]中的一组数据,这是一个由15个物体和足够多的单位箱子(容量为1)组成的装箱问题,物品重量。设定混合算法的运行参数为{迭代次数,种群大小,交叉概率,变异概率,禁忌长度}={100,100,0.7,0.1,4}进行试算,运行20次,以100%的概率找到最优解4,与文献[5]中的计算结果比较如表1所示。
由以上数据可以看出,与文献[5]中采用的混合遗传算法和简单遗传算法相比,本文算法能在较短的时间内收敛到最优解,其效率要优于以上两种算法。
4.2 算例二
为了进一步测试本混合算法的性能,作者对另外19组数据进行试验并和简单遗传算法比较,这些数据由随机方法产生,箱子数从10到100个,算法由Matlab编程实现。实验结果如图2所示。
通过以上比较图,我们可以看到,当物品数量较少F10≤n≤30F时,两种算法最终收敛到相同的解。随着问题规模的扩大,简单遗传算法的装箱方案所使用的箱子数要比混合算法的多。用△表示多用的箱子,当物品数n=50,△=2,△随n的增大而逐渐增大,当n=100,△=5。由此可见,当箱子数量增大的一定规模时,简单遗传算法因其固有的缺点,在运行过程中可能会过早收敛到非满意解,不适合用来求解;而此时混合算法却能在较短的时间内求得较优的装箱方案,表现出明显的优越性。
5结论
本文为求解装箱问题提出了一种基于遗传算法和禁忌搜索的混合算法,该算法具有多点出发和爬山能力强等特点,有效地解决了传统遗传算法的早熟收敛问题。通过实例计算,证明遗传禁忌混合算法是一种行之有效的算法,对解决装箱问题有很好的实用价值。
参考文献
[1]Garey M R,Johnson D S.Computers and intractabililty:a guide to the theory of NP-completeness[M].San Francisco:Freeman,1979.
[2]Coffman E G,Garey M R,Johnson D S.Approximation Algorithms for Bin packing:A survey[C]//In:D Hochbaumed.Approximation Algorithms for NP-Hard problems.Boston:PWS Publishing,1996,46-93.
[3]王凌.智能优化算法及其应用[M].北京:清华大学出版社,施普林格出版社,2001.
[4]李大卫,王莉,王梦光.遗传算法与禁忌搜索算法的混合策略[J].系统工程学报,1998,13(3):28-34.
装箱算法 篇5
关键词：集装箱,空箱,调运,遗传算法
随着经济全球化、贸易国际化的深入发展,国际海运业得到迅猛发展,集装箱运输具有运量大、装卸及疏运快、节约包装材料、安全便捷等优点,越来越多的散杂货选择集装箱运输,所以,集装箱运输已成为全球国际贸易中最重要的运输方式之一。然而集装箱海运业的繁荣对其自身的经营管理模式及网络结构提出了更高要求,高效、有序的港口集装箱运输网络有待完善与优化。由于地区间经济贸易的不平衡性以及船运公司集装箱管理水平存在差异,空箱调运在整个集装箱运输系统中占据了大量比重。研究如何减少集装箱空箱调运,对于促进集装箱运输快速发展、协调多式联运、提高企业经济效益具有重要意义。
由于空箱调运产生的成本对船公司的运营收益产生了很大影响,船公司对该问题非常重视,并引发了学术界的研究兴趣。集装箱调运问题主要研究的是何时从何地将多少数量的空箱通过何种运输方式调运到有需求的指定地点。空箱调运问题具有随时间推移供需地发生变化的动态性,箱种、节点、运输工具众多的复杂性,以及空箱需求与供给的随机性和运输能力及供应时间的限制性等多方面特性。由于空箱调运问题中过程参数、不确定因素众多使问题相当复杂。当前国内相关专家、学者对此问题进行了较多的研究,取得了相当的成果,并对实际运营过程做出有益的参考。其中,施欣对海上空箱调运的过程进行分析,并建立了系统优化模型[1];刘恒江等以航线经营人为主体,建立了空箱调运的Petri网模型[2];周红梅等借鉴了铁路空车调度优化模型,建立了海运空箱调运优化模型[3];Florez等建立利润优化模型来研究远洋航运企业空箱租赁和重新配置问题[4];Shen等构建了海运空箱调运决策支持系统[5]。
然而这些研究在建立模型时都进行了大量假设,考虑因素较少,与实际系统相差较远,大大降低了模型的实用性。本文拟在考虑多箱种的情况下,建立合理的空箱调运动态优化模型,并运用遗传算法进行优化求解,并用某港口实例数据对模型进行了验证,证明了模型的正确性和遗传算法的有效性。
1 空箱调运模型
本文将建立多箱种情况下的空箱调运模型,目标函数为在满足重箱运输的前提下,使空箱调运的总费用最少。总费用由以下几种费用组成:空箱的运输费用、在各节点的储存费用以及租箱费用。
1.1 模型假设
(1)每一期每个节点的空箱数量已知、每个节点的空箱需求量已知;(2)不考虑集装箱的维修、报废情况,即所有集装箱均是可用的;(3)不存在转运现象,空箱是直接由供应地向需求地的直达运输;(4)各航线的集装箱运输不允许不同箱型相互替换;(5)考虑两种箱型:20英尺和40英尺;(6)空箱调运决策期为1周(5天计算),决策间隔以天计算;(7)需求客户的需求必须得到满足,不存在弃货问题;(8)只有到时段末还未运送的集装箱发生堆存费用。
1.2 模型建立
根据以上假设及其空箱调运实际情况,可以建立如下空箱调运模型,相关参数和变量规定如下:
1.2.1 参数
T:为计划周期;Dt:t时段时所有需求点的集合;St:t时段是所有供给点的集合;dtik:t时段节点i缺k种箱型的数量;stjk:t时段节点j能供应k种箱型的数量;M:所有供给点和需求点的集合;K:各种箱型的集合,包括20英尺和40英尺两种;Ctijk:在时段t从i到j运输第k种箱型的单位运输费用;Xtijk:在时段t从i到j运输第k种箱型的箱量;Ytik:在时段t节点i的第k种箱型的存储量;UYit:节点i的存储能力限制;Ctik:在时段t节点的k种箱的单位存储费用;XLtijk:在时段t节点i和j之间由k种箱运输的调运量;τij:从节点i到j得运输时间;UTtij:运输能力限制;Rtmk:系统外调箱的单位费用;Ztmk:系统外调箱量;Ptmk:t时段m点本地产生的空箱。
1.2.2 目标函数
目标函数考虑各期在需求客户和供给客户之间的空箱调运费用最少。
1.2.3 约束条件
约束条件(2)表示客户的集装箱需求量必须满足。
约束条件(3)表示各时段末各节点处的空箱库存。
约束条件(4)表示各时段供应节点的供应量。
约束条件(5)表示在各个时段,节点之间的运输量不能超过该种运输方式的运输能力。
约束条件(6)表示各节点的存箱量不能超过该点的容量。
2 遗传算法原理
遗传算法(Genetic Algorithms,GA)是由美国Michigan大学的John H.Holland教授创建的,它模拟了自然选择和进化过程中的繁殖、杂交和突变现象。其基本思想为:按照“适者生存”和“优胜劣汰”的原理,从优化问题一个种群(即一组可行解)开始,逐代进化产生出越来越好的一个新的种群(一组的可行解)。在每一代,根据个体(可行解)适应度(目标函数值)的优劣挑选一分优良个体复制(繁殖)到下一代,被选择的个体经过交叉和变异算子的作用生成新的一代,新的个体由于继承了上一代的一些优良性状,因而在性能上优于上一代,这个过程将导致种群类似自然进化一样,子代种群比父代种群更加适于环境,也就是生成新的可行解优于旧的可行解,最后,将整个进化过程中最优个体作为问题的最终解。
由于遗传算法对适应度函数没有连续可微的要求,具有高效的全局优化能力,并且其操作对象是编码个体,可以处理诸如矩阵、树和图等结构形式的对象,因此在解决高维复杂优化问题上显示出很强的生命力,在实际中得到了广泛的应用。基于遗传算法的特点和空箱调运问题的特征,本文采用了遗传算法对该问题进行优化。
3 算法描述及其实例
3.1 算法设计
(1)编码方案:根据本文模型决策变量的特征,本文采用多维的实数编码形式。例如,用实数集合M=,1,2,…,n,表示港口集合,K=1,,2,表示箱型(20英尺和40英尺),则t时段的一个可行解表示为:
这个解直观的表达就是:港口1向港口2调运x1个集装箱(箱型是20英尺),港口5向港口3调运x2个集装箱(箱型是40英尺),……。
(2)选择:采用轮盘赌选择算子,这虽然增大了遗传算法的随机性,但保证群体的多样性,使算法不至于过早收敛。
(3)交叉:交叉运算是遗传算法区别于其他进化算法的重要特征,它在遗传算法中起关键作用。由于基本交叉算子单点交叉、多点交叉不能满足本文空箱调运问题的特殊性要求(它们都会产生大量不可行解),所以本文采用的交叉算子为循环交叉算子,该算子能修正交叉过程中生成的不可行解。
(4)变异:变异是指将个体编码串中的某些基因值用其它基因值来替换,从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法,它是必不可少的一个运算步骤。变异本身是一种全局随机搜索,与选择算子结合在一起,保证了遗传算法的有效性,使遗传算法具有全局的随机搜索能力,同时使得遗传算法保持种群的多样性,以防止出现非成熟收敛。本文在考虑编码设计及问题实际的情况下采用均匀变异算子对种群进行变异操作。
算法流程图如图1所示。
3.2 实例
本文考虑六个港口的空箱调运问题,算例中假设运输能力和堆存能力无限制,只考虑一种箱型(40英尺),在一个计划期内,航线挂靠顺序不变。这六个港口的运输网络模型如图2所示。港口运输时间、费用如表1所示。港口初始库存和各时段需求状况分别如表2、表3所示。
单位:天、$/TEU
单位:TEU
该算法利用matlab R2009程序实现,取最大迭代数G=500,本文针对不同种群规模进行了大量测试,结果表明当种群规模N=100左右时效率最高;对交叉概pc为0.7、0.8、0.9分别进行了10次试验发现交叉概率的变化对算法的效率影响并不是很大,所以取交叉概率pc=0.8。最后,我们进行了三组实验,分别取变异概率pm为0.001、0.01、0.1,由实验结果分析得出当变异概率时pm=0.01,效果最好。最终得出最优解,第一期调运结果:由港口B至A调运空箱80个,由E至C调运空箱163个,由F至E调运空箱10个,总费用为6 119美元,其中库存费用为2 158美元;第二期调运结果:由B至A调运空箱75个,由E至A调运空箱9个,由C至E调运空箱13个,总费用为5 051美元,其中库存费用为3 014美元;第三期调运结果:由B至A调运空箱119个,由E至C调运空箱110个,总费用为6 734美元,其中库存费用为3 065美元;第四期调运结果:由B至C调运空箱24个,由A至E调运空箱23个,由D至E调运空箱200个,总费用为8 738美元,其中库存费用为2 065美元;第五期调运结果:由B至A调运空箱76个,由E至C调运空箱125个,由D至E调运空箱46个,总费用为6 938美元,其中库存费用为3 075美元,租箱费用为315美元。这一周期的总费用为33 580美元。
4 结论
本文力求与实际情况接近,充分考虑了空箱调运问题中多箱型的现实情况,应用动态规划的思想,建立了多箱型的集装箱空箱调运优化模型。最后,本文运用遗传算法对所建立的模型在matlab平台下进行了编程仿真,为港口间空箱调运提供了具体的方案。本文模型的目的在于提高航运企业的空箱调运管理水平和调运效率,节省不必要的运输费用。
参考文献
[1]施欣.集装箱海运空箱调运优化分析[J].系统工程理论与实践,2003(23):70-75.
[2]刘恒江,施欣.基于Petri网的集装箱空箱调运方针分析[J].交通运输工程报,2002,2(3):97-102.
[3]周红梅,方芳.航运集装箱空箱调运优化模型的研究[J].武汉理工大学学报,2003,2(7):384-387.
[4]Florez.H.Empty container Repositioning and Leas2ing:An Optimization Model[R].Ph.D Dissertation,Polytechnic Institute of New York,New York,1986.
[5]W.S.Shen,C.M.Khoong.A DSS for empty container distribution planning[J].Decision Support Systems,1995(15):75-82.
[6]王斌.海运空箱调运模糊优化研究[J].港工技术,2007,8(4):11-13.
[7]王小平,曹立明.遗传算法—理论、应用与软件实现[M].西安:西安交通大学出版社,2002.
装箱算法 篇6
在集装箱的实际 装载过程 中 ,除了考虑 最大化空间利用率之 外 ,还要考虑 多种约束 因素 ,如:货物的摆放方向 、某些货物的 隔离性、货 物的承载 能力、货物 装载的稳定性 、装载的优 先级、集装 箱的承重 性等。目前,针对货物装载过 程中具有 优先装载 约束的研 究成果还比较少 ,主要有Ren[1]等人提出的基于树搜索的 方法,在该方法中 ,采用5个评价函 数选择简 单块。NingWang[2]等人提出的基于PartialBeamSearch的方法 ,该方法改进了BeamSearch算法,定义了更 加高效的 块选择函数和完整装载方案的评价函数 ,计算效果优于Ren等人提出的基于树搜索的方法。目前,满足C1和C2约束的集装箱装载 问题的最 好算法是I.Araya[3]等人提出的基于BeamSearch的算法 ,该算法的 最主要特 点是运用BeamSearch算法进行搜索时 ,通过去除 搜索过程中产生的相 似中间状 态来提高 搜索过程 的多样性 ,进而提高搜索效率。
本文针对具有优先装载约束的集装箱装载问题,改进了PartialBeamSearch算法,通过去除搜索过程中生成的相似中间状态来增加搜索过程的多样性,进而提高算法的搜索效率。
1改 进 的 具 有 优 先 装 载 约 束 的 PartialBeamSearch算法
根据WenbinZhu[4]等提出的集装箱装载算法分析框架,改进的具有优先装载约束的PartialBeamSearch算法可以从以下6个方面进行描述。
1.1空间表达方法
基于coverrepresentation方法而不是cutrepresentation方法进行装载空间表达,这是获得较高装载率的关键因素之一。
1.2货物块种类
分别基于简单块和复合块,各用总体计算时间的一半来计算装载方案。在计算过程中不仅使用简单块,同时也使用复合块,这是获得较高装载率的关键因素之一。
1.3选择装载空间
选择最佳装载空间遵循以下标准:1选择具有最小z轴坐标的可用空间;2如果满足上述标准的空间有多个,则选择具有最小CornerDistance的可用装载空间,见图1;3如果满足上述标准的空间有多个,则选择其中体积最大的空间;4如果满足上述标准的空间有多个,假设 (x1,y1,z1)和 (x2,y2,z2)分别为可用装载空间的corner中离坐标原点最近和最远的点的坐标,按照 (y1,z1,y2,z2,x1,x2)的次序依次选择具有最小值的空间。
1.4货物块选择策略
对状态S ,在选择可用空间s后,可根据货物块的适应值最多选择m个货物块。设h(b)和l(b)分别为货物块b中优先装载的 货物体积 和非优先 装载的货 物体积。货物块的适应值函数f(s,b,S)为:
其中waste是货物块b装载到空间s产生的浪费空间近似值,waste项前面的 负号表示 浪费空间 越大的货 物块,其适应值越小。l(S)是当前状态非优先装载货物的总体积,maxnh是装载方案中非优先装载货物和浪费空间的体积之和。货物块适应值函数的第一项倾向于装载优先货物,在适应值函数的第二项中,(1-l(S)/maxnh)是一个随非优先装载货物被装载到集装箱而不断减少的权重系数。
1.5货物块放置方式
当货物块b放入到可 用装载空 间后,放在AnchorCorner,也就是具有最小CornerDistance的可装载空间的底角。
1.6全局搜索算法
整体搜索过程采用基于DoubleSearchEffort机制的PartialBeamSearch算法。对一个给定的beamWidth值,当m设置为一个很小的值时,常常会得到一个很差的解,而如果m取值太大,计算过程耗时又太长。因此,采用多次运行PartialBeamSearch优化过程进行计算。计算开始时以很小的搜索代价r=m2进行计算,然后加倍r的值再次进行计算,连续进行此类过程直到计算时间结束,而beamWidth作为算法的一个参数通过实验来确定它的最佳值。
PartialBeamSearch算法如图2所示。每一次的搜索以stateList中包含一个代表空集装箱的状态开始。对每个stateList中的状态S ,如果它不是一个装载方案的最终状态,算法将产 生最多个后继状 态并加入 到canList中。在所有下一层的候选状态都生成之后,开始评价每一个候选状态。在第一轮搜索,初始化搜索代价r=8,这个值对应搜索宽度m =2。在一轮搜索完成后,开始把r值加倍,得到m值后开始下一轮搜索。在给定的计算时间内连续进行多轮搜索,然后返回,找到最好的装载方案。
集装箱装载的PartialBeamSearch算法的伪代码如下:
评价在状态S下生成的m个后继节点,采用一种深度受限制的树搜索算法,如图3所示。root节点对应要装载的一个货物块,对每个root节点的后继 节点状态 的评价,采用连续装载适应值最好的货物块策略,直到完成所有装载过程。在得到所有的完整装载方案后,装载方案的评价函数由装载方案中优先装载货物的体积和装载方案总体积组成数据对,然后对所有装载方案所对应的数据对值进行降序排序,排序越靠前,函数值就越高。为了避免搜索过程收敛到相似的状态,提高搜索过程的多样性,在搜索过程生成新状态的集合S中去除相似的状态。规定如果搜索过程中的两个中间状态通过贪婪过程得到的装载方案包括完全相同的货物,则认为状态S1和S2是相似的,如果出现这种情况,那么在新的状态集合S中只保留那个货物体积最小的中间状态。
2计算结果
表1是在BR数据集合上的改进算法与原有算法计算结果的对比情况,PartialBeamSearch算法用BSSOLVER标识,本文算法用BSSOLVER’标识。每个数据组包含100个实例,装载率的 值是100个实例装 载率的平 均值。在Intel酷睿2双核T7200,2G内存计算机上,每个实例运行和BSSOLVER算法相同的时间400s。从表1可以看出,BSSOLVER’算法在计 算机性能 较低的情 况下,计算结果优 于BSSOLVER算法,平均装载 率提高了0.27%。
3结语
本文针对具有优先装载约束的集装箱装载问题,在集装箱装载的PartialBeamSearch算法基础上进行了改进,通过去除搜索过程中生成的相似中间状态来增加搜索过程的多样性,有效提高了算法的搜索效率。今后的研究方向是提高搜索过程的多样性。
参考文献
[1]REN J,TIAN Y,SAWARAGI T.A tree search method for the container loading problem with shipment priority[J].European Journal of Operational Research,2011:526-535.
[2]WANG N,LIM A,ZHU W.A multi-round partial beam search approach for the single container loading problem with shipment priority[J].International Journal of Production Economics,2013,145(2):531-540.
[3]I ARAYA,M C RIFF.A beam search approach to the container loading problem[J].Computers&Operations Research,2014(43):100-107.
装箱算法 篇7
粒子群优化 (particle swarm optimization, PSO) 算法是Kennedy和Eberhart受人工生命研究结果的启发并通过模拟鸟群觅食过程中的迁徙和群聚行为而提出的一种基于群体智能的全局随机搜索算法[7]。作为一个有效的优化算法, PSO算法被广泛应用于函数优化、模式分类、模糊系统控制、神经网络训练以及其他工程领域中[8]。由于PSO算法程序实现简单, 需要调整的参数很少, 因此近年来出现了研究热潮, 并提出了很多改进的算法[9—12]。
标准PSO算法在进化后期由于粒子多样性的缺失而易于陷入局部最优, 发生早熟收敛问题。在文献[12]提出的简化粒子群算法 (simplified PSO, SPSO) 基础上, 融入蛙跳算法 (shuffled frog leaping algorithm, SFLA) 的分组思想, 可以有效避免算法早熟收敛现象的发生, 提高算法PSO的收敛速度和收敛精度。论文最后将这种改进的PSO算法用于集装箱装箱问题, 与现有文献相比, 可以得到更高的装箱率。
1 问题描述
集装箱装载问题是指将一批小的物体按照一定的顺序和方式装入集装箱中, 目标是使集装箱的空间利用率和 (或) 载重利用率最高。集装箱装载问题可从集装箱和货物两方面考虑, 即单集装箱贯序装配和多集装箱并行装配、同种货物装配和不同货物装配, 这两种方法相互组合, 对应单集装箱贯序装配、多集装箱并行装配、同种货物装配、不同货物装配四种装配情形。对于集装箱装载问题, 国内外已经开展了相应的研究, 现选取三空间分割法结合PSO算法实现装箱。这种方法规则简单, 且能够保证货物有足够的稳定性, 对于实际装箱具有现实性的指导意义。下面是对三空间分割法进行简单介绍。
假设待装载的货物均为长方体, 货物在装入集装箱时要求各边分别与集装箱各边平行, 不能斜放。集装箱的后左下处于空间坐标系的零点位置, L、W、H分别表示集装箱的长、宽、高尺寸, 如图1所示。装载开始前, 先按一定的规则整理好待装入的货物, 包括货物装载顺序、是否有旋转、如何旋转等。装载开始时, 首先将整个集装箱作为当前的装载空间, 第一个货物放在集装箱的后左下角的位置上。这样集装箱就被分割成三个空间:前空间 (front space) 、右空间 (right space) 和上空间 (top space) 。空间的分割方式如图1所示, 之所以这样分割, 一方面是为了使剩余的空间尽可能的大块存在, 有利于提高装箱利用率, 另一方面是为了保证小的货物在大的货物上面, 提高货物的稳定性。在第二个货物放入时就依次以这三个空间为当前装载空间, 被放入的那个空间又被分割成前、右、上三个空间。随着货物的依次装入, 不断重复上述分解过程, 直到货物全部装完或集装箱没有可以利用的空间为止。在集装箱中装载货物遵循以下规则: (1) 对当前空间按照体积由小到大的顺序进行排序, 每个货物选择能放下且体积最小的空间, 放在该空间的后左下角; (2) 每放入一个货物后, 删除体积为零的空间和不能放下剩下任一货物的空间。
2 算法描述
PSO算法是一种基于种群的智能优化算法。假设在D维的搜索空间中, 粒子群的规模是N, xi= (xi1, xi2, …, xi D) 是第i个粒子的位置, vi= (vi1, vi2, …, vi D) 是其对应的飞行速度, 则PSO算法的迭代公式如下:
式中, c1和c2被称为学习因子, pbest和gbest表示粒子自身历史最优位置和粒子群最优位置, r1和r2为介于 (0, 1) 之间的随机数。
胡旺等人仔细分析了PSO算法的式 (1) 和式 (2) , 发现速度项并不是必须的, 它的存在有可能使得粒子偏离正确的进化方向, 为此给出简化粒子群算法:
式 (3) 中, ω表示收缩因子。文献[12]从理论和实验上证明了这种简化粒子群算法的高效性。
蛙跳算法是模拟一群青蛙在一片湿地中跳动觅食行为而提出的一种优化计算方法[13]。假设一群青蛙生活在一片湿地里, 每个青蛙代表问题的一个解, 青蛙通过在不同的石头间跳跃寻找食物。这群青蛙又被分为可以进行充分交流的若干个子群, 即算法进化到一段时间后, 各子群间进行信息交流。这样, 每个青蛙同时利用子群和种群的信息来寻找食物。
由于SPSO算法只用到位置信息, 而SFLA算法也只需要位置项, 这样可以将SFLA算法的分组思想引入到SPSO中, 可以确保各个小组内粒子间的差异性, 有利于粒子位置的更新。混合蛙跳粒子群 (hybrid frog leaping particle swarm optimization, HFLPSO) 算法更新公式如下
式 (4) 中, 右边的第1项为“历史”部分, 第2项为“认知”部分, 第3项为“社会”部分, 第4项为“超社会”部分。“历史”部分表示过去对现在的影响, “认知”部分表示粒子对自身的思考, “社会”部分表示粒子与组内最优粒子的比较和模仿, “超社会”部分表示粒子与总的粒子群体最优值的比较和模仿。这样, 粒子可以获得更丰富的信息, 且局部信息和全局信息能够得到更加充分的利用, 粒子间的信息共享和合作也变得更加充分, 借此来更新粒子自身的位置。
3 数值试验
对于集装箱装箱问题, 物体和集装箱的形状会有多样, 本节数值试验研究的是三维空间中长方体的物体装入到长方体的集装箱中的情形, 即在三维欧氏空间中, 给定一个长方体容器和有限个待放长方体, 要求将这些长方体尽可能多地装入容器中, 使得容器剩余的空闲空间最小, 即容器的空间利用率最大。长方体在放入时要求满足以下三个条件:①完全在容器内, 不与容器的壁相嵌;②不与任一已放入的长方体相嵌;③长方体的棱与容器的某条棱平行, 即垂直放入长方体。
采用HFLPSO算法解决集装箱装载问题, 步骤如下:
Step 1随机生成m×n个箱子种类装箱序列;
Step 2利用三空间分割法计算每个种类装箱序列对应的集装箱空间利用率, 然后按照空间利用率由大到小的顺序进行排序, 选出种群内最优种类装箱序列g'best;
Step 3按照混合蛙跳算法的分组方式将种类装箱序列分为m组, 每组n个种类装箱序列。则第i组种类装箱序列为{xi, xm+i, x2m+i, …, x (j-1) m+i}, i∈[1, m], j∈[1, n];
Step 4将每个种类装箱序列对应的利用率与其自身历史最优种类装箱序列对应的空间利用率作比较, 如更高, 则更新自身历史最优种类装箱序列pbest, 否则, 保持pbest不变;
Step 5选出组内最优种类装箱序列gbest, 第i组种类装箱序列中的最优种类装箱序列为xi;
Step 6更新每个种类装箱序列, 在各小组内按照空间利用率由大到小的顺序对种类装箱序列进行排序, 然后进入下一次迭代, 转到Step 5;
Step 7达到组内迭代次数后, 得到了一组新的种类装箱序列, 再重新分组, 转到Step 2;
Step 8达到分组次数后, 存盘退出。
文献[14]给出15个LN算例, 本节应用HFLP-SO算法计算了其中6个, 这6个LN算例具体数据见文献[15], 计算结果见表1和图2。试验过程中取ω=1, c1=c3=2, c2=0.8;粒子群分为5组, 每组10个粒子;为了计算快速, 组内迭代次数取1, 分组次数为30;程序独立运行20次, 取最高利用率对应的解得到图2。
对于给定的集装箱R和箱子C={c1, c2, …, cn}, 集装箱R的长、宽、高分别为L、W、H, 第ci种箱子对应的长、宽、高、数量分别为li、wi、hi、ni, 则每个ci种箱子的体积为vi=li×wi×hi。由于箱子体积之和与集装箱的体积大小关系会随着问题的变化而变化, 集装箱不一定装入所有箱子, 同种箱子也不一定能全部装入集装箱中, 因此引入参数Lmax和ni_max。Lmax表示装箱结束后, 箱子在集装箱长度方向 (X方向) 占用的最远距离, 此时占用集装箱的体积为Vo=Lmax×W×H。如不作此处理, 当所有的箱子都能装入集装箱时, 集装箱的利用率将不会随着装载顺序的不同而发生改变, 永远保持固定值不变, 算法无法寻优。ni_max表示装入集装箱中第ci种箱子的最大个数, 显然有ni_max∈ (0, ni) 。有了上述定义后, 集装箱装载问题的适应度函数表示为
式 (5) 中, 或xi=0。在求解Vs时, 集装箱R要装下所有xi=1的箱子ci。
由表1可知, 本文算法在六组测试数据中均达到了86%以上的容积利用率, 其中组别LN01、LN02、LN06、LN07相对于文献[15]来说容积利用率均得到了提高, 尤其是LN06提高了5.05%, LN08和LN09原文献没有给出相应的容积利用率, 相应的装箱图见图2所示。从图2可以得到, 小箱子都是放在大箱子的上面, 满足了稳定性的要求;箱子按照由下到上、由左到右、由后到前的规则进行装载, 这样就保证了箱子摆放比较紧凑, 剩余空间比较集中, 有利于后续箱子的装入。
由于在实际的装箱过程中, 既要给出装入集装箱中货物的种类、数量, 更重要的是要给出一个清晰的三维装箱图, 才能给人工装箱时一个直接的参考。为此, 作者在Windows XP环境下利用matlab7.10.0 (R2010a) 中的用户图形界面 (GUI) 设计了一个集装箱装载软件。该软件可实现原始数据的输入, 在计算前可对算法参数进行调整。通过计算后能得到装箱图和装载结果表, 装箱图可三维观察, 装载结果表中给出了每个货物的具体位置。该软件用于解决大量货物在单一集装箱中的装载问题, 软件的输入界面和输出界面如图3所示。
4 结论