?基于贪心-遗传算法的物品冲突情形下装箱问题研究
首发时间:2020-12-09
摘要:合理的装箱方案可以提高货物装载率,降低物流成本。冲突装箱问题由物品的特殊性派生而来的,为优化带冲突关系物品的装箱方案,本文针对冲突装箱问题(BPPC)模型,提出了一种贪心算法与改进的遗传算法相结合的算法。首先基于图着色模型定义货物之间的冲突关系,运用贪心算法求解最小色数问题以消除货物的冲突关系,再结合降序最佳适应法(BFD)改进遗传算法初始种群生成及遗传算子操作,通过改进的算法对不含冲突关系的货物独立集分别进行装箱操作。最后通过实验分析验证了算法的有效性,应用该算法对不同冲突密度值的货物装箱问题找到了满意解。
For information in English, please click here
Research on Packing Problem in Case of Item Conflict Based on Creedy-Genetic Algorithm
Abstract:Reasonable packing scheme can improve the loading rate of goods and reduce the logistics cost. The conflict packing problem is derived from the particularity of items. In order to optimize the packing scheme of items with conflict relationship, this paper proposes an algorithm combining greedy algorithm and improved genetic algorithm for the conflict packing problem (BPPC) model. Firstly, the conflict relationship between goods is defined based on the graph coloring model, and the greedy algorithm is used to solve the minimum chromatic number problem to eliminate the conflict relationship of goods. Then combined with BFD algorithm to improve initial population generation and genetic operator operation of the genetic algorithm. Through the improved algorithm, the independent set of goods without conflict relationship is encased respectively. Finally, the validity of the algorithm is verified by experimental analysis, and a feasible solution is found to the problem of loading goods with different conflict density values.
Keywords: Conflict packing Greedy algorithm Genetic algorithm (GA)
引用
No.****
同行评议
共计0人参与
勘误表
?基于贪心-遗传算法的物品冲突情形下装箱问题研究
评论
全部评论0/1000