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/DBL
Files:
4 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;
Note: See TracChangeset for help on using the changeset viewer.