Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
11/08/17 16:30:41 (7 years ago)
Author:
rhanghof
Message:

#2817
-Added unit tests for bin packing 3d.
-The items can now be sorted by the material.

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

    r15454 r15462  
    1 using HeuristicLab.Core;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2016 Joseph Helm and 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.Core;
    223using HeuristicLab.Encodings.PermutationEncoding;
    324using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    … …  
    1334  [StorableClass]
    1435  public abstract class BinPacker {
    15     protected Permutation _permutation;
    16     protected PackingShape _binShape;
    17     protected IList<PackingItem> _items;
    18     protected bool _useStackingConstraints;
     36   
     37    public BinPacker() { }
    1938
    2039    /// <summary>
    2140    /// Packs all items of the bin packer and returns a collection of BinPacking3D objects
    2241    /// </summary>
     42    /// <param name="sortedItems">Permutation of items sorted by a sorting method. The value of each permutation index references to the index of the items list</param>
     43    /// <param name="binShape">Bin for storing the items</param>
     44    /// <param name="items">A list of packing items which should be assigned to a bin</param>
     45    /// <param name="useStackingConstraints">Flag for using stacking constraints</param>
    2346    /// <returns></returns>
    24     public abstract IList<BinPacking3D> PackItems();
     47    public abstract IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints);
    2548
    26     /// <summary>
    27     /// Tries to pack the remainig items into a given BinPacking3D object. Each item could be packed into the BinPacking3D object will be removed from the list of remaining ids
    28     /// </summary>
    29     /// <param name="remainingIds">List of remaining ids. After the method has been executed the list has to have less items</param>
    30     /// <param name="items">List of packing items. Some of the items will be assigned to the BinPacking3D object</param>
    31     /// <param name="packingBin">This object will be filled with some of the given items</param>
    32     protected void PackRemainingItems(ref IList<int> remainingIds, ref BinPacking3D packingBin, IList<PackingItem> items, bool useStackingConstraints, Dictionary<int, bool> rotationArray) {
    33 
    34       foreach (var itemId in new List<int>(remainingIds)) {
    35         bool rotated = rotationArray == null ? false : rotationArray[itemId];
    36         PackingPosition position = FindPackingPositionForItem(packingBin, items[itemId], useStackingConstraints, rotated);
    37         // if a valid packing position could be found, the current item can be added to the given bin
    38         if (position != null) {
    39           PackItem(ref packingBin, itemId, items[itemId], position, useStackingConstraints);
    40           remainingIds.Remove(itemId);
    41         }
    42       }
    43     }
     49   
    4450
    4551    /// <summary>
    … …  
    5258    protected void PackItem(ref BinPacking3D packingBin, int itemId, PackingItem packingItem, PackingPosition position, bool useStackingConstraints) {
    5359
    54       packingBin.AddItem(itemId, packingItem, position);
     60      packingBin.PackItem(itemId, packingItem, position);
    5561      packingBin.UpdateResidualSpace(packingItem, position);
    5662      packingBin.UpdateExtremePoints(packingItem, position, useStackingConstraints);

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

    r15454 r15462  
    1 using HeuristicLab.Core;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2016 Joseph Helm and 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.Core;
    223using HeuristicLab.Encodings.PermutationEncoding;
    324using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    … …  
    1435  public class BinPackerFirstFit : BinPacker {
    1536
    16     public BinPackerFirstFit(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
    17       _permutation = permutation;
    18       _binShape = binShape;
    19       _items = items;
    20       _useStackingConstraints = useStackingConstraints;
    21     }
    22 
     37    public BinPackerFirstFit() : base() { }   
    2338
    2439    /// <summary>
    … …  
    2641    /// </summary>
    2742    /// <returns>Returns a collection of bin packing 3d objects. Each object represents a bin and the packed items</returns>
    28     public override IList<BinPacking3D> PackItems() {
     43    public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
    2944      IList<BinPacking3D> packingList = new List<BinPacking3D>();
    30       IList<int> remainingIds = new List<int>(_permutation);
     45      IList<int> remainingIds = new List<int>(sortedItems);
    3146
    3247      while (remainingIds.Count > 0) {
    33         BinPacking3D packingBin = new BinPacking3D(_binShape);
    34         PackRemainingItems(ref remainingIds, ref packingBin, _items, _useStackingConstraints, null);
     48        BinPacking3D packingBin = new BinPacking3D(binShape);
     49        PackRemainingItems(ref remainingIds, ref packingBin, items, useStackingConstraints, null);
    3550        packingList.Add(packingBin);
    3651      }
    … …  
    3853      return packingList;
    3954    }
     55
     56    /// <summary>
     57    /// Tries to pack the remainig items into a given BinPacking3D object. Each item could be packed into the BinPacking3D object will be removed from the list of remaining ids
     58    /// </summary>
     59    /// <param name="remainingIds">List of remaining ids. After the method has been executed the list has to have less items</param>
     60    /// <param name="items">List of packing items. Some of the items will be assigned to the BinPacking3D object</param>
     61    /// <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
     64      foreach (var itemId in new List<int>(remainingIds)) {
     65        bool rotated = rotationArray == null ? false : rotationArray[itemId];
     66        PackingPosition position = FindPackingPositionForItem(packingBin, items[itemId], useStackingConstraints, rotated);
     67        // if a valid packing position could be found, the current item can be added to the given bin
     68        if (position != null) {
     69          PackItem(ref packingBin, itemId, items[itemId], position, useStackingConstraints);
     70          remainingIds.Remove(itemId);
     71        }
     72      }
     73    }
    4074  }
    4175}

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

    r15454 r15462  
    1 using HeuristicLab.Core;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2016 Joseph Helm and 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.Core;
    223using HeuristicLab.Encodings.PermutationEncoding;
    324using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    … …  
    1233  [StorableClass]
    1334  public class BinPackerFreeVolumeBestFit : BinPacker {
    14     public BinPackerFreeVolumeBestFit(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
    15       _permutation = permutation;
    16       _binShape = binShape;
    17       _items = items;
    18       _useStackingConstraints = useStackingConstraints;
    19     }
    2035
    21     public override IList<BinPacking3D> PackItems() {
     36    public BinPackerFreeVolumeBestFit() : base() { }
     37
     38    public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
    2239      IList<BinPacking3D> packingList = new List<BinPacking3D>();
    23       IList<int> remainingIds = new List<int>(_permutation);
    24      
     40      IList<int> remainingIds = new List<int>(sortedItems);
     41
    2542
    2643      foreach (int remainingId in remainingIds) {
    2744        var sortedBins = packingList.OrderBy(x => x.FreeVolume);
    28         PackingItem item = _items[remainingId];
     45        var z = sortedBins.ToList();
     46
     47        PackingItem item = items[remainingId];
    2948        bool positionFound = false;
    3049
    3150        foreach (var packingBin in sortedBins) {
    32           PackingPosition position = FindPackingPositionForItem(packingBin, item, _useStackingConstraints, false);
     51          PackingPosition position = FindPackingPositionForItem(packingBin, item, useStackingConstraints, false);
    3352          positionFound = position != null;
    3453          var bin = packingBin;
    3554          if (positionFound) {
    36             PackItem(ref bin, remainingId, item, position, _useStackingConstraints);
     55            PackItem(ref bin, remainingId, item, position, useStackingConstraints);
    3756            break;
    38           }           
     57          }
    3958        }
    4059
    4160        if (!positionFound) {
    42           BinPacking3D packingBin = new BinPacking3D(_binShape);
    43           PackingPosition position = FindPackingPositionForItem(packingBin, item, _useStackingConstraints, false);
     61          BinPacking3D packingBin = new BinPacking3D(binShape);
     62          PackingPosition position = FindPackingPositionForItem(packingBin, item, useStackingConstraints, false);
    4463
    4564          if (position == null) {
    … …  
    4766          }
    4867
    49           PackItem(ref packingBin, remainingId, item, position, _useStackingConstraints);
     68          PackItem(ref packingBin, remainingId, item, position, useStackingConstraints);
    5069          packingList.Add(packingBin);
    5170        }

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

    r15454 r15462  
    1 using HeuristicLab.Core;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2016 Joseph Helm and 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.Core;
    223using HeuristicLab.Encodings.PermutationEncoding;
    324using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    … …  
    1233  [StorableClass]
    1334  public class BinPackerResidualSpaceBestFit : BinPacker {
    14     public BinPackerResidualSpaceBestFit(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
    15       _permutation = permutation;
    16       _binShape = binShape;
    17       _items = items;
    18       _useStackingConstraints = useStackingConstraints;
    19     }
    2035
     36    public BinPackerResidualSpaceBestFit() : base() { }/*
     37    public BinPackerResidualSpaceBestFit(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints)
     38      : base(permutation, binShape, items, useStackingConstraints) { }
     39      */
    2140    /// <summary>
    2241    /// Packs the items into the bins by using a best fit residual space algorithm.
    … …  
    2544    /// </summary>
    2645    /// <returns></returns>
    27     public override IList<BinPacking3D> PackItems() {
     46    public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
    2847      IList<BinPacking3D> packingList = new List<BinPacking3D>();
    29       IList<int> remainingIds = new List<int>(_permutation);
     48      IList<int> remainingIds = new List<int>(sortedItems);
    3049      bool rotated = false;
    3150
    3251      foreach (var remainingId in remainingIds) {
    33         PackingItem item = _items[remainingId];
     52        PackingItem item = items[remainingId];
    3453        var residualSpacePoints = GetResidualSpaceForAllPoints(packingList, item);
    3554        var sortedPoints = residualSpacePoints.OrderBy(x => x.Item3);
    … …  
    3756
    3857        foreach (var point in sortedPoints) {
    39           if (point.Item1.IsPositionFeasible(item, point.Item2, _useStackingConstraints)) {
     58          if (point.Item1.IsPositionFeasible(item, point.Item2, useStackingConstraints)) {
    4059            var binPacking = point.Item1;
    41             PackItem(ref binPacking, remainingId, item, point.Item2, _useStackingConstraints);
     60            PackItem(ref binPacking, remainingId, item, point.Item2, useStackingConstraints);
    4261            packed = true;
    4362            break;
    … …  
    4665
    4766        if (!packed) {
    48           BinPacking3D binPacking = new BinPacking3D(_binShape);
    49           var position = FindPackingPositionForItem(binPacking, item, _useStackingConstraints, rotated);
     67          BinPacking3D binPacking = new BinPacking3D(binShape);
     68          var position = FindPackingPositionForItem(binPacking, item, useStackingConstraints, rotated);
    5069          if (position != null) {
    51             PackItem(ref binPacking, remainingId, item, position, _useStackingConstraints);
     70            PackItem(ref binPacking, remainingId, item, position, useStackingConstraints);
    5271          } else {
    5372            throw new InvalidOperationException("Item " + remainingId + " cannot be packed in an empty bin.");
Note: See TracChangeset for help on using the changeset viewer.