Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
06/07/13 01:20:12 (11 years ago)
Author:
jhelm
Message:

#1966: More refactoring; Added more sophisticated structures for packing-plan and bin-packing representation; Transferred parts of the decoding-algorithms to these structures; Did some more refactoring and cleanup;

File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r9593 r9596  
    6060
    6161    public static PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> Decode(MultiComponentVectorEncoding solution, CuboidPackingBin binMeasures, ItemList<CuboidPackingItem> itemMeasures) {
    62      
    63       PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> result =
    64         new PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem>();
    65                                                                    /*
    66       #region Preperations
    67       int nrOfBins = solution.NrOfBins;
    68                      
    69       Dictionary<int, List<PackingInformation>> unpackedItemIndexesPerBin = new Dictionary<int, List<PackingInformation>>();
    70       Dictionary<int, HashSet<ThreeDimensionalPacking>> extremePointsForBin = new Dictionary<int, HashSet<ThreeDimensionalPacking>>(); 
    71       ObservableDictionary<int, CuboidPackingBin> resultingBinMeasures = new ObservableDictionary<int, CuboidPackingBin>();
    72       var occupiedPoints = new List<int[, ,]>();
     62      PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> resultPlan = new PackingPlan3D(binMeasures);
     63      ObservableList<BinPacking3D> result = new ObservableList<BinPacking3D>();
    7364
    74       for (int i = 0; i < nrOfBins; i++) {
    75         unpackedItemIndexesPerBin[i] = new List<PackingInformation>(solution.PackingInformations[i]);
     65      var sequenceMatrix = solution.GenerateSequenceMatrix();
     66      Dictionary<int, bool> rotated = solution.GenerateRotationArray();
    7667
    77         extremePointsForBin[i] = new HashSet<ThreeDimensionalPacking>();
    78         extremePointsForBin[i].Add(new ThreeDimensionalPacking(i, 0, 0, 0, false));
    79         occupiedPoints = ExtremePointsFunctions3D.IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
    80         resultingBinMeasures[i] = new CuboidPackingBin(binMeasures.Width, binMeasures.Height, binMeasures.Depth);
     68      //Fill bins according to grouping vector
     69      List<int> remainingIDs = new List<int>();
     70      foreach (var sequence in sequenceMatrix) {
     71        remainingIDs = remainingIDs.Concat(sequence).ToList();
     72        var bp = new BinPacking3D(binMeasures);
     73        bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, true, rotated);
     74        if (remainingIDs.Count > 0) {
     75          bp.DoubleDepth();
     76          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, true, rotated);
     77        }
     78        result.Add(bp);
    8179      }
     80      result.RemoveAll(x => x.ItemPositions.Count == 0);
     81      result = new ObservableList<BinPacking3D>(result.OrderByDescending(bp => bp.PackingDensity));
    8282
    83       ObservableDictionary<int, ThreeDimensionalPacking> itemPositions = new ObservableDictionary<int, ThreeDimensionalPacking>();
    84       var remainingItems = new List<PackingInformation>();
    85 
    86       #endregion Preperations
    87 
    88 
    89       //Iterate over all bin-lists
    90       for (int binNr = 0; binNr < nrOfBins; binNr++) {
    91         //Iterate over the current bin-item-list and find feasible positions in the current bin for each item
    92         var unpackedItems = unpackedItemIndexesPerBin[binNr];
    93         for (int i = 0; i < unpackedItems.Count; i++) {
    94           var itemIndex = unpackedItems[i].ItemID;
    95           var item = itemMeasures[itemIndex];
    96 
    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 
    105           if (positionFound != null) {
    106             extremePointsForBin[binNr].Remove(positionFound);
    107             itemPositions[itemIndex] = positionFound;
    108             occupiedPoints = ExtremePointsFunctions3D.OccupyPointsForNewItem(occupiedPoints, item, positionFound, itemIndex);
    109             extremePointsForBin[binNr] = ExtremePointsFunctions3D.GenerateNewExtremePointsForNewItem(extremePointsForBin[binNr], occupiedPoints, item, positionFound, resultingBinMeasures[binNr]);
    110           } else {
    111             remainingItems.Add(unpackedItems[i]);
    112             solution.PackingInformations[binNr].Remove(unpackedItems[i]);
     83      //Try to put remaining items in existing bins
     84      var temp = new List<int>(remainingIDs);
     85      foreach (int id in temp) {
     86        foreach (var bp in result) {
     87          var position = bp.FindExtremePointForItem(itemMeasures[id], rotated[id], true);
     88          if (remainingIDs.Count > 0) {
     89            bp.DoubleDepth();
     90            position = bp.FindExtremePointForItem(itemMeasures[id], rotated[id], true);
     91          }
     92          if (position != null) {
     93            bp.PackItem(id, itemMeasures[id], position);
     94            remainingIDs.Remove(id);
    11395          }
    11496        }
    11597      }
    11698
    117 
    118       //Packing of remaining items   
    119       //Iterate over all bin-lists
    120       for (int binNr = 0; binNr < nrOfBins && remainingItems.Count > 0; binNr++) {
    121         var unpackedItems = new List<PackingInformation>(remainingItems);
    122         //Iterate over all the remaining items
    123         for (int i = 0; i < unpackedItems.Count; i++) {
    124           var itemIndex = unpackedItems[i].ItemID;
    125           var item = itemMeasures[itemIndex];
    126 
    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          
    136           if (positionFound != null) {
    137             extremePointsForBin[binNr].Remove(positionFound);
    138             itemPositions[itemIndex] = positionFound;
    139             occupiedPoints = ExtremePointsFunctions3D.OccupyPointsForNewItem(occupiedPoints, item, positionFound, itemIndex);
    140             extremePointsForBin[binNr] = ExtremePointsFunctions3D.GenerateNewExtremePointsForNewItem(extremePointsForBin[binNr], occupiedPoints, item, positionFound, resultingBinMeasures[binNr]);
    141             remainingItems.Remove(unpackedItems[i]);
    142             solution.PackingInformations[binNr].Add(unpackedItems[i]);
    143           }
     99      //Put still remaining items in new bins
     100      while (remainingIDs.Count > 0) {
     101        var bp = new BinPacking3D(binMeasures);
     102        bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, true, rotated);
     103        if (remainingIDs.Count > 0) {
     104          bp.DoubleDepth();
     105          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, true, rotated);
    144106        }
    145         if (remainingItems.Count > 0 && binNr + 1 >= nrOfBins) {
    146           extremePointsForBin[nrOfBins] = new HashSet<ThreeDimensionalPacking>();
    147           extremePointsForBin[nrOfBins].Add(new ThreeDimensionalPacking(nrOfBins, 0, 0, 0, false));
    148           occupiedPoints = ExtremePointsFunctions3D.IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
    149           resultingBinMeasures[nrOfBins] = new CuboidPackingBin(binMeasures.Width, binMeasures.Height, binMeasures.Depth);
    150           solution.PackingInformations[nrOfBins] = new ItemList<PackingInformation>();
    151           nrOfBins++;
    152         }
     107        result.Add(bp);
    153108      }
    154 
    155       result.BinPackings = BinPacking<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem>.GetBinPackings(itemPositions, resultingBinMeasures, itemMeasures, nrOfBins);   */
    156       return result;
    157     }
    158 
    159     private static List<int[, ,]> DoubleDepthForBinNr(List<int[, ,]> occupiedPoints, ref ObservableDictionary<int, CuboidPackingBin> binMeasures, int binNr) {
    160       var oldDepth = binMeasures[binNr].Depth;
    161       binMeasures[binNr].Depth = binMeasures[binNr].Depth * 2;
    162       var newBinOccupation = new int[binMeasures[binNr].Width, binMeasures[binNr].Height, binMeasures[binNr].Depth];
    163       for (int w = 0; w < binMeasures[binNr].Width; w++) {
    164         for (int h = 0; h < binMeasures[binNr].Height; h++) {
    165           for (int d = 0; d < binMeasures[binNr].Depth; d++) {
    166             if (d < oldDepth)
    167               newBinOccupation[w, h, d] = occupiedPoints[binNr][w, h, d];
    168             else
    169               newBinOccupation[w, h, d] = -1;
    170           }
    171         }
    172       }
    173 
    174       occupiedPoints[binNr] = newBinOccupation;
    175       return occupiedPoints;
     109      result.RemoveAll(x => x.ItemPositions.Count == 0);
     110      resultPlan.BinPackings = new ObservableList<BinPacking<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem>>(result.OrderByDescending(bp => bp.PackingDensity));
     111      return resultPlan;
    176112    }
    177113
    178114
    179 
    180 
    181115    public override PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> CreatePackingPlanFromEncoding(IItem encodedSolution, CuboidPackingBin binMeasures, ItemList<CuboidPackingItem> itemMeasures) {
    182 
    183116      var solution = encodedSolution as MultiComponentVectorEncoding;
    184117      if (solution == null) throw new InvalidOperationException("Encoding is not of type MultiComponentVector");
    185 
    186118      return Decode(solution, binMeasures, itemMeasures);
    187119    }
Note: See TracChangeset for help on using the changeset viewer.