总第２６６期 ２０１１年第ｌ２期 计算机与数字工程 Ｃｏｍｐｕｔｅｒ＆Ｄｉｇｉｔａｌ Ｅｎｇｉｎｅｅｒｉｎｇ Ｖｏ１．３９ Ｎｏ．１２ １７ 求解多车辆装载问题的启发式改进蚁群算法设计 陈洁廖伟 ８３００４２） （军区司令部电教站乌鲁木齐摘要针对启发式优化算法不能较理想地对多车辆大规模装载问题进行优化的局限性，文章设计了一种启发式改 进蚁群算法，该算法将单车辆的启发式装载与多车辆装载时的蚁群优化算法有机结合，较好地解决了多车辆大规模装载问 题。经过实例验证，该算法具有较高的计算效率和较好的收敛特性。 关键词多车辆装载问题；启发式；改进蚁群算法 中图分类号ＴＰ３０１．６ Ｄｅｓｉｇｎ ｏｆ Ｈｅｕｒｉｓｔｉｃ Ｉｍｐｒｏｖｅｄ Ａｎｔ Ｃｏｌｏｎｙ Ａｌｇｏｒｉｔｈｍ ｉｎ Ｓｏｌｖｉｎｇ Ｍｕｌｔｉ－ｖｅｈｉｃｌｅ Ｌｏａｄｉｎｇ Ｐｒｏｂｌｅｍ Ｃｈｅｎ Ｊｉｅ Ｌｉａｏ Ｗｅｉ （Ｅｌｅｃｔｒｏｎｉｃ Ｔｅａｃｈｉｎｇ Ｓｔａｔｉｏｎｓ ｏｆ ＸｉＮｉａｎｇ Ｍｉｌｉｔａｒｙ Ｃｏｍｍａｎｄ，Ｕｒｕｍｑｉ ８３００４２） Ａｂｓｔｒａｃｔ Ｃｏｎｓｉｄｅｒｉｎｇ ｔｈｅ ｌｉｍｉｔａｔｉｏｎ ｏｆ Ｈｅｕｒｉｓｔｉｃ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｉｎ ｓｏｌｖｉｎｇ Ｌａｒｇｅ－ｓｃａｌｅ ｍｕｌｔｉ－ｖｅｈｉｃｌｅ ｌｏａｄｉｎｇ ｐｒｏｂｌｅｍ，ｄｅｓｉｇｎｅｄ ａ ｈｅｕｒｉｓｔｉｃ ｉｍｐｒｏｖｅｄ ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ，ｔｈｉｓ ａｌｇｏｒｉｔｈｍ ｈａｖｅ Ｃｏｍｂｉｎｅｄ Ｈｅｕｒｉｓｔｉｃ １ｏａｄｉｎｇ ｍｅｔｈｏｄ ｏｆ ｓｉｎ— ｇｌｅ ｖｅｈｉｃｌｅ ｗｉｔｈ ＡＣＯ ｉｎ ｍｕｌｔｉ－ｖｅｈｉｃｌｅ ｌｏａｄｉｎｇ ｐｒｏｂｌｅｍ．Ｖｅｒｉｆｉｅｄ ｔｈｒｏｕｇｈ ｅｘａｍｐｌｅ，ｔｈｅ ａｌｇｏｒｉｔｈｍ ｈａｓ ｈｉｇｈ ｃｏｍｐｕｔａｔｉｏｎａｌ ｅｆｆｉ— ｃｉｅｎｃｙ ａｎｄ ｇｏｏｄ ｃｏｎｖｅｒｇｅｎｃｅ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ． Ｋｅｙ Ｗｏｒｄｓ ｍｕｌｔｉ—ｖｅｈｉｃｌｅ ｌｏａｄｉｎｇ ｐｒｏｂｌｅｍ，ｈｅｕｒｉｓｔｉｃ，ｉｍｐｒｏｖｅｄ ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ Ｃｌａｓｓ Ｎｕｍｂｅｒ ＴＰ３０】．６ １ 引言 ２问题描述 装载问题就是研究如何在有限的立体空间 问题描述：从某一供应点向一需求点运输多种 内把不同种类、大小、形状和性质的物资进行合 物资，使用的运载工具为某型载重车，其车厢的长 理地配置，以使车辆装备的额定载重量得到充分 度、宽度和装载限高为已知。要求在满足约束条件 利用，以期获得最大的空间利用率，降低运输成 的情况下，将一批货物经过箱体的处理按照适当的 本，增加运输效率和效益［１］。装载问题是一个具 装载方法装入车厢中，使得车厢的容积利用率或装 有复杂约束的组合优化问题，其求解极为困 载质量利用率最大，以便减少运输车辆，提高运输 难［２］。以往采用一些启发式算法来求解［引，但启 效益，从而降低单位运输成本。记符号ｚ ，Ｗ ，ｈ ，ｇ 发式优化算法随着问题规模的增大会产生时间 分别表示货箱 （ —ｌ，２，…， ）的长、宽、高、质量； 维数灾难问题，同时不能较理想地对多车辆装载 表示货箱的装载与否， ，Ｇ分别表示车厢的最大装 问题进行优化，带有一定局限性，本文设计了一 载容积、最大装载质量。（ ，Ｙ ， ）表示货箱的重 种启发式改进蚁群算法用于求解多车辆大规模 心坐标；（ｚ，Ｙ， ）表示装载后车厢的重心坐标，要求 的装载问题。 ｚ∈Ｅａ，，ｂｌｊ，ｙｆｆ ａ２，ｂ２ ， ∈［０，ｂ３］。 ＊收稿日期：２０１１年６月８日，修回日期：２０１１年７月１９日 作者简介：陈洁，女，工程师，研究方向：信息化教学。廖伟，男，硕士研究生，助理工程师，研究方向：指挥自动化与战 场数字化。 １８ 陈洁等：求解多车辆装载问题的启发式改进蚁群算法设计 第３９卷 目标函数： ｎ 选择填充货箱体积最大的填充。重复以上操作直 至不满足其他的限定条件。该算法在装载货箱时， Ｉｒｌａｘｚ￣－Ａ∑（ｚ Ｗ ＾ ）／ ＋（１一 ）∑（ｇ ）／Ｇ ｉ＝１ ｉ一１ 当装载的首货箱确定后，其余货箱的装载顺序及方 法也可以唯一确定，因此该算法可以生成唯一的货 箱装载顺序。 （１） ＡＥ Ｅｏ，１］，当目标为容积利用率最大时， ＝１， 当目标为装载质量利用率最大时Ａ：０。 ３．２ 多车辆装载的启发式改进蚁群算法设计 １）单车辆装载方案的评价函数 单车辆装载方案的评价函数为： Ｆ（）一是１ （）＋ｋ２Ｍ（）＋尼３Ｓ（） （２） ３ 多车辆装载的启发式改进蚁群求 解算法设计 ３．１ 单车辆装载的启发式算法说明 空间分割和车厢填充策略说明：当一个货物置 入一个车厢后，该车厢的空间被分割成三个空间 （除货箱外），分别为 边空间、前空间和上 空问，分割如图１所 示。同理当每个子空 式中：ｋ 、ｋ 和ｋ。为均大于０的常数，依据评价的 具体需要设置。 （）表示空间利用率函数，Ｍ（）表 示质量考察函数，Ｓ（）表示重心考察函数，下面分别 对这几个函数进行说明。 （１）空间利用率函数： 一『（ ）］×１０ｏ ｌ— 。＿ ｝（３） 间被新置入的货箱填 充后，同样被分割为 图１三维空间分割示意图 三个空间。 式中： 为第ｉ个填充货箱的体积； 为车厢的容 积；ｎ为填充的货箱数。 货箱在填充剩余空间时，对于所有的剩余的空 间，首先选定其中一个空间，找到未填充满足条件 （２）质量考察函数： （依据货箱的方向约束，货箱可填充人剩余空间）， 且使得剩余空问利用率最高的货箱，并记录这个货 Ｍ（）一 ｌ Ｍ ｊ 『ｆ １× 。。， Ｍ ｚ— ，（４） ｌ【 ０箱和空间利用率，对每个剩余空间进行以上操作并 ∑Ｍ＞ 记录每个剩余空间对应的货箱和空间利用率，选择 式中：Ｍ 为第ｉ个填充货箱的质量；Ｍ 为车厢最 所有空间利用率最高的货箱和剩余空间进行填充 大承载质量，超过最大承载质量，惩罚Ｍ（）为Ｏ。 操作。当有两个或两个以上的空间利用率最高时， （３）重心考察函数： ｆ 一ｆ （ｇｉ￣Ｘｉ ）／ 一 ｌ，ｎ （ｇｉｓｃｉ ／妻 ６ …一 Ｉ Ｉ江１ ｉ：ｌ Ｉ ｉ：ｌ （５） ｌ ｏ，∑（ ）／∑ ＞６， １或∑（ｇｉｘｉ９：）／∑ ＜以， ｆｂ下ｚ Ｊｒ－ａｚ—ｌ奎（ｇｉＹｉ￣ ）／ ｇ 一堕 ｌ，以 奎（ｇｉｙｉ￣ ）／妻ｇ ６ ，、 Ｊ ｌ ｌ ｉ＝１ ｌ１ ｉ：１ ｕ一１ ， ， （６） Ｉ ｏ，∑（ｇ ）／∑ｇ ＞ｂ２或∑（ｇ ）／∑ｇ ＜以。 Ｓ 』（ （ ）／ ）， （ ）／ （）一 ６ｓ （７） Ｊ０，∑（ ）／∑ｇ ＞ｂ。 Ｓ（）一 （）＋Ｓｙ（）＋Ｓ （８） ２）多车辆装载的启发式改进蚁群算法求解说明 现在以３辆车装载８个货箱的简单情形来解 释一下如何应用启发式蚁群算法解决车辆装载问 式中： （）、ｓ （）、Ｓ 分别为Ｘ，ｙ，ｚ三个坐标的重 心考察函数。 ２０１１年第１２期 １ ２ 计算机与数字工程 题。假设有３辆车，８个货 箱，如图２显示。ｎｏｄｅ（ｉ， ） 为了解决蚂蚁求得局部最优解而不是全局 最优解的问题，在概率计算公式加人扰动项变为 ３ 表示使用第ｉ个货箱填充第 Ｊ辆车的车厢，货箱内的数 筋（￡） ＝＝＝（１＋ｇ） （ ），ｇ为随机数产生的扰动 项ｇ一 ×ｒａｎｄ，叫＝＝＝Ｗｏ× ＿。，如果训＜Ｗ１，则 货４ 箱５回 回 回 字表示货箱被装入车辆的 令叫一０。其中：Ｓ为迭代次数；ｙ为指数退火因 ６口 口 回 编号，内有圆形的货箱表示 子；ｒａｎｄ为（０，１）间均匀分布的随机数；Ｗ。为扰 ７口 回 回 由蚂蚁选择的填充指定车 动初始值；Ｗ 为预先设定的较小扰动水平。当 ８口 回 回 厢的首货箱，内有方形的货 ｗ＜ｗ 时，认为已经不能改变概率极大点Ｅ９￣１０］。 ３）启发式改进蚁群算法的执行过程 图２车辆装载模型 箱表示由启发式算法选择 的填充货箱。设计虚拟的人工蚁具有以下特征的 个体： （１）通过计算每个节点转移概率大小选择下一 步转移节点，转移概率由节点上的信息激素值ｒ和 启发式算子叩 计算得出； （２）建立禁忌表ｔａｂｕ，保证每个货厢只被装载 一次； （３）在其所选择代表填充首货箱的节点上施放 信息激素ｒ。 设ｔ时刻节点ｎｏｄｅ（ ， ）上信息激素为 （￡）， 在该节点停留蚂蚁所施放的信息激素之和为△ （ ），则在下一时刻（ ＋１），节点上的信息激素更新 为 （ ＋１）一ＩＤ・ （ ）＋Ａｒｉ￣ （９） ｌＤ为信息素残留系数（０ ｌ０≤１）。 Ａｒ ∑△砖 （１０） 一１ △南为第ｋ只蚂蚁在节点ｎｏｄｅ（ ， ）上放置的 信息激素，△ 与该节点作为填充首货箱采用启发 式算法生成的单车厢装载方案的评价函数Ｆ（）成 正比。 为了加快蚂蚁搜索速度，设置每个节点的被选 择的期望程度为： 珈一 （１１） ∑Ｆ（ｚ一１ ） 由上设定条件可以给出第ｋ只蚂蚁选择节点 的概率计算公式： 舢）一一 Ｊ【 生 ０ ．［ …一 ～ （１２） 这里ａｌｌｏｗｅｄ 一｛Ｎ—ｔａｂｕ ），ａ和 分别是控 制信息素和启发式信息素在概率中权重的参 数Ｅ 川］，ｔａｂｕ 表示第 只蚂蚁按约束不能再使用 的填充箱。 算法的执行过程可以描述如下： Ｓｔｅｐｌ：初始化。∞ 一Ｏ（ｃｏｕｎｔ为循环次数）， Ｚ＇／ｊ（０）一ｃ，Ｃ为一较小常数，Ａｎｉ（Ｏ）一０，为每只蚂蚁 走随机设置一个初始节点，以此节点作为首货箱采 用启发式算法生成第一辆车的装载方案，并建立禁 忌列表ｔａｂｕ 。 Ｓｔｅｐ２：将ｍ个蚂蚁置于各自的初始领域，每个 蚂蚁按概率 选择节点作为车辆启发式算法装载 的首货箱，并将已装载货箱代表的节点加入禁忌列 表ｔａｂｕ ，判断所有蚂蚁是否完成搜索，否则继续 Ｓｔｅｐ２； Ｓｔｅｐ３：计算各个蚂蚁目标函数值，记录当前最 好解，更新 （ ＋１）； Ｓｔｅｐ４：∞ ＝＝：ｃｏｕｎｔ４－１，若ｃｏｕｎｔ小于设置的 迭代次数则转至Ｓｔｅｐ２； Ｓｔｅｐ５：输出目前的最优解。 ４效性验证 运载工具为两辆ＣＡｌ５载重车（厢式），其 装载空间尺寸为：长５．７ｍ，宽４．３ｍ，高２．２ｍ，载重 量为１２吨，任务中５６０个弹药箱的详细数据如表。 采用本论文描述的算法进行计算，如图得到的最优 结果为共装人弹药箱３３２箱。 图３三维装箱问题的启发式改进蚁群算法求解 （下转第５０页） ５０ 李云超：联机手写女书采集与教学演示系统的设计与实现 第３９卷 ３．６女书文字模仿书写 模仿书写时，持手写笔在“输入区”内，模仿笔 划动静态演示结果进行书写，书写完成后可选择 参考文献 Ｅｌｉ朱宗晓，王江晴，等．女书信息化工程［ｃ］／／中国“女书 习俗”抢救保护研讨会暨“女书文化记录工程”项目结 题论文集，２０１０：１１９￣１２１ “擦除”、“翻页”、“保存”等功能，其操作与“样本采 集”时一致。 ３．７模仿书写校验，获取模仿书写正确率评估等 信息 ［２］李庆福．女书文化研究Ｉ－Ｍ］．北京：人民出版社，２００７：１６ ～１７ 书写完成后，可选择“校验”功能，获取模仿书 ［３］陈依国．ＶＢ下基于Ｗｉｎｔａｂ标准的数字化仪接口程序 编制［Ｊ］．信息技术，２００８ ［４］柳洪轶．联机手写藏文识别特征提取方法的研究［Ｄ］． 西北民族大学硕士论文，２００６：１９￣２２ 写正确率评估等信息。具体步骤如下： 对模仿书写结果进行预处理、笔划分离、笔划 特征点提取、文字特征码获取，将获取到的特征码 与字库中该文字的标准特征码进行匹配¨ｇ］，获取两 特征码的最长公共子序列，模仿书写正确率一 １００ ＊（最长公共子序列长度）／（文字特征码与标 准特征码平均长度）。 字符ｅ２５ｂ的模仿书写校验结果如图７所示。 ［５］马文婷．江永女书文字的性质研究［Ｄ］．湖南师范大学 硕士论文，２００９：５～２２ ［６］陈万军．联机手写藏文识别的研究［Ｄ］．西北民族大学 硕士论文，２００５：１４～１６，９～１Ｏ ［７］王江晴，万晨．周边方向贡献度在脱机手写女书特征提 取中的应用Ｉ－Ｊ］．中南民族大学学报（自然科学版）， ２０１０，２９（３）：６５～６７ ４ 结语 本文从理论和实践两个方面对联机手写女书 ［８］黄绍媛．联机汉字手写识别［Ｄ一．武汉：中南民族大学本 科论文，２００８：１３～１７ ｒ９］Ｄｅｅｐｕ Ｖ，Ｍａｄｈｖａｎａｔｈ Ｓ，Ｒａｍａｋｒｉｓｈｎａｎ Ａ Ｇ．Ｐｒｉｎｃｉ— ｐａｌ Ｃｏｍｐｏｎｅｎｔ Ａｎａｌｙｓｉｓ ｆｏｒ Ｏｎｌｉｎｅ Ｈａｎｄｗｒｉｔｔｅｎ Ｃｈａｒ— 采集与教学演示系统的设计和实现做了详细的探 讨和研究，针对样本采集、教学演示、模式识别工作 的需求，完成了系统的设计和功能的实现。经多次 测试，系统样本采集结果正确无误，教学演示效果 ａｃｔｅｒ Ｒｅｃｏｇｎｉｔｉｏｎ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １ ７ｔｈ Ｉｎｔｅｒｎａ— ｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ，２００４，２：３２７ ，～３３０ 较好，为女书的识别以及女书的传承和保护ｌ＿】。＿打 好了坚实基础。 ；． ；． 矫 矫 ：乖 带 茚 铞 ．． 尔 不 ． 秘 乖 不 不 ［１ｏ］田微，王江晴，朱宗晓，等．女书计算机键盘布局与输 入法的研究口］．中文信息学报，２０１０，２４（５）：１２４￣１２６ 乖 希 乖 乔 Ｊ，乖 希 希 （上接第１９页） 表１待装弹药箱情况一览表 弹药名称 弹药长 宽 高 数量重量 （ｎ１ｍ）（ｒａｍ）（ｒａｍ）（箱）（ｋｇ） 步机弹 ９０５ １０００ ７００ 加农炮弹 ９０７ １９００ ５００ 高炮弹 ９０９ ２０００ ８００ ５００ １７４ ［５］阎威武，邵惠鹤，田雅杰．集装箱装载的一种启发式算 法［Ｊ］．信息与控制，２００２，３１（８）：３５３￣３５６ ［６］Ｃｏｌｏｒｎｉ Ａ，Ｄｏｒｉｇｏ Ｍ，Ｍａｎｉｅｚｚｏ Ｖ，ｅｔ ａ１．Ｄｉｓｔｒｉｂｕｔｅｄ ２００ ９００ ２４０ ５２ ４０ ８７ ４５ １９００ ４０ ４００ ｏｐｔｉｍｉｚａｔｉｏｎ ｂｙ ａｎｔ ｃｏｌｏｎｉｅｓ［ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １ ｓｔ Ｅｕｒｏｐｅａｎ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｒｔｉｆｉｃｉａｌ Ｌｉｆｅ，１９９１：１３４～１４２ 木箱手榴弹９１２ ８００ ２４０ ３６ ［７］Ｄｏｒｉｇｏ Ｍ．Ｏｐｔｉｍｉｚａｔｉｏｎ，ｌｅａｒｎｉｎｇ ａｎｄ ｎａｔｕｒａｌ ａｌｇｏ— 参考文献 Ｅｌｉ胡瑞，丁香乾，张峰，等．基于混合遗传算法的多约束集 ｒｉｔｈｍｓ．Ｐｈ．Ｄ．Ｔｈｅｓｉｓ，Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｅｌｅｃｔｒｏｎｉｃｓ， Ｐｏｌｉｔｅｃｎｉｃｏ ｄｉＭｉｌａｎｏ，Ｉｔａｌｙ，１９９２ 装箱装载问题研究［Ｊ］．电子技术应用，２００６，１１６（２）：２４ ～［８］Ｄｏｒｉｇｏ Ｍ，Ｍａｎｉｅｚｚｏ Ｖ，Ｃｏｌｉｒｎｉ Ａ．Ａｎｔ ｓｙｓｔｅｍ：ｏｐｔｉｍｉ— ｚａｔｉｏｎ ｂｙ ａ ｃｏｌｏｎｙ ｏｆ ｃｏｏｐｅｒａｔｉｎｇ ａｇｅｎｔｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎ ｏｎ ｓｙｓｔｅｍ，Ｍａｎ，ａｎｄ Ｃｙｂｅｒｎｅｔｉｃｓ—Ｐａｒｔ Ｂ， ２６ ［２］卜雷，袁新江，薄云，等．基于遗传算法的集装箱单箱三 维装载优化问题［Ｊ］．中国铁道科学，２００４，９９（４）：１Ｏ８～ １１１ １９９６，２６（１）：２９～４１ ［９］段海滨，马冠军，王道波，等．一种求解连续空间优化问 题的改进蚁群算法［Ｊ］．系统仿真学报，２００７，１９（５）：９７４ ，～［３］张启义．军事物流运输成本模型研究及应用［Ｄ］．南京： 理工大学，２００８ ９７７ ［４］杭文，李旭宏，何杰．基于车辆轴型分类的公路货运车 ［１Ｏ］张宗永，孙静，谭家华．蚁群算法的改进及其应用［Ｊ］． 上海交通大学学报，２００２，３６（１１）：１５６４￣１５６８ 辆运营成本研究ＥＪ］．公路交通科技，２００５，２２（９）：１７Ｏ～
