Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
02/07/18 14:54:42 (7 years ago)
Author:
rhanghof
Message:

#2817:

  • Added a new packer.
  • Enhanced the material types.
  • Added extreme point pruning for layer support in the extrem point creators.
  • BinPacking3D: Added a graph for calculating weigth distribution of the items.
Location:
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3
Files:
3 added
1 deleted
17 edited

Legend:

Unmodified
Added
Removed

  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Algorithms/ExtremePointAlgorithm.cs

    r15646 r15731  
    4040
    4141  public enum SortingMethod { All, Given, VolumeHeight, HeightVolume, AreaHeight, HeightArea, ClusteredAreaHeight, ClusteredHeightArea }
    42   public enum FittingMethod { All, FirstFit, ResidualSpaceBestFit, FreeVolumeBestFit, MinimumResidualSpaceLeft }
     42  public enum FittingMethod { All, FirstFit, ResidualSpaceBestFit, FreeVolumeBestFit, MinimumResidualSpaceLeft, FormClosure }
    4343
    4444  public enum ExtremePointCreationMethod { All, PointProjection, LineProjection }

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

    r15705 r15731  
    2929using HeuristicLab.Problems.BinPacking3D.Geometry;
    3030using HeuristicLab.Collections;
     31using HeuristicLab.Problems.BinPacking3D.Graph;
    3132
    3233namespace HeuristicLab.Problems.BinPacking3D {
    … …  
    3738    [Storable]
    3839    public IDictionary<PackingPosition, IEnumerable<ResidualSpace>> ExtremePoints { get; protected set; }
    39    
     40
     41    [Storable]
     42    public IDirectedGraph WeightDistirbution { get; protected set; }
    4043
    4144    public BinPacking3D(PackingShape binShape)
    4245      : base(binShape) {
    4346      ExtremePoints = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();
    44 
    4547      ExtremePoints.Add(binShape.Origin, new List<ResidualSpace>() { ResidualSpace.Create(binShape.Width, binShape.Height, binShape.Depth) });
     48
     49      WeightDistirbution = new DirectedGraph();
    4650    }
    4751
    … …  
    5862        }
    5963        ExtremePoints.Add(cloner.Clone(extremePoint.Key), residualSpaces);
    60       }     
     64      }
     65
     66      // todo clone WeightDistirbution graph
    6167    }
    6268
    … …  
    7783      Positions[itemID] = position;
    7884      ExtremePoints.Remove(position);
    79     }
     85
     86      AddToGraph(itemID, item, position);
     87    }
     88
     89
     90    #region Graph for the calculating the weight distirbution       
     91    private void AddToGraph(int itemId, PackingItem item, PackingPosition position) {
     92      var sourceVertex = new VertexWithItemId(itemId);
     93      WeightDistirbution.AddVertex(sourceVertex);
     94
     95      var itemsBelow = GetItemsUnderAnItem(position, item);
     96      foreach (var itemBelow in itemsBelow) {
     97        var targetVertex = GetVertexForItemBelow(itemBelow);
     98        if (targetVertex == null) {
     99          continue;
     100        }
     101
     102        double overlay = CalculateOverlay(itemBelow, Tuple.Create<PackingPosition, PackingItem>(position, item));
     103        double area = (item.Width * item.Depth);
     104        var arc = new Arc(sourceVertex, targetVertex) {
     105          Weight = overlay / area
     106        };
     107        WeightDistirbution.AddArc(arc);
     108      }
     109    }
     110
     111    /// <summary>
     112    /// Returns a vertex related to the given tuple of an item and packing position.
     113    /// If there is no related vertex the method returns null.
     114    /// </summary>
     115    /// <param name="itemBelow"></param>
     116    /// <returns></returns>
     117    private IVertex GetVertexForItemBelow(Tuple<PackingPosition, PackingItem> itemBelow) {
     118      var filteredItems = Items.Where(x => x.Value == itemBelow.Item2);
     119      if (filteredItems.Count() <= 0) {
     120        return null;
     121      }
     122      var itemIdBelow = filteredItems.First().Key;
     123
     124      var targetVertex = WeightDistirbution.Vertices.Where(x => {
     125        if (x is VertexWithItemId) {
     126          return ((VertexWithItemId)x).ItemId == itemIdBelow;
     127        }
     128        return false;
     129      }).FirstOrDefault();
     130
     131      return targetVertex;
     132    }
     133
     134
     135    #endregion
     136
     137    #region Calculation of the stacked weight
     138    public double GetStackedWeightForItemId(int itemId) {
     139      return GetStackedWeightForItemIdRec(itemId);
     140    }
     141
     142    private double GetStackedWeightForItemIdRec(int itemId) {
     143      var arcs = WeightDistirbution.Arcs.Where(x => ((VertexWithItemId)x.Target).ItemId == itemId);
     144      var stackedWeight = 0.0;
     145      foreach (var arc in arcs) {
     146        var sourceItemId = ((VertexWithItemId)arc.Source).ItemId;
     147        var sourceItem = Items[sourceItemId];
     148        stackedWeight += (GetStackedWeightForItemIdRec(sourceItemId) + sourceItem.Weight) * arc.Weight;
     149      }
     150
     151      return stackedWeight;
     152    }
     153
     154    #endregion
    80155
    81156    #region MassPoint
    … …  
    316391      }
    317392
    318       var overlayZ = inFront.Item2.Width;
    319       if (behind.Item1.X + behind.Item2.Width < inFront.Item1.X + inFront.Item2.Width) {
    320         overlayZ = behind.Item1.X + behind.Item2.Width - inFront.Item1.X;
     393      var overlayZ = inFront.Item2.Depth;
     394      if (behind.Item1.Z + behind.Item2.Depth < inFront.Item1.Z + inFront.Item2.Depth) {
     395        overlayZ = behind.Item1.Z + behind.Item2.Depth - inFront.Item1.Z;
    321396      }
    322397
    … …  
    337412    }
    338413
     414    /// <summary>
     415    /// Returns a collection of items and its position which have contact to an given item below
     416    /// </summary>
     417    /// <param name="position"></param>
     418    /// <param name="item"></param>
     419    /// <returns></returns>
    339420    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsUnderAnItem(PackingPosition position, PackingItem item) {
    340421      var selected = Items.Select(x => new {
    … …  
    344425        .Where(x => x.Position.X <= position.X && x.Position.X + x.Item.Width > position.X ||
    345426                    x.Position.X > position.X && x.Position.X < position.X + item.Width)
    346         .Where(x => x.Position.Z <= position.Z && x.Position.Z + x.Item.Height > position.Z ||
    347                     x.Position.Z > position.Z && x.Position.Z < position.Z + item.Height);
     427        .Where(x => x.Position.Z <= position.Z && x.Position.Z + x.Item.Depth > position.Z ||
     428                    x.Position.Z > position.Z && x.Position.Z < position.Z + item.Depth);
    348429
    349430      return selected.Select(x => Tuple.Create(x.Position, x.Item));

  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Evaluators/BinUtilizationEvaluator.cs

    r15646 r15731  
    8181    }
    8282
    83     public Tuple<int, double, int> Evaluate1(Solution solution) {
     83    public Tuple<int, double, int, int> Evaluate1(Solution solution) {
    8484
    8585
    86       var res = Tuple.Create<int, double, int>(
     86      var res = Tuple.Create<int, double, int, int>(
    8787        GetBinCount(solution),
    8888        CalculateBinUtilizationFirstBin(solution),
    89         GetNumberOfResidualSpaces(solution)
     89        GetNumberOfResidualSpaces(solution),
     90        CalculateMaxDepth(solution)
    9091        );
    9192
    … …  
    107108    }
    108109
     110    private static int CalculateMaxDepth(Solution solution) {
     111      var packing = solution.Bins.Last();
     112      if (packing == null) {
     113        return Int32.MaxValue;
     114      }
     115
     116      return packing.Positions.Select(x => x.Value.Z + packing.Items[x.Key].Depth).Max();
     117    }
     118
    109119
    110120    #endregion

  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Evaluators/IEvaluator.cs

    r15646 r15731  
    4141    /// <param name="solution"></param>
    4242    /// <returns></returns>
    43     Tuple<int, double, int> Evaluate1(Solution solution);
     43    Tuple<int, double, int, int> Evaluate1(Solution solution);
    4444  }
    4545}

  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Evaluators/PackingRatioEvaluator.cs

    r15646 r15731  
    9898    }
    9999
    100     public Tuple<int, double, int> Evaluate1(Solution solution) {
     100    public Tuple<int, double, int, int> Evaluate1(Solution solution) {
    101101
    102102
    103       var res = Tuple.Create<int, double, int>(
     103      var res = Tuple.Create<int, double, int, int>(
    104104        GetBinCount(solution),
    105105        CalculateBinUtilizationFirstBin(solution),
    106         GetNumberOfResidualSpaces(solution)
     106        GetNumberOfResidualSpaces(solution),
     107        CalculateMaxDepth(solution)
    107108        );
    108109
    … …  
    124125    }
    125126
     127    private static int CalculateMaxDepth(Solution solution) {
     128      var packing = solution.Bins.Last();
     129      if (packing == null) {
     130        return Int32.MaxValue;
     131      }
     132
     133      return packing.Positions.Select(x => x.Value.Z + packing.Items[x.Key].Depth).Max();
     134    }
     135
    126136    #endregion
    127137  }

  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/LineProjectionBasedEPCreator.cs

    r15705 r15731  
    3535  /// This projection method enhances the point based projection method by creating extra extreme points on the intersection points of two items.
    3636  /// </summary>
    37   public class LineProjectionBasedEPCreator : ExtremePointCreator {
    38 
    39     /// <summary>
    40     /// This lock object is needed because of creating the extreme points in an parallel for loop.
    41     /// </summary>
    42     object _lockAddExtremePoint = new object();
    43 
    44     protected override void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    45       binPacking.ExtremePoints.Clear();
    46 
    47       // generate all new extreme points parallel. This speeds up the creator.
    48       Parallel.ForEach(binPacking.Items, i => {
    49         PackingItem it = i.Value;
    50         PackingPosition p = binPacking.Positions[i.Key];
    51         GenerateNewExtremePointsForItem(binPacking, it, p);
    52       });
    53 
    54       // remove not needed extreme points.
    55       foreach (var extremePoint in binPacking.ExtremePoints.ToList()) {
    56         // check if a residual space can be removed
    57         foreach (var rs in extremePoint.Value.ToList()) {
    58           if (ResidualSpaceCanBeRemoved(binPacking, extremePoint.Key, rs)) {
    59             ((IList<ResidualSpace>)extremePoint.Value).Remove(rs);
    60           }
    61         }
    62         // if the current extreme point has no more residual spaces, it can be removed.
    63         if (((IList<ResidualSpace>)extremePoint.Value).Count <= 0) {
    64           binPacking.ExtremePoints.Remove(extremePoint);
    65         }
    66       }
    67      
    68     }
    69 
    70     /// <summary>
    71     /// Returns true if a given residual space can be removed.
    72     /// The given residual space can be removed if it is within another residual space and
    73     /// - neither the position of the other residual space and the current extreme point have an item below or
    74     /// - the current extreme point has an item below.
    75     /// </summary>
    76     /// <param name="binPacking"></param>
    77     /// <param name="position"></param>
    78     /// <param name="rs"></param>
    79     /// <returns></returns>
    80     private bool ResidualSpaceCanBeRemoved(BinPacking3D binPacking, PackingPosition position, ResidualSpace rs) {
    81       foreach (var extremePoint in binPacking.ExtremePoints) {
    82         if (position.Equals(extremePoint.Key)) {
    83           continue;
    84         }
    85         if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(position), rs, extremePoint.Key, extremePoint.Value)) {
    86           var itemBelowEp = LiesOnAnyItem(binPacking, extremePoint.Key);
    87           var itemBelowPos = LiesOnAnyItem(binPacking, position);
    88 
    89           if (itemBelowEp || !itemBelowEp && !itemBelowPos) {
    90             return true;
    91           }
    92         }
    93       }
    94       return false;
    95     }
    96 
    97     /// <summary>
    98     /// Returns true if the given position lies on an item or an the ground.
    99     /// </summary>
    100     /// <param name="binPacking"></param>
    101     /// <param name="position"></param>
    102     /// <returns></returns>
    103     private bool LiesOnAnyItem(BinPacking3D binPacking, PackingPosition position) {
    104       if (position.Y == 0) {
    105         return true;
    106       }
    107 
    108       var items = binPacking.Items.Where(x => {
    109         var itemPosition = binPacking.Positions[x.Key];
    110         var item = x.Value;
    111         int width = item.Width;
    112         int depth = item.Depth;
    113 
    114         return itemPosition.Y + item.Height == position.Y &&
    115                itemPosition.X <= position.X && position.X < itemPosition.X + width &&
    116                itemPosition.Z <= position.Z && position.Z < itemPosition.Z + depth;
    117       });
    118 
    119       return items.Count() > 0;
    120     }
    121 
    122 
    123     /// <summary>
    124     /// Adds a new extreme point an the related residual spaces to a given bin packing.
    125     /// - The given position has to be valid.
    126     /// - The extreme point does not exist in the bin packing.
    127     /// - There must be at minimum one valid residual space. A residual space is invalid if the space is zero.
    128     /// </summary>
    129     /// <param name="binPacking"></param>
    130     /// <param name="position"></param>
    131     /// <returns>True = the given point and its related residual spaces were successfully added to the bin packing</returns>
    132     protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) {
    133       if (position == null) {
    134         return false;
    135       }
    136 
    137       if (PointIsInAnyItem(binPacking, new Vector3D(position))) {
    138         return false;
    139       }
    140 
    141       // this is necessary if the extreme points are being created in a parallel loop.
    142       lock (_lockAddExtremePoint) {
    143         if (binPacking.ExtremePoints.ContainsKey(position)) {
    144           return false;
    145         }
    146 
    147         var rs = CalculateResidualSpace(binPacking, new Vector3D(position));
    148 
    149         if (rs.Count() <= 0) {
    150           return false;
    151         }
    152 
    153         binPacking.ExtremePoints.Add(position, rs);
    154         return true;
    155       }
    156     }
     37  public class LineProjectionBasedEPCreator : PointProjectionBasedEPCreator {
     38   
     39
    15740
    15841    /// <summary>
    … …  
    16851      EdgeProjectionForNewItem(binPacking, newItem, position);
    16952    }
    170 
    171     #region Extreme point creation by using a point projection based method
    172 
    173     /// <summary>
    174     /// This method creates extreme points by using a point projection based method.
    175     /// For each item there will be created three points and each of the points will be projected twice.
    176     /// The direction of the projection depends on position of the point.
    177     /// </summary>
    178     /// <param name="binPacking"></param>
    179     /// <param name="newItem"></param>
    180     /// <param name="position"></param>
    181     private void PointProjectionForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
    182       int newWidth = newItem.Width;
    183       int newDepth = newItem.Depth;
    184       var binShape = binPacking.BinShape;
    185       var sourcePoint = new PackingPosition(position.AssignedBin, position.X + newWidth, position.Y, position.Z);
    186       PointProjection(binPacking, sourcePoint, ProjectDown);
    187       PointProjection(binPacking, sourcePoint, ProjectBackward);
    188 
    189       sourcePoint = new PackingPosition(position.AssignedBin, position.X, position.Y + newItem.Height, position.Z);
    190       PointProjection(binPacking, sourcePoint, ProjectLeft);
    191       PointProjection(binPacking, sourcePoint, ProjectBackward);
    192 
    193       sourcePoint = new PackingPosition(position.AssignedBin, position.X, position.Y, position.Z + newDepth);
    194       PointProjection(binPacking, sourcePoint, ProjectDown);
    195       PointProjection(binPacking, sourcePoint, ProjectLeft);
    196     }
    197 
    198 
    199     /// <summary>
    200     /// Projects a given point by using the given projection method to the neares item.
    201     /// The given projection method returns a point which lies on a side of the nearest item in the direction.
    202     /// </summary>
    203     /// <param name="binPacking"></param>
    204     /// <param name="position"></param>
    205     /// <param name="projectionMethod"></param>
    206     private void PointProjection(BinPacking3D binPacking, PackingPosition position, Func<BinPacking3D, Vector3D, Vector3D> projectionMethod) {
    207       Vector3D sourcePoint = new Vector3D(position);
    208       if (sourcePoint.X < binPacking.BinShape.Width && sourcePoint.Y < binPacking.BinShape.Height && sourcePoint.Z < binPacking.BinShape.Depth) {
    209         Vector3D point = projectionMethod?.Invoke(binPacking, sourcePoint);
    210         if (point != null) {
    211           AddExtremePoint(binPacking, new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z));
    212         }
    213       }
    214     }
    215     #endregion
     53   
    21654
    21755    #region Extreme point creation by using an edge projection based method
    … …  
    24583    }
    24684    #endregion
    247 
    248     /// <summary>
    249     /// Updates the residual spaces.
    250     /// It removes not needed ones.
    251     /// A residual space will be removed if the space is a subspace of another one and
    252     /// the current one has no item below or both have an item below.
    253     /// </summary>
    254     /// <param name="binPacking"></param>
    255     /// <param name="item"></param>
    256     /// <param name="position"></param>
    257     protected override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    258     }
     85   
    25986
    26087    /// <summary>
    … …  
    609436      return eps as IEnumerable<Vector3D>;
    610437    }
    611 
    612 
    613 
    614438    #endregion
    615 
    616     /// <summary>
    617     /// Calculates the residual spaces for an extreme point.
    618     /// </summary>
    619     /// <param name="binPacking"></param>
    620     /// <param name="pos"></param>
    621     /// <returns></returns>
    622     protected override IEnumerable<ResidualSpace> CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) {
    623       return ResidualSpaceCalculatorFactory.CreateCalculator().CalculateResidualSpaces(binPacking, pos);
    624     }
     439   
    625440  }
    626 
    627 
    628441}

  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/PointProjectionBasedEPCreator.cs

    r15705 r15731  
    2121
    2222using HeuristicLab.Common;
     23using HeuristicLab.Problems.BinPacking3D.ExtremePointPruning;
    2324using HeuristicLab.Problems.BinPacking3D.Geometry;
    2425using HeuristicLab.Problems.BinPacking3D.ResidualSpaceCalculation;
    … …  
    4041    /// This lock object is needed because of creating the extreme points in an parallel for loop.
    4142    /// </summary>
    42     object _lockAddExtremePoint = new object();
     43    protected object _lockAddExtremePoint = new object();
    4344
    4445    protected override void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    4546      binPacking.ExtremePoints.Clear();
    4647
     48      if (binPacking.Items.Count <= 0) {
     49        return;
     50      }
     51
    4752      // generate all new extreme points parallel. This speeds up the creator.
    48       Parallel.ForEach(binPacking.Items, i => {
     53      var items = binPacking.Items.OrderBy(x => x.Value.Layer);
     54      Parallel.ForEach(items.Where(x => x.Value.Layer < item.Layer), i => {
    4955        PackingItem it = i.Value;
    50         PackingPosition p = binPacking.Positions[i.Key];
    51         GenerateNewExtremePointsForItem(binPacking, it, p);
     56        PackingPosition pos = binPacking.Positions[i.Key];
     57        GenerateNewExtremePointsForItem(binPacking, it, pos);
    5258      });
    53 
     59      ExtremePointPruningFactory.CreatePruning().PruneExtremePoints(ExtremePointPruningMethod.PruneBehind, new List<BinPacking3D>() { binPacking });
     60
     61      Parallel.ForEach(items.Where(x => x.Value.Layer >= item.Layer), i => {
     62        PackingItem it = i.Value;
     63        PackingPosition pos = binPacking.Positions[i.Key];
     64        GenerateNewExtremePointsForItem(binPacking, it, pos);
     65      });
     66     
    5467      // remove not needed extreme points.
    5568      foreach (var extremePoint in binPacking.ExtremePoints.ToList()) {
    … …  
    178191    /// <param name="newItem"></param>
    179192    /// <param name="position"></param>
    180     private void PointProjectionForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
     193    protected void PointProjectionForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
    181194      int newWidth = newItem.Width;
    182195      int newDepth = newItem.Depth;
    … …  
    210223          AddExtremePoint(binPacking, new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z));
    211224        }
    212       }
    213     }
    214     #endregion
    215 
    216     #region Extreme point creation by using an edge projection based method
    217 
    218     /// <summary>
    219     /// This method creates extreme points be projecting the edges of a given item
    220     ///   - left
    221     ///   - back
    222     ///   - down.
    223     /// A extreme point will be created, if an edge instersects with an edge of another item.
    224     /// </summary>
    225     /// <param name="binPacking"></param>
    226     /// <param name="newItem"></param>
    227     /// <param name="position"></param>
    228     private void EdgeProjectionForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
    229       int newWidth = newItem.Width;
    230       int newDepth = newItem.Depth;
    231       var binShape = binPacking.BinShape;
    232 
    233       foreach (var ep in GetEpsOnLeft(binPacking, newItem, position)) {
    234         AddExtremePoint(binPacking, ep.Key);
    235       }
    236 
    237       foreach (var ep in GetEpsBelow(binPacking, newItem, position)) {
    238         AddExtremePoint(binPacking, ep.Key);
    239       }
    240 
    241       foreach (var ep in GetEpsBehind(binPacking, newItem, position)) {
    242         AddExtremePoint(binPacking, ep.Key);
    243225      }
    244226    }
    … …  
    277259    }
    278260
    279     /// <summary>
    280     /// Returns true if an item is in the residual space of a given extrem point
    281     /// </summary>
    282     /// <param name="rs">KeyValuePair with the position of the extreme point and the size of the residual space</param>
    283     /// <param name="item">Given Item</param>
    284     /// <param name="position">Given position</param>
    285     /// <returns></returns>
    286     private bool ItemIsInRs(KeyValuePair<PackingPosition, ResidualSpace> rs, PackingItem item, PackingPosition position) {
    287       return GetVertices(item, position).Where(pos => pos.IsInside(rs.Key, rs.Value)).Any();
    288     }
    289 
    290     protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelow(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    291       return binPacking.Items.Select(x => new {
    292         Item = x.Value,
    293         Position = binPacking.Positions[x.Key]
    294       }).Where(x => x.Position.Y < position.Y)
    295           .Select(x => Tuple.Create(x.Position, x.Item));
    296     }
    297 
    298     protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBehind(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    299       return binPacking.Items.Select(x => new {
    300         Item = x.Value,
    301         Position = binPacking.Positions[x.Key]
    302       }).Where(x => x.Position.Z < position.Z)
    303           .Select(x => Tuple.Create(x.Position, x.Item));
    304     }
    305 
    306     protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnLeft(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    307       return binPacking.Items.Select(x => new {
    308         Item = x.Value,
    309         Position = binPacking.Positions[x.Key]
    310       }).Where(x => x.Position.X < position.X)
    311           .Select(x => Tuple.Create(x.Position, x.Item));
    312     }
    313 
    314     /// <summary>
    315     /// Returns the extreme points and its related residual spaces on the left side of an given item.
    316     /// This extreme points are being created by intersecting two edges on the left side of the given item
    317     /// (left - in front, left - on top) with all edges on the right side of all other items int the bin packing.
    318     /// </summary>
    319     /// <param name="item"></param>
    320     /// <param name="position"></param>
    321     /// <returns></returns>
    322     private IDictionary<PackingPosition, IEnumerable<ResidualSpace>> GetEpsOnLeft(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    323       var eps = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();
    324       IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsOnLeft(binPacking, item, position);
    325       var edges = GetProjectionEdgesOnLeft(item, position);
    326 
    327       foreach (var otherItem in items) {
    328         if (position.Equals(otherItem.Item1)) {
    329           continue;
    330         }
    331 
    332         var otherItemEdges = GetEdgesOnRight(otherItem.Item2, otherItem.Item1);
    333         // left - in front
    334         foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(1, 0, 0))) {
    335           if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
    336             // As this edge has a vertical direction, every point of intersection won't have an item below.
    337             // So finally it is being projected down.
    338             var point = ProjectDown(binPacking, ProjectLeft(binPacking, ep));
    339             var residualSpaces = CalculateResidualSpace(binPacking, point);
    340             var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
    341             if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
    342               eps.Add(newExtremePoint, residualSpaces);
    343             }
    344           }
    345         }
    346 
    347         // left - on top
    348         foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(1, 0, 0))) {
    349           if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
    350             var point = ProjectLeft(binPacking, ep);
    351             var residualSpaces = CalculateResidualSpace(binPacking, point);
    352             var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
    353             if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
    354               eps.Add(newExtremePoint, residualSpaces);
    355             }
    356           }
    357         }
    358       }
    359       return eps;
    360     }
    361 
    362 
    363     /// <summary>
    364     /// Returns the extreme points and its related residual spaces below of an given item.
    365     /// This extreme points are being created by intersecting two edges below of the given item
    366     /// (below - in front, below - right) with all edges on top side of all other items int the bin packing.
    367     /// </summary>
    368     /// <param name="item"></param>
    369     /// <param name="position"></param>
    370     /// <returns></returns>
    371     private IDictionary<PackingPosition, IEnumerable<ResidualSpace>> GetEpsBelow(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    372       var eps = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();
    373       IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsBelow(binPacking, position);
    374       var edges = GetProjectionEdgesBelow(item, position);
    375 
    376       foreach (var otherItem in items) {
    377         if (position.Equals(otherItem.Item1)) {
    378           continue;
    379         }
    380 
    381         var otherItemEdges = GetEdgesOnTop(otherItem.Item2, otherItem.Item1);
    382         // below - in front
    383         foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(0, 1, 0))) {
    384           if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
    385             var point = ProjectDown(binPacking, ep);
    386             var residualSpaces = CalculateResidualSpace(binPacking, point);
    387             var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
    388             if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
    389               eps.Add(newExtremePoint, residualSpaces);
    390             }
    391           }
    392         }
    393 
    394         // below - right
    395         foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(0, 1, 0))) {
    396           if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
    397             var point = ProjectDown(binPacking, ep);
    398             var residualSpaces = CalculateResidualSpace(binPacking, point);
    399             var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
    400             if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
    401               eps.Add(newExtremePoint, residualSpaces);
    402             }
    403           }
    404         }
    405       }
    406       return eps;
    407     }
    408 
    409     /// <summary>
    410     /// Returns the extreme points and its related residual spaces below of an given item.
    411     /// This extreme points are being created by intersecting two edges below of the given item
    412     /// (right - behind, on top - behind) with all edges on top side of all other items int the bin packing.
    413     /// </summary>
    414     /// <param name="item"></param>
    415     /// <param name="position"></param>
    416     /// <returns></returns>
    417     private IDictionary<PackingPosition, IEnumerable<ResidualSpace>> GetEpsBehind(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    418       var eps = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();
    419       IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsBehind(binPacking, position);
    420       var edges = GetProjectionEdgesBehind(item, position);
    421 
    422       foreach (var otherItem in items) {
    423         if (position.Equals(otherItem.Item1)) {
    424           continue;
    425         }
    426 
    427         var otherItemEdges = GetEdgesInFront(otherItem.Item2, otherItem.Item1);
    428         // right - behind
    429         foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(0, 0, 1))) {
    430           if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
    431             // As this edge has a vertical direction, every point of intersection won't have an item below.
    432             // So finally it is being projected down.
    433             var point = ProjectDown(binPacking, ProjectBackward(binPacking, ep));
    434             var residualSpaces = CalculateResidualSpace(binPacking, point);
    435             var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
    436             if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
    437               eps.Add(newExtremePoint, residualSpaces);
    438             }
    439           }
    440         }
    441 
    442         // on top - behind
    443         foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(0, 0, 1))) {
    444           if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
    445             var point = ProjectBackward(binPacking, ep);
    446             var residualSpaces = CalculateResidualSpace(binPacking, point);
    447             var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
    448             if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
    449               eps.Add(newExtremePoint, residualSpaces);
    450             }
    451           }
    452         }
    453       }
    454       return eps;
    455     }
    456 
    457     #region Methods for getting the edges for items
    458 
    459     /// <summary>
    460     /// Returns an array of packing position which represents the vertices of an item.
    461     /// The position of a vertex in the array is mapped to an item as followed:
    462     ///      4----------5
    463     ///     /|         /|
    464     ///    / |        / |
    465     ///   /  0-------/--1
    466     ///  6--/-------7  /
    467     ///  | /        | /
    468     ///  |/         |/
    469     ///  2----------3
    470     /// 
    471     ///  0 = (0,0,0)
    472     /// </summary>
    473     /// <param name="item"></param>
    474     /// <param name="position"></param>
    475     /// <returns></returns>
    476     private Vector3D[] GetVertices(PackingItem item, PackingPosition position) {
    477       int width = item.Width;
    478       int depth = item.Depth;
    479       return new Vector3D[] {
    480         new Vector3D(position.X + 0,     position.Y + 0,           position.Z + 0), // (0,0,0)
    481         new Vector3D(position.X + width, position.Y + 0,           position.Z + 0), // (x,0,0)
    482         new Vector3D(position.X + 0,     position.Y + 0,           position.Z + depth), // (0,0,z)
    483         new Vector3D(position.X + width, position.Y + 0,           position.Z + depth), // (x,0,z)
    484 
    485         new Vector3D(position.X + 0,     position.Y + item.Height, position.Z + 0), // (0,y,0)
    486         new Vector3D(position.X + width, position.Y + item.Height, position.Z + 0), // (x,y,0)
    487         new Vector3D(position.X + 0,     position.Y + item.Height, position.Z + depth), // (0,y,z)
    488         new Vector3D(position.X + width, position.Y + item.Height, position.Z + depth), //(x,y,z)
    489       };
    490     }
    491 
    492     private Edge3D[] GetProjectionEdgesOnLeft(PackingItem item, PackingPosition position) {
    493       Vector3D[] points = GetVertices(item, position);
    494 
    495       return new Edge3D[] {
    496         new Edge3D(points[2], points[6]),
    497         new Edge3D(points[6], points[4])
    498       };
    499     }
    500 
    501     private Edge3D[] GetProjectionEdgesBelow(PackingItem item, PackingPosition position) {
    502       Vector3D[] points = GetVertices(item, position);
    503 
    504       return new Edge3D[] {
    505         new Edge3D(points[2], points[3]),
    506         new Edge3D(points[3], points[1])
    507       };
    508     }
    509 
    510     private Edge3D[] GetProjectionEdgesBehind(PackingItem item, PackingPosition position) {
    511       Vector3D[] points = GetVertices(item, position);
    512 
    513       return new Edge3D[] {
    514         new Edge3D(points[1], points[5]),
    515         new Edge3D(points[5], points[4])
    516       };
    517     }
    518 
    519     /// <summary>
    520     /// Returns an array of edges which contains all edges of the rigth side of an given item.
    521     /// </summary>
    522     /// <param name="item"></param>
    523     /// <param name="position"></param>
    524     /// <returns></returns>
    525     private Edge3D[] GetEdgesOnRight(PackingItem item, PackingPosition position) {
    526       Vector3D[] points = GetVertices(item, position);
    527 
    528       return new Edge3D[] {
    529         new Edge3D(points[1], points[5]),
    530         new Edge3D(points[5], points[7]),
    531         new Edge3D(points[7], points[3]),
    532         new Edge3D(points[3], points[1])
    533       };
    534     }
    535 
    536     /// <summary>
    537     /// Returns an array of edges which contains all edges on the top of an given item.
    538     /// </summary>
    539     /// <param name="item"></param>
    540     /// <param name="position"></param>
    541     /// <returns></returns>
    542     private Edge3D[] GetEdgesOnTop(PackingItem item, PackingPosition position) {
    543       Vector3D[] points = GetVertices(item, position);
    544 
    545       return new Edge3D[] {
    546         new Edge3D(points[4], points[5]),
    547         new Edge3D(points[5], points[7]),
    548         new Edge3D(points[7], points[6]),
    549         new Edge3D(points[6], points[4])
    550       };
    551     }
    552 
    553     /// <summary>
    554     /// Returns an array of edges which contains all edges in front of an given item.
    555     /// </summary>
    556     /// <param name="item"></param>
    557     /// <param name="position"></param>
    558     /// <returns></returns>
    559     private Edge3D[] GetEdgesInFront(PackingItem item, PackingPosition position) {
    560       Vector3D[] points = GetVertices(item, position);
    561 
    562       return new Edge3D[] {
    563         new Edge3D(points[2], points[3]),
    564         new Edge3D(points[3], points[7]),
    565         new Edge3D(points[7], points[6]),
    566         new Edge3D(points[6], points[2])
    567       };
    568     }
    569 
    570     #endregion
    571 
    572 
    573     #region Intersections
    574 
    575     /// <summary>
    576     /// Returns a collection of points where a given edge (projectedEdge) intersects with other edges.
    577     /// The given edge (projectedEdge) will be projected by using the given vector direction
    578     /// and a edge of the given edge collection.
    579     /// The returned collecten can be empty.
    580     /// </summary>
    581     /// <param name="projectedEdge"></param>
    582     /// <param name="edges"></param>
    583     /// <param name="direction"></param>
    584     /// <returns></returns>
    585     private IEnumerable<Vector3D> IntersectionsForItem(Edge3D projectedEdge, Edge3D[] edges, Vector3D direction = null) {
    586       IList<Vector3D> eps = new List<Vector3D>();
    587       foreach (var edge in edges) {
    588         Edge3D e = projectedEdge;
    589         if (direction != null) {
    590           if (direction.X != 0) {
    591             e.Start.X = edge.Start.X;
    592             e.End.X = edge.End.X;
    593           } else if (direction.Y != 0) {
    594             e.Start.Y = edge.Start.Y;
    595             e.End.Y = edge.End.Y;
    596           } else if (direction.Z != 0) {
    597             e.Start.Z = edge.Start.Z;
    598             e.End.Z = edge.End.Z;
    599           }
    600         }
    601 
    602         var ep = edge.Intersects(e);
    603         if (ep != null) {
    604           eps.Add(ep);
    605         }
    606       }
    607 
    608       return eps as IEnumerable<Vector3D>;
    609     }
    610 
    611 
    612 
    613     #endregion
    614261
    615262    /// <summary>

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

    r15618 r15731  
    7373      }
    7474    }
    75    
    7675  }
    7776}

  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/ThreeDInstanceParser.cs

    r15646 r15731  
    5959                RotateEnabled = rotate == 0 ? false : true,
    6060                TiltEnabled = tilt == 0 ? false : true,
    61                 IsStackabel = stack == 0 ? false : true
     61                IsStackabel = stack == 0 ? false : true,
     62                SupportedWeight = weight
    6263              };
    6364              Items.Add(item);

  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Material/MaterialType.cs

    r15705 r15731  
    88 
    99  public enum MaterialType {
    10     EuroPallet,
     10    EuroPallet = 0,
     11    IncaPallet,
    1112    Wood,
     13    Paperboard,
    1214    Steel,
    13     Paperboard
     15    ScreenPrintingPlate,
     16    NonSlipMat,
     17    Carriage
    1418  }
    1519}

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

    r15705 r15731  
    125125      return clonedItems;
    126126    }
    127 
     127   
    128128  }
    129129}

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

    r15617 r15731  
    5353          binPacker = new BinPackerMinRSLeft();
    5454          break;
     55        case FittingMethod.FormClosure:
     56          binPacker = new BinPackerFormClosure();
     57          break;
    5558        default:
    5659          throw new ArgumentException("Unknown fitting method: " + fittingMethod);

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

    r15705 r15731  
    9494      ExtremePointPruningFactory.CreatePruning().PruneExtremePoints(epPruningMethod, packingList);
    9595    }
     96   
    9697
    9798    /// <summary>
    … …  
    107108      var remainingNotWeightSupportedItems = new List<int>();
    108109      foreach (var itemId in new List<int>(remainingIds)) {
    109         var item = items[itemId];
     110        var item = items[itemId];       
    110111
    111112        // If an item doesn't support any weight it should have a minimum waste of the residual space.

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

    r15705 r15731  
    295295
    296296    public bool SupportsStacking(IPackingItem other) {
    297       return ((other.Layer < this.Layer) || (other.Layer.Equals(this.Layer) && other.Weight <= this.Weight));
     297      return other.Layer <= this.Layer && SupportedWeight > 0;
    298298    }
    299299    #endregion

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

    r15646 r15731  
    6666      }
    6767
     68      if (evaluatedThis.Item4 > evaluatedOther.Item4) {
     69        return false;
     70      }
     71
    6872      if (evaluatedThis.Item3 > evaluatedOther.Item3) {
    6973        return false;

  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Sorting/PermutationPackingItemSorter.cs

    r15705 r15731  
    136136      return new Permutation(PermutationTypes.Absolute,
    137137                    items.Select((v, i) => new { Index = i, Item = v })
    138                          .OrderByDescending(x => x.Item.Layer)
     138                         .OrderBy(x => x.Item.Layer)
    139139                         .ThenByDescending(x => x.Item.Depth * x.Item.Width * x.Item.Height)
    140140                         .ThenByDescending(x => x.Item.Height)
    … …  
    150150      return new Permutation(PermutationTypes.Absolute,
    151151                    items.Select((v, i) => new { Index = i, Item = v })
    152                          .OrderByDescending(x => x.Item.Layer)
     152                         .OrderBy(x => x.Item.Layer)
    153153                         .ThenByDescending(x => x.Item.Height)
    154154                         .ThenByDescending(x => x.Item.Depth * x.Item.Width * x.Item.Height)
    … …  
    164164      return new Permutation(PermutationTypes.Absolute,
    165165                    items.Select((v, i) => new { Index = i, Item = v })
    166                          .OrderByDescending(x => x.Item.Layer)
     166                         .OrderBy(x => x.Item.Layer)
    167167                         .ThenByDescending(x => x.Item.Depth * x.Item.Width)
    168168                         .ThenByDescending(x => x.Item.Height)
    … …  
    178178      return new Permutation(PermutationTypes.Absolute,
    179179                    items.Select((v, i) => new { Index = i, Item = v })
    180                          .OrderByDescending(x => x.Item.Layer)
     180                         .OrderBy(x => x.Item.Layer)
    181181                         .ThenByDescending(x => x.Item.Height)
    182182                         .ThenByDescending(x => x.Item.Depth * x.Item.Width)
    … …  
    198198                items.Select((v, i) => new { Index = i, Item = v, ClusterId = (int)(Math.Ceiling(v.Width * v.Depth / clusterRange)) })
    199199                    .GroupBy(x => x.ClusterId)
    200                     .Select(x => new { Cluster = x.Key, Items = x.OrderByDescending(z => z.Item.Layer).ThenByDescending(y => y.Item.Height).ToList() })
     200                    .Select(x => new { Cluster = x.Key, Items = x.OrderBy(z => z.Item.Layer).ThenByDescending(y => y.Item.Height).ToList() })
    201201                    .OrderByDescending(x => x.Cluster)
    202202                    .SelectMany(x => x.Items)
    … …  
    218218                items.Select((v, i) => new { Index = i, Item = v, ClusterId = (int)(Math.Ceiling(v.Height / clusterRange2)) })
    219219                    .GroupBy(x => x.ClusterId)
    220                     .Select(x => new { Cluster = x.Key, Items = x.OrderByDescending(z => z.Item.Layer).ThenByDescending(y => y.Item.Depth * y.Item.Width).ToList() })
     220                    .Select(x => new { Cluster = x.Key, Items = x.OrderBy(z => z.Item.Layer).ThenByDescending(y => y.Item.Depth * y.Item.Width).ToList() })
    221221                    .OrderByDescending(x => x.Cluster)
    222222                    .SelectMany(x => x.Items)

  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj

    r15646 r15731  
    113113    <Compile Include="3D\ExtremePointPruning\IExtremePointPruning.cs" />
    114114    <Compile Include="3D\Geometry\Edge3D.cs" />
    115     <Compile Include="3D\Material\FrictionalCoefficientTable.cs" />
     115    <Compile Include="3D\Graph\VertexWithItemId.cs" />
    116116    <Compile Include="3D\Material\MaterialType.cs" />
    117117    <Compile Include="3D\Packer\BinPacker.cs" />
    … …  
    128128    <Compile Include="3D\Packer\BinPackerFreeVolumeBestFit.cs" />
    129129    <Compile Include="3D\Packer\BinPackerMinRSLeft.cs" />
     130    <Compile Include="3D\Packer\BinPackerFormClosure.cs" />
    130131    <Compile Include="3D\Packer\BinPackerResidualSpaceBestFit.cs" />
    131132    <Compile Include="3D\Instances\ThreeDInstanceDescriptor.cs" />
Note: See TracChangeset for help on using the changeset viewer.