Changeset 15462


Ignore:
Timestamp:
11/08/17 16:30:41 (2 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
Files:
12 edited

Legend:

Unmodified
Added
Removed
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs

    r15454 r15462  
    6767    #region New methods for bin packer class
    6868
    69     public void AddItem(int itemID, PackingItem item, PackingPosition position) {
     69    public override void PackItem(int itemID, PackingItem item, PackingPosition position) {
    7070      Items[itemID] = item;
    7171      Positions[itemID] = position;
     
    7474    }
    7575
     76    /// <summary>
     77    /// Updates the extreme points of the bin
     78    /// </summary>
     79    /// <param name="item"></param>
     80    /// <param name="position"></param>
     81    /// <param name="stackingConstraints"></param>
    7682    public void UpdateExtremePoints(PackingItem item, PackingPosition position, bool stackingConstraints) {
    77       /*if (stackingConstraints) {
    78         AddExtremePoint(new PackingPosition(position.AssignedBin, position.X + item.Width, position.Y, position.Z));
    79         AddExtremePoint(new PackingPosition(position.AssignedBin, position.X, position.Y + item.Height, position.Z));
    80         AddExtremePoint(new PackingPosition(position.AssignedBin, position.X, position.Y, position.Z + item.Depth));
    81       } else {*/
     83      if (stackingConstraints) {
     84        UpdateExtremePointsWithStackingConstriants(item, position);
     85      } else {
     86        UpdateExtremePointsWithoutStackingConstriants(item, position);
     87      }
     88    }
     89
     90    /// <summary>
     91    /// Updates the extreme points of the bin.
     92    /// As there is no need to project the extreme points to the next side of an item, the extreme points are only generated for the current item.
     93    /// </summary>
     94    /// <param name="item"></param>
     95    /// <param name="position"></param>
     96    private void UpdateExtremePointsWithStackingConstriants(PackingItem newItem, PackingPosition position) {
     97
     98      //UpdateExtremePointsWithoutStackingConstriants(newItem, position);
     99      //return;
     100
     101      int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
     102      int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
     103      var ep1 = new PackingPosition(position.AssignedBin, position.X + newWidth, position.Y, position.Z);
     104      var ep2 = new PackingPosition(position.AssignedBin, position.X, position.Y + newItem.Height, position.Z);
     105      var ep3 = new PackingPosition(position.AssignedBin, position.X, position.Y, position.Z + newDepth);
     106      AddExtremePoint(ep1);
     107      AddExtremePoint(ep2);
     108      AddExtremePoint(ep3);
     109
     110      /*
     111      ExtremePoints.Add(ep1);
     112      ExtremePoints.Add(ep2);
     113      ExtremePoints.Add(ep3);
     114
     115      var rs1 = CalculateResidualSpace(CreateRs(ep1));
     116      var rs2 = CalculateResidualSpace(CreateRs(ep2));
     117      var rs3 = CalculateResidualSpace(CreateRs(ep3));
     118      ResidualSpace.Add(ep1, rs1);
     119      ResidualSpace.Add(ep2, rs2);
     120      ResidualSpace.Add(ep3, rs3);*/
     121    }
     122
     123
     124    /*private bool AddExtremePoint(PackingPosition position) {
     125      if ()
     126
     127      return true;
     128    }
     129
     130   
     131    private bool AddExtremePoint(PackingPosition pos) {
     132      if (ExtremePoints.Add(pos)) {
     133        var rs = CalculateResidualSpace(new Vector3D(pos));
     134        ResidualSpace.Add(pos, rs);
     135        // Check if existing extreme points are shadowed by the new point
     136        // That is, their residual space fit entirely into the residual space of the new point
     137        foreach (var ep in ExtremePoints.Where(x => x != pos && new Vector3D(x).IsInside(pos, rs)).ToList()) {
     138          if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), ResidualSpace[ep], pos, rs)) {
     139            ExtremePoints.Remove(ep);
     140            ResidualSpace.Remove(ep);
     141          }
     142        }
     143        return true;
     144      }
     145      return false;
     146    }*/
     147
     148
     149    private Tuple<int, int, int> CalculateResidualSpace(Vector3D pos) {
     150      var itemPos = Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] });
     151      Vector3D limit = new Vector3D() { X = BinShape.Width, Y = BinShape.Height, Z = BinShape.Depth };
     152      if (pos.X < limit.X && pos.Y < limit.Y && pos.Z < limit.Z) {
     153        var rightLimit = ProjectRight(pos);
     154        var upLimit = ProjectUp(pos);
     155        var forwardLimit = ProjectForward(pos);
     156        if (rightLimit.X > 0) {
     157          limit.X = rightLimit.X;
     158        }
     159        if (upLimit.Y > 0) {
     160          limit.Y = upLimit.Y;
     161        }
     162        if (forwardLimit.Z > 0) {
     163          limit.Z = forwardLimit.Z;
     164        }
     165      }
     166
     167     
     168     
     169      if (limit.X - pos.X <= 0 || limit.Y - pos.Y <= 0  || limit.Z - pos.Z <= 0) {
     170        return Tuple.Create(0, 0, 0);
     171      }
     172
     173
     174      return Tuple.Create(limit.X - pos.X, limit.Y - pos.Y, limit.Z - pos.Z);
     175    }
     176
     177
     178    private Vector3D CreateRs(PackingPosition position) {
     179      return new Vector3D() { X = position.X, Y = position.Y, Z = position.Z };
     180    }
     181
     182    private void UpdateExtremePointsWithoutStackingConstriants(PackingItem item, PackingPosition position) {
    82183      GenerateNewExtremePointsForNewItem(item, position);
    83184
     
    92193        GenerateNewExtremePointsForNewItem(right.Item2, right.Item1);
    93194      }
    94       //}
    95195    }
    96196
     
    147247        }
    148248      }
    149       return true;     
     249      return true;
    150250    }
    151251
     
    156256    /// <param name="t2"></param>
    157257    /// <returns></returns>
    158     bool ItemsCollides(Tuple<PackingPosition, PackingItem> t1, Tuple<PackingPosition, PackingItem> t2) {
     258    private bool ItemsCollides(Tuple<PackingPosition, PackingItem> t1, Tuple<PackingPosition, PackingItem> t2) {
    159259      var position1 = t1.Item1;
    160260      var item1 = t1.Item2;
     
    189289    /// <param name="position"></param>
    190290    /// <returns></returns>
    191     public bool HasOnePointWithAnItemBelow(PackingItem item, PackingPosition position) {
     291    private bool HasOnePointWithAnItemBelow(PackingItem item, PackingPosition position) {
    192292      bool p1, p2, p3, p4;
    193       PointsLiesOnAnItems(item, position, out p1, out p2, out p3, out p4);
     293      PointsLiesOnAnItem(item, position, out p1, out p2, out p3, out p4);
    194294
    195295      return p1 || p2 || p3 || p4;
     
    205305    public override bool IsStaticStable(PackingItem item, PackingPosition position) {
    206306      bool p1, p2, p3, p4;
    207       PointsLiesOnAnItems(item, position, out p1, out p2, out p3, out p4);
     307      PointsLiesOnAnItem(item, position, out p1, out p2, out p3, out p4);
    208308      return p1 && p2 && p3 && p4;
    209309    }
    210310
    211311    /// <summary>
    212     /// This method sets the out parameters p1 ... p3 if the point lies on another item.
     312    /// This method sets the out parameters p1 ... p4 if the point lies on another item.
    213313    /// p1 ... p3 represents one point on the bottom side of an given item.
    214314    /// +---------+
     
    224324    /// <param name="p3"></param>
    225325    /// <param name="p4"></param>
    226     public void PointsLiesOnAnItems(PackingItem item, PackingPosition position, out bool p1, out bool p2, out bool p3, out bool p4) {
     326    private void PointsLiesOnAnItem(PackingItem item, PackingPosition position, out bool p1, out bool p2, out bool p3, out bool p4) {
    227327      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP1;
    228328      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP2;
     
    240340
    241341    /// <summary>
    242     ///
     342    /// This method returns a collection for the out parameters itemsP1 ... itemsP4 with the items below
     343    /// itemsP1 ... itemsP4 represents one point on the bottom side of an given item.
     344    /// +---------+
     345    /// |p1     p2|
     346    /// |         |
     347    /// |p4     p3|
     348    /// +---------+
    243349    /// </summary>
    244350    /// <param name="item"></param>
     
    277383    /// <param name="position"></param>
    278384    /// <returns></returns>
    279     public bool IsWeightSupported(PackingItem item, PackingPosition position) {
     385    private bool IsWeightSupported(PackingItem item, PackingPosition position) {
    280386      if (position.Y == 0) {
    281387        return true;
     
    298404    #endregion
    299405
    300     public override void PackItem(int itemID, PackingItem item, PackingPosition position) {
    301       // base call is deliberately omitted, because UpdateResidualSpace needs to be fitted in before
    302       // generating new extreme points
    303       Items[itemID] = item;
    304       Positions[itemID] = position;
    305       ExtremePoints.Remove(position);
    306       ResidualSpace.Remove(position);
    307       UpdateResidualSpace(item, position);
    308       GenerateNewExtremePointsForNewItem(item, position);
    309       // if an item is fit in below, before, or left of another its extreme points have to be regenerated
    310       foreach (var above in GetItemsAbove(position))
    311         GenerateNewExtremePointsForNewItem(above.Item2, above.Item1);
    312       foreach (var front in GetItemsInfront(position))
    313         GenerateNewExtremePointsForNewItem(front.Item2, front.Item1);
    314       foreach (var right in GetItemsOnRight(position))
    315         GenerateNewExtremePointsForNewItem(right.Item2, right.Item1);
    316       AddNewItemToOccupationLayers(itemID, item, position);
    317     }
    318 
    319 
    320 
     406    /// <summary>
     407    /// Generates new extreme points for a given item and its position.
     408    /// It also recalcualtes the residual space and removes the extreme points which are not needed any more.
     409    /// </summary>
     410    /// <param name="newItem"></param>
     411    /// <param name="position"></param>
    321412    protected override void GenerateNewExtremePointsForNewItem(PackingItem newItem, PackingPosition position) {
    322413      int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
     
    404495    }
    405496
    406 
    407497    private bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> residualSpace) {
    408498      var eps = ExtremePoints.Where(x => !pos.Equals(x) && pos.IsInside(x, ResidualSpace[x]));
     
    432522    }
    433523
    434     private Tuple<int, int, int> CalculateResidualSpace(Vector3D pos) {
     524    private Tuple<int, int, int> CalculateResidualSpace1(Vector3D pos) {
    435525      var itemPos = Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] });
    436526      var rightLimit = ProjectRight(pos);
     
    505595    #region Get items
    506596
    507     /// <summary>
    508     ///
    509     /// </summary>
    510     /// <param name="pos"></param>
    511     /// <returns></returns>
    512597    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsAbove(PackingPosition pos) {
    513598      var line = new Line3D(pos, new Vector3D(0, 1, 0));
     
    573658
    574659
    575 
     660    #region Sliding based packing  and obsolet methods
    576661    public override PackingPosition FindExtremePointForItem(PackingItem item, bool rotated, bool stackingConstraints) {
     662      throw new NotSupportedException();
    577663      PackingItem newItem = new PackingItem(
    578664        rotated ? item.Depth : item.Width,
     
    590676    }
    591677
    592  
    593 
    594     #region Sliding based packing   
     678
     679
     680
    595681    public override PackingPosition FindPositionBySliding(PackingItem item, bool rotated, bool stackingConstraints) {
    596       //Starting-position at upper right corner (=left bottom point of item-rectangle is at position item.width,item.height)
    597       PackingPosition currentPosition = new PackingPosition(0,
    598         BinShape.Width - (rotated ? item.Depth : item.Width),
    599         BinShape.Height - item.Height,
    600         BinShape.Depth - (rotated ? item.Width : item.Depth), rotated);
    601       //Slide the item as far as possible to the bottom
    602       while (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition), stackingConstraints)
    603         || IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints)
    604         || IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition), stackingConstraints)) {
    605         //Slide the item as far as possible to the left
    606         while (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints)
    607       || IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition), stackingConstraints)) {
    608           //Slide the item as far as possible to the back
    609           while (IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition), stackingConstraints)) {
    610             currentPosition = PackingPosition.MoveBack(currentPosition);
    611           }
    612           if (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints))
    613             currentPosition = PackingPosition.MoveLeft(currentPosition);
    614         }
    615         if (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition), stackingConstraints))
    616           currentPosition = PackingPosition.MoveDown(currentPosition);
    617       }
    618 
    619       return IsPositionFeasible(item, currentPosition, stackingConstraints) ? currentPosition : null;
     682      throw new NotSupportedException();
    620683    }
    621684
    622685    public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) {
    623       var temp = new List<int>(sequence);
    624       for (int i = 0; i < temp.Count; i++) {
    625         var item = items[temp[i]];
    626         var position = FindPositionBySliding(item, false, stackingConstraints);
    627         if (position != null) {
    628           PackItem(temp[i], item, position);
    629           sequence.Remove(temp[i]);
    630         }
    631       }
     686      throw new NotSupportedException();
    632687    }
    633688    public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, Dictionary<int, bool> rotationArray, bool stackingConstraints) {
    634       var temp = new List<int>(sequence);
    635       for (int i = 0; i < temp.Count; i++) {
    636         var item = items[temp[i]];
    637         var position = FindPositionBySliding(item, rotationArray[i], stackingConstraints);
    638         if (position != null) {
    639           PackItem(temp[i], item, position);
    640           sequence.Remove(temp[i]);
    641         }
    642       }
     689      throw new NotSupportedException();
     690    }
     691
     692
     693    public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) {
     694      throw new NotSupportedException();
     695    }
     696
     697    public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints, Dictionary<int, bool> rotationArray) {
     698      throw new NotSupportedException();
     699    }
     700
     701    public override int ShortestPossibleSideFromPoint(PackingPosition position) {
     702      throw new NotSupportedException();
     703    }
     704
     705
     706    protected override void InitializeOccupationLayers() {
     707    }
     708    protected override void AddNewItemToOccupationLayers(int itemID, PackingItem item, PackingPosition position) {
     709    }
     710
     711
     712    protected override List<int> GetLayerItemIDs(PackingPosition position) {
     713      return null;
     714    }
     715    protected override List<int> GetLayerItemIDs(PackingItem item, PackingPosition position) {
     716      return null;
    643717    }
    644718    #endregion
    645     public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) {
    646       var temp = new List<int>(sequence);
    647       foreach (int itemID in temp) {
    648         var item = items[itemID];
    649         var positionFound = FindExtremePointForItem(item, false, stackingConstraints);
    650         if (positionFound != null) {
    651           PackItem(itemID, item, positionFound);
    652           sequence.Remove(itemID);
    653         }
    654       }
    655     }
    656     public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints, Dictionary<int, bool> rotationArray) {
    657       var temp = new List<int>(sequence);
    658       foreach (int itemID in temp) {
    659         var item = items[itemID];
    660         var positionFound = FindExtremePointForItem(item, rotationArray[itemID], stackingConstraints);
    661         if (positionFound != null) {
    662           PackItem(itemID, item, positionFound);
    663           sequence.Remove(itemID);
    664         }
    665       }
    666     }
    667     public override int ShortestPossibleSideFromPoint(PackingPosition position) {
    668 
    669       int shortestSide = int.MaxValue;
    670       int width = BinShape.Width;
    671       int height = BinShape.Height;
    672       int depth = BinShape.Depth;
    673 
    674       if (position.X >= width || position.Y >= height || position.Z >= depth)
    675         return shortestSide;
    676 
    677       PackingPosition current = new PackingPosition(0, position.X, position.Y, position.Z);
    678       while (current.X < width && IsPointOccupied(current)) { current = PackingPosition.MoveRight(current); }
    679       if (current.X - position.X < shortestSide)
    680         shortestSide = current.X - position.X;
    681 
    682 
    683       current = new PackingPosition(0, position.X, position.Y, position.Z);
    684       while (current.Y < height && IsPointOccupied(current)) { current = PackingPosition.MoveUp(current); }
    685       if (current.Y - position.Y < shortestSide)
    686         shortestSide = current.Y - position.Y;
    687 
    688 
    689       current = new PackingPosition(0, position.X, position.Y, position.Z);
    690       while (current.Z < depth && IsPointOccupied(current)) { current = PackingPosition.MoveFront(current); }
    691       if (current.Z - position.Z < shortestSide)
    692         shortestSide = current.Z - position.Z;
    693 
    694       return shortestSide;
    695     }
    696    
    697 
    698     protected override void InitializeOccupationLayers() {
    699       for (int i = 0; i * 10 <= BinShape.Depth; i += 1) {
    700         OccupationLayers[i] = new List<int>();
    701       }
    702     }
    703     protected override void AddNewItemToOccupationLayers(int itemID, PackingItem item, PackingPosition position) {
    704       int z1 = position.Z / 10;
    705       int z2 = (position.Z + (position.Rotated ? item.Width : item.Depth)) / 10;
    706 
    707       for (int i = z1; i <= z2; i++)
    708         OccupationLayers[i].Add(itemID);
    709     }
    710     protected override List<int> GetLayerItemIDs(PackingPosition position) {
    711       return OccupationLayers[position.Z / 10];
    712     }
    713     protected override List<int> GetLayerItemIDs(PackingItem item, PackingPosition position) {
    714       List<int> result = new List<int>();
    715       int z1 = position.Z / 10;
    716       int z2 = (position.Z + (position.Rotated ? item.Width : item.Depth)) / 10;
    717 
    718       for (int i = z1; i <= z2; i++)
    719         result.AddRange(OccupationLayers[i]);
    720       return result;
    721     }
     719
    722720
    723721    public void UpdateResidualSpace(PackingItem item, PackingPosition pos) {
     
    762760      return;
    763761    }
    764 
    765 
    766762  }
    767763}
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Decoder/ExtremePointPermutationDecoder.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;
     
    1738  [Item("Extreme-point Permutation Decoder (3d) Base", "Base class for 3d decoders")]
    1839  [StorableClass]
    19   public class ExtremePointPermutationDecoder : Item, IDecoder<Permutation> {
     40  public class ExtremePointPermutationDecoder : Item, IDecoder<Permutation>
     41    //where TBinPacker : BinPacker, new ()
     42    {
    2043
    2144    [StorableConstructor]
    2245    protected ExtremePointPermutationDecoder(bool deserializing) : base(deserializing) { }
    23     protected ExtremePointPermutationDecoder(ExtremePointPermutationDecoderBase original, Cloner cloner)
     46    protected ExtremePointPermutationDecoder(ExtremePointPermutationDecoder original, Cloner cloner)
    2447      : base(original, cloner) {
    2548    }
     
    3457
    3558    public override IDeepCloneable Clone(Cloner cloner) {
    36       throw new NotImplementedException();
     59      return new ExtremePointPermutationDecoder(this, cloner);
    3760    }
    3861
     
    4972    public Solution Decode(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
    5073      Solution solution = new Solution(binShape, useExtremePoints: true, stackingConstraints: useStackingConstraints);
    51      
    52       foreach (var packedBin in _binPacker.PackItems()) {
     74      foreach (var packedBin in _binPacker.PackItems(permutation, binShape, items, useStackingConstraints)) {
    5375        solution.Bins.Add(packedBin);
    5476      }
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Evaluators/PackingRatioEvaluator.cs

    r14167 r15462  
    4747    }
    4848
    49     /*
    50         Falkenauer:1996 - A Hybrid Grouping Genetic Algorithm for Bin Packing
    51        
    52         fBPP = (SUM[i=1..N](Fi / C)^k)/N
    53         N.......the number of bins used in the solution,
    54         Fi......the sum of sizes of the items in the bin i (the fill of the bin),
    55         C.......the bin capacity and
    56         k.......a constant, k>1.
    57      */
     49    /// <summary>
     50    /// Falkenauer:1996 - A Hybrid Grouping Genetic Algorithm for Bin Packing
     51    /// fBPP = (SUM[i=1..N](Fi / C)^k)/N
     52    /// N.......the number of bins used in the solution,
     53    /// Fi......the sum of sizes of the items in the bin i (the fill of the bin),
     54    /// C.......the bin capacity and
     55    /// k.......a constant, k>1.
     56    /// </summary>
     57    /// <param name="solution"></param>
     58    /// <returns></returns>
    5859    public static double CalculatePackingRatio(Solution solution) {
    5960      int nrOfBins = solution.NrOfBins;
  • 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.");
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/PackingPosition.cs

    r15454 r15462  
    115115      if (result == 0)
    116116        result = Y.CompareTo(other.Y);
    117 
     117     
    118118      return result;
    119119
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/PermutationEncoding/PermutationProblem.cs

    r15069 r15462  
    3030using HeuristicLab.Optimization.Operators;
    3131using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     32using HeuristicLab.Problems.BinPacking3D.Decoder;
     33using HeuristicLab.Problems.BinPacking3D.Packer;
    3234
    3335namespace HeuristicLab.Problems.BinPacking3D {
     
    4749    public PermutationProblem()
    4850      : base() {
    49       Decoder = new ExtremePointPermutationDecoder(); // default decoder
     51      Decoder = new ExtremePointPermutationDecoder(new BinPackerFirstFit()); // default decoder
    5052
    5153      Encoding = new PermutationEncoding(EncodedSolutionName, Items.Count, PermutationTypes.Absolute);
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/Algorithms/3D/ExtremePointAlgorithm.cs

    r15454 r15462  
    3333using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    3434using HeuristicLab.Problems.BinPacking3D.Packer;
     35using HeuristicLab.Problems.BinPacking3D.Decoder;
     36
     37using HeuristicLab.Problems.BinPacking3D.Sorting;
    3538
    3639namespace HeuristicLab.Problems.BinPacking3D {
     
    7477      get { return deltaParameter; }
    7578    }
     79
     80    [Storable]
     81    private readonly IValueParameter<BoolValue> sortByMaterialParameter;
     82
     83    public IValueParameter<BoolValue> SortByMaterialParameter {
     84      get { return sortByMaterialParameter; }
     85    }   
    7686
    7787    [StorableConstructor]
     
    8494    }
    8595    public ExtremePointAlgorithm() {
    86       Parameters.Add(sortingMethodParameter = new ValueParameter<EnumValue<SortingMethod>>("SortingMethod", "In which order the items should be packed.", new EnumValue<SortingMethod>(SortingMethod.All)));
    87       Parameters.Add(fittingMethodParameter = new ValueParameter<EnumValue<FittingMethod>>("FittingMethod", "Which method to fit should be used.", new EnumValue<FittingMethod>(FittingMethod.All)));
    88       Parameters.Add(deltaParameter = new ValueParameter<PercentValue>("Delta", "[1;100]% Clustered sorting methods use a delta parameter to determine the clusters.", new PercentValue(.1)));
     96      Parameters.Add(sortingMethodParameter = new ValueParameter<EnumValue<SortingMethod>>(
     97        "SortingMethod", "In which order the items should be packed.", new EnumValue<SortingMethod>(SortingMethod.All)));
     98
     99      Parameters.Add(fittingMethodParameter = new ValueParameter<EnumValue<FittingMethod>>(
     100        "FittingMethod", "Which method to fit should be used.", new EnumValue<FittingMethod>(FittingMethod.All)));
     101
     102      Parameters.Add(deltaParameter = new ValueParameter<PercentValue>(
     103        "Delta", "[1;100]% Clustered sorting methods use a delta parameter to determine the clusters.", new PercentValue(.1)));
     104
     105      Parameters.Add(sortByMaterialParameter = new ValueParameter<BoolValue>(
     106        "SortByMaterial", "If this parameter is set, the items will be sorted by their material first", new BoolValue(true)));
    89107
    90108      Problem = new PermutationProblem();
     
    146164    }
    147165
     166    /// <summary>
     167    /// Retunrs the best solution for the given parameters
     168    /// </summary>
     169    /// <param name="bin"></param>
     170    /// <param name="items"></param>
     171    /// <param name="sortings"></param>
     172    /// <param name="fittings"></param>
     173    /// <param name="token"></param>
     174    /// <returns></returns>
    148175    private Tuple<Solution, double, SortingMethod?, FittingMethod?> GetBest(PackingShape bin, IList<PackingItem> items, SortingMethod[] sortings, FittingMethod[] fittings, CancellationToken token) {
    149176      SortingMethod? bestSorting = null;
     
    153180      foreach (var fit in fittings) {
    154181        foreach (var sort in sortings) {
    155           var result = Optimize(bin, items, sort, fit, DeltaParameter.Value.Value, Problem.UseStackingConstraints, Problem.SolutionEvaluator, token);
     182          IDecoder<Permutation> decoder = new ExtremePointPermutationDecoder(BinPackerFactory.CreateBinPacker(fit));
     183          Permutation sortedItems;
     184          if (SortByMaterialParameter.Value.Value) {
     185            sortedItems = SortItemsByMaterialAndSortingMethod(bin, items, sort, DeltaParameter.Value.Value);
     186          } else {
     187            sortedItems = SortItemsBySortingMethod(bin, items, sort, DeltaParameter.Value.Value);
     188          }
     189                   
     190          var result = Optimize(sortedItems, bin, items, Problem.UseStackingConstraints, decoder, Problem.SolutionEvaluator);
     191
    156192          if (double.IsNaN(result.Item2) || double.IsInfinity(result.Item2)) {
    157193            continue;
     
    175211    }
    176212
    177     private static Tuple<Solution, double> Optimize(PackingShape bin, IList<PackingItem> items, SortingMethod sorting, FittingMethod fitting, double delta, bool stackingConstraints, IEvaluator evaluator, CancellationToken token) {
    178       Permutation sortedItems = SortItemsBySortingMethod(bin, items, sorting, delta);
    179 
    180       if (false) {// alt
    181         ExtremePointPermutationDecoderBase decoder = GetDecoderByFittingMethod(fitting);
    182         var sol = decoder.Decode(sortedItems, bin, items, stackingConstraints);
    183         var fit = evaluator.Evaluate(sol);
    184 
    185         return Tuple.Create(sol, fit);
    186       } else {
    187         Decoder.ExtremePointPermutationDecoder decoder = new Decoder.ExtremePointPermutationDecoder(GetBinPackerByFittingMethod(fitting, sortedItems, bin, items, stackingConstraints));
    188 
    189         var sol = decoder.Decode(sortedItems, bin, items, stackingConstraints);
    190         var fit = evaluator.Evaluate(sol);
    191 
    192         return Tuple.Create(sol, fit);
    193       }
     213    /// <summary>
     214    /// Returns a tuple with the solution and the packing ratio depending on the given parameters
     215    /// </summary>
     216    /// <param name="sortedItems"></param>
     217    /// <param name="bin"></param>
     218    /// <param name="items"></param>
     219    /// <param name="stackingConstraints"></param>
     220    /// <param name="decoder"></param>
     221    /// <param name="evaluator"></param>
     222    /// <returns></returns>
     223    private static Tuple<Solution, double> Optimize(Permutation sortedItems, PackingShape bin, IList<PackingItem> items, bool stackingConstraints, IDecoder<Permutation> decoder, IEvaluator evaluator) {
    194224     
    195 
    196      
    197     }
    198 
    199 
    200 
    201     private static BinPacker GetBinPackerByFittingMethod(FittingMethod fittingMethod, Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
    202       BinPacker binPacker = null;
    203       switch (fittingMethod) {
    204         case FittingMethod.FirstFit:
    205           binPacker = new BinPackerFirstFit(sortedItems, binShape, items, useStackingConstraints);
    206           break;
    207         case FittingMethod.FreeVolumeBestFit:
    208           binPacker = new BinPackerFreeVolumeBestFit(sortedItems, binShape, items, useStackingConstraints);
    209           break;
    210         case FittingMethod.ResidualSpaceBestFit:
    211           binPacker = new BinPackerResidualSpaceBestFit(sortedItems, binShape, items, useStackingConstraints);
    212           break;
    213         default:
    214           throw new ArgumentException("Unknown fitting method: " + fittingMethod);
    215       }
    216       return binPacker;
    217     }
     225      var sol = decoder.Decode(sortedItems, bin, items, stackingConstraints);
     226      var fit = evaluator.Evaluate(sol);
     227
     228      return Tuple.Create(sol, fit);
     229    }
     230   
    218231
    219232    /// <summary>
     
    225238    /// <param name="delta"></param>
    226239    /// <returns></returns>
    227     private static Permutation SortItemsBySortingMethod(PackingShape bin, IList<PackingItem> items, SortingMethod sortingMethod, double delta) {
     240    private Permutation SortItemsBySortingMethod(PackingShape bin, IList<PackingItem> items, SortingMethod sortingMethod, double delta) {
    228241      Permutation sorted = null;
     242     
    229243      switch (sortingMethod) {
    230244        case SortingMethod.Given:
     
    232246          break;
    233247        case SortingMethod.VolumeHeight:
    234           sorted = new Permutation(PermutationTypes.Absolute,
    235                     items.Select((v, i) => new { Index = i, Item = v })
    236                          .OrderByDescending(x => x.Item.Depth * x.Item.Width * x.Item.Height)
    237                          .ThenByDescending(x => x.Item.Height)
    238                          .Select(x => x.Index).ToArray());
     248          sorted = items.SortByVolumeHeight();
    239249          break;
    240250        case SortingMethod.HeightVolume:
    241           sorted = new Permutation(PermutationTypes.Absolute,
    242                     items.Select((v, i) => new { Index = i, Item = v })
    243                          .OrderByDescending(x => x.Item.Height)
    244                          .ThenByDescending(x => x.Item.Depth * x.Item.Width * x.Item.Height)
    245                          .Select(x => x.Index).ToArray());
     251          sorted = items.SortByMaterialHeightVolume();
    246252          break;
    247253        case SortingMethod.AreaHeight:
    248           sorted = new Permutation(PermutationTypes.Absolute,
    249                     items.Select((v, i) => new { Index = i, Item = v })
    250                          .OrderByDescending(x => x.Item.Depth * x.Item.Width)
    251                          .ThenByDescending(x => x.Item.Height)
    252                          .Select(x => x.Index).ToArray());
     254          sorted = items.SortByMaterialAreaHeight();
    253255          break;
    254256        case SortingMethod.HeightArea:
    255           sorted = new Permutation(PermutationTypes.Absolute,
    256                     items.Select((v, i) => new { Index = i, Item = v })
    257                          .OrderByDescending(x => x.Item.Height)
    258                          .ThenByDescending(x => x.Item.Depth * x.Item.Width)
    259                          .Select(x => x.Index).ToArray());
     257          sorted = items.SortByMaterialHeightArea();
    260258          break;
    261259        case SortingMethod.ClusteredAreaHeight:
    262           double clusterRange = bin.Width * bin.Depth * delta;
    263           sorted = new Permutation(PermutationTypes.Absolute,
    264                     items.Select((v, i) => new { Index = i, Item = v, ClusterId = (int)(Math.Ceiling(v.Width * v.Depth / clusterRange)) })
    265                         .GroupBy(x => x.ClusterId)
    266                         .Select(x => new { Cluster = x.Key, Items = x.OrderByDescending(y => y.Item.Height).ToList() })
    267                         .OrderByDescending(x => x.Cluster)
    268                         .SelectMany(x => x.Items)
    269                         .Select(x => x.Index).ToArray());
     260          sorted = items.SortByMaterialClusteredAreaHeight(bin, delta);
    270261          break;
    271262        case SortingMethod.ClusteredHeightArea:
    272           double clusterRange2 = bin.Height * delta;
    273           sorted = new Permutation(PermutationTypes.Absolute,
    274                     items.Select((v, i) => new { Index = i, Item = v, ClusterId = (int)(Math.Ceiling(v.Height / clusterRange2)) })
    275                         .GroupBy(x => x.ClusterId)
    276                         .Select(x => new { Cluster = x.Key, Items = x.OrderByDescending(y => y.Item.Depth * y.Item.Width).ToList() })
    277                         .OrderByDescending(x => x.Cluster)
    278                         .SelectMany(x => x.Items)
    279                         .Select(x => x.Index).ToArray());
     263          sorted = items.SortByMaterialClusteredHeightArea(bin, delta);
    280264          break;
    281265        default:
     
    286270
    287271    /// <summary>
    288     /// Returns a decoder depending on the given fitting method
    289     /// </summary>
    290     /// <param name="fittingMethod"></param>
     272    /// Returns a new permutation of the given items depending on the material and sorting method
     273    /// </summary>
     274    /// <param name="bin"></param>
     275    /// <param name="items"></param>
     276    /// <param name="sortingMethod"></param>
     277    /// <param name="delta"></param>
    291278    /// <returns></returns>
    292     private static ExtremePointPermutationDecoderBase GetDecoderByFittingMethod(FittingMethod fittingMethod) {
    293       ExtremePointPermutationDecoderBase decoder = null;
    294       switch (fittingMethod) {
    295         case FittingMethod.FirstFit:
    296           decoder = new ExtremePointPermutationDecoder();
    297           break;
    298         case FittingMethod.FreeVolumeBestFit:
    299           decoder = new FreeVolumeBestFitExtremePointPermutationDecoder();
    300           break;
    301         case FittingMethod.ResidualSpaceBestFit:
    302           decoder = new ResidualSpaceBestFitExtremePointPermutationDecoder();
     279    private Permutation SortItemsByMaterialAndSortingMethod(PackingShape bin, IList<PackingItem> items, SortingMethod sortingMethod, double delta) {
     280      Permutation sorted = null;
     281
     282      switch (sortingMethod) {
     283        case SortingMethod.Given:
     284          sorted = new Permutation(PermutationTypes.Absolute, Enumerable.Range(0, items.Count).ToArray());
     285          break;
     286        case SortingMethod.VolumeHeight:
     287          sorted = items.SortByVolumeHeight();
     288          break;
     289        case SortingMethod.HeightVolume:
     290          sorted = items.SortByHeightVolume();
     291          break;
     292        case SortingMethod.AreaHeight:
     293          sorted = items.SortByAreaHeight();
     294          break;
     295        case SortingMethod.HeightArea:
     296          sorted = items.SortByHeightArea();
     297          break;
     298        case SortingMethod.ClusteredAreaHeight:
     299          sorted = items.SortByClusteredAreaHeight(bin, delta);
     300          break;
     301        case SortingMethod.ClusteredHeightArea:
     302          sorted = items.SortByClusteredHeightArea(bin, delta);
    303303          break;
    304304        default:
    305           throw new ArgumentException("Unknown fitting method: " + fittingMethod);
    306       }
    307       return decoder;
    308     }
     305          throw new ArgumentException("Unknown sorting method: " + sortingMethod);
     306      }
     307      return sorted;
     308    }
     309
     310
     311
     312    #region Sorting methods   
     313
     314    #endregion
    309315  }
    310316}
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj

    r15454 r15462  
    104104    <Compile Include="2D\Solution.cs" />
    105105    <Compile Include="3D\Packer\BinPacker.cs" />
     106    <Compile Include="3D\Packer\BinPackerFactory.cs" />
    106107    <Compile Include="3D\Packer\BinPackerFirstFit.cs" />
    107108    <Compile Include="3D\BinPacking3D.cs" />
     
    115116    <Compile Include="3D\Packer\BinPackerFreeVolumeBestFit.cs" />
    116117    <Compile Include="3D\Packer\BinPackerResidualSpaceBestFit.cs" />
    117     <Compile Include="Algorithms\3D\ExtremePointAlgorithm.cs" />
    118118    <Compile Include="3D\Instances\ThreeDInstanceDescriptor.cs" />
    119119    <Compile Include="3D\Instances\BPPData.cs" />
    120120    <Compile Include="3D\Instances\RandomDataDescriptor.cs" />
    121121    <Compile Include="3D\Instances\RealWorldContainerPackingInstanceProvider.cs" />
    122     <Compile Include="3D\Instances\ThreeDInstanceParser.cs" />
     122    <Compile Include="3D\IntegerVectorEncoding\ThreeDInstanceParser.cs" />
    123123    <Compile Include="3D\IntegerVectorEncoding\BottomLeftIntegerVectorDecoder.cs" />
    124124    <Compile Include="3D\IntegerVectorEncoding\ExtremePointIntegerVectorDecoder.cs" />
     
    132132    <Compile Include="3D\PackingPosition.cs" />
    133133    <Compile Include="3D\PackingShape.cs" />
    134     <Compile Include="3D\PermutationEncoding\BottomLeftPermutationDecoder.cs" />
    135     <Compile Include="3D\PermutationEncoding\ResidualSpaceBestFitExtremePointPermutationDecoder.cs" />
    136     <Compile Include="3D\PermutationEncoding\FreeVolumeBestFitExtremePointPermutationDecoder.cs" />
    137     <Compile Include="3D\PermutationEncoding\ExtremePointPermutationDecoderBase.cs" />
    138     <Compile Include="3D\PermutationEncoding\ExtremePointPermutationDecoder.cs" />
    139134    <Compile Include="3D\PermutationEncoding\PermutationProblem.cs" />
    140135    <Compile Include="3D\PermutationEncoding\Swap2MoveEvaluator.cs" />
     
    142137    <Compile Include="3D\ProblemBase.cs" />
    143138    <Compile Include="3D\Solution.cs" />
     139    <Compile Include="3D\Sorting\PackingItemSorter.cs" />
     140    <Compile Include="Algorithms\3D\ExtremePointAlgorithm.cs" />
    144141    <Compile Include="BinPacking.cs" />
    145142    <Compile Include="Interfaces\IPackingItem.cs">
     
    165162    <None Include="Plugin.cs.frame" />
    166163  </ItemGroup>
    167   <ItemGroup />
     164  <ItemGroup>
     165    <Folder Include="3D\Algorithms\" />
     166  </ItemGroup>
    168167  <ItemGroup>
    169168    <ProjectReference Include="..\..\HeuristicLab.Analysis\3.3\HeuristicLab.Analysis-3.3.csproj">
  • branches/2817-BinPackingSpeedup/HeuristicLab.Tests/HeuristicLab.Tests.csproj

    r15418 r15462  
    583583    <Compile Include="HeuristicLab.PluginInfraStructure-3.3\InstallationManagerTest.cs" />
    584584    <Compile Include="HeuristicLab.PluginInfraStructure-3.3\TypeExtensionsTest.cs" />
    585     <Compile Include="HeuristicLab.Problems.Bin-Packing-3.3\AlgorithmTest.cs" />
     585    <Compile Include="HeuristicLab.Problems.Bin-Packing-3.3\3D\AlgorithmTest.cs" />
     586    <Compile Include="HeuristicLab.Problems.Bin-Packing-3.3\3D\PermutationSortingTest.cs" />
     587    <Compile Include="HeuristicLab.Problems.Bin-Packing-3.3\3D\ExtremePointAlgorithmTest.cs" />
     588    <Compile Include="HeuristicLab.Problems.Bin-Packing-3.3\Utils\TestUtils.cs" />
    586589    <Compile Include="HeuristicLab.Problems.DataAnalysis-3.4\ThresholdCalculatorsTest.cs" />
    587590    <Compile Include="HeuristicLab.Problems.DataAnalysis-3.4\OnlineCalculatorPerformanceTest.cs" />
Note: See TracChangeset for help on using the changeset viewer.