Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
06/02/13 04:26:26 (11 years ago)
Author:
jhelm
Message:

#1966: Implemented additional Operator-Wrappers for PackingSequence and GroupingVector; Implemented additional problem-class for Rosenbauer-Problemstatement; Added marker-interfaces for decoder-types;

Location:
branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Decoders/3D/EP
Files:
1 deleted
5 edited

Legend:

Unmodified
Added
Removed

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

    r9495 r9563  
    4444      ThreeDimensionalPacking,
    4545      CuboidPackingBin,
    46       CuboidPackingItem> {
     46      CuboidPackingItem>, I3DGVDecoder {
    4747
    4848    public ExtremePointGroupingVectorDecoder3D ()
    … …  
    6767    }
    6868
    69     public override PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> CreatePackingPlanFromEncoding(IPackingSolutionEncoding encodedSolution, CuboidPackingBin binMeasures, ItemList<CuboidPackingItem> itemMeasures) {
     69    public override PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> CreatePackingPlanFromEncoding(IItem encodedSolution, CuboidPackingBin binMeasures, ItemList<CuboidPackingItem> itemMeasures) {
    7070                     
    7171      var solution = encodedSolution as GroupingVectorEncoding;

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

    r9495 r9563  
    4545      ThreeDimensionalPacking,
    4646      CuboidPackingBin,
    47       CuboidPackingItem> {
     47      CuboidPackingItem>, I3DMCVDecoder {
    4848
    4949    public ExtremePointMultiComponentVectorDecoder3D ()
    … …  
    6868    }
    6969
    70     public override PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> CreatePackingPlanFromEncoding(IPackingSolutionEncoding encodedSolution, CuboidPackingBin binMeasures, ItemList<CuboidPackingItem> itemMeasures) {
     70    public override PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> CreatePackingPlanFromEncoding(IItem encodedSolution, CuboidPackingBin binMeasures, ItemList<CuboidPackingItem> itemMeasures) {
    7171
    7272      var solution = encodedSolution as MultiComponentVectorEncoding;

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

    r9495 r9563  
    4343      ThreeDimensionalPacking,
    4444      CuboidPackingBin,
    45       CuboidPackingItem> {
     45      CuboidPackingItem>, I3DPSDecoder {
    4646
    4747    public ExtremePointPackingSequenceDecoder3D ()
    … …  
    5858
    5959
    60     public override PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> CreatePackingPlanFromEncoding(IPackingSolutionEncoding encodedSolution, CuboidPackingBin binMeasures, ItemList<CuboidPackingItem> itemMeasures) {
     60    public override PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> CreatePackingPlanFromEncoding(IItem encodedSolution, CuboidPackingBin binMeasures, ItemList<CuboidPackingItem> itemMeasures) {
    6161
    6262      var solution = encodedSolution as PackingSequenceEncoding;
    … …  
    6464
    6565      PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> result =
    66         new PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem>(PackingBinMeasuresParameter.ActualValue, PackingItemMeasuresParameter.ActualValue);
     66        new PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem>(binMeasures, itemMeasures);
    6767
    68       result.PackingItemPositions = ExtremePointsFunctions3D.ExtremePointBasedPacking(solution, PackingItemMeasuresParameter.ActualValue, PackingBinMeasuresParameter.ActualValue);
     68      result.PackingItemPositions = ExtremePointsFunctions3D.ExtremePointBasedPacking(solution, itemMeasures, binMeasures);
    6969
    7070      return result;

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

    r9495 r9563  
    99using HeuristicLab.Encodings.PackingEncoding.MultiComponentVector;
    1010using HeuristicLab.Encodings.PackingEncoding.PackingSequence;
     11using HeuristicLab.Encodings.PermutationEncoding;
    1112using HeuristicLab.Problems.BinPacking.Dimensions;
    1213using HeuristicLab.Problems.BinPacking.Interfaces;
    … …  
    221222          return FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePoints, occupiedPoints, itemPositions, false);
    222223    }
     224    public static ThreeDimensionalPacking FindExtremePointForItemUsingMaterialAndWeightConstraint(int itemIndex, ItemList<CuboidPackingItem> itemMeasures, CuboidPackingBin binMeasures,
     225       HashSet<ThreeDimensionalPacking> extremePoints, List<int[, ,]> occupiedPoints, ObservableDictionary<int, ThreeDimensionalPacking> itemPositions, bool rotated) {
     226
     227      var itemFromList = itemMeasures[itemIndex];
     228      CuboidPackingItem item = new CuboidPackingItem(
     229        rotated ? itemFromList.Depth : itemFromList.Width,
     230        itemFromList.Height,
     231        rotated ? itemFromList.Width : itemFromList.Depth,
     232        itemFromList.TargetBin, itemFromList.Weight, itemFromList.Material);
     233
     234      int epIndex = 0;
     235      while (epIndex < extremePoints.Count &&
     236        (!DeepestBottomLeftFunctions.IsPositionFeasible(binMeasures, extremePoints.ElementAt(epIndex).AssignedBin, item, extremePoints.ElementAt(epIndex), itemPositions, itemMeasures) ||
     237        !IsStaticStable(occupiedPoints[extremePoints.ElementAt(epIndex).AssignedBin], item, extremePoints.ElementAt(epIndex)) ||
     238        !WeightIsSupported(occupiedPoints[extremePoints.ElementAt(epIndex).AssignedBin], item, extremePoints.ElementAt(epIndex), itemMeasures))) { epIndex++; }
     239
     240      if (epIndex < extremePoints.Count) {
     241        var result = extremePoints.ElementAt(epIndex);
     242        result.Rotated = rotated;
     243        return result;
     244      }
     245      return null;
     246    }
    223247    public static ThreeDimensionalPacking FindExtremePointForItem(int itemIndex, ItemList<CuboidPackingItem> itemMeasures, CuboidPackingBin binMeasures,
    224248        HashSet<ThreeDimensionalPacking> extremePoints, List<int[,,]> occupiedPoints, ObservableDictionary<int, ThreeDimensionalPacking> itemPositions, bool rotated) {
    … …  
    228252        rotated ? itemFromList.Depth : itemFromList.Width,
    229253        itemFromList.Height,
    230         rotated ? itemFromList.Width : itemFromList.Depth, 
     254        rotated ? itemFromList.Width : itemFromList.Depth,
    231255        itemFromList.TargetBin);
    232256
    … …  
    280304      return false;
    281305    }
     306    public static bool WeightIsSupported(int[, ,] occupiedPoints, CuboidPackingItem item, ThreeDimensionalPacking ep, ItemList<CuboidPackingItem> items) {
     307      //Static stability is given, if item is placed on the ground
     308      if (ep.Y == 0)
     309        return true;
     310
     311      if (items[occupiedPoints[ep.X, ep.Y - 1, ep.Z]].SupportsStacking(item)
     312        && items[occupiedPoints[ep.X + item.Width - 1, ep.Y - 1, ep.Z]].SupportsStacking(item)
     313        && items[occupiedPoints[ep.X, ep.Y - 1, ep.Z + item.Depth - 1]].SupportsStacking(item)
     314        && items[occupiedPoints[ep.X + item.Width - 1, ep.Y - 1, ep.Z + item.Depth - 1]].SupportsStacking(item))
     315        return true;
     316
     317      //int groundCount = 0;
     318      //for (int x = ep.X; x < ep.X + item.Width - 1; x++) {
     319      //  for (int z = ep.Z; z < ep.Z + item.Depth - 1; z++) {
     320      //    if (occupiedPoints[x,ep.Y-1, z] != -1)                                                     
     321      //      groundCount++;
     322      //  }
     323      //}
     324      //double stableGround = (double)(groundCount) / (double)(item.Width * item.Depth);
     325      //if (stableGround > 0.75)
     326      //  return true;
     327
     328      return false;
     329    }
    282330    public static List<int[, ,]>  OccupyPointsForNewItem(List<int[, ,]> occupiedPoints, CuboidPackingItem newItem, ThreeDimensionalPacking position, int itemIndex) {
    283331      int width = position.Rotated ? newItem.Depth : newItem.Width;

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

    r9495 r9563  
    4040
    4141namespace HeuristicLab.Problems.BinPacking.Decoders {
    42   [Item("Identical bin, three dimensional, extreme points based decoder for the MultiComponentVector encoding.", "<Description missing...>")]
     42  [Item("ISO container decoder for the MultiComponentVector encoding.", "<Description missing...>")]
    4343  [StorableClass]
    44   public class ISOContainerMultiComponentVectorDecoder3D : IdenticalBinPackingSolutionDecoder<
     44  public class ISOContainerMultiComponentVectorDecoder3D : PackingSolutionDecoder<
    4545      ThreeDimensionalPacking,
    4646      CuboidPackingBin,
    47       CuboidPackingItem,
    48       MultipleBinSizePackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem>> {
     47      CuboidPackingItem>, I3DMCVDecoder {
    4948
    5049    public ISOContainerMultiComponentVectorDecoder3D ()
    … …  
    6059    }
    6160
    62     public static MultipleBinSizePackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> Decode(MultiComponentVectorEncoding solution, CuboidPackingBin binMeasures, ItemList<CuboidPackingItem> itemMeasures) {
     61    public static PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> Decode(MultiComponentVectorEncoding solution, CuboidPackingBin binMeasures, ItemList<CuboidPackingItem> itemMeasures) {
    6362     
    64       MultipleBinSizePackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> result =
    65         new MultipleBinSizePackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem>(new ObservableDictionary<int, CuboidPackingBin>(), itemMeasures);
     63      PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> result =
     64        new PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem>(new ObservableDictionary<int, CuboidPackingBin>(), itemMeasures);
    6665
    6766      #region Preperations
    6867      int nrOfBins = solution.NrOfBins;
    69 
    70       //Get all indexes of items for every bin according to grouping-vector                     
     68                     
    7169      Dictionary<int, List<PackingInformation>> unpackedItemIndexesPerBin = new Dictionary<int, List<PackingInformation>>();
    72       Dictionary<int, HashSet<ThreeDimensionalPacking>> extremePointsForBin = new Dictionary<int, HashSet<ThreeDimensionalPacking>>();
     70      Dictionary<int, HashSet<ThreeDimensionalPacking>> extremePointsForBin = new Dictionary<int, HashSet<ThreeDimensionalPacking>>(); 
     71      ObservableDictionary<int, CuboidPackingBin> resultingBinMeasures = new ObservableDictionary<int, CuboidPackingBin>();
    7372      var occupiedPoints = new List<int[, ,]>();
    7473
    … …  
    7978        extremePointsForBin[i].Add(new ThreeDimensionalPacking(i, 0, 0, 0, false));
    8079        occupiedPoints = ExtremePointsFunctions3D.IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
     80        resultingBinMeasures[i] = new CuboidPackingBin(binMeasures.Width, binMeasures.Height, binMeasures.Depth);
    8181      }
    8282
    … …  
    9595          var item = itemMeasures[itemIndex];
    9696
    97           extremePointsForBin[binNr] = ExtremePointsFunctions3D.OrderExtremePoints(extremePointsForBin[binNr], occupiedPoints, binMeasures);
    98           var positionFound = ExtremePointsFunctions3D.FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePointsForBin[binNr], occupiedPoints, itemPositions, unpackedItems[i].Rotated);
     97          extremePointsForBin[binNr] = ExtremePointsFunctions3D.OrderExtremePoints(extremePointsForBin[binNr], occupiedPoints, resultingBinMeasures[binNr]);
     98          var positionFound = ExtremePointsFunctions3D.FindExtremePointForItemUsingMaterialAndWeightConstraint(itemIndex, itemMeasures, resultingBinMeasures[binNr], extremePointsForBin[binNr], occupiedPoints, itemPositions, unpackedItems[i].Rotated);
     99
     100          if (positionFound == null && resultingBinMeasures[binNr].Depth.Equals(binMeasures.Depth)) {
     101            occupiedPoints = DoubleDepthForBinNr(occupiedPoints, ref resultingBinMeasures, binNr);
     102            positionFound = ExtremePointsFunctions3D.FindExtremePointForItemUsingMaterialAndWeightConstraint(itemIndex, itemMeasures, resultingBinMeasures[binNr], extremePointsForBin[binNr], occupiedPoints, itemPositions, unpackedItems[i].Rotated);
     103          }
     104
    99105          if (positionFound != null) {
    100106            extremePointsForBin[binNr].Remove(positionFound);
    101107            itemPositions[itemIndex] = positionFound;
    102108            occupiedPoints = ExtremePointsFunctions3D.OccupyPointsForNewItem(occupiedPoints, item, positionFound, itemIndex);
    103             extremePointsForBin[binNr] = ExtremePointsFunctions3D.GenerateNewExtremePointsForNewItem(extremePointsForBin[binNr], occupiedPoints, item, positionFound, binMeasures);
     109            extremePointsForBin[binNr] = ExtremePointsFunctions3D.GenerateNewExtremePointsForNewItem(extremePointsForBin[binNr], occupiedPoints, item, positionFound, resultingBinMeasures[binNr]);
    104110          } else {
    105111            remainingItems.Add(unpackedItems[i]);
    106             //solution.PackingInformations[binNr].Remove(unpackedItems[i]);
     112            solution.PackingInformations[binNr].Remove(unpackedItems[i]);
    107113          }
    108114        }
    … …  
    119125          var item = itemMeasures[itemIndex];
    120126
    121           extremePointsForBin[binNr] = ExtremePointsFunctions3D.OrderExtremePoints(extremePointsForBin[binNr], occupiedPoints, binMeasures);
    122           var positionFound = ExtremePointsFunctions3D.FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePointsForBin[binNr], occupiedPoints, itemPositions, unpackedItems[i].Rotated);
     127          extremePointsForBin[binNr] = ExtremePointsFunctions3D.OrderExtremePoints(extremePointsForBin[binNr], occupiedPoints, resultingBinMeasures[binNr]);
     128          var positionFound = ExtremePointsFunctions3D.FindExtremePointForItemUsingMaterialAndWeightConstraint(itemIndex, itemMeasures, resultingBinMeasures[binNr], extremePointsForBin[binNr], occupiedPoints, itemPositions, unpackedItems[i].Rotated);
     129
     130
     131          if (positionFound == null && resultingBinMeasures[binNr].Depth.Equals(binMeasures.Depth)) {
     132            occupiedPoints = DoubleDepthForBinNr(occupiedPoints, ref resultingBinMeasures, binNr);
     133            positionFound = ExtremePointsFunctions3D.FindExtremePointForItemUsingMaterialAndWeightConstraint(itemIndex, itemMeasures, resultingBinMeasures[binNr], extremePointsForBin[binNr], occupiedPoints, itemPositions, unpackedItems[i].Rotated);
     134          }
     135         
    123136          if (positionFound != null) {
    124137            extremePointsForBin[binNr].Remove(positionFound);
    125138            itemPositions[itemIndex] = positionFound;
    126139            occupiedPoints = ExtremePointsFunctions3D.OccupyPointsForNewItem(occupiedPoints, item, positionFound, itemIndex);
    127             extremePointsForBin[binNr] = ExtremePointsFunctions3D.GenerateNewExtremePointsForNewItem(extremePointsForBin[binNr], occupiedPoints, item, positionFound, binMeasures);
     140            extremePointsForBin[binNr] = ExtremePointsFunctions3D.GenerateNewExtremePointsForNewItem(extremePointsForBin[binNr], occupiedPoints, item, positionFound, resultingBinMeasures[binNr]);
    128141            remainingItems.Remove(unpackedItems[i]);
    129             //solution.PackingInformations[binNr].Add(unpackedItems[i]);
     142            solution.PackingInformations[binNr].Add(unpackedItems[i]);
    130143          }
    131144        }
    … …  
    134147          extremePointsForBin[nrOfBins].Add(new ThreeDimensionalPacking(nrOfBins, 0, 0, 0, false));
    135148          occupiedPoints = ExtremePointsFunctions3D.IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
    136           //solution.PackingInformations[nrOfBins] = new ItemList<PackingInformation>();
     149          resultingBinMeasures[nrOfBins] = new CuboidPackingBin(binMeasures.Width, binMeasures.Height, binMeasures.Depth);
     150          solution.PackingInformations[nrOfBins] = new ItemList<PackingInformation>();
    137151          nrOfBins++;
    138152        }
    139153      }
    140154
    141       return itemPositions;
    142 
    143 
     155      result.PackingItemPositions = itemPositions;
     156      result.PackingBinMeasures = resultingBinMeasures;
    144157      return result;
    145158    }
    146159
    147     protected override MultipleBinSizePackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> CreatePackingPlanFromEncoding(IPackingSolutionEncoding encodedSolution) {
     160    private static List<int[, ,]> DoubleDepthForBinNr(List<int[, ,]> occupiedPoints, ref ObservableDictionary<int, CuboidPackingBin> binMeasures, int binNr) {
     161      var oldDepth = binMeasures[binNr].Depth;
     162      binMeasures[binNr].Depth = binMeasures[binNr].Depth * 2;
     163      var newBinOccupation = new int[binMeasures[binNr].Width, binMeasures[binNr].Height, binMeasures[binNr].Depth];
     164      for (int w = 0; w < binMeasures[binNr].Width; w++) {
     165        for (int h = 0; h < binMeasures[binNr].Height; h++) {
     166          for (int d = 0; d < binMeasures[binNr].Depth; d++) {
     167            if (d < oldDepth)
     168              newBinOccupation[w, h, d] = occupiedPoints[binNr][w, h, d];
     169            else
     170              newBinOccupation[w, h, d] = -1;
     171          }
     172        }
     173      }
     174
     175      occupiedPoints[binNr] = newBinOccupation;
     176      return occupiedPoints;
     177    }
     178
     179
     180
     181
     182    public override PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> CreatePackingPlanFromEncoding(IItem encodedSolution, CuboidPackingBin binMeasures, ItemList<CuboidPackingItem> itemMeasures) {
    148183
    149184      var solution = encodedSolution as MultiComponentVectorEncoding;
    150185      if (solution == null) throw new InvalidOperationException("Encoding is not of type MultiComponentVector");
    151186
    152       return Decode(solution, PackingBinMeasuresParameter.ActualValue, PackingItemMeasuresParameter.ActualValue);
     187      return Decode(solution, binMeasures, itemMeasures);
    153188    }
    154189  }
Note: See TracChangeset for help on using the changeset viewer.