基于图着色模型的冲突装箱问题启发式算法

运筹与管理 ›› 2013, Vol. 22 ›› Issue (5): 12-16.

基于图着色模型的冲突装箱问题启发式算法

元野¹, 李一军¹, 王延青¹, 王晓博²

1.哈尔滨工业大学管理学院,黑龙江哈尔滨 150001;
2.黑龙江大学信息管理学院,黑龙江哈尔滨 150080

收稿日期:2012-09-21 出版日期:2013-10-25
作者简介:元野(1985-),男,朝鲜族,黑龙江双鸭山人,博士研究生,研究方向:运筹学,物流优化;李一军(1957-),男,黑龙江哈尔滨人,教授,博士生导师,研究方向:电子商务,管理信息系统。
基金资助:
国家社会科学基金项目资助项目(10CGL076)

Heuristic Algorithm for Bin Packing Problem with Conflicts Based on Graph Coloring Model

YUAN Ye¹, LI Yi-jun¹, WANG Yan-qing¹, WANG Xiao-bo²

1. School of Management, Harbin Institute of Technology, Harbin 150001, China;
2. School of Information Management, Heilongjiang University, Harbin 150080, China

Received:2012-09-21 Online:2013-10-25

摘要/Abstract

摘要： 带有冲突关系装箱问题的优化目标是在满足货物冲突关系的前提下,使用数量最少的货箱完成货物装箱的目的。本文分析了冲突装箱问题的数学模型,提出了基于图着色模型的启发式算法进行求解。首先,使用冲突图来描述货物之间的冲突关系;其次,基于冲突图,采取图着色的方式将货物进行分组,并且组内的货物之间不存在冲突关系;最后,采取改进FFD算法对每组的货物进行装箱操作。实验表明,本文提出的启发式算法能够快速有效地找到问题的可行解,为此类装箱问题的求解提供了新思路。

关键词: 运筹学与控制论, 冲突装箱问题, 图着色, 启发式算法

Abstract: The objection of bin packing problem with conflicts(BPPC)is to minimize the number of bins used to accommodate all the items, and also has to satisfy the conflict constraints among the items. This paper summaries the mathematical model of BPPC, and proposes a heuristic algorithm based on graph coloring model to solve it. Firstly, a conflict graph structure is used to represent the conflict relationship among the items, and then, based on the conflict graph, the algorithm will finish a coloring procedure to group all the items and ensure that there is no items with conflict relationship in each group, and lastly, an improved FFD algorithm is used to complete the packing operation for the items in each group. The experiments show that the algorithm of this paper could find a feasible solution of BPPC quickly and efficiently, and provide a new approach for this kind of bin packing problems.

Key words: operations research and cybernetics, bin packing problem with conflicts, graph coloring, heuristic algorithm

中图分类号:

F224.31

元野, 李一军, 王延青, 王晓博. 基于图着色模型的冲突装箱问题启发式算法[J]. 运筹与管理, 2013, 22(5): 12-16.

YUAN Ye, LI Yi-jun, WANG Yan-qing, WANG Xiao-bo. Heuristic Algorithm for Bin Packing Problem with Conflicts Based on Graph Coloring Model[J]. Operations Research and Management Science, 2013, 22(5): 12-16.

参考文献

[1] Wäscher G, Hauβner H, Schumann H. An improved typology of cutting and packing problems[J]. European Journal of Operational Research, 2007, 183(3): 1109-1130.
[2] Lin Y H, Lin C, Lin B. On conflict and cooperation in a two-echelon inventory model for deteriorating items[J]. Computers and Industrial Engineering, 2010, 59(4): 703-711.
[3] Garey M R, Johnson D S. Computers and Intractability: a guide to the theory of NP-Completeness[M]. New York: W H Freeman, 1979.
[4] Lodi A, Martello S, Monaci M. Two-dimensional packing problems: a survey[J]. European Journal of Operational Research, 2002, 141(2): 241-252.
[5] Jansen K. An approximation scheme for bin packing with conflicts[J]. Journal of Combinational Optimization, 1999, 3(4): 363-377.
[6] Gendreau M, Laporte G, Semet F. Heuristics and lower bounds for the bin packing problem with conflicts[J]. Computers and Operations Research, 2004, 31(3): 347-358.
[7] Elhedhli S, Li L Z, Gzara M, Naoum-sawaya J. A branch-and-price algorithm for the bin packing problem with conflicts[J]. INFORMS Journal on Computing, 2011, 22(3): 404-415.
[8] Laporte G, Desroches S. Examination timetabling by computer[J]. Computers and Operations Research, 1984, 11(4): 351-360.
[9] Jansen K, Oehring S. Approximation algorithms for time constrained scheduling[J]. Information and Computation, 1997, 132(2): 85-108.
[10] Galinier P, Hertz A. A survey of local search methods for graph coloring[J]. Computers and Operations Research, 2006, 33(9) : 2547-2562.
[11] Malaguti E, Monaci M, Toth P. A metaheuristic approach for the vertex coloring problem[J]. INFORMS Journal on Computing, 2008, 20(2) : 302-316.
[12] Csirik J. The parametric behavior of the first-fit decreasing bin packing problem[J]. Journal of Algorithms, 1993, 15(1): 1-28.
[13] Elhedhli S. Ranking lower bounds for the bin-packing problem[J]. European Journal of Operational Research, 2005, 160(1): 34-46.
[14] Zhu W B, Zhang Z Y, Oon W C, Lim A. Space defragmentation for packing problems[J]. European Journal of Operational Research, 2012, 222(3) : 452-463.
[15] Muritiba A E F, Iori M, Malaguti E, Toth P. Algorithms for the bin packing problem with conflicts[J]. INFORMS Journal on Computing, 2010, 22(3): 401-415.