Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
01/16/18 15:40:43 (7 years ago)
Author:
rhanghof
Message:

#2817:

  • The items can be rotated and tilted now.
  • Added pruning of extreme points in packed bins.
  • Added new packer which packs items by positioning them on the point with the minimum of wasted space. He uses rotating and tilting of items.
  • Added classes for sorting given items.
Location:
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer
Files:
6 edited

Legend:

Unmodified
Added
Removed

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

    r15554 r15617  
    11#region License Information
    22/* HeuristicLab
    3  * Copyright (C) 2002-2016 Joseph Helm and Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     3 * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
    44 *
    55 * This file is part of HeuristicLab.
    … …  
    4949    public BinPacker() { }
    5050
     51   
    5152    /// <summary>
    5253    /// Packs all items of the bin packer and returns a collection of BinPacking3D objects
    … …  
    5758    /// <param name="useStackingConstraints">Flag for using stacking constraints</param>
    5859    /// <returns>Returns a collection of bin packing 3d objects. Each object represents a bin and the packed items</returns>
    59     public abstract IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, bool useStackingConstraints);
     60    public abstract IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, ExtremePointPruningMethod epPruningMethod, bool useStackingConstraints);
    6061   
    6162    /// <summary>
    … …  
    6667    /// <param name="packingItem"></param>
    6768    /// <param name="position"></param>
    68     protected virtual void PackItem(BinPacking3D packingBin, int itemId, PackingItem packingItem, PackingPosition position, IExtremePointCreator extremePointCreator, bool useStackingConstraints) {
    69       if (!CheckItemDimensions(packingBin, packingItem, position)) {
    70         throw new BinPacking3DException($"The dimensions of the given item exceeds the bin dimensions. " +
    71           $"Bin: ({packingBin.BinShape.Width} {packingBin.BinShape.Depth} {packingBin.BinShape.Height})" +
    72           $"Item: ({packingItem.Width} {packingItem.Depth} {packingItem.Height})");
    73       }
     69    protected virtual void PackItem(BinPacking3D packingBin, int itemId, PackingItem packingItem, PackingPosition position, IExtremePointCreator extremePointCreator, bool useStackingConstraints) {     
    7470      packingBin.PackItem(itemId, packingItem, position);
    7571      extremePointCreator.UpdateBinPacking(packingBin, packingItem, position);
    … …  
    8278    /// <param name="packingItem"></param>
    8379    /// <param name="useStackingConstraints"></param>
    84     /// <param name="rotated"></param>
    8580    /// <returns>Returns the packing position for an given item. If there could not be found a valid position it returns null</returns>
    86     protected PackingPosition FindPackingPositionForItem(BinPacking3D packingBin, PackingItem packingItem, bool useStackingConstraints, bool rotated) {
     81    protected virtual PackingPosition FindPackingPositionForItem(BinPacking3D packingBin, PackingItem packingItem, bool useStackingConstraints) {
     82      if (!CheckItemDimensions(packingBin, packingItem)) {
     83        throw new BinPacking3DException($"The dimensions of the given item exceeds the bin dimensions. " +
     84          $"Bin: ({packingBin.BinShape.Width} {packingBin.BinShape.Depth} {packingBin.BinShape.Height})" +
     85          $"Item: ({packingItem.Width} {packingItem.Depth} {packingItem.Height})");
     86      }
     87
    8788      PackingItem newItem = new PackingItem(
    88         rotated ? packingItem.Depth : packingItem.Width,
     89        packingItem.Width,
    8990        packingItem.Height,
    90         rotated ? packingItem.Width : packingItem.Depth,
     91        packingItem.Depth,
    9192        packingItem.TargetBin, packingItem.Weight, packingItem.Material);
    9293
    … …  
    102103    /// <param name="item"></param>
    103104    /// <returns>Returns true if the dimensions of an given item are less or equal to the bin.</returns>
    104     private bool CheckItemDimensions(BinPacking3D packingBin, PackingItem item, PackingPosition itemPosition) {
    105       var width = itemPosition.Rotated ? item.Depth : item.Width;
    106       var depth = itemPosition.Rotated ? item.Width : item.Depth;
     105    protected virtual bool CheckItemDimensions(BinPacking3D packingBin, PackingItem item) {
     106      var width = item.Width;
     107      var depth = item.Depth;
    107108      return packingBin.BinShape.Width >= width && packingBin.BinShape.Height >= item.Height && packingBin.BinShape.Depth >= depth;
    108109    }
     110
     111    /// <summary>
     112    /// Clones a given list of packing items.
     113    /// </summary>
     114    /// <param name="items"></param>
     115    /// <returns></returns>
     116    protected static IList<PackingItem> CloneItems(IList<PackingItem> items) {
     117      var clonedItems = new List<PackingItem>();
     118      foreach (var item in items) {
     119        clonedItems.Add(item.Clone() as PackingItem);
     120      }
     121      return clonedItems;
     122    }
     123
    109124  }
    110125}

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

    r15554 r15617  
    1 using System;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     4 *
     5 * This file is part of HeuristicLab.
     6 *
     7 * HeuristicLab is free software: you can redistribute it and/or modify
     8 * it under the terms of the GNU General Public License as published by
     9 * the Free Software Foundation, either version 3 of the License, or
     10 * (at your option) any later version.
     11 *
     12 * HeuristicLab is distributed in the hope that it will be useful,
     13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
     14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     15 * GNU General Public License for more details.
     16 *
     17 * You should have received a copy of the GNU General Public License
     18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
     19 */
     20#endregion
     21
     22using System;
    223using System.Collections.Generic;
    324using System.Linq;
    … …  
    2950          binPacker = new BinPackerResidualSpaceBestFit();
    3051          break;
     52        case FittingMethod.MinimumResidualSpaceLeft:
     53          binPacker = new BinPackerMinRSLeft();
     54          break;
    3155        default:
    3256          throw new ArgumentException("Unknown fitting method: " + fittingMethod);

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

    r15554 r15617  
    11#region License Information
    22/* HeuristicLab
    3  * Copyright (C) 2002-2016 Joseph Helm and Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     3 * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
    44 *
    55 * This file is part of HeuristicLab.
    … …  
    2525using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2626using HeuristicLab.Problems.BinPacking3D.ExtremePointCreation;
     27using HeuristicLab.Problems.BinPacking3D.ExtremePointPruning;
    2728using System;
    2829using System.Collections.Generic;
    … …  
    5253    /// </summary>
    5354    /// <returns>Returns a collection of bin packing 3d objects. Each object represents a bin and the packed items</returns>
    54     public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epGenerationMethod, bool useStackingConstraints) {
     55    public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, ExtremePointPruningMethod epPruningMethod, bool useStackingConstraints) {
    5556      IList<BinPacking3D> packingList = new List<BinPacking3D>();
    5657      IList<int> remainingIds = new List<int>(sortedItems);
    … …  
    5859      while (remainingIds.Count > 0) {
    5960        BinPacking3D packingBin = new BinPacking3D(binShape);
    60         PackRemainingItems(ref remainingIds, ref packingBin, items, epGenerationMethod, useStackingConstraints, null);
     61        PackRemainingItems(ref remainingIds, ref packingBin, items, epCreationMethod, useStackingConstraints);
    6162        packingList.Add(packingBin);
    6263      }
    6364
     65      ExtremePointPruningFactory.CreatePruning().PruneExtremePoints(epPruningMethod, packingList);
    6466      return packingList;
    6567    }
    … …  
    6971    /// </summary>
    7072    /// <param name="remainingIds">List of remaining ids. After the method has been executed the list has to have less items</param>
     73    /// <param name="packingBin">This object will be filled with some of the given items</param>
    7174    /// <param name="items">List of packing items. Some of the items will be assigned to the BinPacking3D object</param>
    72     /// <param name="packingBin">This object will be filled with some of the given items</param>
    73     protected void PackRemainingItems(ref IList<int> remainingIds, ref BinPacking3D packingBin, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, bool useStackingConstraints, Dictionary<int, bool> rotationArray) {
     75    /// <param name="epCreationMethod"></param>
     76    /// <param name="useStackingConstraints"></param>
     77    protected void PackRemainingItems(ref IList<int> remainingIds, ref BinPacking3D packingBin, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, bool useStackingConstraints) {
    7478      IExtremePointCreator extremePointCreator = ExtremePointCreatorFactory.CreateExtremePointCreator(epCreationMethod, useStackingConstraints);
    7579      foreach (var itemId in new List<int>(remainingIds)) {
    76         bool rotated = rotationArray == null ? false : rotationArray[itemId];
    77         PackingPosition position = FindPackingPositionForItem(packingBin, items[itemId], useStackingConstraints, rotated);
     80        PackingPosition position = FindPackingPositionForItem(packingBin, items[itemId], useStackingConstraints);
    7881        // if a valid packing position could be found, the current item can be added to the given bin
    7982        if (position != null) {

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

    r15554 r15617  
    11#region License Information
    22/* HeuristicLab
    3  * Copyright (C) 2002-2016 Joseph Helm and Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     3 * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
    44 *
    55 * This file is part of HeuristicLab.
    … …  
    2525using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2626using HeuristicLab.Problems.BinPacking3D.ExtremePointCreation;
     27using HeuristicLab.Problems.BinPacking3D.ExtremePointPruning;
    2728using System;
    2829using System.Collections.Generic;
    … …  
    6162    /// <param name="useStackingConstraints"></param>
    6263    /// <returns>Returns a collection of bin packing 3d objects. Each object represents a bin and the packed items</returns>
    63     public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epGenerationMethod, bool useStackingConstraints) {
     64    public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epGenerationMethod, ExtremePointPruningMethod epPruningMethod, bool useStackingConstraints) {
    6465      IList<BinPacking3D> packingList = new List<BinPacking3D>();
    6566      IList<int> remainingIds = new List<int>(sortedItems);
    … …  
    7374
    7475        foreach (var packingBin in sortedBins) {
    75           PackingPosition position = FindPackingPositionForItem(packingBin, item, useStackingConstraints, false);
     76          PackingPosition position = FindPackingPositionForItem(packingBin, item, useStackingConstraints);
    7677          positionFound = position != null;
    7778          var bin = packingBin;
    … …  
    8485        if (!positionFound) {
    8586          BinPacking3D packingBin = new BinPacking3D(binShape);
    86           PackingPosition position = FindPackingPositionForItem(packingBin, item, useStackingConstraints, false);
     87          PackingPosition position = FindPackingPositionForItem(packingBin, item, useStackingConstraints);
    8788
    8889          if (position == null) {
    … …  
    9495        }
    9596      }
     97      ExtremePointPruningFactory.CreatePruning().PruneExtremePoints(epPruningMethod, packingList);
    9698      return packingList.ToList();
    9799    }

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

    r15554 r15617  
    11#region License Information
    22/* HeuristicLab
    3  * Copyright (C) 2002-2016 Joseph Helm and Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     3 * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
    44 *
    55 * This file is part of HeuristicLab.
    … …  
    2525using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2626using HeuristicLab.Problems.BinPacking3D.ExtremePointCreation;
     27using HeuristicLab.Problems.BinPacking3D.ExtremePointPruning;
    2728using System;
    2829using System.Collections.Generic;
    … …  
    5556    /// </summary>
    5657    /// <returns>Returns a collection of bin packing 3d objects. Each object represents a bin and the packed items</returns>
    57     public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, bool useStackingConstraints) {
     58    public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, ExtremePointPruningMethod epPruningMethod, bool useStackingConstraints) {
    5859      IList<BinPacking3D> packingList = new List<BinPacking3D>();
    5960      IList<int> remainingIds = new List<int>(sortedItems);
    6061      IExtremePointCreator extremePointCreator = ExtremePointCreatorFactory.CreateExtremePointCreator(epCreationMethod, useStackingConstraints);
    61       bool rotated = false;
    6262
    6363      foreach (var remainingId in remainingIds) {
    … …  
    7878        if (!packed) {
    7979          BinPacking3D binPacking = new BinPacking3D(binShape);
    80           var position = FindPackingPositionForItem(binPacking, item, useStackingConstraints, rotated);
     80          var position = FindPackingPositionForItem(binPacking, item, useStackingConstraints);
    8181          if (position != null) {
    8282            PackItem(binPacking, remainingId, item, position, extremePointCreator, useStackingConstraints);
    … …  
    8787        }
    8888      }
     89
     90      ExtremePointPruningFactory.CreatePruning().PruneExtremePoints(epPruningMethod, packingList);
    8991      return packingList;
    9092    }

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

    r15554 r15617  
    1 using HeuristicLab.Encodings.PermutationEncoding;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     4 *
     5 * This file is part of HeuristicLab.
     6 *
     7 * HeuristicLab is free software: you can redistribute it and/or modify
     8 * it under the terms of the GNU General Public License as published by
     9 * the Free Software Foundation, either version 3 of the License, or
     10 * (at your option) any later version.
     11 *
     12 * HeuristicLab is distributed in the hope that it will be useful,
     13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
     14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     15 * GNU General Public License for more details.
     16 *
     17 * You should have received a copy of the GNU General Public License
     18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
     19 */
     20#endregion
     21
     22using HeuristicLab.Encodings.PermutationEncoding;
    223using System;
    324using System.Collections.Generic;
    … …  
    1637    /// <param name="useStackingConstraints">Flag for using stacking constraints</param>
    1738    /// <returns>Returns a collection of bin packing 3d objects. Each object represents a bin and the packed items</returns>
    18     IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, bool useStackingConstraints);
     39    IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, ExtremePointPruningMethod epPruningMethod, bool useStackingConstraints);
    1940
    2041  }
Note: See TracChangeset for help on using the changeset viewer.