Changeset 15462 for branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D

Timestamp:

11/08/17 16:30:41 (6 years ago)

Author:

rhanghof

Message:

#2817
-Added unit tests for bin packing 3d.
-The items can now be sorted by the material.

Location:

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D

Files:

• BinPacking3D.cs (modified) (17 diffs)
• Decoder/ExtremePointPermutationDecoder.cs (modified) (4 diffs)
• Evaluators/PackingRatioEvaluator.cs (modified) (1 diff)
• Packer/BinPacker.cs (modified) (3 diffs)
• Packer/BinPackerFirstFit.cs (modified) (4 diffs)
• Packer/BinPackerFreeVolumeBestFit.cs (modified) (3 diffs)
• Packer/BinPackerResidualSpaceBestFit.cs (modified) (5 diffs)
• PackingPosition.cs (modified) (1 diff)
• PermutationEncoding/PermutationProblem.cs (modified) (2 diffs)

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs

@@ -67 +67 @@
     #region New methods for bin packer class
 
-    public void AddItem(int itemID, PackingItem item, PackingPosition position) {
+    public override void PackItem(int itemID, PackingItem item, PackingPosition position) {
       Items[itemID] = item;
       Positions[itemID] = position;
@@ -74 +74 @@
     }
 
+    /// <summary>
+    /// Updates the extreme points of the bin
+    /// </summary>
+    /// <param name="item"></param>
+    /// <param name="position"></param>
+    /// <param name="stackingConstraints"></param>
     public void UpdateExtremePoints(PackingItem item, PackingPosition position, bool stackingConstraints) {
-      /*if (stackingConstraints) {
-        AddExtremePoint(new PackingPosition(position.AssignedBin, position.X + item.Width, position.Y, position.Z));
-        AddExtremePoint(new PackingPosition(position.AssignedBin, position.X, position.Y + item.Height, position.Z));
-        AddExtremePoint(new PackingPosition(position.AssignedBin, position.X, position.Y, position.Z + item.Depth));
-      } else {*/
+      if (stackingConstraints) {
+        UpdateExtremePointsWithStackingConstriants(item, position);
+      } else {
+        UpdateExtremePointsWithoutStackingConstriants(item, position);
+      }
+    }
+
+    /// <summary>
+    /// Updates the extreme points of the bin. 
+    /// As there is no need to project the extreme points to the next side of an item, the extreme points are only generated for the current item.
+    /// </summary>
+    /// <param name="item"></param>
+    /// <param name="position"></param>
+    private void UpdateExtremePointsWithStackingConstriants(PackingItem newItem, PackingPosition position) {
+
+      //UpdateExtremePointsWithoutStackingConstriants(newItem, position);
+      //return;
+
+      int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
+      int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
+      var ep1 = new PackingPosition(position.AssignedBin, position.X + newWidth, position.Y, position.Z);
+      var ep2 = new PackingPosition(position.AssignedBin, position.X, position.Y + newItem.Height, position.Z);
+      var ep3 = new PackingPosition(position.AssignedBin, position.X, position.Y, position.Z + newDepth);
+      AddExtremePoint(ep1);
+      AddExtremePoint(ep2);
+      AddExtremePoint(ep3);
+
+      /*
+      ExtremePoints.Add(ep1);
+      ExtremePoints.Add(ep2);
+      ExtremePoints.Add(ep3);
+
+      var rs1 = CalculateResidualSpace(CreateRs(ep1));
+      var rs2 = CalculateResidualSpace(CreateRs(ep2));
+      var rs3 = CalculateResidualSpace(CreateRs(ep3));
+      ResidualSpace.Add(ep1, rs1);
+      ResidualSpace.Add(ep2, rs2);
+      ResidualSpace.Add(ep3, rs3);*/
+    }
+
+
+    /*private bool AddExtremePoint(PackingPosition position) {
+      if ()
+
+      return true;
+    }
+
+    
+    private bool AddExtremePoint(PackingPosition pos) {
+      if (ExtremePoints.Add(pos)) {
+        var rs = CalculateResidualSpace(new Vector3D(pos));
+        ResidualSpace.Add(pos, rs);
+        // Check if existing extreme points are shadowed by the new point
+        // That is, their residual space fit entirely into the residual space of the new point
+        foreach (var ep in ExtremePoints.Where(x => x != pos && new Vector3D(x).IsInside(pos, rs)).ToList()) {
+          if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), ResidualSpace[ep], pos, rs)) {
+            ExtremePoints.Remove(ep);
+            ResidualSpace.Remove(ep);
+          }
+        }
+        return true;
+      }
+      return false;
+    }*/
+
+
+    private Tuple<int, int, int> CalculateResidualSpace(Vector3D pos) {
+      var itemPos = Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] });
+      Vector3D limit = new Vector3D() { X = BinShape.Width, Y = BinShape.Height, Z = BinShape.Depth };
+      if (pos.X < limit.X && pos.Y < limit.Y && pos.Z < limit.Z) {
+        var rightLimit = ProjectRight(pos);
+        var upLimit = ProjectUp(pos);
+        var forwardLimit = ProjectForward(pos);
+        if (rightLimit.X > 0) {
+          limit.X = rightLimit.X;
+        }
+        if (upLimit.Y > 0) {
+          limit.Y = upLimit.Y;
+        }
+        if (forwardLimit.Z > 0) {
+          limit.Z = forwardLimit.Z;
+        }
+      }
+
+      
+      
+      if (limit.X - pos.X <= 0 || limit.Y - pos.Y <= 0  || limit.Z - pos.Z <= 0) {
+        return Tuple.Create(0, 0, 0);
+      }
+
+
+      return Tuple.Create(limit.X - pos.X, limit.Y - pos.Y, limit.Z - pos.Z);
+    }
+
+
+    private Vector3D CreateRs(PackingPosition position) {
+      return new Vector3D() { X = position.X, Y = position.Y, Z = position.Z };
+    }
+
+    private void UpdateExtremePointsWithoutStackingConstriants(PackingItem item, PackingPosition position) {
       GenerateNewExtremePointsForNewItem(item, position);
 
@@ -92 +193 @@
         GenerateNewExtremePointsForNewItem(right.Item2, right.Item1);
       }
-      //}
     }
 
@@ -147 +247 @@
         }
       }
-      return true;     
+      return true;
     }
 
@@ -156 +256 @@
     /// <param name="t2"></param>
     /// <returns></returns>
-    bool ItemsCollides(Tuple<PackingPosition, PackingItem> t1, Tuple<PackingPosition, PackingItem> t2) {
+    private bool ItemsCollides(Tuple<PackingPosition, PackingItem> t1, Tuple<PackingPosition, PackingItem> t2) {
       var position1 = t1.Item1;
       var item1 = t1.Item2;
@@ -189 +289 @@
     /// <param name="position"></param>
     /// <returns></returns>
-    public bool HasOnePointWithAnItemBelow(PackingItem item, PackingPosition position) {
+    private bool HasOnePointWithAnItemBelow(PackingItem item, PackingPosition position) {
       bool p1, p2, p3, p4;
-      PointsLiesOnAnItems(item, position, out p1, out p2, out p3, out p4);
+      PointsLiesOnAnItem(item, position, out p1, out p2, out p3, out p4);
 
       return p1 || p2 || p3 || p4;
@@ -205 +305 @@
     public override bool IsStaticStable(PackingItem item, PackingPosition position) {
       bool p1, p2, p3, p4;
-      PointsLiesOnAnItems(item, position, out p1, out p2, out p3, out p4);
+      PointsLiesOnAnItem(item, position, out p1, out p2, out p3, out p4);
       return p1 && p2 && p3 && p4;
     }
 
     /// <summary>
-    /// This method sets the out parameters p1 ... p3 if the point lies on another item.
+    /// This method sets the out parameters p1 ... p4 if the point lies on another item.
     /// p1 ... p3 represents one point on the bottom side of an given item.
     /// +---------+
@@ -224 +324 @@
     /// <param name="p3"></param>
     /// <param name="p4"></param>
-    public void PointsLiesOnAnItems(PackingItem item, PackingPosition position, out bool p1, out bool p2, out bool p3, out bool p4) {
+    private void PointsLiesOnAnItem(PackingItem item, PackingPosition position, out bool p1, out bool p2, out bool p3, out bool p4) {
       IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP1;
       IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP2;
@@ -240 +340 @@
 
     /// <summary>
-    /// 
+    /// This method returns a collection for the out parameters itemsP1 ... itemsP4 with the items below
+    /// itemsP1 ... itemsP4 represents one point on the bottom side of an given item.
+    /// +---------+
+    /// |p1     p2|
+    /// |         |
+    /// |p4     p3|
+    /// +---------+
     /// </summary>
     /// <param name="item"></param>
@@ -277 +383 @@
     /// <param name="position"></param>
     /// <returns></returns>
-    public bool IsWeightSupported(PackingItem item, PackingPosition position) {
+    private bool IsWeightSupported(PackingItem item, PackingPosition position) {
       if (position.Y == 0) {
         return true;
@@ -298 +404 @@
     #endregion
 
-    public override void PackItem(int itemID, PackingItem item, PackingPosition position) {
-      // base call is deliberately omitted, because UpdateResidualSpace needs to be fitted in before
-      // generating new extreme points
-      Items[itemID] = item;
-      Positions[itemID] = position;
-      ExtremePoints.Remove(position);
-      ResidualSpace.Remove(position);
-      UpdateResidualSpace(item, position);
-      GenerateNewExtremePointsForNewItem(item, position);
-      // if an item is fit in below, before, or left of another its extreme points have to be regenerated
-      foreach (var above in GetItemsAbove(position))
-        GenerateNewExtremePointsForNewItem(above.Item2, above.Item1);
-      foreach (var front in GetItemsInfront(position))
-        GenerateNewExtremePointsForNewItem(front.Item2, front.Item1);
-      foreach (var right in GetItemsOnRight(position))
-        GenerateNewExtremePointsForNewItem(right.Item2, right.Item1);
-      AddNewItemToOccupationLayers(itemID, item, position);
-    }
-
-
-
+    /// <summary>
+    /// Generates new extreme points for a given item and its position.
+    /// It also recalcualtes the residual space and removes the extreme points which are not needed any more.
+    /// </summary>
+    /// <param name="newItem"></param>
+    /// <param name="position"></param>
     protected override void GenerateNewExtremePointsForNewItem(PackingItem newItem, PackingPosition position) {
       int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
@@ -404 +495 @@
     }
 
-
     private bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> residualSpace) {
       var eps = ExtremePoints.Where(x => !pos.Equals(x) && pos.IsInside(x, ResidualSpace[x]));
@@ -432 +522 @@
     }
 
-    private Tuple<int, int, int> CalculateResidualSpace(Vector3D pos) {
+    private Tuple<int, int, int> CalculateResidualSpace1(Vector3D pos) {
       var itemPos = Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] });
       var rightLimit = ProjectRight(pos);
@@ -505 +595 @@
     #region Get items
 
-    /// <summary>
-    /// 
-    /// </summary>
-    /// <param name="pos"></param>
-    /// <returns></returns>
     private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsAbove(PackingPosition pos) {
       var line = new Line3D(pos, new Vector3D(0, 1, 0));
@@ -573 +658 @@
 
 
-
+    #region Sliding based packing  and obsolet methods 
     public override PackingPosition FindExtremePointForItem(PackingItem item, bool rotated, bool stackingConstraints) {
+      throw new NotSupportedException();
       PackingItem newItem = new PackingItem(
         rotated ? item.Depth : item.Width,
@@ -590 +676 @@
     }
 
-  
-
-    #region Sliding based packing    
+
+
+
     public override PackingPosition FindPositionBySliding(PackingItem item, bool rotated, bool stackingConstraints) {
-      //Starting-position at upper right corner (=left bottom point of item-rectangle is at position item.width,item.height)
-      PackingPosition currentPosition = new PackingPosition(0,
-        BinShape.Width - (rotated ? item.Depth : item.Width),
-        BinShape.Height - item.Height,
-        BinShape.Depth - (rotated ? item.Width : item.Depth), rotated);
-      //Slide the item as far as possible to the bottom
-      while (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition), stackingConstraints)
-        || IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints)
-        || IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition), stackingConstraints)) {
-        //Slide the item as far as possible to the left
-        while (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints)
-      || IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition), stackingConstraints)) {
-          //Slide the item as far as possible to the back
-          while (IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition), stackingConstraints)) {
-            currentPosition = PackingPosition.MoveBack(currentPosition);
-          }
-          if (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints))
-            currentPosition = PackingPosition.MoveLeft(currentPosition);
-        }
-        if (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition), stackingConstraints))
-          currentPosition = PackingPosition.MoveDown(currentPosition);
-      }
-
-      return IsPositionFeasible(item, currentPosition, stackingConstraints) ? currentPosition : null;
+      throw new NotSupportedException();
     }
 
     public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) {
-      var temp = new List<int>(sequence);
-      for (int i = 0; i < temp.Count; i++) {
-        var item = items[temp[i]];
-        var position = FindPositionBySliding(item, false, stackingConstraints);
-        if (position != null) {
-          PackItem(temp[i], item, position);
-          sequence.Remove(temp[i]);
-        }
-      }
+      throw new NotSupportedException();
     }
     public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, Dictionary<int, bool> rotationArray, bool stackingConstraints) {
-      var temp = new List<int>(sequence);
-      for (int i = 0; i < temp.Count; i++) {
-        var item = items[temp[i]];
-        var position = FindPositionBySliding(item, rotationArray[i], stackingConstraints);
-        if (position != null) {
-          PackItem(temp[i], item, position);
-          sequence.Remove(temp[i]);
-        }
-      }
+      throw new NotSupportedException();
+    }
+
+
+    public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) {
+      throw new NotSupportedException();
+    }
+
+    public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints, Dictionary<int, bool> rotationArray) {
+      throw new NotSupportedException();
+    }
+
+    public override int ShortestPossibleSideFromPoint(PackingPosition position) {
+      throw new NotSupportedException();
+    }
+
+
+    protected override void InitializeOccupationLayers() {
+    }
+    protected override void AddNewItemToOccupationLayers(int itemID, PackingItem item, PackingPosition position) {
+    }
+
+
+    protected override List<int> GetLayerItemIDs(PackingPosition position) {
+      return null;
+    }
+    protected override List<int> GetLayerItemIDs(PackingItem item, PackingPosition position) {
+      return null;
     }
     #endregion
-    public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) {
-      var temp = new List<int>(sequence);
-      foreach (int itemID in temp) {
-        var item = items[itemID];
-        var positionFound = FindExtremePointForItem(item, false, stackingConstraints);
-        if (positionFound != null) {
-          PackItem(itemID, item, positionFound);
-          sequence.Remove(itemID);
-        }
-      }
-    }
-    public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints, Dictionary<int, bool> rotationArray) {
-      var temp = new List<int>(sequence);
-      foreach (int itemID in temp) {
-        var item = items[itemID];
-        var positionFound = FindExtremePointForItem(item, rotationArray[itemID], stackingConstraints);
-        if (positionFound != null) {
-          PackItem(itemID, item, positionFound);
-          sequence.Remove(itemID);
-        }
-      }
-    }
-    public override int ShortestPossibleSideFromPoint(PackingPosition position) {
-
-      int shortestSide = int.MaxValue;
-      int width = BinShape.Width;
-      int height = BinShape.Height;
-      int depth = BinShape.Depth;
-
-      if (position.X >= width || position.Y >= height || position.Z >= depth)
-        return shortestSide;
-
-      PackingPosition current = new PackingPosition(0, position.X, position.Y, position.Z);
-      while (current.X < width && IsPointOccupied(current)) { current = PackingPosition.MoveRight(current); }
-      if (current.X - position.X < shortestSide)
-        shortestSide = current.X - position.X;
-
-
-      current = new PackingPosition(0, position.X, position.Y, position.Z);
-      while (current.Y < height && IsPointOccupied(current)) { current = PackingPosition.MoveUp(current); }
-      if (current.Y - position.Y < shortestSide)
-        shortestSide = current.Y - position.Y;
-
-
-      current = new PackingPosition(0, position.X, position.Y, position.Z);
-      while (current.Z < depth && IsPointOccupied(current)) { current = PackingPosition.MoveFront(current); }
-      if (current.Z - position.Z < shortestSide)
-        shortestSide = current.Z - position.Z;
-
-      return shortestSide;
-    }
-    
-
-    protected override void InitializeOccupationLayers() {
-      for (int i = 0; i * 10 <= BinShape.Depth; i += 1) {
-        OccupationLayers[i] = new List<int>();
-      }
-    }
-    protected override void AddNewItemToOccupationLayers(int itemID, PackingItem item, PackingPosition position) {
-      int z1 = position.Z / 10;
-      int z2 = (position.Z + (position.Rotated ? item.Width : item.Depth)) / 10;
-
-      for (int i = z1; i <= z2; i++)
-        OccupationLayers[i].Add(itemID);
-    }
-    protected override List<int> GetLayerItemIDs(PackingPosition position) {
-      return OccupationLayers[position.Z / 10];
-    }
-    protected override List<int> GetLayerItemIDs(PackingItem item, PackingPosition position) {
-      List<int> result = new List<int>();
-      int z1 = position.Z / 10;
-      int z2 = (position.Z + (position.Rotated ? item.Width : item.Depth)) / 10;
-
-      for (int i = z1; i <= z2; i++)
-        result.AddRange(OccupationLayers[i]);
-      return result;
-    }
+
 
     public void UpdateResidualSpace(PackingItem item, PackingPosition pos) {
@@ -762 +760 @@
       return;
     }
-
-
   }
 }

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Decoder/ExtremePointPermutationDecoder.cs

@@ -1 @@
-using HeuristicLab.Core;
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2016 Joseph Helm and Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using HeuristicLab.Core;
 using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
@@ -17 +38 @@
   [Item("Extreme-point Permutation Decoder (3d) Base", "Base class for 3d decoders")]
   [StorableClass]
-  public class ExtremePointPermutationDecoder : Item, IDecoder<Permutation> {
+  public class ExtremePointPermutationDecoder : Item, IDecoder<Permutation>
+    //where TBinPacker : BinPacker, new ()
+    {
 
     [StorableConstructor]
     protected ExtremePointPermutationDecoder(bool deserializing) : base(deserializing) { }
-    protected ExtremePointPermutationDecoder(ExtremePointPermutationDecoderBase original, Cloner cloner)
+    protected ExtremePointPermutationDecoder(ExtremePointPermutationDecoder original, Cloner cloner)
       : base(original, cloner) {
     }
@@ -34 +57 @@
 
     public override IDeepCloneable Clone(Cloner cloner) {
-      throw new NotImplementedException();
+      return new ExtremePointPermutationDecoder(this, cloner);
     }
 
@@ -49 +72 @@
     public Solution Decode(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
       Solution solution = new Solution(binShape, useExtremePoints: true, stackingConstraints: useStackingConstraints);
-      
-      foreach (var packedBin in _binPacker.PackItems()) {
+      foreach (var packedBin in _binPacker.PackItems(permutation, binShape, items, useStackingConstraints)) {
         solution.Bins.Add(packedBin);
       }

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Evaluators/PackingRatioEvaluator.cs

@@ -47 +47 @@
     }
 
-    /* 
-        Falkenauer:1996 - A Hybrid Grouping Genetic Algorithm for Bin Packing
-        
-        fBPP = (SUM[i=1..N](Fi / C)^k)/N
-        N.......the number of bins used in the solution,
-        Fi......the sum of sizes of the items in the bin i (the fill of the bin),
-        C.......the bin capacity and
-        k.......a constant, k>1.
-     */
+    /// <summary>
+    /// Falkenauer:1996 - A Hybrid Grouping Genetic Algorithm for Bin Packing
+    /// fBPP = (SUM[i=1..N](Fi / C)^k)/N
+    /// N.......the number of bins used in the solution,
+    /// Fi......the sum of sizes of the items in the bin i (the fill of the bin),
+    /// C.......the bin capacity and
+    /// k.......a constant, k>1.
+    /// </summary>
+    /// <param name="solution"></param>
+    /// <returns></returns>
     public static double CalculatePackingRatio(Solution solution) {
       int nrOfBins = solution.NrOfBins;

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPacker.cs

@@ -1 @@
-using HeuristicLab.Core;
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2016 Joseph Helm and Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using HeuristicLab.Core;
 using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
@@ -13 +34 @@
   [StorableClass]
   public abstract class BinPacker {
-    protected Permutation _permutation;
-    protected PackingShape _binShape;
-    protected IList<PackingItem> _items;
-    protected bool _useStackingConstraints;
+    
+    public BinPacker() { }
 
     /// <summary>
     /// Packs all items of the bin packer and returns a collection of BinPacking3D objects
     /// </summary>
+    /// <param name="sortedItems">Permutation of items sorted by a sorting method. The value of each permutation index references to the index of the items list</param>
+    /// <param name="binShape">Bin for storing the items</param>
+    /// <param name="items">A list of packing items which should be assigned to a bin</param>
+    /// <param name="useStackingConstraints">Flag for using stacking constraints</param>
     /// <returns></returns>
-    public abstract IList<BinPacking3D> PackItems();
+    public abstract IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints);
 
-    /// <summary>
-    /// Tries to pack the remainig items into a given BinPacking3D object. Each item could be packed into the BinPacking3D object will be removed from the list of remaining ids
-    /// </summary>
-    /// <param name="remainingIds">List of remaining ids. After the method has been executed the list has to have less items</param>
-    /// <param name="items">List of packing items. Some of the items will be assigned to the BinPacking3D object</param>
-    /// <param name="packingBin">This object will be filled with some of the given items</param>
-    protected void PackRemainingItems(ref IList<int> remainingIds, ref BinPacking3D packingBin, IList<PackingItem> items, bool useStackingConstraints, Dictionary<int, bool> rotationArray) {
-
-      foreach (var itemId in new List<int>(remainingIds)) {
-        bool rotated = rotationArray == null ? false : rotationArray[itemId];
-        PackingPosition position = FindPackingPositionForItem(packingBin, items[itemId], useStackingConstraints, rotated);
-        // if a valid packing position could be found, the current item can be added to the given bin
-        if (position != null) {
-          PackItem(ref packingBin, itemId, items[itemId], position, useStackingConstraints);
-          remainingIds.Remove(itemId);
-        }
-      }
-    }
+    
 
     /// <summary>
@@ -52 +58 @@
     protected void PackItem(ref BinPacking3D packingBin, int itemId, PackingItem packingItem, PackingPosition position, bool useStackingConstraints) {
 
-      packingBin.AddItem(itemId, packingItem, position);
+      packingBin.PackItem(itemId, packingItem, position);
       packingBin.UpdateResidualSpace(packingItem, position);
       packingBin.UpdateExtremePoints(packingItem, position, useStackingConstraints);

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFirstFit.cs

@@ -1 @@
-using HeuristicLab.Core;
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2016 Joseph Helm and Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using HeuristicLab.Core;
 using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
@@ -14 +35 @@
   public class BinPackerFirstFit : BinPacker {
 
-    public BinPackerFirstFit(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
-      _permutation = permutation;
-      _binShape = binShape;
-      _items = items;
-      _useStackingConstraints = useStackingConstraints;
-    }
-
+    public BinPackerFirstFit() : base() { }    
 
     /// <summary>
@@ -26 +41 @@
     /// </summary>
     /// <returns>Returns a collection of bin packing 3d objects. Each object represents a bin and the packed items</returns>
-    public override IList<BinPacking3D> PackItems() {
+    public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
       IList<BinPacking3D> packingList = new List<BinPacking3D>();
-      IList<int> remainingIds = new List<int>(_permutation);
+      IList<int> remainingIds = new List<int>(sortedItems);
 
       while (remainingIds.Count > 0) {
-        BinPacking3D packingBin = new BinPacking3D(_binShape);
-        PackRemainingItems(ref remainingIds, ref packingBin, _items, _useStackingConstraints, null);
+        BinPacking3D packingBin = new BinPacking3D(binShape);
+        PackRemainingItems(ref remainingIds, ref packingBin, items, useStackingConstraints, null);
         packingList.Add(packingBin);
       }
@@ -38 +53 @@
       return packingList;
     }
+
+    /// <summary>
+    /// Tries to pack the remainig items into a given BinPacking3D object. Each item could be packed into the BinPacking3D object will be removed from the list of remaining ids
+    /// </summary>
+    /// <param name="remainingIds">List of remaining ids. After the method has been executed the list has to have less items</param>
+    /// <param name="items">List of packing items. Some of the items will be assigned to the BinPacking3D object</param>
+    /// <param name="packingBin">This object will be filled with some of the given items</param>
+    protected void PackRemainingItems(ref IList<int> remainingIds, ref BinPacking3D packingBin, IList<PackingItem> items, bool useStackingConstraints, Dictionary<int, bool> rotationArray) {
+
+      foreach (var itemId in new List<int>(remainingIds)) {
+        bool rotated = rotationArray == null ? false : rotationArray[itemId];
+        PackingPosition position = FindPackingPositionForItem(packingBin, items[itemId], useStackingConstraints, rotated);
+        // if a valid packing position could be found, the current item can be added to the given bin
+        if (position != null) {
+          PackItem(ref packingBin, itemId, items[itemId], position, useStackingConstraints);
+          remainingIds.Remove(itemId);
+        }
+      }
+    }
   }
 }

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFreeVolumeBestFit.cs

@@ -1 @@
-using HeuristicLab.Core;
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2016 Joseph Helm and Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using HeuristicLab.Core;
 using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
@@ -12 +33 @@
   [StorableClass]
   public class BinPackerFreeVolumeBestFit : BinPacker {
-    public BinPackerFreeVolumeBestFit(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
-      _permutation = permutation;
-      _binShape = binShape;
-      _items = items;
-      _useStackingConstraints = useStackingConstraints;
-    }
 
-    public override IList<BinPacking3D> PackItems() {
+    public BinPackerFreeVolumeBestFit() : base() { }
+
+    public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
       IList<BinPacking3D> packingList = new List<BinPacking3D>();
-      IList<int> remainingIds = new List<int>(_permutation);
-      
+      IList<int> remainingIds = new List<int>(sortedItems);
+
 
       foreach (int remainingId in remainingIds) {
         var sortedBins = packingList.OrderBy(x => x.FreeVolume);
-        PackingItem item = _items[remainingId];
+        var z = sortedBins.ToList();
+
+        PackingItem item = items[remainingId];
         bool positionFound = false;
 
         foreach (var packingBin in sortedBins) {
-          PackingPosition position = FindPackingPositionForItem(packingBin, item, _useStackingConstraints, false);
+          PackingPosition position = FindPackingPositionForItem(packingBin, item, useStackingConstraints, false);
           positionFound = position != null;
           var bin = packingBin;
           if (positionFound) {
-            PackItem(ref bin, remainingId, item, position, _useStackingConstraints);
+            PackItem(ref bin, remainingId, item, position, useStackingConstraints);
             break;
-          }            
+          }
         }
 
         if (!positionFound) {
-          BinPacking3D packingBin = new BinPacking3D(_binShape);
-          PackingPosition position = FindPackingPositionForItem(packingBin, item, _useStackingConstraints, false);
+          BinPacking3D packingBin = new BinPacking3D(binShape);
+          PackingPosition position = FindPackingPositionForItem(packingBin, item, useStackingConstraints, false);
 
           if (position == null) {
@@ -47 +66 @@
           }
 
-          PackItem(ref packingBin, remainingId, item, position, _useStackingConstraints);
+          PackItem(ref packingBin, remainingId, item, position, useStackingConstraints);
           packingList.Add(packingBin);
         }

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerResidualSpaceBestFit.cs

@@ -1 @@
-using HeuristicLab.Core;
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2016 Joseph Helm and Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using HeuristicLab.Core;
 using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
@@ -12 +33 @@
   [StorableClass]
   public class BinPackerResidualSpaceBestFit : BinPacker {
-    public BinPackerResidualSpaceBestFit(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
-      _permutation = permutation;
-      _binShape = binShape;
-      _items = items;
-      _useStackingConstraints = useStackingConstraints;
-    }
 
+    public BinPackerResidualSpaceBestFit() : base() { }/*
+    public BinPackerResidualSpaceBestFit(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints)
+      : base(permutation, binShape, items, useStackingConstraints) { }
+      */
     /// <summary>
     /// Packs the items into the bins by using a best fit residual space algorithm.
@@ -25 +44 @@
     /// </summary>
     /// <returns></returns>
-    public override IList<BinPacking3D> PackItems() {
+    public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
       IList<BinPacking3D> packingList = new List<BinPacking3D>();
-      IList<int> remainingIds = new List<int>(_permutation);
+      IList<int> remainingIds = new List<int>(sortedItems);
       bool rotated = false;
 
       foreach (var remainingId in remainingIds) {
-        PackingItem item = _items[remainingId];
+        PackingItem item = items[remainingId];
         var residualSpacePoints = GetResidualSpaceForAllPoints(packingList, item);
         var sortedPoints = residualSpacePoints.OrderBy(x => x.Item3);
@@ -37 +56 @@
 
         foreach (var point in sortedPoints) {
-          if (point.Item1.IsPositionFeasible(item, point.Item2, _useStackingConstraints)) {
+          if (point.Item1.IsPositionFeasible(item, point.Item2, useStackingConstraints)) {
             var binPacking = point.Item1;
-            PackItem(ref binPacking, remainingId, item, point.Item2, _useStackingConstraints);
+            PackItem(ref binPacking, remainingId, item, point.Item2, useStackingConstraints);
             packed = true;
             break;
@@ -46 +65 @@
 
         if (!packed) {
-          BinPacking3D binPacking = new BinPacking3D(_binShape);
-          var position = FindPackingPositionForItem(binPacking, item, _useStackingConstraints, rotated);
+          BinPacking3D binPacking = new BinPacking3D(binShape);
+          var position = FindPackingPositionForItem(binPacking, item, useStackingConstraints, rotated);
           if (position != null) {
-            PackItem(ref binPacking, remainingId, item, position, _useStackingConstraints);
+            PackItem(ref binPacking, remainingId, item, position, useStackingConstraints);
           } else {
             throw new InvalidOperationException("Item " + remainingId + " cannot be packed in an empty bin.");

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/PackingPosition.cs

@@ -115 +115 @@
       if (result == 0)
         result = Y.CompareTo(other.Y);
-
+      
       return result;
 

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/PermutationEncoding/PermutationProblem.cs

@@ -30 +30 @@
 using HeuristicLab.Optimization.Operators;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Problems.BinPacking3D.Decoder;
+using HeuristicLab.Problems.BinPacking3D.Packer;
 
 namespace HeuristicLab.Problems.BinPacking3D {
@@ -47 +49 @@
     public PermutationProblem()
       : base() {
-      Decoder = new ExtremePointPermutationDecoder(); // default decoder
+      Decoder = new ExtremePointPermutationDecoder(new BinPackerFirstFit()); // default decoder
 
       Encoding = new PermutationEncoding(EncodedSolutionName, Items.Count, PermutationTypes.Absolute);