Changeset 9495 for branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Decoders/3D/DBL/DeepestBottomLeftFunctions.cs

Timestamp:

05/15/13 22:23:36 (11 years ago)

Author:

jhelm

Message:

#1966: Did some major refactoring in Decoder-classes; Added MoveEvaluator classes for different encodings and dimensions; Added new crossover-class for MCV encoding;

File:

• branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Decoders/3D/DBL/DeepestBottomLeftFunctions.cs (modified) (3 diffs)

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Decoders/3D/DBL/DeepestBottomLeftFunctions.cs

@@ -6 +6 @@
 using HeuristicLab.Core;
 using HeuristicLab.Encodings.PackingEncoding.GroupingVector;
+using HeuristicLab.Encodings.PackingEncoding.MultiComponentVector;
 using HeuristicLab.Encodings.PackingEncoding.PackingSequence;
 using HeuristicLab.Problems.BinPacking.Dimensions;
@@ -16 +17 @@
   public static class DeepestBottomLeftFunctions {
 
+    public static ObservableDictionary<int, ThreeDimensionalPacking> DeepestLeftBottomPacking(MultiComponentVectorEncoding solution, CuboidPackingBin binMeasures, ItemList<CuboidPackingItem> itemMeasures) {
+      int nrOfBins = solution.NrOfBins;
+
+      //Get all indexes of items for every bin according to grouping-vector
+      Dictionary<int, List<PackingInformation>> unpackedItemIndexesPerBin = new Dictionary<int, List<PackingInformation>>();
+
+      for (int i = 0; i < nrOfBins; i++) {
+        unpackedItemIndexesPerBin[i] = new List<PackingInformation>(solution.PackingInformations[i]);
+      }
+
+      ObservableDictionary<int, ThreeDimensionalPacking> packingPositions = new ObservableDictionary<int, ThreeDimensionalPacking>();
+      var remainingItems = new List<PackingInformation>();
+
+      //Iterate over all bin-lists
+      for (int binNr = 0; binNr < nrOfBins; binNr++) {
+        //Iterate over the current bin-item-list and find feasible positions in the current bin for each item
+        var unpackedItems = unpackedItemIndexesPerBin[binNr];
+        for (int i = 0; i < unpackedItems.Count; i++) {
+          var itemIndex = unpackedItems[i].ItemID;
+          var item = itemMeasures[itemIndex];
+          ThreeDimensionalPacking position = null;
+
+          position = DeepestBottomLeftFunctions.DeepestLeftBottomPosition(binMeasures, binNr, item, packingPositions, itemMeasures, unpackedItems[i].Rotated);
+
+          if (position == null) {
+            position = DeepestBottomLeftFunctions.DeepestLeftBottomPosition(binMeasures, binNr, item, packingPositions, itemMeasures, !unpackedItems[i].Rotated);
+          }
+          if (position == null) {
+            remainingItems.Add(unpackedItems[i]);
+            solution.PackingInformations[binNr].Remove(unpackedItems[i]);
+          } else {
+            packingPositions[itemIndex] = position;
+            solution.PackingInformations[binNr].Find(pi => pi.ItemID == itemIndex).Rotated = position.Rotated;
+          }
+        }
+      }
+
+      //Packing of remaining items
+      //Iterate over all bin-lists
+      for (int binNr = 0; binNr < nrOfBins && remainingItems.Count > 0; binNr++) {
+        var unpackedItems = new List<PackingInformation>(remainingItems);
+        for (int i = 0; i < unpackedItems.Count; i++) {
+          var itemIndex = unpackedItems[i].ItemID;
+          var item = itemMeasures[itemIndex];
+          ThreeDimensionalPacking position = null;
+
+          //Look for space in current bin
+          position = DeepestBottomLeftFunctions.DeepestLeftBottomPosition(binMeasures, binNr, item, packingPositions, itemMeasures, unpackedItems[i].Rotated);
+
+          if (position == null) {
+            position = DeepestBottomLeftFunctions.DeepestLeftBottomPosition(binMeasures, binNr, item, packingPositions, itemMeasures, !unpackedItems[i].Rotated);
+          }
+          if (position != null) {
+            packingPositions[itemIndex] = position;
+            remainingItems.Remove(unpackedItems[i]);
+            solution.PackingInformations[binNr].Add(unpackedItems[i]);
+            solution.PackingInformations[binNr].Find(pi => pi.ItemID == itemIndex).Rotated = position.Rotated;
+          }
+        }
+        if (remainingItems.Count > 0 && binNr + 1 >= nrOfBins) {
+          solution.PackingInformations[nrOfBins] = new ItemList<PackingInformation>();
+          nrOfBins++;
+        }
+      }
+
+      return packingPositions;
+    }
+
     public static ObservableDictionary<int, ThreeDimensionalPacking> DeepestLeftBottomPacking(GroupingVectorEncoding solution, CuboidPackingBin binMeasures, ItemList<CuboidPackingItem> itemMeasures) {
       int nrOfBins = solution.GroupingVector.Max() + 1;
@@ -77 +146 @@
     }
 
-
+    public static ObservableDictionary<int, ThreeDimensionalPacking> DeepestLeftBottomPacking(PackingSequenceEncoding solution, CuboidPackingBin binMeasures, ItemList<CuboidPackingItem> itemMeasures) {
+      ObservableDictionary<int, ThreeDimensionalPacking> packingPositions = new ObservableDictionary<int, ThreeDimensionalPacking>();
+      int nrOfBins = 1;
+      for (int i = 0; i < solution.PackingSequence.Length; i++) {
+        var item = itemMeasures[solution.PackingSequence[i]];
+        ThreeDimensionalPacking position = null;
+        //Look for space in existing bins
+        for (int binNr = 0; binNr < nrOfBins; binNr++) {
+          position = DeepestBottomLeftFunctions.DeepestLeftBottomPosition(binMeasures, binNr, item, packingPositions, itemMeasures);
+          if (position != null)
+            break;
+        }
+        //Did not find enough space in any of the existing bins => create new bin
+        if (position == null) {
+          nrOfBins++;
+          position = DeepestBottomLeftFunctions.DeepestLeftBottomPosition(binMeasures, nrOfBins - 1, item, packingPositions, itemMeasures);
+        }
+
+        if (position == null)
+          position = new ThreeDimensionalPacking(-1, 0, 0, 0);
+
+        packingPositions[solution.PackingSequence[i]] = position;
+      }
+
+      return packingPositions;
+    }
 
     public static ThreeDimensionalPacking DeepestLeftBottomPosition(CuboidPackingBin binMeasures, int binNr, CuboidPackingItem currentItem, ObservableDictionary<int, ThreeDimensionalPacking> itemPositions, ItemList<CuboidPackingItem> itemMeasures) {