Changeset 15229 for branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/PermutationEncoding/ResidualSpaceBestFitExtremePointPermutationDecoder.cs

Timestamp:

07/13/17 15:22:59 (7 years ago)

Author:

abeham

Message:

#2762:

• Implemented review comments
• Fixed ResidualSpaceBestFitExtremePointPermutationDecoder by sorting from smallest to largest (merit function should be minimized)
• Some restructuring of the methods

File:

• branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/PermutationEncoding/ResidualSpaceBestFitExtremePointPermutationDecoder.cs (modified) (2 diffs)

branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/PermutationEncoding/ResidualSpaceBestFitExtremePointPermutationDecoder.cs

@@ -44 +44 @@
 
     public override Solution Decode(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
+      return Apply(permutation, binShape, items, useStackingConstraints);
+    }
+
+    public static Solution Apply(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
       Solution result = new Solution(binShape, useExtremePoints: true, stackingConstraints: useStackingConstraints);
       IList<int> remainingIDs = new List<int>(permutation);
-      Dictionary<Tuple<BinPacking3D,PackingPosition>, int> points = new Dictionary<Tuple<BinPacking3D,PackingPosition>,int>();
       var bpg = new BinPacking3D(binShape);
       bpg.ExtremePointBasedPacking(ref remainingIDs, items, stackingConstraints: useStackingConstraints);
       result.Bins.Add(bpg);
       foreach (int ID in remainingIDs) {
-        points = GetResidualSpaceAllPoints(result, items[ID]);
-        var sortedPoints = points.OrderByDescending(x => x.Value).ToDictionary(x => x.Key, x => x.Value);
-        if (!ExtremePointBasedPacking(sortedPoints, ID, items, stackingConstraints: useStackingConstraints)) { 
+        var item = items[ID];
+        var points = GetResidualSpaceAllPoints(result, item);
+        var sortedPoints = points.OrderBy(x => x.Item3);
+        var packed = false;
+        foreach (var p in sortedPoints) {
+          packed = p.Item1.PackItemIfFeasible(ID, item, p.Item2, useStackingConstraints);
+          if (packed) break;
+        }
+        if (!packed) {
+          // pack item in a new bin
           var bp = new BinPacking3D(binShape);
-          bp.ExtremePointBasedPacking(ID, items, stackingConstraints: useStackingConstraints);
+          var positionFound = bp.FindExtremePointForItem(item, false, useStackingConstraints);
+          if (positionFound != null) {
+            bp.PackItem(ID, item, positionFound);
+          } else throw new InvalidOperationException("Item " + ID + " cannot be packed in an empty bin.");
           result.Bins.Add(bp);
         }
@@ -62 +75 @@
       return result;
     }
+
+    public static IList<Tuple<BinPacking3D, PackingPosition, int>> GetResidualSpaceAllPoints(Solution solution, PackingItem item) {
+      var result = new List<Tuple<BinPacking3D, PackingPosition, int>>();
+      foreach (BinPacking3D bp in solution.Bins) {
+        foreach (var ep in bp.ExtremePoints) {
+          var rs = bp.ResidualSpace[ep];
+          if (rs.Item1 < item.Width || rs.Item2 < item.Height || rs.Item3 < item.Depth) continue;
+          result.Add(Tuple.Create(bp, ep, GetResidualMerit(rs, item, ep)));
+        }
+      }
+      return result;
+    }
+
+    private static int GetResidualMerit(Tuple<int, int, int> rs, PackingItem item, PackingPosition ep) {
+      return ((rs.Item1 - item.Width) +
+          (rs.Item2 - item.Height) +
+          (rs.Item3 - item.Depth));
+    }
   }
 }