Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
11/28/17 16:10:31 (7 years ago)
Author:
rhanghof
Message:

#2817:

  • Added line projection based bin packing
  • Added residual spaces to the view
Location:
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer
Files:
4 edited

Legend:

Unmodified
Added
Removed

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

    r15473 r15488  
    2020#endregion
    2121
     22using HeuristicLab.Common;
    2223using HeuristicLab.Core;
    2324using HeuristicLab.Encodings.PermutationEncoding;
    2425using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2526using HeuristicLab.Problems.BinPacking3D;
     27using HeuristicLab.Problems.BinPacking3D.ExtremePointCreation;
    2628using System;
    2729using System.Collections.Generic;
    … …  
    3133
    3234namespace HeuristicLab.Problems.BinPacking3D.Packer {
    33   [Item("BinPacker", "A class for packing bins for the 3D bin-packer problem.")]
    34   [StorableClass]
    35   public abstract class BinPacker {
     35  public abstract class BinPacker : Item {
     36
     37    /*
     38    [Storable]
     39    IPositionFinder PositionFinder
    3640   
     41    */
     42
     43    #region Constructors for HEAL
     44
     45   
     46    [StorableConstructor]
     47    protected BinPacker(bool deserializing) : base(deserializing) { }
     48
     49    protected BinPacker(BinPacker original, Cloner cloner)
     50      : base(original, cloner) {
     51      //this.PositionFinder = original.PositionFinder;
     52    }
     53
     54    #endregion
     55
    3756    public BinPacker() { }
    3857
    … …  
    4564    /// <param name="useStackingConstraints">Flag for using stacking constraints</param>
    4665    /// <returns>Returns a collection of bin packing 3d objects. Each object represents a bin and the packed items</returns>
    47     public abstract IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints);
     66    public abstract IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, bool useStackingConstraints);
    4867   
    4968    /// <summary>
    … …  
    5473    /// <param name="packingItem"></param>
    5574    /// <param name="position"></param>
    56     protected virtual void PackItem(BinPacking3D packingBin, int itemId, PackingItem packingItem, PackingPosition position, bool useStackingConstraints) {
    57 
     75    protected virtual void PackItem(BinPacking3D packingBin, int itemId, PackingItem packingItem, PackingPosition position, IExtremePointCreator extremePointCreator, bool useStackingConstraints) {
     76      if (!CheckItemDimensions(packingBin, packingItem, position)) {
     77        throw new BinPacking3DException($"The dimensions of the given item exceeds the bin dimensions. " +
     78          $"Bin: ({packingBin.BinShape.Width} {packingBin.BinShape.Depth} {packingBin.BinShape.Height})" +
     79          $"Item: ({packingItem.Width} {packingItem.Depth} {packingItem.Height})");
     80      }
    5881      packingBin.PackItem(itemId, packingItem, position);
    59       packingBin.UpdateResidualSpace(packingItem, position);
    60       packingBin.UpdateExtremePoints(packingItem, position, useStackingConstraints);
     82      extremePointCreator.UpdateExtremePoints(packingBin, packingItem, position);
     83      extremePointCreator.UpdateResidualSpace(packingBin, packingItem, position);
    6184    }
    6285
    … …  
    79102      return packingBin.ExtremePoints.Where(x => packingBin.IsPositionFeasible(newItem, x, useStackingConstraints)).FirstOrDefault();
    80103    }
     104
     105    /// <summary>
     106    /// Compares the dimensions of a given item and the current bin.
     107    /// </summary>
     108    /// <param name="item"></param>
     109    /// <returns>Returns true if the dimensions of an given item are less or equal to the bin.</returns>
     110    private bool CheckItemDimensions(BinPacking3D packingBin, PackingItem item, PackingPosition itemPosition) {
     111      var width = itemPosition.Rotated ? item.Depth : item.Width;
     112      var depth = itemPosition.Rotated ? item.Width : item.Depth;
     113      return packingBin.BinShape.Width >= width && packingBin.BinShape.Height >= item.Height && packingBin.BinShape.Depth >= depth;
     114    }
    81115  }
    82116}

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

    r15473 r15488  
    2020#endregion
    2121
     22using HeuristicLab.Common;
    2223using HeuristicLab.Core;
    2324using HeuristicLab.Encodings.PermutationEncoding;
    2425using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     26using HeuristicLab.Problems.BinPacking3D.ExtremePointCreation;
    2527using System;
    2628using System.Collections.Generic;
    … …  
    3032
    3133namespace HeuristicLab.Problems.BinPacking3D.Packer {
     34  public class BinPackerFirstFit : BinPacker {
     35    #region Constructors for HEAL
     36    [StorableConstructor]
     37    protected BinPackerFirstFit(bool deserializing) : base(deserializing) { }
    3238
    33   [Item("BinPackerFirstFit", "A class for packing bins for the 3D bin-packer problem. It uses a first fit algorithm")]
    34   [StorableClass]
    35   public class BinPackerFirstFit : BinPacker {
     39    protected BinPackerFirstFit(BinPackerFirstFit original, Cloner cloner)
     40      : base(original, cloner) {
     41    }
     42
     43    public override IDeepCloneable Clone(Cloner cloner) {
     44      return new BinPackerFirstFit(this, cloner);
     45    }
     46    #endregion
    3647
    3748    public BinPackerFirstFit() : base() { }   
    … …  
    4152    /// </summary>
    4253    /// <returns>Returns a collection of bin packing 3d objects. Each object represents a bin and the packed items</returns>
    43     public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
     54    public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epGenerationMethod, bool useStackingConstraints) {
    4455      IList<BinPacking3D> packingList = new List<BinPacking3D>();
    4556      IList<int> remainingIds = new List<int>(sortedItems);
    … …  
    4758      while (remainingIds.Count > 0) {
    4859        BinPacking3D packingBin = new BinPacking3D(binShape);
    49         PackRemainingItems(ref remainingIds, ref packingBin, items, useStackingConstraints, null);
     60        PackRemainingItems(ref remainingIds, ref packingBin, items, epGenerationMethod, useStackingConstraints, null);
    5061        packingList.Add(packingBin);
    5162      }
    … …  
    6071    /// <param name="items">List of packing items. Some of the items will be assigned to the BinPacking3D object</param>
    6172    /// <param name="packingBin">This object will be filled with some of the given items</param>
    62     protected void PackRemainingItems(ref IList<int> remainingIds, ref BinPacking3D packingBin, IList<PackingItem> items, bool useStackingConstraints, Dictionary<int, bool> rotationArray) {
    63 
     73    protected void PackRemainingItems(ref IList<int> remainingIds, ref BinPacking3D packingBin, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, bool useStackingConstraints, Dictionary<int, bool> rotationArray) {
     74      IExtremePointCreator extremePointCreator = ExtremePointCreatorFactory.CreateExtremePointCreator(epCreationMethod, useStackingConstraints);
    6475      foreach (var itemId in new List<int>(remainingIds)) {
    6576        bool rotated = rotationArray == null ? false : rotationArray[itemId];
    … …  
    6778        // if a valid packing position could be found, the current item can be added to the given bin
    6879        if (position != null) {
    69           PackItem(packingBin, itemId, items[itemId], position, useStackingConstraints);
     80          PackItem(packingBin, itemId, items[itemId], position, extremePointCreator, useStackingConstraints);
    7081          remainingIds.Remove(itemId);
    7182        }

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

    r15473 r15488  
    2020#endregion
    2121
     22using HeuristicLab.Common;
    2223using HeuristicLab.Core;
    2324using HeuristicLab.Encodings.PermutationEncoding;
    2425using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     26using HeuristicLab.Problems.BinPacking3D.ExtremePointCreation;
    2527using System;
    2628using System.Collections.Generic;
    … …  
    3032
    3133namespace HeuristicLab.Problems.BinPacking3D.Packer {
    32   [Item("BinPackerFreeVolumeBestFit", "A class for packing bins for the 3D bin-packer problem. It uses a best fit algortihm depending on the free volume.")]
    33   [StorableClass]
    3434  public class BinPackerFreeVolumeBestFit : BinPacker {
     35   
     36    #region Constructors for HEAL
     37    [StorableConstructor]
     38    protected BinPackerFreeVolumeBestFit(bool deserializing) : base(deserializing) { }
     39
     40    protected BinPackerFreeVolumeBestFit(BinPackerFreeVolumeBestFit original, Cloner cloner)
     41      : base(original, cloner) {
     42    }
     43
     44    public override IDeepCloneable Clone(Cloner cloner) {
     45      return new BinPackerFreeVolumeBestFit(this, cloner);
     46    }
     47    #endregion
    3548
    3649    public BinPackerFreeVolumeBestFit() : base() { }
    … …  
    4861    /// <param name="useStackingConstraints"></param>
    4962    /// <returns>Returns a collection of bin packing 3d objects. Each object represents a bin and the packed items</returns>
    50     public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
     63    public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epGenerationMethod, bool useStackingConstraints) {
    5164      IList<BinPacking3D> packingList = new List<BinPacking3D>();
    5265      IList<int> remainingIds = new List<int>(sortedItems);
    53 
     66      IExtremePointCreator extremePointCreator = ExtremePointCreatorFactory.CreateExtremePointCreator(epGenerationMethod, useStackingConstraints);
    5467      foreach (int remainingId in remainingIds) {
    5568        var sortedBins = packingList.OrderBy(x => x.FreeVolume);
    … …  
    6477          var bin = packingBin;
    6578          if (positionFound) {
    66             PackItem(bin, remainingId, item, position, useStackingConstraints);
     79            PackItem(bin, remainingId, item, position, extremePointCreator, useStackingConstraints);
    6780            break;
    6881          }
    … …  
    7487
    7588          if (position == null) {
    76             throw new InvalidOperationException("Item " + remainingId + " cannot be packed in empty bin.");
     89            throw new InvalidOperationException("Item " + remainingId + " cannot be packed into an empty bin.");
    7790          }
    7891
    79           PackItem(packingBin, remainingId, item, position, useStackingConstraints);
     92          PackItem(packingBin, remainingId, item, position, extremePointCreator, useStackingConstraints);
    8093          packingList.Add(packingBin);
    8194        }

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

    r15473 r15488  
    2020#endregion
    2121
     22using HeuristicLab.Common;
    2223using HeuristicLab.Core;
    2324using HeuristicLab.Encodings.PermutationEncoding;
    2425using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     26using HeuristicLab.Problems.BinPacking3D.ExtremePointCreation;
    2527using System;
    2628using System.Collections.Generic;
    … …  
    3032
    3133namespace HeuristicLab.Problems.BinPacking3D.Packer {
    32   [Item("BinPackerResidualSpaceBestFit", "A class for packing bins for the 3D bin-packer problem. It uses a best fit algortihm depending on the residual space.")]
    33   [StorableClass]
    3434  public class BinPackerResidualSpaceBestFit : BinPacker {
     35
     36    #region Constructors for HEAL
     37    [StorableConstructor]
     38    protected BinPackerResidualSpaceBestFit(bool deserializing) : base(deserializing) { }
     39
     40    protected BinPackerResidualSpaceBestFit(BinPackerResidualSpaceBestFit original, Cloner cloner)
     41      : base(original, cloner) {
     42    }
     43
     44    public override IDeepCloneable Clone(Cloner cloner) {
     45      return new BinPackerResidualSpaceBestFit(this, cloner);
     46    }
     47    #endregion
    3548
    3649    public BinPackerResidualSpaceBestFit() : base() { }
    … …  
    4255    /// </summary>
    4356    /// <returns>Returns a collection of bin packing 3d objects. Each object represents a bin and the packed items</returns>
    44     public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
     57    public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epGenerationMethod, bool useStackingConstraints) {
    4558      IList<BinPacking3D> packingList = new List<BinPacking3D>();
    4659      IList<int> remainingIds = new List<int>(sortedItems);
     60      IExtremePointCreator extremePointCreator = ExtremePointCreatorFactory.CreateExtremePointCreator(epGenerationMethod, useStackingConstraints);
    4761      bool rotated = false;
    4862
    … …  
    5670          if (point.Item1.IsPositionFeasible(item, point.Item2, useStackingConstraints)) {
    5771            var binPacking = point.Item1;
    58             PackItem(binPacking, remainingId, item, point.Item2, useStackingConstraints);
     72            PackItem(binPacking, remainingId, item, point.Item2, extremePointCreator, useStackingConstraints);
    5973            packed = true;
    6074            break;
    … …  
    6680          var position = FindPackingPositionForItem(binPacking, item, useStackingConstraints, rotated);
    6781          if (position != null) {
    68             PackItem(binPacking, remainingId, item, position, useStackingConstraints);
     82            PackItem(binPacking, remainingId, item, position, extremePointCreator, useStackingConstraints);
    6983          } else {
    70             throw new InvalidOperationException("Item " + remainingId + " cannot be packed in an empty bin.");
     84            throw new InvalidOperationException("Item " + remainingId + " cannot be packed into an empty bin.");
    7185          }
    7286          packingList.Add(binPacking);
    7387        }
    7488      }
    75 
    7689      return packingList;
    7790    }
    … …  
    110123          (rs.Item3 - item.Depth));
    111124    }
    112 
    113125  }
    114126}
Note: See TracChangeset for help on using the changeset viewer.