A Parallel Nash Genetic Algorithm for the 3D Orthogonal Knapsack Problem

被引：0
作者：
Soto, Daniel [1 ]
Soto, Wilson [1 ,2 ]
Pinzon, Yoan [1 ]
机构：
[1] Univ Nacl Colombia, Res Grp Algorithms & Combinator ALGOS UN, Bogota, Colombia
[2] Univ Cent Colombia, Intelligent Syst & Spatial Informat Res Grp SIGA, Bogota, Colombia
来源：
INTERNATIONAL JOURNAL OF COMBINATORIAL OPTIMIZATION PROBLEMS AND INFORMATICS | 2013年 / 4卷 / 03期
关键词：
Genetic Algorithms; Island Model; Knapsack Problem; Nash Equilibrium theory;
D O I：
暂无
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
The Three-Dimensional Knapsack Packing Problem consists of finding the maximum profit for packing a subset of boxes in a larger box (packing box). The boxes to pack are rectangular but of different sizes. This problem is a variant of the Knapsack Problem and therefore its computational complexity is NP-Complete. This article shows a parallel genetic algorithm based on the Island Model and the Nash equilibrium theory for solving the 3D Knapsack Packing Problem assuming both, orthogonally packing and rotation prevention. Computational experiments comparing the developed algorithm with previous approach indicate that the results are very hopeful for three-dimensional problem.
引用
收藏
页码：2 / 10
页数：9
相关论文
共 8 条
  • [1] Cantu Paz E., 1998, RESEAUX ET SYST REPA, V10, P141
  • [2] Crainic T.G., 2012, NEW TECHNOLOGIES TRE, P91
  • [3] Egeblad J, 2008, THESIS U COPENHAGEN, P238
  • [4] Heuristic approaches for the two- and three-dimensional knapsack packing problem
    Egeblad, Jens
    Pisinger, David
    [J]. COMPUTERS & OPERATIONS RESEARCH, 2009, 36 (04) : 1026 - 1049
  • [5] A combinatorial characterization of higher-dimensional orthogonal packing
    Fekete, SP
    Schepers, J
    [J]. MATHEMATICS OF OPERATIONS RESEARCH, 2004, 29 (02) : 353 - 368
  • [6] Perboli G., 2011, 7 ANN IEEE C AUT SCI, P1
  • [7] Sefrioui M, 2000, IEEE C EVOL COMPUTAT, P509, DOI 10.1109/CEC.2000.870339
  • [8] Torres E., 1999, THESIS
1