分支限界装载问题的算法分析与设计

孙瑞芳 焦晓君 施瑞娜 李雯璐

摘要：该文主要介绍用分支限界的方法解决装载问题。首先给出对装载问题的描述；接着着重优先队列式分支限界法的算法设计思想和算法分析展开谈论；最后给出实验，用分支限界法来解决装载问题，从而得到集装箱装载问题的装载方案或者不存在合理的装载方案。

关键词：队列式分支限界法；优先队列式分支限界法；装载问题

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2015）03-0105-01

在美国，运输费占GDP的比重大约为6%，大于库存费用4%的比重[1]。在我国，自从加入WTO后，很多领域相继对外开放，更多的跨国企业进入我国参与竞争，我们的物流配送也出现了一些新的变化和趋向[2]。可见目前运输问题在实际操作中存在的效率和效益低下的现状。本文解决装载问题的理论依据就是分支限界法，即在满足约束条件的前提下，通过限界条件来加快找到最佳方案的效率。

1 问题描述

有一批共[n]个集装箱要装上2艘载重量分别为[c1]和[c2]的两艘轮船，其中集装箱[i]的重量为[wi]，且[i=1nwi≤c1+c2]。装载问题要求确定是否存在一个合理的装载方案可将这[n]个集装箱要装上这2艘轮船。如果有，找出装载方案[3]。

2 分支限界装载问题算法设计

对于该问题容易证明，如果给定的装载问题有解，则可以通过下面的方案得到可行的装载方案[3]：

1）首先将第一艘轮船尽可能装满；

2）然后将剩余的集装箱装上第二艘轮船。

则装载问题可以描述为：

[maxi=1nwixi] （1）

s.t.[i=1nwixi≤c1]，（[xi∈{0，1}，1≤i≤n]） （2）

分支限界法的求解目标是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解。装载问题的要求是确定是否存在一个合理的装载方案可将这个集装箱要装上这2艘轮船。如果有，找出装载方案，即只需找出一种求解方案即可。根据公式1、公式2可知装载问题可转化为0-1背包问题，故只需将第一艘轮船尽可能装满，剩余的集装箱全部装入第一艘轮船中，则装载问题等价于选取全体集装箱的一个子集，使该子集中集装箱的重量之和尽可能接近其中的一个轮船。解决装载问题也就是在满足约束条件公式2的解中找出使目标函数公式1达到极大的解，故装载问题适用于分支限界法。

用优先队列式分支限界法时，从第一个集装箱[A]开始，分支、限界的方法也相同。优先队列式分支限界法用一个极大堆表示活结点表的优先队列。活结点[x]在优先队列中的优先级定义为从根节点到活结点[x]的路径所相应的载重量再加上剩余集装箱的重量之和，即[Ew+w[i]+r[i]]（[Ew]为扩展结点所相应的载重量，[w[i]]为活结点所对应集装箱的重量，[r[i]]为剩余集装箱的重量）。加入活结点表时根据该结点所代表集装箱的重量加入到最大堆中，选取下一个扩展结点时，总是选取堆顶元素进行扩展。容易知道，子集树中叶子结点的载重量与其优先级相同，所以一旦有叶子结点成为当前扩展结点，则该叶子结点所相应的解就是最优解，此时便可终止算法。

3 算法复杂度分析

优先队列式分支限界法同样需要存储解空间树，因此空间复杂度也是[O（2n）]。但该算法是以最小耗费（最大效益）的方式搜索解空间树，最小耗费（最大效益）是用最小堆（最大堆）实现最小（最大）优先队列，故其时间复杂度为[（nlogn）]。算法执行完毕后，可以用队列式分支限界法中构造最优解的方法得出最优解。

4 实验分析

4.1实验环境

实验的硬件环境为CPU：intel（R） Core（TM） i5-3210M CPU @2.50GHz，内存4G。操作系统为WIN7旗舰版。软件环境为VC++6.0，使用语言为C++语言。

4.2实验数据

5集装箱要装入两艘轮船，集装箱的重量[w[]={7，2，6，5，4}]，第一艘轮船的载重量[c=10]。

4.3算法过程分析

先求出解空间树各个层的剩余集装箱的总重量，即[r[1..4]={17，15，9，4}]。当前扩展结点0（数字零，用以表示进行扩展的第一个结点，此时还没有扩展任何一个集装箱）为载重量为0，即[Ew=0]；所在层数为第一层，即[i=1]，故[Ew+w[i]=7]（<10）。由于[Ew+w[i]=7]，大于[bestw]的初始值0，所以更新[bestw]为7。又有[Ew+w[i]+r[i]=24>7]，所以将左儿子结点[A]加入最大堆。由于[Ew+r[i]=17>7]，故可能包含最优解，所以将右儿子结点[B]加入最大堆。然后从最大堆中取出对顶元素，按照上述扩展方法进行扩展，直到达到叶子结点。然后可以构造出最优解，最优解为[bestx[]={0，0，1，0，1}]。

4.4实验结果

根据分支限界算法的基本原理，运用C++程序设计语言实现该算法，可以得到这5只集装箱的装载方案，如图1所示：

图1 集装箱装载方案

5 结论

分支限界方法是在回溯法的基础上加上了约束条件和限界条件，由此可以加速找到最优解，从而降低时间复杂度和空间复杂度。分支限界法根据扩展下一结点的不同可以有队列式分支限界法和优先队列式分支限界法。优先队列式分支限界法采用最大堆或最小堆实现最大或最小优先队列，使搜索始终想着最优的方向，相对队列式分支限界可以更加快的搜索到最优解。

参考文献：

[1] 吴志惠.美国的物流成本[J].中国储运，2002（5）.

[2] 张晓丽.物流配送中心货物装载问题研究[D].郑州：郑州大学，2012.

[3] 王晓东.计算机算法与技术分析[M].4版.北京：电子工业出版社，2012.