Changeset 9473 for branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Decoders/3D

Timestamp:

05/09/13 15:03:41 (12 years ago)

Author:

jhelm

Message:

#1966: Fixed some problems in MCV-move operators; Added parts of potvin-encoding implementation;

Location:

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Decoders/3D/EP

Files:

• ExtremePointPotvinDecoder3D.cs (added)
• ExtremePointsFunctions3D.cs (modified) (8 diffs)

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Decoders/3D/EP/ExtremePointsFunctions3D.cs

@@ -5 +5 @@
 using HeuristicLab.Collections;
 using HeuristicLab.Core;
+using HeuristicLab.Encodings.IntegerVectorEncoding;
 using HeuristicLab.Encodings.PackingEncoding.GroupingVector;
 using HeuristicLab.Encodings.PackingEncoding.MultiComponentVector;
 using HeuristicLab.Encodings.PackingEncoding.PackingSequence;
+using HeuristicLab.Encodings.PackingEncoding.Potvin;
 using HeuristicLab.Problems.BinPacking.Dimensions;
 using HeuristicLab.Problems.BinPacking.Interfaces;
@@ -18 +20 @@
 
 
+
+    public static ObservableDictionary<int, ThreeDimensionalPacking> ExtremePointBasedPacking(ref PotvinEncoding solution, 
+      ItemList<CuboidPackingItem> itemMeasures, CuboidPackingBin binMeasures) {
+        if (!solution.DelimiterInitialized) {
+          #region Preperations
+          var itemPositions = new ObservableDictionary<int, ThreeDimensionalPacking>();
+          int nrOfBins = 1;
+
+          var occupiedPoints = new List<int[, ,]>();
+          occupiedPoints = IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
+
+          HashSet<ThreeDimensionalPacking> extremePoints = new HashSet<ThreeDimensionalPacking>();
+          extremePoints.Add(new ThreeDimensionalPacking(0, 0, 0, 0, false));
+          #endregion
+
+          Dictionary<int, List<int>> itemIndexesForBin = new Dictionary<int, List<int>>();
+          itemIndexesForBin[0] = new List<int>();
+
+          foreach (int itemIndex in solution.IntVector) {
+            var item = itemMeasures[itemIndex];
+            extremePoints = OrderExtremePoints(extremePoints, occupiedPoints, binMeasures);
+            var positionFound = FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePoints, occupiedPoints, itemPositions);
+            if (positionFound != null) {
+              extremePoints.Remove(positionFound);
+            } else {
+              positionFound = new ThreeDimensionalPacking(nrOfBins, 0, 0, 0);
+              occupiedPoints = IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
+              itemIndexesForBin[nrOfBins] = new List<int>();
+              nrOfBins++;
+            }
+            itemPositions[itemIndex] = positionFound;
+            itemIndexesForBin[positionFound.AssignedBin].Add(itemIndex);
+            occupiedPoints = OccupyPointsForNewItem(occupiedPoints, item, positionFound, itemIndex);
+            extremePoints = GenerateNewExtremePointsForNewItem(extremePoints, occupiedPoints, item, positionFound, binMeasures);
+          }
+          List<int> intVector = new List<int>();
+          foreach (var indexes in itemIndexesForBin) {
+            foreach (var index in indexes.Value) {
+              intVector.Add(index);
+            }
+            intVector.Add(-1);
+          }
+          intVector.RemoveAt(intVector.Count - 1);
+          solution.IntVector = new IntegerVector (intVector.ToArray());
+
+          return itemPositions;
+        } else {
+          #region Preperations
+          int nrOfBins = solution.IntVector.Count(i => i.Equals (-1)) + 1;
+
+          //Get all indexes of items for every bin according to int vector
+          Dictionary<int, List<int>> unpackedItemIndexesPerBin = new Dictionary<int, List<int>>();
+          Dictionary<int, HashSet<ThreeDimensionalPacking>> extremePointsForBin = new Dictionary<int, HashSet<ThreeDimensionalPacking>>();
+          var occupiedPoints = new List<int[, ,]>();
+
+          int binCounter = 0;
+          unpackedItemIndexesPerBin[binCounter] = new List<int>();
+          for (int i = 0; i < solution.IntVector.Length; i++) {
+            if (solution.IntVector[i].Equals(-1)) {
+              unpackedItemIndexesPerBin[binCounter++] = new List<int>();
+              extremePointsForBin[i] = new HashSet<ThreeDimensionalPacking>();
+              extremePointsForBin[i].Add(new ThreeDimensionalPacking(i, 0, 0, 0, false));
+              occupiedPoints = IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
+            } else {
+              unpackedItemIndexesPerBin[binCounter].Add(solution.IntVector[i]);
+            }
+
+          }
+
+
+          ObservableDictionary<int, ThreeDimensionalPacking> itemPositions = new ObservableDictionary<int, ThreeDimensionalPacking>();
+          var remainingItems = new List<int>();
+
+          #endregion Preperations
+
+
+
+          //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];
+              var item = itemMeasures[itemIndex];
+
+              extremePointsForBin[binNr] = OrderExtremePoints(extremePointsForBin[binNr], occupiedPoints, binMeasures);
+              var positionFound = FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePointsForBin[binNr], occupiedPoints, itemPositions);
+              if (positionFound != null) {
+                extremePointsForBin[binNr].Remove(positionFound);
+                itemPositions[itemIndex] = positionFound;
+                occupiedPoints = OccupyPointsForNewItem(occupiedPoints, item, positionFound, itemIndex);
+                extremePointsForBin[binNr] = GenerateNewExtremePointsForNewItem(extremePointsForBin[binNr], occupiedPoints, item, positionFound, binMeasures);
+              } else
+                remainingItems.Add(itemIndex);
+            }
+          }
+
+
+
+          //Packing of remaining items    
+          //Iterate over all bin-lists
+          for (int binNr = 0; binNr < nrOfBins && remainingItems.Count > 0; binNr++) {
+            var unpackedItems = new List<int>(remainingItems);
+            //Iterate over all the remaining items
+            for (int i = 0; i < unpackedItems.Count; i++) {
+              var itemIndex = unpackedItems[i];
+              var item = itemMeasures[itemIndex];
+
+              extremePointsForBin[binNr] = OrderExtremePoints(extremePointsForBin[binNr], occupiedPoints, binMeasures);
+              var positionFound = FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePointsForBin[binNr], occupiedPoints, itemPositions);
+              if (positionFound != null) {
+                extremePointsForBin[binNr].Remove(positionFound);
+                InsertItemgeneAfterLastItemgeneOfUsedBin(ref solution, itemIndex, binNr);
+                itemPositions[itemIndex] = positionFound;
+                occupiedPoints = OccupyPointsForNewItem(occupiedPoints, item, positionFound, itemIndex);
+                extremePointsForBin[binNr] = GenerateNewExtremePointsForNewItem(extremePointsForBin[binNr], occupiedPoints, item, positionFound, binMeasures);
+                remainingItems.Remove(itemIndex);
+              }
+            }
+            if (remainingItems.Count > 0 && binNr + 1 >= nrOfBins) {
+              extremePointsForBin[nrOfBins] = new HashSet<ThreeDimensionalPacking>();
+              extremePointsForBin[nrOfBins].Add(new ThreeDimensionalPacking(nrOfBins, 0, 0, 0, false));
+              occupiedPoints = IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
+              nrOfBins++;
+            }
+          }
+
+          return itemPositions;
+        }
+    }
+    private static void InsertItemgeneAfterLastItemgeneOfUsedBin(ref PotvinEncoding solution, int itemIndex, int binNr) { 
+      List<int> temp = new List<int> (solution.IntVector);
+      temp.Remove(itemIndex);
+      var delimiterIndexes = temp.Select((value, index) => value == -1).Select((value, index) => index);
+      int insertionIndex = temp.Count; 
+      if (binNr < delimiterIndexes.Count()) {
+        insertionIndex = delimiterIndexes.ElementAt(binNr);
+      }
+      temp.Insert(insertionIndex, itemIndex);
+      solution.IntVector = new IntegerVector (temp.ToArray());
+    }
 
 
@@ -56 +199 @@
           var item = itemMeasures[itemIndex];
 
-          extremePointsForBin[binNr] = new HashSet<ThreeDimensionalPacking>(extremePointsForBin[binNr].OrderBy(ep => ep.AssignedBin).ThenBy(ep => ShortestPossibleSideFromEP(ep, occupiedPoints, binMeasures)));
+          extremePointsForBin[binNr] = OrderExtremePoints(extremePointsForBin[binNr], occupiedPoints, binMeasures);
           var positionFound = FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePointsForBin[binNr], occupiedPoints, itemPositions, unpackedItems[i].Rotated);
           if (positionFound != null) {
@@ -78 +221 @@
           var item = itemMeasures[itemIndex];
 
-          extremePointsForBin[binNr] = new HashSet<ThreeDimensionalPacking>(extremePointsForBin[binNr].OrderBy(ep => ep.AssignedBin).ThenBy(ep => ShortestPossibleSideFromEP(ep, occupiedPoints, binMeasures)));
+          extremePointsForBin[binNr] = OrderExtremePoints(extremePointsForBin[binNr], occupiedPoints, binMeasures);
           var positionFound = FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePointsForBin[binNr], occupiedPoints, itemPositions, unpackedItems[i].Rotated);
           if (positionFound != null) {
@@ -147 +290 @@
           var item = itemMeasures[itemIndex];
 
-          extremePointsForBin[binNr] = new HashSet<ThreeDimensionalPacking>(extremePointsForBin[binNr].OrderBy(ep => ep.AssignedBin).ThenBy(ep => ShortestPossibleSideFromEP(ep, occupiedPoints, binMeasures)));
+          extremePointsForBin[binNr] = OrderExtremePoints(extremePointsForBin[binNr], occupiedPoints, binMeasures);
           var positionFound = FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePointsForBin[binNr], occupiedPoints, itemPositions);
           if (positionFound != null) {
@@ -170 +313 @@
           var item = itemMeasures[itemIndex];
 
-          extremePointsForBin[binNr] = new HashSet<ThreeDimensionalPacking>(extremePointsForBin[binNr].OrderBy(ep => ep.AssignedBin).ThenBy(ep => ShortestPossibleSideFromEP(ep, occupiedPoints, binMeasures)));
+          extremePointsForBin[binNr] = OrderExtremePoints(extremePointsForBin[binNr], occupiedPoints, binMeasures);
           var positionFound = FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePointsForBin[binNr], occupiedPoints, itemPositions);
           if (positionFound != null) {
@@ -208 +351 @@
       foreach (int itemIndex in solution.PackingSequence) {
         var item = itemMeasures[itemIndex];
-        extremePoints = new HashSet<ThreeDimensionalPacking>(extremePoints.OrderBy(ep => ep.AssignedBin).ThenBy(ep => ShortestPossibleSideFromEP(ep, occupiedPoints, binMeasures)));
+        extremePoints = OrderExtremePoints(extremePoints, occupiedPoints, binMeasures);
         var positionFound = FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePoints, occupiedPoints, itemPositions);
         if (positionFound != null) {
@@ -373 +516 @@
       return extremePoints;
     }
+
+
+    private static HashSet<ThreeDimensionalPacking> OrderExtremePoints(HashSet<ThreeDimensionalPacking> hashSet, List<int[, ,]> occupiedPoints, CuboidPackingBin binMeasures) {
+      return new HashSet<ThreeDimensionalPacking>(hashSet.OrderBy(ep => ep.AssignedBin).ThenBy(ep => ep.Z).ThenBy(ep => ep.X).ThenBy(ep => ep.Y).ThenBy(ep => ShortestPossibleSideFromEP(ep, occupiedPoints, binMeasures)));
+    }
     private static int ShortestPossibleSideFromEP(ThreeDimensionalPacking ep, List<int[, ,]> occupiedPoints, CuboidPackingBin binMeasures) {
       int shortestSide = int.MaxValue;