source: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs @ 15731

Last change on this file since 15731 was 15731, checked in by rhanghof, 3 years ago

#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.
File size: 19.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2018 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 System;
23using System.Collections.Generic;
24using System.Linq;
25using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
26using HeuristicLab.Core;
27using HeuristicLab.Common;
28using HeuristicLab.Problems.BinPacking;
29using HeuristicLab.Problems.BinPacking3D.Geometry;
30using HeuristicLab.Collections;
31using HeuristicLab.Problems.BinPacking3D.Graph;
32
33namespace HeuristicLab.Problems.BinPacking3D {
34  [Item("BinPacking3D", "Represents a single-bin packing for a 3D bin-packing problem.")]
35  [StorableClass]
36  public class BinPacking3D : BinPacking<PackingPosition, PackingShape, PackingItem> {
37
38    [Storable]
39    public IDictionary<PackingPosition, IEnumerable<ResidualSpace>> ExtremePoints { get; protected set; }
40
41    [Storable]
42    public IDirectedGraph WeightDistirbution { get; protected set; }
43
44    public BinPacking3D(PackingShape binShape)
45      : base(binShape) {
46      ExtremePoints = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();
47      ExtremePoints.Add(binShape.Origin, new List<ResidualSpace>() { ResidualSpace.Create(binShape.Width, binShape.Height, binShape.Depth) });
48
49      WeightDistirbution = new DirectedGraph();
50    }
51
52    [StorableConstructor]
53    protected BinPacking3D(bool deserializing) : base(deserializing) { }
54
55    protected BinPacking3D(BinPacking3D original, Cloner cloner)
56      : base(original, cloner) {
57      this.ExtremePoints = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();
58      foreach (var extremePoint in original.ExtremePoints) {
59        var residualSpaces = new List<ResidualSpace>();
60        foreach (var residualSpace in extremePoint.Value) {
61          residualSpaces.Add(cloner.Clone(residualSpace));
62        }
63        ExtremePoints.Add(cloner.Clone(extremePoint.Key), residualSpaces);
64      }
65
66      // todo clone WeightDistirbution graph
67    }
68
69    public override IDeepCloneable Clone(Cloner cloner) {
70      return new BinPacking3D(this, cloner);
71    }
72
73
74
75    /// <summary>
76    /// Puts a given item into the bin packing at the given position.
77    /// </summary>
78    /// <param name="itemID">Offset in the internal item array</param>
79    /// <param name="item">Item</param>
80    /// <param name="position">Position of the item in the bin packing</param>
81    public override void PackItem(int itemID, PackingItem item, PackingPosition position) {
82      Items[itemID] = item;
83      Positions[itemID] = position;
84      ExtremePoints.Remove(position);
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
155
156    #region MassPoint
157
158    /// <summary>
159    /// This property contains the value of the mass point for the current bin packing.
160    /// </summary>
161    public Tuple<double, double, double> MassPoint { get { return CalculateMassPoint(); } }
162
163    private Tuple<double, double, double> CalculateMassPoint() {
164      var packingMassPoint = new { X = 0.0, Y = 0.0, Z = 0.0 };
165      var totalWeight = 0.0;
166      foreach (var item in Items) {
167        var position = Positions[item.Key];
168        var w = item.Value.Width;
169        var h = item.Value.Height;
170        var d = item.Value.Depth;
171
172        var massPoint = new { X = position.X + w / 2.0, Y = position.Y + h / 2.0, Z = position.Z + d / 2.0 };
173        var weight = Math.Max(item.Value.Weight, 1);
174        if (packingMassPoint == null) {
175          packingMassPoint = massPoint;
176          totalWeight += weight;
177        } else {
178          var newTotalWeight = totalWeight + weight;
179          packingMassPoint = new {
180            X = (massPoint.X * weight + packingMassPoint.X * totalWeight) / newTotalWeight,
181            Y = (massPoint.Y * weight + packingMassPoint.Y * totalWeight) / newTotalWeight,
182            Z = (massPoint.Z * weight + packingMassPoint.Z * totalWeight) / newTotalWeight
183          };
184          totalWeight = newTotalWeight;
185        }
186      }
187
188      return Tuple.Create<double, double, double>(packingMassPoint.X, packingMassPoint.Y, packingMassPoint.Z);
189    }
190    #endregion
191
192    #region Position feasability
193
194    /// <summary>
195    /// In this case feasability is defined as following:
196    /// 1. the point is supported by something;
197    /// 2. the item does not collide with another already packed item
198    /// </summary>
199    /// <param name="item"></param>
200    /// <param name="position"></param>
201    /// <param name="stackingConstraints"></param>
202    /// <returns></returns>
203    public override bool IsPositionFeasible(PackingItem item, PackingPosition position, bool stackingConstraints) {
204      return ItemCanBePlaced(item, position) && CheckStackingConstraints(item, position, stackingConstraints);
205    }
206
207
208
209    /// <summary>
210    /// Returns true if a given item can be placed in the current bin
211    /// </summary>
212    /// <param name="givenItem"></param>
213    /// <param name="givenItemPosition"></param>
214    /// <returns></returns>
215    private bool ItemCanBePlaced(PackingItem givenItem, PackingPosition givenItemPosition) {
216      // Check if the boundings of the bin would injured
217      if (givenItemPosition.X + givenItem.Width > BinShape.Width ||
218          givenItemPosition.Y + givenItem.Height > BinShape.Height ||
219          givenItemPosition.Z + givenItem.Depth > BinShape.Depth) {
220        return false;
221      }
222
223      //if the given item collides with any other item, it can not be placed
224      foreach (var item in Items) {
225        if (ItemsCollides(new Tuple<PackingPosition, PackingItem>(Positions[item.Key], item.Value),
226                          new Tuple<PackingPosition, PackingItem>(givenItemPosition, givenItem))) {
227          return false;
228        }
229      }
230      return true;
231    }
232
233    /// <summary>
234    /// Checks if two given items in a space collides
235    /// </summary>
236    /// <param name="t1"></param>
237    /// <param name="t2"></param>
238    /// <returns></returns>
239    private bool ItemsCollides(Tuple<PackingPosition, PackingItem> t1, Tuple<PackingPosition, PackingItem> t2) {
240      var position1 = t1.Item1;
241      var item1 = t1.Item2;
242      var position2 = t2.Item1;
243      var item2 = t2.Item2;
244      var cx = (position2.X == position1.X) || (position2.X < position1.X && position2.X + item2.Width > position1.X) || (position2.X > position1.X && position1.X + item1.Width > position2.X);
245      var cy = (position2.Y == position1.Y) || (position2.Y < position1.Y && position2.Y + item2.Height > position1.Y) || (position2.Y > position1.Y && position1.Y + item1.Height > position2.Y);
246      var cz = (position2.Z == position1.Z) || (position2.Z < position1.Z && position2.Z + item2.Depth > position1.Z) || (position2.Z > position1.Z && position1.Z + item1.Depth > position2.Z);
247      return cx && cy && cz;
248    }
249
250    /// <summary>
251    /// Checks the stacking constraints. This method depends that the given item can be placed at this position
252    /// </summary>
253    /// <param name="item"></param>
254    /// <param name="position"></param>
255    /// <param name="stackingConstraints"></param>
256    /// <returns></returns>
257    private bool CheckStackingConstraints(PackingItem item, PackingPosition position, bool stackingConstraints) {
258      if (position.Y == 0 || !stackingConstraints && HasOnePointWithAnItemBelow(item, position)) {
259        return true;
260      }
261
262      return IsStaticStable(item, position) && IsWeightSupported(item, position);
263    }
264
265    /// <summary>
266    /// Checks if a given item has any point lieing on another item.
267    /// </summary>
268    /// <param name="item"></param>
269    /// <param name="position"></param>
270    /// <returns></returns>
271    private bool HasOnePointWithAnItemBelow(PackingItem item, PackingPosition position) {
272      bool p1, p2, p3, p4;
273      PointsLiesOnAnStackableItem(item, position, out p1, out p2, out p3, out p4);
274
275      return p1 || p2 || p3 || p4;
276    }
277
278    /// <summary>
279    /// Checks if a given item is static stable.
280    /// A item is static stable if all edges have an object below.
281    /// </summary>
282    /// <param name="item"></param>
283    /// <param name="position"></param>
284    /// <returns></returns>
285    public override bool IsStaticStable(PackingItem item, PackingPosition position) {
286      bool p1, p2, p3, p4;
287      PointsLiesOnAnStackableItem(item, position, out p1, out p2, out p3, out p4);
288      return p1 && p2 && p3 && p4;
289    }
290
291    /// <summary>
292    /// This method sets the out parameters p1 ... p4 if the point lies on another item.
293    /// p1 ... p3 represents one point on the bottom side of an given item.
294    /// +---------+
295    /// |p1     p2|
296    /// |         |
297    /// |p4     p3|
298    /// +---------+
299    /// </summary>
300    /// <param name="item">Given item</param>
301    /// <param name="position">Given item position</param>
302    /// <param name="p1"></param>
303    /// <param name="p2"></param>
304    /// <param name="p3"></param>
305    /// <param name="p4"></param>
306    private void PointsLiesOnAnStackableItem(PackingItem item, PackingPosition position, out bool p1, out bool p2, out bool p3, out bool p4) {
307      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP1;
308      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP2;
309      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP3;
310      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP4;
311
312      GetItemsUnderItemWithContact(item, position, out itemsP1, out itemsP2, out itemsP3, out itemsP4);
313
314      p1 = itemsP1.Where(x => x.Item2.IsStackabel && position.X < x.Item1.X + x.Item2.Width && position.Z < x.Item1.Z + x.Item2.Depth).Any();
315      p2 = itemsP2.Where(x => x.Item2.IsStackabel && position.X + item.Width > x.Item1.X && position.Z < x.Item1.Z + x.Item2.Depth).Any();
316      p3 = itemsP3.Where(x => x.Item2.IsStackabel && position.X + item.Width > x.Item1.X && position.Z + item.Depth > x.Item1.Z).Any();
317      p4 = itemsP4.Where(x => x.Item2.IsStackabel && position.X < x.Item1.X + x.Item2.Width && position.Z + item.Depth > x.Item1.Z).Any();
318    }
319
320    /// <summary>
321    /// This method returns a collection for the out parameters itemsP1 ... itemsP4 with the items below
322    /// itemsP1 ... itemsP4 represents one point on the bottom side of an given item.
323    /// +---------+
324    /// |p1     p2|
325    /// |         |
326    /// |p4     p3|
327    /// +---------+
328    /// </summary>
329    /// <param name="item"></param>
330    /// <param name="position"></param>
331    /// <param name="itemsP1"></param>
332    /// <param name="itemsP2"></param>
333    /// <param name="itemsP3"></param>
334    /// <param name="itemsP4"></param>
335    private void GetItemsUnderItemWithContact(PackingItem item, PackingPosition position,
336                                   out IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP1,
337                                   out IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP2,
338                                   out IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP3,
339                                   out IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP4) {
340      itemsP1 = GetItemsBelowForPosition(new PackingPosition(0, position.X, position.Y, position.Z, false));
341      itemsP2 = GetItemsBelowForPosition(new PackingPosition(0, position.X + item.Width - 1, position.Y, position.Z, false));
342      itemsP3 = GetItemsBelowForPosition(new PackingPosition(0, position.X, position.Y, position.Z + item.Depth - 1, false));
343      itemsP4 = GetItemsBelowForPosition(new PackingPosition(0, position.X + item.Width - 1, position.Y, position.Z + item.Depth - 1, false));
344
345    }
346
347    /// <summary>
348    /// Returns a collection of items which are below a given point.
349    /// The top side of every item is at the same level as the Y-coordinate of the given position.
350    /// </summary>
351    /// <param name="position"></param>
352    /// <returns></returns>
353    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelowForPosition(PackingPosition position) {
354      return GetItemsBelow(position).Where(x => (x.Item1.Y + x.Item2.Height) == position.Y);
355    }
356
357    #region Weight supported
358    //old implementation
359    /// <summary>
360    /// Checks if a given the weight of an given item is supported by the items below.
361    /// </summary>
362    /// <param name="item"></param>
363    /// <param name="position"></param>
364    /// <returns></returns>
365    private bool IsWeightSupported(PackingItem item, PackingPosition position) {
366      if (position.Y == 0) {
367        return true;
368      }
369      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP1;
370      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP2;
371      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP3;
372      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP4;
373
374      GetItemsUnderItemWithContact(item, position, out itemsP1, out itemsP2, out itemsP3, out itemsP4);
375
376      return itemsP1.Where(x => x.Item2.SupportsStacking(item)).Any() &&
377        itemsP2.Where(x => x.Item2.SupportsStacking(item)).Any() &&
378        itemsP3.Where(x => x.Item2.SupportsStacking(item)).Any() &&
379        itemsP4.Where(x => x.Item2.SupportsStacking(item)).Any();
380    }
381
382    private double CalculateOverlay(Tuple<PackingPosition, PackingItem> item1, Tuple<PackingPosition, PackingItem> item2) {
383      var left = item1.Item1.X <= item2.Item1.X ? item1 : item2;
384      var right = item1.Item1.X <= item2.Item1.X ? item2 : item1;
385      var behind = item1.Item1.Z <= item2.Item1.Z ? item1 : item2;
386      var inFront = item1.Item1.Z <= item2.Item1.Z ? item2 : item1;
387
388      var overlayX = right.Item2.Width;
389      if (left.Item1.X + left.Item2.Width < right.Item1.X + right.Item2.Width) {
390        overlayX = left.Item1.X + left.Item2.Width - right.Item1.X;
391      }
392
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;
396      }
397
398      return overlayX * overlayZ;
399    }
400
401    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsAboveAnItem(PackingPosition position, PackingItem item) {
402      var selected = Items.Select(x => new {
403        Item = x.Value,
404        Position = Positions[x.Key]
405      }).Where(x => x.Position.Y == position.Y + item.Height)
406        .Where(x => x.Position.X <= position.X && x.Position.X + x.Item.Width > position.X ||
407                    x.Position.X > position.X && x.Position.X < position.X + item.Width)
408        .Where(x => x.Position.Z <= position.Z && x.Position.Z + x.Item.Height > position.Z ||
409                    x.Position.Z > position.Z && x.Position.Z < position.Z + item.Height);
410
411      return selected.Select(x => Tuple.Create(x.Position, x.Item));
412    }
413
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>
420    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsUnderAnItem(PackingPosition position, PackingItem item) {
421      var selected = Items.Select(x => new {
422        Item = x.Value,
423        Position = Positions[x.Key]
424      }).Where(x => x.Position.Y + x.Item.Height == position.Y)
425        .Where(x => x.Position.X <= position.X && x.Position.X + x.Item.Width > position.X ||
426                    x.Position.X > position.X && x.Position.X < position.X + item.Width)
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);
429
430      return selected.Select(x => Tuple.Create(x.Position, x.Item));
431    }
432
433    #endregion
434
435
436    #endregion
437
438    protected override void GenerateNewExtremePointsForNewItem(PackingItem newItem, PackingPosition position) {
439      throw new NotImplementedException();
440    }
441
442    #region Get items
443
444    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelow(PackingPosition pos) {
445      var line = new Line3D(pos, new Vector3D(0, 1, 0));
446      return Items.Select(x => new {
447        Item = x.Value,
448        Position = Positions[x.Key],
449        Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Top))
450      }).Where(x => x.Intersection != null && x.Intersection.Y <= pos.Y)
451        .Select(x => Tuple.Create(x.Position, x.Item));
452    }
453
454    #endregion
455  }
456}
Note: See TracBrowser for help on using the repository browser.