Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
05/15/13 22:23:36 (12 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;

Location:
branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Decoders/3D
Files:
1 added
8 edited

Legend:

Unmodified
Added
Removed

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

    r9440 r9495  
    66using HeuristicLab.Core;
    77using HeuristicLab.Encodings.PackingEncoding.GroupingVector;
     8using HeuristicLab.Encodings.PackingEncoding.MultiComponentVector;
    89using HeuristicLab.Encodings.PackingEncoding.PackingSequence;
    910using HeuristicLab.Problems.BinPacking.Dimensions;
    … …  
    1617  public static class DeepestBottomLeftFunctions {
    1718
     19    public static ObservableDictionary<int, ThreeDimensionalPacking> DeepestLeftBottomPacking(MultiComponentVectorEncoding solution, CuboidPackingBin binMeasures, ItemList<CuboidPackingItem> itemMeasures) {
     20      int nrOfBins = solution.NrOfBins;
     21
     22      //Get all indexes of items for every bin according to grouping-vector
     23      Dictionary<int, List<PackingInformation>> unpackedItemIndexesPerBin = new Dictionary<int, List<PackingInformation>>();
     24
     25      for (int i = 0; i < nrOfBins; i++) {
     26        unpackedItemIndexesPerBin[i] = new List<PackingInformation>(solution.PackingInformations[i]);
     27      }
     28
     29      ObservableDictionary<int, ThreeDimensionalPacking> packingPositions = new ObservableDictionary<int, ThreeDimensionalPacking>();
     30      var remainingItems = new List<PackingInformation>();
     31
     32      //Iterate over all bin-lists
     33      for (int binNr = 0; binNr < nrOfBins; binNr++) {
     34        //Iterate over the current bin-item-list and find feasible positions in the current bin for each item
     35        var unpackedItems = unpackedItemIndexesPerBin[binNr];
     36        for (int i = 0; i < unpackedItems.Count; i++) {
     37          var itemIndex = unpackedItems[i].ItemID;
     38          var item = itemMeasures[itemIndex];
     39          ThreeDimensionalPacking position = null;
     40
     41          position = DeepestBottomLeftFunctions.DeepestLeftBottomPosition(binMeasures, binNr, item, packingPositions, itemMeasures, unpackedItems[i].Rotated);
     42
     43          if (position == null) {
     44            position = DeepestBottomLeftFunctions.DeepestLeftBottomPosition(binMeasures, binNr, item, packingPositions, itemMeasures, !unpackedItems[i].Rotated);
     45          }
     46          if (position == null) {
     47            remainingItems.Add(unpackedItems[i]);
     48            solution.PackingInformations[binNr].Remove(unpackedItems[i]);
     49          } else {
     50            packingPositions[itemIndex] = position;
     51            solution.PackingInformations[binNr].Find(pi => pi.ItemID == itemIndex).Rotated = position.Rotated;
     52          }
     53        }
     54      }
     55
     56      //Packing of remaining items
     57      //Iterate over all bin-lists
     58      for (int binNr = 0; binNr < nrOfBins && remainingItems.Count > 0; binNr++) {
     59        var unpackedItems = new List<PackingInformation>(remainingItems);
     60        for (int i = 0; i < unpackedItems.Count; i++) {
     61          var itemIndex = unpackedItems[i].ItemID;
     62          var item = itemMeasures[itemIndex];
     63          ThreeDimensionalPacking position = null;
     64
     65          //Look for space in current bin
     66          position = DeepestBottomLeftFunctions.DeepestLeftBottomPosition(binMeasures, binNr, item, packingPositions, itemMeasures, unpackedItems[i].Rotated);
     67
     68          if (position == null) {
     69            position = DeepestBottomLeftFunctions.DeepestLeftBottomPosition(binMeasures, binNr, item, packingPositions, itemMeasures, !unpackedItems[i].Rotated);
     70          }
     71          if (position != null) {
     72            packingPositions[itemIndex] = position;
     73            remainingItems.Remove(unpackedItems[i]);
     74            solution.PackingInformations[binNr].Add(unpackedItems[i]);
     75            solution.PackingInformations[binNr].Find(pi => pi.ItemID == itemIndex).Rotated = position.Rotated;
     76          }
     77        }
     78        if (remainingItems.Count > 0 && binNr + 1 >= nrOfBins) {
     79          solution.PackingInformations[nrOfBins] = new ItemList<PackingInformation>();
     80          nrOfBins++;
     81        }
     82      }
     83
     84      return packingPositions;
     85    }
     86
    1887    public static ObservableDictionary<int, ThreeDimensionalPacking> DeepestLeftBottomPacking(GroupingVectorEncoding solution, CuboidPackingBin binMeasures, ItemList<CuboidPackingItem> itemMeasures) {
    1988      int nrOfBins = solution.GroupingVector.Max() + 1;
    … …  
    77146    }
    78147
    79 
     148    public static ObservableDictionary<int, ThreeDimensionalPacking> DeepestLeftBottomPacking(PackingSequenceEncoding solution, CuboidPackingBin binMeasures, ItemList<CuboidPackingItem> itemMeasures) {
     149      ObservableDictionary<int, ThreeDimensionalPacking> packingPositions = new ObservableDictionary<int, ThreeDimensionalPacking>();
     150      int nrOfBins = 1;
     151      for (int i = 0; i < solution.PackingSequence.Length; i++) {
     152        var item = itemMeasures[solution.PackingSequence[i]];
     153        ThreeDimensionalPacking position = null;
     154        //Look for space in existing bins
     155        for (int binNr = 0; binNr < nrOfBins; binNr++) {
     156          position = DeepestBottomLeftFunctions.DeepestLeftBottomPosition(binMeasures, binNr, item, packingPositions, itemMeasures);
     157          if (position != null)
     158            break;
     159        }
     160        //Did not find enough space in any of the existing bins => create new bin
     161        if (position == null) {
     162          nrOfBins++;
     163          position = DeepestBottomLeftFunctions.DeepestLeftBottomPosition(binMeasures, nrOfBins - 1, item, packingPositions, itemMeasures);
     164        }
     165
     166        if (position == null)
     167          position = new ThreeDimensionalPacking(-1, 0, 0, 0);
     168
     169        packingPositions[solution.PackingSequence[i]] = position;
     170      }
     171
     172      return packingPositions;
     173    }
    80174
    81175    public static ThreeDimensionalPacking DeepestLeftBottomPosition(CuboidPackingBin binMeasures, int binNr, CuboidPackingItem currentItem, ObservableDictionary<int, ThreeDimensionalPacking> itemPositions, ItemList<CuboidPackingItem> itemMeasures) {

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

    r9440 r9495  
    4040  [Item("Identical bin three dimensional direct grouping vector decoder", "<Description missing...>")]
    4141  [StorableClass]
    42   public class DeepestBottomLeftGroupingVectorDecoder : IdenticalBinPackingSolutionDecoder<
     42  public class DeepestBottomLeftGroupingVectorDecoder : PackingSolutionDecoder<
    4343      ThreeDimensionalPacking,
    4444      CuboidPackingBin,
    45       CuboidPackingItem,
    46       PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem>> {
     45      CuboidPackingItem> {
    4746
    4847    public DeepestBottomLeftGroupingVectorDecoder()
    … …  
    6059
    6160
    62     protected override PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> CreatePackingPlanFromEncoding(IPackingSolutionEncoding encodedSolution) {
     61    public override PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> CreatePackingPlanFromEncoding(IPackingSolutionEncoding encodedSolution, CuboidPackingBin binMeasures, ItemList<CuboidPackingItem> itemMeasures) {
    6362
    6463      var solution = encodedSolution as GroupingVectorEncoding;

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

    r9440 r9495  
    4141  [Item("Identical bin three dimensional multi component vector decoder", "<Description missing...>")]
    4242  [StorableClass]
    43   public class DeepestBottomLeftMultiComponentVectorDecoder : IdenticalBinPackingSolutionDecoder<
     43  public class DeepestBottomLeftMultiComponentVectorDecoder : PackingSolutionDecoder<
    4444      ThreeDimensionalPacking,
    4545      CuboidPackingBin,
    46       CuboidPackingItem,
    47       PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem>> {
     46      CuboidPackingItem> {
    4847
    4948    public DeepestBottomLeftMultiComponentVectorDecoder()
    … …  
    6160
    6261
    63     protected override PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> CreatePackingPlanFromEncoding(IPackingSolutionEncoding encodedSolution) {
     62    public override PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> CreatePackingPlanFromEncoding(IPackingSolutionEncoding encodedSolution, CuboidPackingBin binMeasures, ItemList<CuboidPackingItem> itemMeasures) {
    6463
    6564      var solution = encodedSolution as MultiComponentVectorEncoding;
    … …  
    6867      PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> result =
    6968        new PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem>(PackingBinMeasuresParameter.ActualValue, PackingItemMeasuresParameter.ActualValue);
    70       int nrOfBins = solution.PackingInformations.Max(pi => pi.AssignedBin) + 1;
    71 
    72       //Get all indexes of items for every bin according to grouping-vector
    73       Dictionary<int, List<PackingInformation>> unpackedItemIndexesPerBin = new Dictionary<int, List<PackingInformation>>();
    74 
    75       for (int i = 0; i < nrOfBins; i++) {
    76         unpackedItemIndexesPerBin[i] = solution.PackingInformations
    77           .Where(pi => pi.AssignedBin == i)
    78           .ToList();
    79       }
    80 
    81       ObservableDictionary<int, ThreeDimensionalPacking> packingPositions = new ObservableDictionary<int, ThreeDimensionalPacking>();
    82       var remainingItems = new List<PackingInformation>();
    83 
    84       //Iterate over all bin-lists
    85       for (int binNr = 0; binNr < nrOfBins; binNr++) {
    86         //Iterate over the current bin-item-list and find feasible positions in the current bin for each item
    87         var unpackedItems = unpackedItemIndexesPerBin[binNr];
    88         for (int i = 0; i < unpackedItems.Count; i++) {
    89           var itemIndex = unpackedItems[i].ItemIndex;
    90           var item = PackingItemMeasuresParameter.ActualValue[itemIndex];
    91           ThreeDimensionalPacking position = null;
    92 
    93           position = DeepestBottomLeftFunctions.DeepestLeftBottomPosition(PackingBinMeasuresParameter.ActualValue, binNr, item, packingPositions, PackingItemMeasuresParameter.ActualValue, unpackedItems[i].Rotated);
    94 
    95           if (position == null) {
    96             position = DeepestBottomLeftFunctions.DeepestLeftBottomPosition(PackingBinMeasuresParameter.ActualValue, binNr, item, packingPositions, PackingItemMeasuresParameter.ActualValue, !unpackedItems[i].Rotated);
    97           }
    98           if (position == null) {
    99             remainingItems.Add(unpackedItems[i]);
    100           } else {
    101             packingPositions[itemIndex] = position;
    102             solution.PackingInformations.Find(pi => pi.ItemIndex == itemIndex).Rotated = position.Rotated;
    103           }
    104         }
    105       }
    106 
    107       //Packing of remaining items
    108       //Iterate over all bin-lists
    109       for (int binNr = 0; binNr < nrOfBins && remainingItems.Count > 0; binNr++) {
    110         var unpackedItems = new List<PackingInformation>(remainingItems);
    111         for (int i = 0; i < unpackedItems.Count; i++) {
    112           var itemIndex = unpackedItems[i].ItemIndex;
    113           var item = PackingItemMeasuresParameter.ActualValue[itemIndex];
    114           ThreeDimensionalPacking position = null;
    115 
    116           //Look for space in current bin
    117           position = DeepestBottomLeftFunctions.DeepestLeftBottomPosition(PackingBinMeasuresParameter.ActualValue, binNr, item, packingPositions, PackingItemMeasuresParameter.ActualValue, unpackedItems[i].Rotated);
    118 
    119           if (position == null) {
    120             position = DeepestBottomLeftFunctions.DeepestLeftBottomPosition(PackingBinMeasuresParameter.ActualValue, binNr, item, packingPositions, PackingItemMeasuresParameter.ActualValue, !unpackedItems[i].Rotated);
    121           }
    122           if (position != null) {   
    123             packingPositions[itemIndex] = position;
    124             remainingItems.Remove(unpackedItems[i]);
    125             solution.PackingInformations.Find(pi => pi.ItemIndex == itemIndex).AssignedBin = binNr;
    126             solution.PackingInformations.Find(pi => pi.ItemIndex == itemIndex).Rotated = position.Rotated;
    127           }
    128         } 
    129         if (remainingItems.Count > 0 && binNr + 1 >= nrOfBins) {
    130           nrOfBins++;
    131         }
    132       }
    133 
    134       result.PackingItemPositions = packingPositions;
     69     
     70      result.PackingItemPositions = DeepestBottomLeftFunctions.DeepestLeftBottomPacking (solution, binMeasures, itemMeasures);
    13571
    13672      return result;

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

    r9440 r9495  
    4040  [Item("Identical bin, three dimensional, direct permutation decoder", "<Description missing...>")]
    4141  [StorableClass]
    42   public class DeepestBottomLeftPackingSequenceDecoder : IdenticalBinPackingSolutionDecoder<
     42  public class DeepestBottomLeftPackingSequenceDecoder : PackingSolutionDecoder<
    4343      ThreeDimensionalPacking,
    4444      CuboidPackingBin,
    45       CuboidPackingItem,
    46       PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem>> {
     45      CuboidPackingItem> {
    4746
    4847    public DeepestBottomLeftPackingSequenceDecoder()
    … …  
    6059
    6160
    62     protected override PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> CreatePackingPlanFromEncoding(IPackingSolutionEncoding encodedSolution) {
     61    public override PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> CreatePackingPlanFromEncoding(IPackingSolutionEncoding encodedSolution, CuboidPackingBin binMeasures, ItemList<CuboidPackingItem> itemMeasures) {
    6362
    6463      var solution = encodedSolution as PackingSequenceEncoding;
    … …  
    6867        new PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem>(PackingBinMeasuresParameter.ActualValue, PackingItemMeasuresParameter.ActualValue);
    6968
    70       ObservableDictionary<int, ThreeDimensionalPacking> packingPositions = new ObservableDictionary<int, ThreeDimensionalPacking>();
    71       int nrOfBins = 1;
    72       for (int i = 0; i < solution.PackingSequence.Length; i++) {
    73         var item = PackingItemMeasuresParameter.ActualValue[solution.PackingSequence[i]];
    74         ThreeDimensionalPacking position = null;
    75         //Look for space in existing bins
    76         for (int binNr = 0; binNr < nrOfBins; binNr++) {
    77           position = DeepestBottomLeftFunctions.DeepestLeftBottomPosition(PackingBinMeasuresParameter.ActualValue, binNr, item, packingPositions, PackingItemMeasuresParameter.ActualValue);
    78           if (position != null)
    79             break;
    80         }
    81         //Did not find enough space in any of the existing bins => create new bin
    82         if (position == null) {
    83           nrOfBins++;
    84           position = DeepestBottomLeftFunctions.DeepestLeftBottomPosition(PackingBinMeasuresParameter.ActualValue, nrOfBins - 1, item, packingPositions, PackingItemMeasuresParameter.ActualValue);
    85         }
    86 
    87         if (position == null)
    88           position = new ThreeDimensionalPacking(-1, 0, 0, 0);
    89 
    90         packingPositions[solution.PackingSequence[i]] = position;
    91       }
    92 
    93       result.PackingItemPositions = packingPositions;
     69      result.PackingItemPositions = DeepestBottomLeftFunctions.DeepestLeftBottomPacking (solution, binMeasures, itemMeasures);
    9470
    9571      return result;

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

    r9440 r9495  
    4141  [Item("Identical bin, three dimensional, extreme points based decoder for the GroupingVector encoding.", "<Description missing...>")]
    4242  [StorableClass]
    43   public class ExtremePointGroupingVectorDecoder3D : IdenticalBinPackingSolutionDecoder<
     43  public class ExtremePointGroupingVectorDecoder3D : PackingSolutionDecoder<
    4444      ThreeDimensionalPacking,
    4545      CuboidPackingBin,
    46       CuboidPackingItem,
    47       PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem>> {
     46      CuboidPackingItem> {
    4847
    4948    public ExtremePointGroupingVectorDecoder3D ()
    … …  
    6867    }
    6968
    70     protected override PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> CreatePackingPlanFromEncoding(IPackingSolutionEncoding encodedSolution) {
     69    public override PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> CreatePackingPlanFromEncoding(IPackingSolutionEncoding encodedSolution, CuboidPackingBin binMeasures, ItemList<CuboidPackingItem> itemMeasures) {
    7170                     
    7271      var solution = encodedSolution as GroupingVectorEncoding;
    7372      if (solution == null) throw new InvalidOperationException("Encoding is not of type GroupingVector");
    7473
    75       return Decode(solution, PackingBinMeasuresParameter.ActualValue, PackingItemMeasuresParameter.ActualValue);
     74      return Decode(solution, binMeasures, itemMeasures);
    7675    }
    7776  }

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

    r9440 r9495  
    4242  [Item("Identical bin, three dimensional, extreme points based decoder for the MultiComponentVector encoding.", "<Description missing...>")]
    4343  [StorableClass]
    44   public class ExtremePointMultiComponentVectorDecoder3D : IdenticalBinPackingSolutionDecoder<
     44  public class ExtremePointMultiComponentVectorDecoder3D : PackingSolutionDecoder<
    4545      ThreeDimensionalPacking,
    4646      CuboidPackingBin,
    47       CuboidPackingItem,
    48       PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem>> {
     47      CuboidPackingItem> {
    4948
    5049    public ExtremePointMultiComponentVectorDecoder3D ()
    … …  
    6968    }
    7069
    71     protected override PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> CreatePackingPlanFromEncoding(IPackingSolutionEncoding encodedSolution) {
     70    public override PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> CreatePackingPlanFromEncoding(IPackingSolutionEncoding encodedSolution, CuboidPackingBin binMeasures, ItemList<CuboidPackingItem> itemMeasures) {
    7271
    7372      var solution = encodedSolution as MultiComponentVectorEncoding;
    7473      if (solution == null) throw new InvalidOperationException("Encoding is not of type MultiComponentVector");
    7574
    76       return Decode(solution, PackingBinMeasuresParameter.ActualValue, PackingItemMeasuresParameter.ActualValue);
     75      return Decode(solution, binMeasures, itemMeasures);
    7776    }
    7877  }

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

    r9440 r9495  
    4040  [Item("Identical bin, three dimensional, extreme points based decoder for the PackingSequence encoding.", "<Description missing...>")]
    4141  [StorableClass]
    42   public class ExtremePointPackingSequenceDecoder3D : IdenticalBinPackingSolutionDecoder<
     42  public class ExtremePointPackingSequenceDecoder3D : PackingSolutionDecoder<
    4343      ThreeDimensionalPacking,
    4444      CuboidPackingBin,
    45       CuboidPackingItem,
    46       PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem>> {
     45      CuboidPackingItem> {
    4746
    4847    public ExtremePointPackingSequenceDecoder3D ()
    … …  
    5958
    6059
    61     protected override PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> CreatePackingPlanFromEncoding(IPackingSolutionEncoding encodedSolution) {
     60    public override PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> CreatePackingPlanFromEncoding(IPackingSolutionEncoding encodedSolution, CuboidPackingBin binMeasures, ItemList<CuboidPackingItem> itemMeasures) {
    6261
    6362      var solution = encodedSolution as PackingSequenceEncoding;

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

    r9473 r9495  
    99using HeuristicLab.Encodings.PackingEncoding.MultiComponentVector;
    1010using HeuristicLab.Encodings.PackingEncoding.PackingSequence;
    11 using HeuristicLab.Encodings.PackingEncoding.Potvin;
    1211using HeuristicLab.Problems.BinPacking.Dimensions;
    1312using HeuristicLab.Problems.BinPacking.Interfaces;
    … …  
    2019
    2120
    22 
    23     public static ObservableDictionary<int, ThreeDimensionalPacking> ExtremePointBasedPacking(ref PotvinEncoding solution,
    24       ItemList<CuboidPackingItem> itemMeasures, CuboidPackingBin binMeasures) {
    25         if (!solution.DelimiterInitialized) {
    26           #region Preperations
    27           var itemPositions = new ObservableDictionary<int, ThreeDimensionalPacking>();
    28           int nrOfBins = 1;
    29 
    30           var occupiedPoints = new List<int[, ,]>();
    31           occupiedPoints = IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
    32 
    33           HashSet<ThreeDimensionalPacking> extremePoints = new HashSet<ThreeDimensionalPacking>();
    34           extremePoints.Add(new ThreeDimensionalPacking(0, 0, 0, 0, false));
    35           #endregion
    36 
    37           Dictionary<int, List<int>> itemIndexesForBin = new Dictionary<int, List<int>>();
    38           itemIndexesForBin[0] = new List<int>();
    39 
    40           foreach (int itemIndex in solution.IntVector) {
    41             var item = itemMeasures[itemIndex];
    42             extremePoints = OrderExtremePoints(extremePoints, occupiedPoints, binMeasures);
    43             var positionFound = FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePoints, occupiedPoints, itemPositions);
    44             if (positionFound != null) {
    45               extremePoints.Remove(positionFound);
    46             } else {
    47               positionFound = new ThreeDimensionalPacking(nrOfBins, 0, 0, 0);
    48               occupiedPoints = IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
    49               itemIndexesForBin[nrOfBins] = new List<int>();
    50               nrOfBins++;
    51             }
    52             itemPositions[itemIndex] = positionFound;
    53             itemIndexesForBin[positionFound.AssignedBin].Add(itemIndex);
    54             occupiedPoints = OccupyPointsForNewItem(occupiedPoints, item, positionFound, itemIndex);
    55             extremePoints = GenerateNewExtremePointsForNewItem(extremePoints, occupiedPoints, item, positionFound, binMeasures);
    56           }
    57           List<int> intVector = new List<int>();
    58           foreach (var indexes in itemIndexesForBin) {
    59             foreach (var index in indexes.Value) {
    60               intVector.Add(index);
    61             }
    62             intVector.Add(-1);
    63           }
    64           intVector.RemoveAt(intVector.Count - 1);
    65           solution.IntVector = new IntegerVector (intVector.ToArray());
    66 
    67           return itemPositions;
    68         } else {
    69           #region Preperations
    70           int nrOfBins = solution.IntVector.Count(i => i.Equals (-1)) + 1;
    71 
    72           //Get all indexes of items for every bin according to int vector
    73           Dictionary<int, List<int>> unpackedItemIndexesPerBin = new Dictionary<int, List<int>>();
    74           Dictionary<int, HashSet<ThreeDimensionalPacking>> extremePointsForBin = new Dictionary<int, HashSet<ThreeDimensionalPacking>>();
    75           var occupiedPoints = new List<int[, ,]>();
    76 
    77           int binCounter = 0;
    78           unpackedItemIndexesPerBin[binCounter] = new List<int>();
    79           for (int i = 0; i < solution.IntVector.Length; i++) {
    80             if (solution.IntVector[i].Equals(-1)) {
    81               unpackedItemIndexesPerBin[binCounter++] = new List<int>();
    82               extremePointsForBin[i] = new HashSet<ThreeDimensionalPacking>();
    83               extremePointsForBin[i].Add(new ThreeDimensionalPacking(i, 0, 0, 0, false));
    84               occupiedPoints = IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
    85             } else {
    86               unpackedItemIndexesPerBin[binCounter].Add(solution.IntVector[i]);
    87             }
    88 
    89           }
    90 
    91 
    92           ObservableDictionary<int, ThreeDimensionalPacking> itemPositions = new ObservableDictionary<int, ThreeDimensionalPacking>();
    93           var remainingItems = new List<int>();
    94 
    95           #endregion Preperations
    96 
    97 
    98 
    99           //Iterate over all bin-lists
    100           for (int binNr = 0; binNr < nrOfBins; binNr++) {
    101             //Iterate over the current bin-item-list and find feasible positions in the current bin for each item
    102             var unpackedItems = unpackedItemIndexesPerBin[binNr];
    103             for (int i = 0; i < unpackedItems.Count; i++) {
    104               var itemIndex = unpackedItems[i];
    105               var item = itemMeasures[itemIndex];
    106 
    107               extremePointsForBin[binNr] = OrderExtremePoints(extremePointsForBin[binNr], occupiedPoints, binMeasures);
    108               var positionFound = FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePointsForBin[binNr], occupiedPoints, itemPositions);
    109               if (positionFound != null) {
    110                 extremePointsForBin[binNr].Remove(positionFound);
    111                 itemPositions[itemIndex] = positionFound;
    112                 occupiedPoints = OccupyPointsForNewItem(occupiedPoints, item, positionFound, itemIndex);
    113                 extremePointsForBin[binNr] = GenerateNewExtremePointsForNewItem(extremePointsForBin[binNr], occupiedPoints, item, positionFound, binMeasures);
    114               } else
    115                 remainingItems.Add(itemIndex);
    116             }
    117           }
    118 
    119 
    120 
    121           //Packing of remaining items   
    122           //Iterate over all bin-lists
    123           for (int binNr = 0; binNr < nrOfBins && remainingItems.Count > 0; binNr++) {
    124             var unpackedItems = new List<int>(remainingItems);
    125             //Iterate over all the remaining items
    126             for (int i = 0; i < unpackedItems.Count; i++) {
    127               var itemIndex = unpackedItems[i];
    128               var item = itemMeasures[itemIndex];
    129 
    130               extremePointsForBin[binNr] = OrderExtremePoints(extremePointsForBin[binNr], occupiedPoints, binMeasures);
    131               var positionFound = FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePointsForBin[binNr], occupiedPoints, itemPositions);
    132               if (positionFound != null) {
    133                 extremePointsForBin[binNr].Remove(positionFound);
    134                 InsertItemgeneAfterLastItemgeneOfUsedBin(ref solution, itemIndex, binNr);
    135                 itemPositions[itemIndex] = positionFound;
    136                 occupiedPoints = OccupyPointsForNewItem(occupiedPoints, item, positionFound, itemIndex);
    137                 extremePointsForBin[binNr] = GenerateNewExtremePointsForNewItem(extremePointsForBin[binNr], occupiedPoints, item, positionFound, binMeasures);
    138                 remainingItems.Remove(itemIndex);
    139               }
    140             }
    141             if (remainingItems.Count > 0 && binNr + 1 >= nrOfBins) {
    142               extremePointsForBin[nrOfBins] = new HashSet<ThreeDimensionalPacking>();
    143               extremePointsForBin[nrOfBins].Add(new ThreeDimensionalPacking(nrOfBins, 0, 0, 0, false));
    144               occupiedPoints = IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
    145               nrOfBins++;
    146             }
    147           }
    148 
    149           return itemPositions;
    150         }
    151     }
    152     private static void InsertItemgeneAfterLastItemgeneOfUsedBin(ref PotvinEncoding solution, int itemIndex, int binNr) {
    153       List<int> temp = new List<int> (solution.IntVector);
    154       temp.Remove(itemIndex);
    155       var delimiterIndexes = temp.Select((value, index) => value == -1).Select((value, index) => index);
    156       int insertionIndex = temp.Count;
    157       if (binNr < delimiterIndexes.Count()) {
    158         insertionIndex = delimiterIndexes.ElementAt(binNr);
    159       }
    160       temp.Insert(insertionIndex, itemIndex);
    161       solution.IntVector = new IntegerVector (temp.ToArray());
    162     }
    163 
    164 
    16521    public static ObservableDictionary<int, ThreeDimensionalPacking> ExtremePointBasedPacking(ref MultiComponentVectorEncoding solution,
    16622        ItemList<CuboidPackingItem> itemMeasures, CuboidPackingBin binMeasures) {
    16723
    16824      #region Preperations
    169       int lowerBound = solution.PackingInformations.Max(x => x.AssignedBin);
    170       int nrOfBins = lowerBound + 1;
     25      int nrOfBins = solution.NrOfBins;
    17126
    17227      //Get all indexes of items for every bin according to grouping-vector                     
    … …  
    17631
    17732      for (int i = 0; i < nrOfBins; i++) {       
    178         unpackedItemIndexesPerBin[i] = solution.PackingInformations
    179           .Where(pi => pi.AssignedBin == i)
    180           .ToList();
     33        unpackedItemIndexesPerBin[i] = new List<PackingInformation> (solution.PackingInformations[i]);
    18134
    18235        extremePointsForBin[i] = new HashSet<ThreeDimensionalPacking>();
    … …  
    19649        var unpackedItems = unpackedItemIndexesPerBin[binNr];
    19750        for (int i = 0; i < unpackedItems.Count; i++) {
    198           var itemIndex = unpackedItems[i].ItemIndex;
     51          var itemIndex = unpackedItems[i].ItemID;
    19952          var item = itemMeasures[itemIndex];
    20053
    … …  
    20659            occupiedPoints = OccupyPointsForNewItem(occupiedPoints, item, positionFound, itemIndex);
    20760            extremePointsForBin[binNr] = GenerateNewExtremePointsForNewItem(extremePointsForBin[binNr], occupiedPoints, item, positionFound, binMeasures);
    208           } else
     61          } else {
    20962            remainingItems.Add(unpackedItems[i]);
     63            solution.PackingInformations[binNr].Remove(unpackedItems[i]);
     64          }
    21065        }
    21166      }
    … …  
    21873        //Iterate over all the remaining items
    21974        for (int i = 0; i < unpackedItems.Count; i++) {
    220           var itemIndex = unpackedItems[i].ItemIndex;
     75          var itemIndex = unpackedItems[i].ItemID;
    22176          var item = itemMeasures[itemIndex];
    22277
    … …  
    22782            itemPositions[itemIndex] = positionFound;
    22883            occupiedPoints = OccupyPointsForNewItem(occupiedPoints, item, positionFound, itemIndex);
    229             extremePointsForBin[binNr] = GenerateNewExtremePointsForNewItem(extremePointsForBin[binNr], occupiedPoints, item, positionFound, binMeasures);
     84            extremePointsForBin[binNr] = GenerateNewExtremePointsForNewItem(extremePointsForBin[binNr], occupiedPoints, item, positionFound, binMeasures);     
    23085            remainingItems.Remove(unpackedItems[i]);
    231             if (binNr <= lowerBound) {
    232               InsertItemgeneAfterLastItemgeneOfUsedBin(ref solution, itemIndex, binNr);
    233             }
     86            solution.PackingInformations[binNr].Add(unpackedItems[i]);
    23487          }
    23588        }
    … …  
    23891          extremePointsForBin[nrOfBins].Add(new ThreeDimensionalPacking(nrOfBins, 0, 0, 0, false));
    23992          occupiedPoints = IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
     93          solution.PackingInformations[nrOfBins] = new ItemList<PackingInformation>();
    24094          nrOfBins++;
    24195        }
    … …  
    24397
    24498      return itemPositions;
    245     }
    246     private static void InsertItemgeneAfterLastItemgeneOfUsedBin(ref MultiComponentVectorEncoding solution, int itemIndex, int binNr) {
    247       var itemgene = solution.PackingInformations.Find(pi => pi.ItemIndex == itemIndex);
    248       solution.PackingInformations.Remove (itemgene);
    249       itemgene.AssignedBin = binNr;
    250       int targetIndex = solution.PackingInformations.FindLastIndex(pi => pi.AssignedBin == binNr);
    251       solution.PackingInformations.Insert(targetIndex + 1, itemgene);
    25299    }
    253100
    … …  
    370217
    371218
    372     private static ThreeDimensionalPacking FindExtremePointForItem(int itemIndex, ItemList<CuboidPackingItem> itemMeasures, CuboidPackingBin binMeasures,
     219    public static ThreeDimensionalPacking FindExtremePointForItem(int itemIndex, ItemList<CuboidPackingItem> itemMeasures, CuboidPackingBin binMeasures,
    373220        HashSet<ThreeDimensionalPacking> extremePoints, List<int[, ,]> occupiedPoints, ObservableDictionary<int, ThreeDimensionalPacking> itemPositions) {
    374221          return FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePoints, occupiedPoints, itemPositions, false);
    375222    }
    376     private static ThreeDimensionalPacking FindExtremePointForItem(int itemIndex, ItemList<CuboidPackingItem> itemMeasures, CuboidPackingBin binMeasures,
     223    public static ThreeDimensionalPacking FindExtremePointForItem(int itemIndex, ItemList<CuboidPackingItem> itemMeasures, CuboidPackingBin binMeasures,
    377224        HashSet<ThreeDimensionalPacking> extremePoints, List<int[,,]> occupiedPoints, ObservableDictionary<int, ThreeDimensionalPacking> itemPositions, bool rotated) {
    378225
    … …  
    397244      return null;
    398245    }
    399     private static List<int[, ,]> IncreaseBinCountForOccupiedPoints(List<int[, ,]> occupiedPoints, CuboidPackingBin binMeasures) {
     246    public static List<int[, ,]> IncreaseBinCountForOccupiedPoints(List<int[, ,]> occupiedPoints, CuboidPackingBin binMeasures) {
    400247      occupiedPoints.Add(new int[binMeasures.Width, binMeasures.Height, binMeasures.Depth]);
    401248      int lastIndex = occupiedPoints.Count - 1;
    … …  
    409256      return occupiedPoints;
    410257    }
    411     private static bool IsStaticStable(int[, ,] occupiedPoints, CuboidPackingItem item, ThreeDimensionalPacking ep) {
     258    public static bool IsStaticStable(int[, ,] occupiedPoints, CuboidPackingItem item, ThreeDimensionalPacking ep) {
    412259      //Static stability is given, if item is placed on the ground
    413260      if (ep.Y == 0)
    … …  
    433280      return false;
    434281    }
    435     private static List<int[, ,]>  OccupyPointsForNewItem(List<int[, ,]> occupiedPoints, CuboidPackingItem newItem, ThreeDimensionalPacking position, int itemIndex) {
     282    public static List<int[, ,]>  OccupyPointsForNewItem(List<int[, ,]> occupiedPoints, CuboidPackingItem newItem, ThreeDimensionalPacking position, int itemIndex) {
    436283      int width = position.Rotated ? newItem.Depth : newItem.Width;
    437284      int depth = position.Rotated ? newItem.Width : newItem.Depth;
    … …  
    445292      return occupiedPoints;
    446293    }
    447     private static HashSet<ThreeDimensionalPacking> GenerateNewExtremePointsForNewItem(HashSet<ThreeDimensionalPacking> extremePoints, List<int[, ,]> occupiedPoints,
     294    public static HashSet<ThreeDimensionalPacking> GenerateNewExtremePointsForNewItem(HashSet<ThreeDimensionalPacking> extremePoints, List<int[, ,]> occupiedPoints,
    448295        CuboidPackingItem newItem, ThreeDimensionalPacking position, CuboidPackingBin binMeasures) {
    449296      int currentBin = position.AssignedBin;
    … …  
    518365
    519366
    520     private static HashSet<ThreeDimensionalPacking> OrderExtremePoints(HashSet<ThreeDimensionalPacking> hashSet, List<int[, ,]> occupiedPoints, CuboidPackingBin binMeasures) {
     367    public static HashSet<ThreeDimensionalPacking> OrderExtremePoints(HashSet<ThreeDimensionalPacking> hashSet, List<int[, ,]> occupiedPoints, CuboidPackingBin binMeasures) {
    521368      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)));
    522369    }
    523     private static int ShortestPossibleSideFromEP(ThreeDimensionalPacking ep, List<int[, ,]> occupiedPoints, CuboidPackingBin binMeasures) {
     370    public static int ShortestPossibleSideFromEP(ThreeDimensionalPacking ep, List<int[, ,]> occupiedPoints, CuboidPackingBin binMeasures) {
    524371      int shortestSide = int.MaxValue;
    525372
Note: See TracChangeset for help on using the changeset viewer.