带冲突关系装箱问题的启发式求解算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇带冲突关系装箱问题的启发式求解算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：现实物流活动中大量存在的食品、药品和危险品等货物的分组包装问题属于带冲突关系的装箱问题（BPPC），其优化目标是

>> 基于蚁群算法的带平衡约束矩形布局问题的启发式求解 有舍弃的装箱问题及其启发式算法 求解课程表问题的启发式算法综述 启发式算法在轨道交通换乘路径求解问题的应用 改进的启发式搜索算法求解农机调度问题 一种有效的求解一维下料问题的启发式算法 解决0―1背包问题的启发式算法 单体型装配问题的启发式算法研究 两阶段启发式算法在带时间窗的车辆路径问题中的应用 基于不同启发式策略的约束满足问题求解研究 集装箱甩挂运输车辆调度优化模型的三阶段启发式算法 基于贪心启发式算法的多目标二维切割问题 基于启发式遗传算法求解加工时间可控单台机器 基于启发式算法的品牌模型的选择 地标导向的启发式路径规划算法 有时间约束的非满载车辆调度问题的启发式改进算法 初中化学“问题”启发式教学的思考 对“问题启发式”教学的探讨 以问题为主的启发式教学 问题情境与启发式教学的结合 常见问题解答 当前所在位置：l上下载。算例分为三类，货物数量分别为120、250和500，其中每件货物的重量在20～100之间随机选定，所有货箱容量值固定为150。每一类算例按照冲突货物数量的密度值8（0.1≤δ≤0.9）不同进一步划分为九个小组，每个小组有十个具体算例。密度值δ的计算方式为：对某一货物i赋予一个满足[0，1]区间上均匀分布的特征值pi，那么，对于同组算例中的另外一件货物j，如果满足（pi+pi）/2≤δ，则在货物i与货物j之间添加一对冲突关系。为验证提出算法的有效性，选取文献中提出的基于图着色的冲突消去方法与本文提出的基于最太团的冲突消去方法分别实现并进行比较，比较内容主要包括针对每组算例计算得出的最优值、最差值和均值，并通过均值来计算算法改进效率。所有算法细节采用Java语言来实现，相应的虚拟机版本为Java Development Kit l.7.O，具体计算结果如表1所示。

（1）在货物数量规模相同的一类算例内部，当冲突密度值较小的时候（0.1≤δ≤0.3），由于兼容图中的边较为稠密，算法求解质量主要取决于改进FFD装箱算法的性能，此时本文提出算法相比基于图着色过程的启发式算法改进程度较小；随着冲突密度值的增大（0.4≤δ≤0.6），兼容图中的顶点集合划分数量增多，此时基于最大团的启发式算法更为有效地将冲突消去过程和装箱过程有机结合在一起，计算结果的改进程度较大；在冲突密度值最大的情况下（0.7≤6≤0.9），兼容图中的边较为稀疏，算法求解质量与冲突消去过程密切相关，此时本文提出算法具有更强的兼容货物搜索能力，但计算结果的改进能力有所下降。

（2）从整体角度来看，不同规模的三类算例在计算结果上均有所改进。相比基于图着色过程的启发式算法，本文提出算法通过迭代方式搜索兼容图上的货物最大团，更大限度的发挥改进FFD装箱算法的汁算性能，有助于获得质量更优的装箱方案。

4 结论

带冲突关系装箱问题是图着色问题与装箱问题这两个经典NP难题融合之后的一个新问题。尽管该问题在实际物流系统中的应用更为广泛，但由于问题的复杂性，直至最近几年才引起国内外学者们的关注。本文根据问题的数学模型，采用最大团计算取代图着色方式实现货物冲突关系的消去，并基于此设计了求解该问题的一个混合启发式算法。实验表明，本文提出的算法有效地将“冲突化解”和“货物装箱”过程融为一体，根据问题蕴含的启发式知识引入局部搜索算子，在保证求解质量的同时，确保了算法的稳定性。但通过实验也发现，算法有时也容易陷入局部最优，尤其问题规模较大时，其求解质量会受到影响，下阶段工作将侧重解决这一方面的问题。