Changeset 15770 for branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking

Timestamp:

02/13/18 16:45:01 (7 years ago)

Author:

rhanghof

Message:

#2817:

• Added a graph to the BinPacking3D for calculating the weight distribution.
• Added some materials.

Location:

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

Files:

• BinPacking3D.cs (modified) (6 diffs)
• PackingItem.cs (modified) (4 diffs)
• PackingShape.cs (modified) (3 diffs)
• ResidualSpaceCalculation/ResidualSpaceCalculator.cs (modified) (2 diffs)

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

@@ -38 +38 @@
     [Storable]
     public IDictionary<PackingPosition, IEnumerable<ResidualSpace>> ExtremePoints { get; protected set; }
-
+    
     [Storable]
     public IDirectedGraph WeightDistirbution { get; protected set; }
@@ -64 +64 @@
       }
 
-      // todo clone WeightDistirbution graph
+      WeightDistirbution = original.WeightDistirbution.Clone() as IDirectedGraph;
     }
 
@@ -88 +88 @@
 
 
-    #region Graph for the calculating the weight distirbution        
+    #region Graph for the calculating the weight distirbution     
+    /// <summary>
+    /// The given item is added to the graph as the source vertex. 
+    /// Its items below are the target vertices.
+    /// </summary>
+    /// <param name="itemId"></param>
+    /// <param name="item"></param>
+    /// <param name="position"></param>
     private void AddToGraph(int itemId, PackingItem item, PackingPosition position) {
       var sourceVertex = new VertexWithItemId(itemId);
@@ -356 +363 @@
 
     #region Weight supported
+
     //old implementation
     /// <summary>
@@ -367 +375 @@
         return true;
       }
-      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP1;
-      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP2;
-      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP3;
-      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP4;
-
-      GetItemsUnderItemWithContact(item, position, out itemsP1, out itemsP2, out itemsP3, out itemsP4);
-
-      return itemsP1.Where(x => x.Item2.SupportsStacking(item)).Any() &&
-        itemsP2.Where(x => x.Item2.SupportsStacking(item)).Any() &&
-        itemsP3.Where(x => x.Item2.SupportsStacking(item)).Any() &&
-        itemsP4.Where(x => x.Item2.SupportsStacking(item)).Any();
-    }
+
+      var itemsBelow = Items.Where(x => Positions[x.Key].Y + x.Value.Height == position.Y)
+                            .Select(x => new {
+                              ItemId = x.Key,
+                              Item = Tuple.Create<PackingPosition, PackingItem>(Positions[x.Key], x.Value),                            
+                              Overlay = CalculateOverlay(Tuple.Create<PackingPosition, PackingItem>(Positions[x.Key], x.Value),
+                                                         Tuple.Create<PackingPosition, PackingItem>(position, item))
+                            })
+                            .Where(x=> x.Overlay > 0);
+
+      var area = item.Width * item.Depth;
+      foreach (var itemBelow in itemsBelow) {
+        var factor = itemBelow.Overlay / area;
+        if (itemBelow.Item.Item2.SupportedWeightPerSquareMeter < item.Weight / area) {
+          return false;
+        }
+
+        if (!IsWeightSupportedRec(itemBelow.Item.Item2, itemBelow.ItemId, item.Weight, factor)) {
+          return false;
+        }
+      }
+      return true;
+    }
+
+    private bool IsWeightSupportedRec(PackingItem item, int itemId, double weigth, double factor) {
+      var stackedWeight = GetStackedWeightForItemId(itemId);
+      if (!item.SupportWeight(weigth * factor + stackedWeight)) {
+        return false;
+      }
+
+      var arcs = WeightDistirbution.Arcs.Where(x => ((VertexWithItemId)x.Source).ItemId == itemId);
+      foreach (var arc in arcs) {
+        var targetItemId = ((VertexWithItemId)arc.Target).ItemId;
+        var targetItem = Items[targetItemId];
+        if (!IsWeightSupportedRec(targetItem, targetItemId, weigth, factor * arc.Weight)) {
+          return false;
+        }
+      }
+
+      return true;
+    }
+    
+
 
     private double CalculateOverlay(Tuple<PackingPosition, PackingItem> item1, Tuple<PackingPosition, PackingItem> item2) {
@@ -452 +491 @@
     }
 
+    public IEnumerable<PackingItem> GetItemsBelow(int itemId) {
+      var item = Items[itemId];
+      var position = Positions[itemId];
+
+      var itemsBelow = Items.Where(x => Positions[x.Key].Y + x.Value.Height == position.Y &&
+                                        CalculateOverlay(Tuple.Create<PackingPosition, PackingItem>(Positions[x.Key], x.Value),
+                                                         Tuple.Create<PackingPosition, PackingItem>(position, item)) > 0)
+                            .Select(x => x.Value);
+      return itemsBelow;
+    }
+
     #endregion
   }

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

@@ -60 +60 @@
     }
 
-    #region Material
-    public IFixedValueParameter<EnumValue<MaterialType>> MaterialBottomParameter {
-      get { return (IFixedValueParameter<EnumValue<MaterialType>>)Parameters["MaterialBottom"]; }
-    }
-    public MaterialType MaterialBottom {
-      get { return MaterialBottomParameter.Value.Value; }
-      set { MaterialBottomParameter.Value.Value = value; }
-    }
+    #region Material    
 
     public IFixedValueParameter<EnumValue<MaterialType>> MaterialTopParameter {
@@ -84 +77 @@
       get { return SupportedWeightParameter.Value.Value; }
       set { SupportedWeightParameter.Value.Value = value; }
+    }
+
+    public double SupportedWeightPerSquareMeter {
+      get {
+        return SupportedWeight / (Width * Depth);
+      }
     }
 
@@ -297 +296 @@
       return other.Layer <= this.Layer && SupportedWeight > 0;
     }
+        
+    public bool SupportWeight(double weigth) {
+      return SupportedWeight >= weigth;
+    }
     #endregion
 
@@ -314 +317 @@
 
       Parameters.Add(new FixedValueParameter<EnumValue<MaterialType>>("MaterialTop"));
-      Parameters.Add(new FixedValueParameter<EnumValue<MaterialType>>("MaterialBottom"));
 
       Parameters.Add(new FixedValueParameter<DoubleValue>("SupportedWeight"));

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

@@ -27 +27 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Problems.BinPacking;
+using HeuristicLab.Problems.BinPacking3D.Material;
 
 namespace HeuristicLab.Problems.BinPacking3D {
@@ -57 +58 @@
     }
 
+    public IFixedValueParameter<EnumValue<MaterialType>> MaterialBottomParameter {
+      get { return (IFixedValueParameter<EnumValue<MaterialType>>)Parameters["MaterialBottom"]; }
+    }
+    public MaterialType MaterialBottom {
+      get { return MaterialBottomParameter.Value.Value; }
+      set { MaterialBottomParameter.Value.Value = value; }
+    }
+
     [StorableConstructor]
     protected PackingShape(bool deserializing) : base(deserializing) { }
@@ -68 +77 @@
       Parameters.Add(new FixedValueParameter<IntValue>("Height"));
       Parameters.Add(new FixedValueParameter<IntValue>("Depth"));
+      Parameters.Add(new FixedValueParameter<EnumValue<MaterialType>>("MaterialBottom"));
+
+      MaterialBottom = MaterialType.ScreenPrintingPlate;
 
       RegisterEvents();

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ResidualSpaceCalculation/ResidualSpaceCalculator.cs

@@ -20 +20 @@
 #endregion
 
+using HeuristicLab.Core;
 using HeuristicLab.Problems.BinPacking3D.Geometry;
 using System;
@@ -26 +27 @@
 using System.Text;
 using System.Threading.Tasks;
+using HeuristicLab.Common;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 
 namespace HeuristicLab.Problems.BinPacking3D.ResidualSpaceCalculation {
-  internal class ResidualSpaceCalculator : IResidualSpaceCalculator {
+  internal class ResidualSpaceCalculator : Item, IResidualSpaceCalculator {
 
     internal ResidualSpaceCalculator() {}
-    
+
+    [StorableConstructor]
+    protected ResidualSpaceCalculator(bool deserializing) : base(deserializing) { }
+
+    protected ResidualSpaceCalculator(ResidualSpaceCalculator original, Cloner cloner) 
+      : base(original, cloner) {
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new ResidualSpaceCalculator(this, cloner);
+    }
+
     public IEnumerable<ResidualSpace> CalculateResidualSpaces(BinPacking3D binPacking, Vector3D point) {
       IList<ResidualSpace> residualSpaces = new List<ResidualSpace>();