Free cookie consent management tool by TermsFeed Policy Generator

Changeset 15801


Ignore:
Timestamp:
02/21/18 16:32:53 (6 years ago)
Author:
rhanghof
Message:

#2817:

  • Little changes on the packer
Location:
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFormClosure.cs

    r15731 r15801  
    1010
    1111namespace HeuristicLab.Problems.BinPacking3D.Packer {
    12   internal class BinPackerFormClosure : BinPacker {
     12  internal class BinPackerFormClosure : BinPackerMinRSLeft {
    1313
    1414    #region Constructors for HEAL
    … …  
    2525    public BinPackerFormClosure() : base() { }
    2626
    27     /// <summary>
    28     ///
    29     /// </summary>
    30     /// <param name="sortedItems"></param>
    31     /// <param name="binShape"></param>
    32     /// <param name="items"></param>
    33     /// <param name="epCreationMethod"></param>
    34     /// <param name="epPruningMethod"></param>
    35     /// <param name="useStackingConstraints"></param>
    36     /// <returns></returns>
    37     public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, ExtremePointPruningMethod epPruningMethod, bool useStackingConstraints) {
    38       var workingItems = CloneItems(items);
    39       IList<BinPacking3D> packingList = new List<BinPacking3D>();
    40       IList<int> remainingIds = new List<int>(sortedItems);
     27
     28    protected override void PackRemainingItems(ref IList<int> remainingIds, ref BinPacking3D packingBin, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, bool useStackingConstraints) {
    4129      IExtremePointCreator extremePointCreator = ExtremePointCreatorFactory.CreateExtremePointCreator(epCreationMethod, useStackingConstraints);
    42 
    43       try {
    44         var groupedItems = items.Select((x, index) => new { Item = x, Id = index })
    45                                 .GroupBy(x => x.Item.Layer)
    46                                 .OrderBy(x => x.Key);
    47 
    48         BinPacking3D packingBin = new BinPacking3D(binShape);
    49         packingList.Add(packingBin);
    50         foreach (var grouping in groupedItems) {
    51           var notPacked = new List<KeyValuePair<int, PackingItem>>();
    52           var gr = grouping.ToList();
    53           var selectedItems = gr.Where(x => ItemBinWidth(x.Item, binShape))
    54                                 .OrderByDescending(x => x.Item.Width)
    55                                 .ThenByDescending(x => x.Item.Height)
    56                                 .ThenByDescending(x => x.Item.Depth);
    57           var otherItems = gr.Except(selectedItems).OrderByDescending(x => x.Item.Width * x.Item.Height);
    58           foreach (var item in selectedItems) {
    59             if (TryToPack(packingBin, item.Item, item.Id, extremePointCreator, useStackingConstraints)) {
    60               remainingIds.Remove(item.Id);
    61             } else {
    62               notPacked.Add(new KeyValuePair<int, PackingItem>(item.Id, item.Item));
    63             }
    64           }
    65           foreach (var item in otherItems) {
    66             if (TryToPack(packingBin, item.Item, item.Id, extremePointCreator, useStackingConstraints)) {
    67               remainingIds.Remove(item.Id);
    68             } else {
    69               notPacked.Add(new KeyValuePair<int, PackingItem>(item.Id, item.Item));
    70             }
    71           }
    72 
    73           while (notPacked.Count > 0) {
    74             packingBin = new BinPacking3D(binShape);
    75             packingList.Add(packingBin);
    76 
    77             foreach (var item in notPacked.ToList()) {
    78               if (TryToPack(packingBin, item.Value, item.Key, extremePointCreator, useStackingConstraints)) {
    79                 remainingIds.Remove(item.Key);
    80                 notPacked.Remove(item);
    81               }
    82             }
    83           }
     30      // If there are any items which width equals to the bin shape width or the result of a modulo division of the width is zero, these items will be packed first
     31      //schauen, ob es einen gegenstand gibt, der die ganze breite ausfuellt oder bei einer division mit der breite ein rest von 0 rauskommt.
     32      var binShape = packingBin.BinShape;
     33      var placeable = remainingIds.ToList().Where(x => ItemFitsBinShapeWidth(x, items[x], binShape))
     34                                           .OrderByDescending(x => items[x].Width)
     35                                           .ThenByDescending(x => items[x].Height);
     36      foreach (var itemId in placeable) {
     37        var item = items[itemId];
     38        if (TryToPack(packingBin, item, itemId, extremePointCreator, useStackingConstraints)) {
     39          remainingIds.Remove(itemId);
    8440        }
    85       } catch { }
     41      }
     42      base.PackRemainingItems(ref remainingIds, ref packingBin, items, epCreationMethod, useStackingConstraints);
     43    }
    8644
    8745
    88       return packingList;
     46      private bool ItemFitsBinShapeWidth(int itemId, PackingItem item, PackingShape binShape) {
     47      item.Rotated = false;
     48      item.Tilted = false;
     49      if (binShape.Width % item.Width == 0) {
     50        return true;
     51      }
     52
     53      if (item.RotateEnabled && !item.TiltEnabled) {
     54        item.Rotated = true;
     55        if (binShape.Width % item.Width == 0) {
     56          return true;
     57        }
     58      }
     59      if (!item.RotateEnabled && item.TiltEnabled) {
     60        item.Rotated = false;
     61        item.Tilted = true;
     62        if (binShape.Width % item.Width == 0) {
     63          return true;
     64        }
     65      }
     66      if (item.RotateEnabled && item.TiltEnabled) {
     67        item.Rotated = true;
     68        item.Tilted = true;
     69        if (binShape.Width % item.Width == 0) {
     70          return true;
     71        }
     72      }
     73      item.Rotated = false;
     74      item.Tilted = false;
     75      return false;
    8976    }
    9077
    … …  
    9885      return false;
    9986    }
    100 
    101     protected override PackingPosition FindPackingPositionForItem(BinPacking3D packingBin, PackingItem packingItem, bool useStackingConstraints) {
    102       if (!CheckItemDimensions(packingBin, packingItem)) {
    103         throw new BinPacking3DException($"The dimensions of the given item exceeds the bin dimensions. " +
    104           $"Bin: ({packingBin.BinShape.Width} {packingBin.BinShape.Depth} {packingBin.BinShape.Height})" +
    105           $"Item: ({packingItem.Width} {packingItem.Depth} {packingItem.Height})");
    106       }
    107 
    108       var newPosition = packingBin.ExtremePoints.Where(x => packingBin.IsPositionFeasible(packingItem, x.Key, useStackingConstraints)).FirstOrDefault();
    109 
    110       return newPosition.Key;
    111     }
    112 
    113 
    114     private static bool ItemBinWidth(PackingItem item, PackingShape bin) {
    115       var itemCopy = item.Clone() as PackingItem;
    116       int binWith = bin.Width;
    117       if (itemCopy.Width <= binWith && binWith % itemCopy.Width == 0) {
    118         return true;
    119       }
    120 
    121       itemCopy.Rotated = true;
    122       if (itemCopy.Width <= binWith && binWith % itemCopy.Width == 0) {
    123         item.Rotated = true;
    124         return true;
    125       }
    126 
    127       itemCopy.Rotated = false;
    128       itemCopy.Tilted = true;
    129       if (itemCopy.Width <= binWith && binWith % itemCopy.Width == 0) {
    130         item.Tilted = true;
    131         return true;
    132       }
    133 
    134       itemCopy.Rotated = true;
    135       itemCopy.Tilted = true;
    136       if (itemCopy.Width <= binWith && binWith % itemCopy.Width == 0) {
    137         item.Rotated = true;
    138         item.Tilted = true;
    139         return true;
    140       }
    141       return false;
    142     }
    143 
    144     public override void PackItemsToPackingList(IList<BinPacking3D> packingList, Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, ExtremePointPruningMethod epPruningMethod, bool useStackingConstraints) {
    145       throw new NotImplementedException();
    146     }
    14787  }
    14888}

  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerMinRSLeft.cs

    r15731 r15801  
    9494      ExtremePointPruningFactory.CreatePruning().PruneExtremePoints(epPruningMethod, packingList);
    9595    }
     96
    9697   
    9798
    … …  
    104105    /// <param name="epCreationMethod"></param>
    105106    /// <param name="useStackingConstraints"></param>
    106     protected void PackRemainingItems(ref IList<int> remainingIds, ref BinPacking3D packingBin, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, bool useStackingConstraints) {
     107    protected virtual void PackRemainingItems(ref IList<int> remainingIds, ref BinPacking3D packingBin, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, bool useStackingConstraints) {
    107108      IExtremePointCreator extremePointCreator = ExtremePointCreatorFactory.CreateExtremePointCreator(epCreationMethod, useStackingConstraints);
     109
    108110      var remainingNotWeightSupportedItems = new List<int>();
    109111      foreach (var itemId in new List<int>(remainingIds)) {
    … …  
    149151          }
    150152        }
    151 
    152153      }
    153154    }
Note: See TracChangeset for help on using the changeset viewer.