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

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

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

中图分类号：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）

分支限界法的求解目标是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解。……