第 ２８ 卷第 ７ 期 ２０１１ 年 ７ 月　 计 算 机 应 用 研 究 Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ 一 种 求 解 航 空 货 代 拼 箱 问 题 的 启 发 式 算 法 桂云苗， 龚本刚， 程幼明 （安徽工程大学 管理工程学院， 安徽 芜湖 ２４１０００） Ｖｏｌ．２８ Ｎｏ．７ Ｊｕｌ．２０１１ 倡 摘　要： 为了有效求解大规模的航空货代拼箱决策问题，在拼箱问题的混合整数规划模型基础上，将模型转换 为集合覆盖问题，利用常用的拉格朗日松弛方法，提出了一个拼箱问题的启发式求解方法，并给出了修正不可行 解的方法和拼箱组合空间调整方法。 数值分析结果表明，该启发式算法是有效可行的，而且运算效率比较高，与 最优解间误差比较小。 关键词： 交通管理； 拼箱； 航空货代； 集合覆盖； 启发式算法 中图分类号： ＴＰ３０１畅６　　　文献标志码： Ａ　　　文章编号： １００１唱３６９５（２０１１）０７唱２４４６唱０３ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１唱３６９５．２０１１．０７．０１１ Ｈｅｕｒｉｓｔｉｃ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｃｏｎｓｏｌｉｄａｔｉｏｎ ｐｒｏｂｌｅｍ ｏｆ ａｉｒ ｃａｒｇｏ ｆｏｒｗａｒｄｅｒｓ ＧＵＩ Ｙｕｎ唱ｍｉａｏ， ＧＯＮＧ Ｂｅｎ唱ｇａｎｇ， ＣＨＥＮＧ Ｙｏｕ唱ｍｉｎｇ （College of Management Engineering， Anhui Polytechnic University， Wuhu Anhui ２４１０００， China） Abstract： Ｉｎ ｏｒｄｅｒ ｔｏ ｓｏｌｖｅ ｒｅａｌｉｓｔｉｃａｌｌｙ ｌａｒｇｅ唱ｓｃａｌｅ ｃａｒｇｏ ｃｏｎｓｏｌｉｄａｔｉｏｎ ｐｒｏｂｌｅｍｓ，ｔｈｉｓ ｐａｐｅｒ ｔｒａｎｓｆｏｒｍｅｄ ｔｈｅ ａｉｒ ｃａｒｇｏ ｆｏｒｗａｒｄ唱 ｅｒｓ ｃｏｎｓｏｌｉｄａｔｉｏｎ ｐｒｏｂｌｅｍ ｔｏ ｗｅｌｌ唱ｋｎｏｗｎ ｓｅｔ ｃｏｖｅｒｉｎｇ ｐｒｏｂｌｅｍ ｂａｓｅｄ ｏｎ ｍｉｘｅｄ ｉｎｔｅｇｅｒ ｐｒｏｇｒａｍｍｉｎｇ ｍｏｄｅｌ ａｎｄ ｕｓｅｄ Ｌａｇｒａｎｇｉａｎ Ｒｅｌａｘａｔｉｏｎ ｔｏ ｄｅｖｅｌｏｐ ａ ｒｅｃｕｒｓｉｖｅ ｈｅｕｒｉｓｔｉｃ ａｌｇｏｒｉｔｈｍ，ａｎｄ ｄｉｓｃｕｓｓｅｄ ｔｈｅ ｐｒｏｂｌｅｍｓ ｏｆ ｆｅａｓｉｂｌｅ ｓｏｌｕｔｉｏｎ ｄｅｔｅｒｍｉｎａｔｉｏｎ ａｎｄ ｓｅｔ ａｄ唱 ｊｕｓｔｍｅｎｔ．Ｔｅｓｔｅｄ ａ ｎｕｍｅｒｉｃａｌ ｅｘｐｅｒｉｍｅｎｔ．Ｔｈｅ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｉｓ ｆｅａｓｉｂｌｅ ｗｉｔｈ ｈｉｇｈ ｃｏｍｐｕｔｉｎｇ ｅｆｆｉｃｉｅｎｃｙ， ａｎｄ ｔｈｅ ｇｅｎｅｒａｔｅｄ ｓｏｌｕｔｉｏｎｓ ｉｓ ｖｅｒｙ ｃｌｏｓｅ ｔｏ ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ． Key words： ｔｒａｆｆｉｃ ｍａｎａｇｅｍｅｎｔ； ｆｒｅｉｇｈｔ ｃｏｎｓｏｌｉｄａｔｉｏｎ； ａｉｒ ｃａｒｇｏ ｆｏｒｗａｒｄｅｒｓ； ｓｅｔ ｃｏｖｅｒｉｎｇ； ｈｅｕｒｉｓｔｉｃ ａｌｇｏｒｉｔｈｍ 人 ［５ ～７］。 中在海运集装箱的拼装箱问题 价体系的重量和体积，建立了货物拼箱的混合整数规划模型。 国内也有少数专家研究货物拼装问题，但大部分的研究内容集 1　问题描述 1畅1　航空货代拼箱的特性 民航的航空运价体系同时考虑了重量和体积，即将货物的 体积按照标准密度转换成体积重量，比较货物的实际重量和体 积重量，取其最大者作为运费的计费重量。 目前 ＩＡＴＡ 推荐使 用的标准密度为１／６ 吨／立方米。 因而航空货代的拼箱过程就 是将密度较大的货物与密度较小的货物进行合并，调整货物整 体的密度，能够有效地降低支付给航空公司的总运费。 航空公 司为了促进货代企业大力揽货，在运价体系中还包括了数量折 扣，因而航空货代在满足顾客要求的情况下，将货物进行合并， 利用较大的托运量向航空公司获得较低的单位运价。 某航空 公司某条航线的运价表如表１ 所示。 ４５ ～１００ 　　随着世界国际贸易自由化和全球物流的发展，全球航空货 ［１］，未来 ２０ 年 运已经进入蓬勃发展阶段。 根据波音公司预测 全球航空货运年均增长率达到 ６．３％，比航空客运高出 ２ ～３ 个百分点。 中国航空货运发展尤为迅猛，未来将以 １０．６％的 速度持续增长。 为了满足中国航空货运的增长需求，提高整个 航空货运流程的效率是目前急需解决的问题。 因为国际航空 货运的经营涉及到货代、机场、海关、航空公司等多方参与者， 操作程序也比较复杂，所以相应的管理决策问题相当多而且比 较复杂。 在众多参与者中，航空货代在整个航空货运流程中扮 演着重要的角色，一方面是货主的服务供应者，直接影响着航 空货运的成本与顾客满意度；另一方面是航空公司的消费需求 者。 航空货代的收入一方面来自货物进出口手续代办的佣金； 另一方面通过对货物进行拼装，以获得向货主收取运费与航空 公司提供费率之间的差价。 由于目前航空货运的运价体系同 时考虑货物的重量和体积，而且运价还有数量折扣，因此航空 货代在满足顾客要求的前提下，对货物进行有效的拼装，降低 支付给航空公司的运费是一个非常复杂的问题，目前有部分专 家和学者研究航空货代的拼箱问题。 Ｊａｅｇｅｒ［２］ 航线网络运费成本的基础上，研究了货物运输路线和货物拼箱 问题，但未考虑货物实际重量与计费重量之间的转换。 Ｘｕｅ 等 　　若航空货代托运货物的计费重量为 ４０ ｋｇ，则需付运费 对香港航空货代的拼箱问题进行了研究，建立了集装箱 １ ２００元；若计费重量为５０ ｋｇ，仅需付运费１ ０００元。 因而在这 ［３］ 租赁和货物拼箱的混合整数规划模型。 Ｗｕ［４］ 种情况下，航空货代会将其他货物与此批货物进行合并，甚至 收稿日期： ２０１０唱１１唱３０； 修回日期： ２０１１唱０１唱１３　　 基金项 目： 国 家 自 然 科 学 基 金 资 助 项 目（７０９０１００１）；安 徽 省 自 然 科 学 基 金 资 助 项 目 （１１０４０６０６Ｍ２４）；国家教育部人文社会科学研究基金资助项目（１０ＹＪＡ６３００４２）；安徽工程大学引进人才启动基金资助项目（２００８ＹＱ００２）；安徽省高 校省级自然科学重点项目（ＫＪ２０１１Ａ０３３） 作者简介：桂云苗（１９７８唱），男，安徽潜山人，副教授，博士，主要研究方向为智能化管理、供应链管理等（ｙｍｇｕｉ＠ａｈｐｕ．ｅｄｕ．ｃｎ）；龚本刚（１９７３唱），男， 安徽金寨人，教授，博士，主要研究方向为供应链协调优化等；程幼明（１９６３唱），男，湖北武汉人，教授，主要研究方向为生产运作管理等． 表 １　某航空公司的货物运价表 １８ 计费重量／ｋｇ 运价／元／ｋｇ 同时考虑航空运 在考虑航空公司 ０ ～４５ ３０ １００ ～３００ ３００ ～５００ １６ ２０ 

桂云苗，等：一种求解航空货代拼箱问题的启发式算法 第 ７ 期 多放一些不相干的重物来增加计费重量，降低总的运费。 因此 对航空货代来说，运价体系存在着重量分界线，当计费重量超 过某一重量分界线，而未达到下一段计费重量界线时，便可依 照下一段费率计算总运价。 从表１ 可以得出考虑运价的重量 分界线的边际运价，如图１ 所示。                 1畅2　混合整数规划模型 在考虑航空货运的运价体系特性基础上，依照 Ｗｕ 建立的 混合整数规划模型，构建出航空货代的拼箱问题的数学模型， 如下所示： yjk≥０ zjk，wjk∈｛０，１｝ yjk≤wj（k －１） ×（Xjk －Xj（k －１））　橙j∈J，橙k∈K yjk≥wjk ×（Xjk －Xj（k －１））　橙j∈J，橙k∈K j ＝１钞l ｍｉｎ 钞m k ＝１Rjk ×yjk ｓ．ｔ．钞 zij ＝１　橙i∈I j∈Mi i ＝１zij ×Gi　橙j∈J 钞l k ＝１yjk≥钞n 钞l k ＝１yjk≥钞n i ＝１zij ×Vi　橙j∈J （１） （２） （３） （４） （５） （６） （７） （８） 其中：i 为欲拼装货物编号，i ＝１，２，…，n；I 为所有要拼装货物 i 的集合；j 为可指派航班编号，j ＝１，２，…，m；J 为所有可指派航 班 j 的集合；Mi 为货物 i 的所有可指派航班 j 的集合（Mi彻j， 橙i）；k 为航班运价的分段编号（ 参照图１），k ＝１，２，…，l；K 是 各航班运价的所有分段 k 的集合；Gi 是货物 i 的实际重量；Vi 是货物 i 的体积重量；Rjk 是航班 j 运价中第 k 段的边际运价； Xjk是航班 j 运价中第 k 段的计费重量分界点，其中 Xj０ ＝０，橙j； zij ＝１ 表示货物 i 指派给航班 j，否则为 ０；yjk 是航班 j 第 k 段运 价的运输重量；wjk ＝１ 表示航班 j 第 k 段运价的运量 yjk 达到上 限值，否则为０，因第一段运量无须考虑前一段的运量是否达 到上限，所以 wj０ ＝１。 模型中式（１） 表示要达到航空货代企业支付给航空公司 的总运费最小化的目标；约束条件式（２） 表示每个货物必须且 只能指派给一个航班；式（３）和（４） 表示各个航班的总计费重 量都应大于等于货物的实际重量和体积重量；式（５）表示每一 分段运量要小于等于该分段的最大运量，此时 wj（k －１） ＝１ 以确 保运量已经达到前一分段的上限值；式（６）表示在该分段的运 量达到上限时，wjk始终等于１。 1畅3　转换为集合覆盖问题 派遣问题。 Ｉｒｎｉｃｈ［９］ 题再进行求解。 由于货物拼箱问题与工作指派、排班等问题相 似，因此航空货代拼箱问题转换为集合覆盖问题是可行的。 在 利用集合覆盖问题描述了空乘排班问题和车辆 也将货物运输路线问题转换为集合覆盖问 Ｍｏｎａｃｉ［８］ Csxs ·７４４２· 　　　 航空货代拼箱过程中，每一个拼箱组合可以代表一个集合，并 且其运费为集合的成本。 将上述货物拼箱模型描述成集合覆 盖问题，转换后的数学模型为 （９） ｍｉｎ 钞 s∈S ｓ．ｔ．钞 （１０） aisxs≥１　橙i∈I s∈S （１１） xs≤１　橙j∈J ∑ s∈Nj xs∈｛０，１｝ （１２） 其中：s 是货物拼箱组合，s∈S；S 是货物所有拼箱组合组成的 集合；Nj 是属于航班 j 的货物拼箱组合组成的集合（ 通常包含 多个拼箱组合 s）；Cs 表示货物拼箱组合 s 所对应的成本；ais 表 示货物拼箱组合与货物编号组成的矩阵元素，当货物 i 包含在 货物拼箱组合 s 内时，ais ＝１，否则为０；xs ＝１ 表示货物拼箱组 合 s 被选取，否则为０。 模型中式（１０） 表示货物 i 可被拼箱组 合覆盖一次或者多次。 由于求解集合覆盖问题比集合分割问 题容易，所以约束条件式（１０） 使用的是大于等于号而不是等 于号。 当货物被覆盖两次以上，只需在原拼箱组合中删除重复 货物，使得货物仅被覆盖一次，从而比直接求解集合分割问题 简单得多，在启发式算法流程中此项修正工作称为求解集合分 割问题。 式（１１）不是经典集合覆盖问题中的约束条件，它表 示每个航班最多仅有一个拼箱组合。 1畅4　拉格朗日松弛方法 虽然货物拼箱问题已经转换为集合覆盖问题，但仍然不易 求解。 本文采用拉格朗日松弛方法将原问题的约束条件式 （１０）放松，进一步降低求解的难度。 模型进一步转换为 （１３） L（u） ＝ｍｉｎ ∑ Cs（u）xs ＋∑ s∈S i∈I （１４） ｓ．ｔ．∑ xs≤１　橙j∈J s∈Nj （１５） xs∈｛０，１｝ 其中：Cs（u） ＝Cs －∑ ui，ui 是货物 i 的拉格朗日乘数；u 是所有 i∈Is 拉格朗日乘数的列向量，u 的初始值可由贪婪算法 取得； Is 表示被货物拼箱组合 s 覆盖的所有货物集合，也就是 Is ＝ ｛ais ＝１，i∈I｝。 从转换后的模型中可以看出，当 Cs（u） ＜０ 时， xs ＝１；当 Cs（u） ＞０ 时，xs ＝０；当 Cs（u） ＝０ 时，xs ＝０ 或者 １。 因为受到约束条件式（１４） 的限制，所以若某一航班所属的拼 箱组合出现两次以上的 Cs（u） ＜０，则仅选择其中 Cs（u） 最小 的拼箱组合 s，令其 xs ＝１，因而在实际运算过程中可对 Cs（u） 值进行排序获取相应的 xs 值。 为了方便求解，当Cs（u） ＝０ 时，令 xs ＝０。 拉格朗日乘数 u 大小的调整可 按照 Ｈｅｌｄ 等 ［１１］ （１６） xs（ut），t 表示第 t 次替代；UBt 表示第 t 次 其中：qi（ut） ＝１ －∑ s∈Is 求得的放松后上限值；λ为调整系数。 1畅5　修正不可行解的方法 求解，所以极有可能产生不可行解，需要对其不可行解进行修 正。 修正拉格朗日法的不可行解为可行解，主要是利用 Cs（u） 值，使得能在目标值增加量最小时找到可行解。 但是修正方法 不能太复杂，以免大幅度增加运算负荷。 本文给出一个简单的 修正不可行解的方法。 先对各个航班的 Cs（u）值从小到大进行排序，然后将各个 提出的次梯度方法实现，其调整方法为 因为拉格朗日松弛方法放松了约束条件对目标函数进行 ‖（q（ut）‖２ qi（ut），０｝ i ＋λUBt －L（ut） i ＝ｍａｘ ｛ut ut ＋１ ［１０］ 人 ui 

计 算 机 应 用 研 究 第 ２８ 卷 初始拼箱组合空间是根据密度高的货物与密度低的货物 ·８４４２· 航班排在前两名的 Cs（u）值相减（排名后者减去排名前者），可 得一个差值。 该差值表示将排名前者的拼箱组合替换为排名 后者的拼箱组合后，原目标值的增加量。 因此在所有航班中选 择差值最小的两个拼箱组合进行交换。 每次修正过程选择一 个航班进行，在两个拼箱组合交换后，判断原不可行解所覆盖 的货物是否仍然覆盖，而且是否增加了一个以上原来未被覆盖 的货物。 若两个条件都成立，则这两个拼箱组合进行交换；否 则，不与相应的拼箱组合进行交换，并依次选择排名下一位的 拼箱组合，计算该航班的这两个拼箱组合的 Cs（u） 之间差值， 再从所有航班中选择差值最小的两个拼箱组合。 重复上述流 程，直至所有航班所有拼箱组合都测试过。 从上述修正过程可以看出，修正过程最多只需要拼箱组合 数减去航班数的次数完成。 在１．６ 节将会说明如何调整拼箱 组合空间大小，以保证修正过程的运算负荷比较小。 因为上述 修正过程并不能保证交换一定会产生可行解，所以如果修正过 程仍然无法找到可行解，那么利用现有可行解替换不可行解。 1畅6　拼箱组合空间的调整 货物拼箱问题转换为集合覆盖问题后，约束条件变少了， 但变量数目变多，拼箱组合空间也呈指数增长。 例如，一个３０ 件货物，６ 个航班可供指派，若没有任何顾客限制，那么货物拼 个，因此有必要缩小拼箱组合空间， 箱组合的数目高达６ ×２３０ 提高求解效率。 所产生的均匀覆盖、各航班符合容量与顾客限制的最大覆盖 （各航班覆盖货物数量最多的情形） 和各航班最小覆盖（ 仅覆 盖单个货物） 三类拼箱组合所产生的。 均匀覆盖产生方法是 先对货物的密度进行排序，然后按照顾客与航班运载容量限 制，平均分配给各个航班。 由于每个航班仅产生一个拼箱组 合，每个货物仅被覆盖一次，且符合航班容量限制与顾客的要 求，因此产生的拼箱组合集合为可行解。 在初始拼箱组合空间 的基础上，对拼箱组合空间进行增加和删除，以保证选择好的 拼箱组合，使其得到理想的近似解。 拼箱组合空间增加和删除 机制如下： ａ）删除机制。 对各个拼箱组合的 Cs（u）值从小到大进行排 序，仅保留一定比例的拼箱组合，其余的删除。 比如每个航班保 留前３０ 个拼箱组合。 因为由模型式（１３）可知，当Cs（u） ＜０ 时， Cs（u） 值越小，代表该拼箱组合对目标值的贡献越大，所以 Cs（u）值可以作为一个拼箱组合是否被保留的指标。 ｂ）增加机制Ⅰ。 因为 qi（u） 值不仅仅表示约束条件式 （１０）是否满足，而且也是拉格朗日乘数 u 的重要修正系数，所 以选择 qi（u）最大者的货物作为加项，与现有拼箱组合逐一比 较，若不含有该货物，则将其加入该拼箱组合；反之，选择qi（u） 最小者的货物作为减项，将该货物从拼箱组合中删除。 由加项 产生的新拼箱组合，由于其 qi（u） 值最大，那么相应的 u 值也 最大，因而新增加的拼箱组合的 Cs（u） 值变小，能产生较好的 拼箱组合；反之，利用减项所产生的新拼箱组合，其 Cs（u）值也 应变小。 ｃ）增加机制Ⅱ。 在集合覆盖问题求解过程中，检查是否 有货物被重复覆盖，若有则将重复的货物保留在 Cs（u） 值最小 的拼箱组合中，再将其他拼箱组合中该货物删除，从而也有可 能产生新的拼箱组合。 为了缩短运算时间，每一航班都设定拼 箱组合数目的最大值，当拼箱组合数达到最大值时，不再增加 新的拼箱组合。 本文首先将拼箱问题转换为集合覆盖问题，然后利用拉格 朗日松弛方法进行第一阶段求解，第二阶段再根据拉格朗日解 求得集合覆盖问题的解，最后利用集合覆盖问题的解修正为集 合分割问题。 启发式算法的流程如图２ 所示。 一般来说，拉格 朗日松弛方法采用上下限逼近方式求得最佳解。 因而当上下 限达到一个合理区间内即为算法计算的停止条件。 产生初始拼箱组合空间与可行解利用贪 婪法产生 初始值  计算 值且排序求得 值      求解式 计算    的值 的值      以增加和删除 调整拼箱给合空间 是否为可行解 是 得到集合覆盖问题的解及 值 根据式 调整  否 修正为集合覆盖 问题的可行解 值     根据集合覆盖问题的解 求集合分割问题 是 是否满足 停止条件 是 得到近似解 否 图  启发式算法的流程图 2　数值分析 假设共有４ 组货物需要拼箱，货物的件数分别为 ３０、４０、 ５０、６０，所对应指派的航班数分别为 ３、４、５、６。 货物的重量和 体积由 ＳＰＳＳ１３．０ 软件产生随机数，并保证货物的密度在［０．１， ２］间变动。 各个航班的运价都是相同的，分别有２ 元和４ 元数 量折扣两种，如表２ 所示。 λ＝０．１，每个航班最大拼箱组合数 为２０。 通过 ＭＡＴＬＡＢ ６．５ 软件编程实现本文提出的启发式算 法，从而求出最佳的拼箱组合。 其中，在２ 元数量折扣下３０ 件 货物拼箱组合结果是：航班 １ 的拼箱组合为｛２，２１｝，｛３，１９， ２５｝，｛２９｝，｛７，１５｝，｛２０，４｝；航班２ 的拼箱组合为｛１，１８｝，｛６， ８，１２｝，｛９，３０｝，｛１４，１６，２６｝，｛２８｝；航班 ３ 的拼箱组合为｛５， １０｝，｛１１，２３｝，｛１３｝，｛１７，２２，２４，２７｝。 表 ２　各个航班的运价表 ０ ～１００ ３００ ～５００ ３６ ４０ ４０ ３２ 计费重量／ｋｇ 运价／元／ｋｇ 运价／元／ｋｇ 　　利用 Ｌｉｎｇｏ ８．０ 软件求解该拼箱问题的最优解。 比较两种 方式求解的结果，得出两者之间的误差都在１％内，在２ 元和４ 元数量折扣下平均误差分别为０．３１５％和０．６０５％。 如表３ 所 示，２ 元和 ４ 元数量折扣下，不同货物件数间的最大与最小平 均误差分别为０．１７％和 ０．５６％。 因此，该算法在处理不同货 物件数，求解效果仍然比较好，而且能在合理时间内收敛，并不 会因货物件数和运价数量折扣的改变而有明显变化。 ７００ ～１０００ １００ ～３００ ５００ ～７００ ３４ ２８ ３２ ２４ ３８ ３６ 表 ３　不同货物件数的误差 ５０ ３０ ０ ．２７ ．２６ ．４４ ．４５ ０ ４０ ０ ．４３ １ ．０ ６０ ．３０ ．５３ 货物件数 平均误差 ０ ０ ０ ０ ０ ０ ．３１５ 误差（２ 元折扣） 误差（４ 元折扣） ．６０５ 　　在求解时间方面，当问题的规模不大时，两种求解方法的 处理时间差不多；当问题规模变大时，两者有明显差别。 在有 ６０ 件货物，６ 个航班可指派时，拼箱问题的混合整数规划模型中 共有４９９ 个变量，其中０唱１ 型整数变量４２６ 个，共有２１２ 个约束 条件。 在相同的硬件条件下（Ｐ４ ２．８ ＧＨｚ ＣＰＵ，５１２ ＭＢ ＲＡＭ）， 利用Ｌｉｎｇｏ 软件求解需要运行１．６ ｍｉｎ 左右， （下转第２４５１ 页） 

第 ７ 期 李春梅，等：非线性 ０唱１ 规划问题的人工鱼群算法 ·１５４２· 　　　 ［３］ 段玉红，高岳林．一类可分离的非线性 ０唱１ 背包问题的分枝定界 算法［Ｊ］．甘肃联合大学学报：自然科学版，２００６，20（６）：１唱４，１１． ［４］ 马良，朱刚，宁爱兵．蚁群优化算法［Ｍ］．北京：科学出版社，２００８． ［５］ 秦玲，白云，章春芳，等．解 ０唱１ 背包问题的蚁群算法［Ｊ］．计算机 工程， ２００６，32（６）：２１２唱２１４． ［６］ 刘勇，马良，宁爱兵．量子竞争决策算法及其在旅行商问题中的应 用［Ｊ］．计算机应用研究，２０１０，27（２）： ５８６唱５８９． ［７］ 李晓磊．一 种 新 型 的 智 能 优 化 方 法———人 工 鱼 群 算 法［Ｄ］．杭 州：浙江大学， ２００３． ［８］ 陈广洲，汪家权，李传军，等．一种改进的人工鱼群算法及其应用 ［Ｊ］．系统工程，２００９，27（１２）：１０５唱１１０． ［９］ 范玉军，王冬冬，孙明明．改进的人工鱼群算法［Ｊ］．重庆师范大学 学报：自然科学版，２００７，24（７）：２３唱２６． ［１０］ 王联国，洪毅，赵付青，等．一种改进的人工鱼群算法［Ｊ］．计算机 工程，２００８，34（１９）：１９２唱１９４． ［１１］ 修春波，张雨虹．基于蚁群与鱼群的混合优化算法［Ｊ］．计算机工 程，２００８，34（１４）：２０６唱２０７，２１８． ［１２］ 黄华娟，周 永 权．最 优 化 问 题 全 局 寻 优 的 ＡＦＳＡ唱ＢＦＧＳ 混 合 算 法 ［Ｊ］．计算机工程与应用，２００９，45（１）：６３唱６５，７９． ［１３］ 周永权，谢竹诚．求解 ＴＳＰ 的改进人工鱼群算法［Ｊ］．系统工程与 电子技术， ２００９，31（６）：１４５８唱１４６１． ［１４］ 黄华娟，周永权．求解全局优化问题的混合人工鱼群算法［Ｊ］．计 算机应用， ２００８，28（１２）：３０６２唱３０６４，３０６７． ［１５］ 王正初，周慕逊，李军，等．基于人工鱼群算法的水库优化调度研 究［Ｊ］．继电器，２００７，35（２１）：４３唱４６，５０． ［１６］ 李晓磊，路 飞， 田 国 会， 等．组 合 优 化 问 题 的 人 工 鱼 群 算 法 应 用 ［Ｊ］．山东大学学报：工学版，２００４，34（５）：６４唱６７． ［１７］ ＮＥＭＨＡＵＳＥＲ Ｇ Ｌ，ＷＯＬＳＥＹ Ｌ Ａ．Ｉｎｔｅｇｅｒ ａｎｄ ｃｏｍｂｉｎａｔｏｒｉａｌ ｏｐｔｉｍｉ唱 ｚａｔｉｏｎ［Ｍ］．Ｎｅｗ Ｙｏｒｋ：Ｗｉｌｅｙ，１９８８． ［１８］ ＨＯＣＨＢＡＵＭ Ｄ．Ａ ｎｏｎｌｉｎｅａｒ ｋｎａｐｓａｃｋ ｐｒｏｂｌｅｍ［Ｊ］．Operations Re唱 search Letters，１９９５，17（３）：１０３唱１１０． ［１９］ ＬＩ Ｄｕａｎ，ＷＡＮＧ Ｊ，ＸＩＡＯ Ｌｉｎｇ．Ｃｏｍｐｕｔｉｎｇ ｅｘａｃｔ ｓｏｌｕｔｉｏｎ ｔｏ ｎｏｎｌｉｎｅａｒ ｉｎｔｅｇｅｒ ｐｒｏｇｒａｍｍｉｎｇ：ｃｏｎｖｅｒｇｅｎｔ Ｌａｇｒａｎｇｉａｎ ａｎｄ ｏｂｊｅｃｔｉｖｅ ｌｅｖｅｌ ｃｕｔ ｍｅｔｈｏｄ［Ｊ］．Journal of Global Optimization，２００７，39 （１）：１２７唱 １５４． ｗａｒｄｓ唱ｍｉｎｉｍｕｍ ｃｏｓｔ ｒｏｕｔｉｎｇ ｐｒｏｂｌｅｍ ｉｎ ａ ｄｉｒｅｃｔｅｄ ｍｕｌｔｉ唱ｃｏｍｍｏｄｉｔｙ ｎｅｔｗｏｒｋ［Ｊ］．Transportation Research，１９７６，10（３）：３４７唱３５４． ［３］ ＸＵＥ Ｊ，ＬＡＩ Ｋ Ｋ．Ａ ｓｔｕｄｙ ｏｎ ｃａｒｇｏ ｆｏｒｗａｒｄｉｎｇ ｄｅｃｉｓｉｏｎｓ［Ｊ］．Compu唱 ters and Industrial Engineering，１９９７，33（１）：６３唱６６． ［４］ ＷＵ Ｓ．Ｔｈｅ ｓｔｕｄｙ ｏｆ ｔｈｅ ｄｅｃｉｓｉｏｎ ｓｕｐｐｏｒｔ ｓｙｓｔｅｍ ｆｏｒ ａｉｒ ｆｒｅｉｇｈｔ ｆｏｒｗａｒ唱 ｄｅｒｓ［Ｄ］．Ｔａｉｗａｎ：Ｎａｔｉｏｎａｌ Ｃｈｉａｏ Ｔｕｎｇ Ｕｎｉｖｅｒｓｉｔｙ，２００３． ［５］ 隋树林，邵巍，高自友．同一尺寸货物三维装箱问题的一种启发式 算法［Ｊ］．信息与控制，２００５，34（４）：４９０唱４９４． ［６］ 陈浩，刘心报，刘林，等．一种用遗传算法求解装箱问题的新编码 方法［Ｊ］．合肥工业大学学报，２００６，29（２）：１４４唱１５０． ［７］ 卜雷，尹传忠，蒲云．优化普零货物拼箱配装的遗传算法［Ｊ］．交通 运输工程学报，２００４，4（１２）：８４唱８７． ［８］ ＭＯＮＡＣＩ Ｍ．Ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｐａｃｋｉｎｇ ａｎｄ ｓｃｈｅｄｕｌｉｎｇ ｐｒｏｂｌｅｍｓ［Ｄ］． Ｂｏｌｏｇｎａ：Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｂｏｌｏｇｎａ，２００１． ［９］ ＩＲＮＩＣＨ Ｓ．Ａ ｍｕｌｔｉ唱ｄｅｐｏｔ ｐｉｃｋｕｐ ａｎｄ ｄｅｌｉｖｅｒｙ ｐｒｏｂｌｅｍ ｗｉｔｈ ａ ｓｉｎｇｌｅ ｈｕｂ ａｎｄ ｈｅｔｅｒｏｇｅｎｅｏｕｓ ｖｅｈｉｃｌｅｓ［Ｊ］．European Journal of Opera唱 tional Research，２０００，122（２）：３１０唱３２８． ［１０］ ＣＡＰＲＡＲＡ Ａ，ＦＩＳＣＨＥＴＴＩ Ｍ，ＴＯＴＨ Ｐ．Ａ ｈｅｕｒｉｓｔｉｃ ｍｅｔｈｏｄ ｆｏｒ ｔｈｅ ｓｅｔ ｃｏｖｅｒｉｎｇ ｐｒｏｂｌｅｍ［Ｊ］．Operations Research，１９９９， 47 （５）：７３０唱 ７４３． ［１１］ ＨＥＬＤ Ｍ，ＫＡＲＰ Ｒ Ｍ．Ｔｈｅ ｔｒａｖｅｌｉｎｇ ｓａｌｅｓｍａｎ ｐｒｏｂｌｅｍ ａｎｄ ｍｉｎｉｍｕｍ ｓｐａｎｎｉｎｇ ｔｒｅｅｓ ［ Ｊ］．Operations Research，１９７０， 18 （６）：１１３８唱 １１６２． 表 ２　算例 ２ 的计算结果 （０ 比较项 乘子法 约束松弛法 ．９９９９，１．００００，０．００００， ０．９９３９，０．００４０） 最优解 （１，１，０，１，１，０） （１，１，０，１，１，０） （０，０，１，１，１，１） 　　 算例 ３　ｍｉｎ（x２１ ＋x２２ ＋２x２３ ＋２x２４ －５x１ －５x２ －２１x３ ＋７x４） 人工鱼群算法 最优值 ８ ｓ．ｔ． ８ －x１ ＋x２ －x３ ＋x４ －x２１ －x２２ －x２３ －x２４≥０ １０ ＋x１ ＋x４ －x２１ －２x２２ －x２３ －２x２４≥０ xi∈｛０，１｝　i ＝１，…，４ 表 ３　算例 ３ 的计算结果 比较项 最优解 最优值 约束松弛法 （１，１，１，０） 量子竞争决策算法 （１，１，１，０） 人工鱼群算法 （１，１，１，０） －２７ 　　实验结果表明，人工鱼群算法对于非线性０唱１ 规划问题的 求解是有效的。 同时，使用较小的种群规模和迭代次数均可得 到最优解，并且具有较强的全局寻优能力，可以得到更多的全 局最优解。 4　结束语 本文针对非线性 ０唱１ 规划问题的特点设计了基于 ＭＡＴ唱 ＬＡＢ 环境的人工鱼群算法。 经过大量算例可知，算法对于该问 题具有较好的性能。 该算法较其他算法而言，可以得到相对多 的最优解。 但是，该算法能否直接解决其他类型的整数规划问 题（如车辆路径问题（ＶＲＰ））或其他的 ＮＰ 问题，还有待于进一 步研究。 参考文献： ［１］ ＣＯＯＰＥＲ Ｍ Ｗ．Ｔｈｅ ｕｓｅ ｏｆ ｄｙｎａｍｉｃ ｐｒｏｇｒａｍｍｉｎｇ ｆｏｒ ｔｈｅ ｓｏｌｕｔｉｏｎ ｏｆ ａ ｃｌａｓｓ ｏｆ ｎｏｎｌｉｎｅａｒ ｐｒｏｇｒａｍｍｉｎｇ ［ Ｊ］．Naval Research Logistics Quarterly，１９８０，27（１）：８９唱９５． ［２］ 隋允康，贾志超，杜家政．非线性 ０唱１ 规划问题的连续性及其遗传 算法解法［Ｊ］．北京工业大学学报，２００８，34（８）：７８７唱７９１． （上接第 ２４４８ 页）而本文提出的启发式算法运算时间在３５ ｓ 内。 当问题的规模变得越来越大，Ｌｉｎｇｏ 软件中求解的规模会呈指数 比例增长，而启发式算法的复杂度较低，能有效提高求解效率。 3　结束语 航空货代企业在航空货运流程中起着非常重要的作用，而 货物拼箱是影响航空货代企业收入的重要因素。 本文在前人 建立拼箱问题的混合整数规划模型的基础上，将拼箱问题转换 为集合覆盖问题，然后采用集合覆盖问题中常用的拉格朗日松 弛方法，提出了一个启发式求解方法，并给出了修正不可行解 的方法、初始拼箱组合空间的设定方法和拼箱组合空间的调整 方法，提高了算法的计算效率。 最后通过数值分析结果表明， 本文提出的算法能在合理时间内收敛，与最优解之间的误差比 较小，求解效率和质量都比较高，为航空货代企业决策提供了 方法指导。 本文只考虑了航空货代企业静态拼箱问题，未来可 将研究范围扩展到动态拼箱。 参考文献： ［１］ 苏宁．波音预测全球航空货运发展［Ｊ］．中国民用航空，２００６（５）： ２８唱２９． ［２］ ｆｏｒ唱 ＪＡＥＧＥＲ Ｆ．Ｃｏｎｓｏｌｉｄａｔｉｏｎ ｓｔｒａｔｅｇｙ ｆｏｒ ｉｎｔｅｒｎａｔｉｏｎａｌ ａｉｒ ｆｒｅｉｇｈｔ