Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 15866 was 15770, checked in by rhanghof, 7 years ago

#2817:

  • Added a graph to the BinPacking3D for calculating the weight distribution.
  • Added some materials.
File size: 21.3 KB
RevLine 
[14162]1#region License Information
2/* HeuristicLab
[15617]3 * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
[14162]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
[15230]22using System;
[14162]23using System.Collections.Generic;
24using System.Linq;
25using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
26using HeuristicLab.Core;
27using HeuristicLab.Common;
28using HeuristicLab.Problems.BinPacking;
[15454]29using HeuristicLab.Problems.BinPacking3D.Geometry;
[15488]30using HeuristicLab.Collections;
[15731]31using HeuristicLab.Problems.BinPacking3D.Graph;
[14162]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> {
[15646]37
[15241]38    [Storable]
[15554]39    public IDictionary<PackingPosition, IEnumerable<ResidualSpace>> ExtremePoints { get; protected set; }
[15770]40   
[15731]41    [Storable]
42    public IDirectedGraph WeightDistirbution { get; protected set; }
43
[14162]44    public BinPacking3D(PackingShape binShape)
45      : base(binShape) {
[15554]46      ExtremePoints = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();
[15731]47      ExtremePoints.Add(binShape.Origin, new List<ResidualSpace>() { ResidualSpace.Create(binShape.Width, binShape.Height, binShape.Depth) });
[15646]48
[15731]49      WeightDistirbution = new DirectedGraph();
[15520]50    }
[15488]51
[14162]52    [StorableConstructor]
53    protected BinPacking3D(bool deserializing) : base(deserializing) { }
[15520]54
[14162]55    protected BinPacking3D(BinPacking3D original, Cloner cloner)
56      : base(original, cloner) {
[15554]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);
[15731]64      }
65
[15770]66      WeightDistirbution = original.WeightDistirbution.Clone() as IDirectedGraph;
[14162]67    }
[15520]68
[14162]69    public override IDeepCloneable Clone(Cloner cloner) {
70      return new BinPacking3D(this, cloner);
71    }
72
[15241]73
[15646]74
[15471]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>
[15462]81    public override void PackItem(int itemID, PackingItem item, PackingPosition position) {
[15454]82      Items[itemID] = item;
83      Positions[itemID] = position;
84      ExtremePoints.Remove(position);
[15731]85
86      AddToGraph(itemID, item, position);
[15454]87    }
88
[15731]89
[15770]90    #region Graph for the calculating the weight distirbution     
91    /// <summary>
92    /// The given item is added to the graph as the source vertex.
93    /// Its items below are the target vertices.
94    /// </summary>
95    /// <param name="itemId"></param>
96    /// <param name="item"></param>
97    /// <param name="position"></param>
[15731]98    private void AddToGraph(int itemId, PackingItem item, PackingPosition position) {
99      var sourceVertex = new VertexWithItemId(itemId);
100      WeightDistirbution.AddVertex(sourceVertex);
101
102      var itemsBelow = GetItemsUnderAnItem(position, item);
103      foreach (var itemBelow in itemsBelow) {
104        var targetVertex = GetVertexForItemBelow(itemBelow);
105        if (targetVertex == null) {
106          continue;
107        }
108
109        double overlay = CalculateOverlay(itemBelow, Tuple.Create<PackingPosition, PackingItem>(position, item));
110        double area = (item.Width * item.Depth);
111        var arc = new Arc(sourceVertex, targetVertex) {
112          Weight = overlay / area
113        };
114        WeightDistirbution.AddArc(arc);
115      }
116    }
117
118    /// <summary>
119    /// Returns a vertex related to the given tuple of an item and packing position.
120    /// If there is no related vertex the method returns null.
121    /// </summary>
122    /// <param name="itemBelow"></param>
123    /// <returns></returns>
124    private IVertex GetVertexForItemBelow(Tuple<PackingPosition, PackingItem> itemBelow) {
125      var filteredItems = Items.Where(x => x.Value == itemBelow.Item2);
126      if (filteredItems.Count() <= 0) {
127        return null;
128      }
129      var itemIdBelow = filteredItems.First().Key;
130
131      var targetVertex = WeightDistirbution.Vertices.Where(x => {
132        if (x is VertexWithItemId) {
133          return ((VertexWithItemId)x).ItemId == itemIdBelow;
134        }
135        return false;
136      }).FirstOrDefault();
137
138      return targetVertex;
139    }
140
141
142    #endregion
143
144    #region Calculation of the stacked weight
145    public double GetStackedWeightForItemId(int itemId) {
146      return GetStackedWeightForItemIdRec(itemId);
147    }
148
149    private double GetStackedWeightForItemIdRec(int itemId) {
150      var arcs = WeightDistirbution.Arcs.Where(x => ((VertexWithItemId)x.Target).ItemId == itemId);
151      var stackedWeight = 0.0;
152      foreach (var arc in arcs) {
153        var sourceItemId = ((VertexWithItemId)arc.Source).ItemId;
154        var sourceItem = Items[sourceItemId];
155        stackedWeight += (GetStackedWeightForItemIdRec(sourceItemId) + sourceItem.Weight) * arc.Weight;
156      }
157
158      return stackedWeight;
159    }
160
161    #endregion
162
[15646]163    #region MassPoint
164
[15462]165    /// <summary>
[15646]166    /// This property contains the value of the mass point for the current bin packing.
[15462]167    /// </summary>
[15646]168    public Tuple<double, double, double> MassPoint { get { return CalculateMassPoint(); } }
[15473]169
[15646]170    private Tuple<double, double, double> CalculateMassPoint() {
171      var packingMassPoint = new { X = 0.0, Y = 0.0, Z = 0.0 };
172      var totalWeight = 0.0;
173      foreach (var item in Items) {
174        var position = Positions[item.Key];
175        var w = item.Value.Width;
176        var h = item.Value.Height;
177        var d = item.Value.Depth;
[15473]178
[15646]179        var massPoint = new { X = position.X + w / 2.0, Y = position.Y + h / 2.0, Z = position.Z + d / 2.0 };
180        var weight = Math.Max(item.Value.Weight, 1);
181        if (packingMassPoint == null) {
182          packingMassPoint = massPoint;
183          totalWeight += weight;
184        } else {
185          var newTotalWeight = totalWeight + weight;
186          packingMassPoint = new {
187            X = (massPoint.X * weight + packingMassPoint.X * totalWeight) / newTotalWeight,
188            Y = (massPoint.Y * weight + packingMassPoint.Y * totalWeight) / newTotalWeight,
189            Z = (massPoint.Z * weight + packingMassPoint.Z * totalWeight) / newTotalWeight
190          };
191          totalWeight = newTotalWeight;
192        }
193      }
[15705]194
[15646]195      return Tuple.Create<double, double, double>(packingMassPoint.X, packingMassPoint.Y, packingMassPoint.Z);
196    }
197    #endregion
198
[15488]199    #region Position feasability
[15462]200
[15454]201    /// <summary>
202    /// In this case feasability is defined as following:
[15488]203    /// 1. the point is supported by something;
204    /// 2. the item does not collide with another already packed item
[15454]205    /// </summary>
206    /// <param name="item"></param>
207    /// <param name="position"></param>
208    /// <param name="stackingConstraints"></param>
209    /// <returns></returns>
210    public override bool IsPositionFeasible(PackingItem item, PackingPosition position, bool stackingConstraints) {
[15646]211      return ItemCanBePlaced(item, position) && CheckStackingConstraints(item, position, stackingConstraints);
[15454]212    }
213
[15646]214
215
[15454]216    /// <summary>
217    /// Returns true if a given item can be placed in the current bin
218    /// </summary>
219    /// <param name="givenItem"></param>
220    /// <param name="givenItemPosition"></param>
221    /// <returns></returns>
222    private bool ItemCanBePlaced(PackingItem givenItem, PackingPosition givenItemPosition) {
223      // Check if the boundings of the bin would injured
[15646]224      if (givenItemPosition.X + givenItem.Width > BinShape.Width ||
[15454]225          givenItemPosition.Y + givenItem.Height > BinShape.Height ||
[15646]226          givenItemPosition.Z + givenItem.Depth > BinShape.Depth) {
[15454]227        return false;
228      }
229
230      //if the given item collides with any other item, it can not be placed
231      foreach (var item in Items) {
232        if (ItemsCollides(new Tuple<PackingPosition, PackingItem>(Positions[item.Key], item.Value),
233                          new Tuple<PackingPosition, PackingItem>(givenItemPosition, givenItem))) {
234          return false;
235        }
236      }
[15462]237      return true;
[15454]238    }
239
240    /// <summary>
241    /// Checks if two given items in a space collides
242    /// </summary>
243    /// <param name="t1"></param>
244    /// <param name="t2"></param>
245    /// <returns></returns>
[15462]246    private bool ItemsCollides(Tuple<PackingPosition, PackingItem> t1, Tuple<PackingPosition, PackingItem> t2) {
[15454]247      var position1 = t1.Item1;
248      var item1 = t1.Item2;
249      var position2 = t2.Item1;
250      var item2 = t2.Item2;
251      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);
252      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);
253      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);
254      return cx && cy && cz;
255    }
256
257    /// <summary>
258    /// Checks the stacking constraints. This method depends that the given item can be placed at this position
259    /// </summary>
260    /// <param name="item"></param>
261    /// <param name="position"></param>
262    /// <param name="stackingConstraints"></param>
263    /// <returns></returns>
264    private bool CheckStackingConstraints(PackingItem item, PackingPosition position, bool stackingConstraints) {
265      if (position.Y == 0 || !stackingConstraints && HasOnePointWithAnItemBelow(item, position)) {
266        return true;
267      }
268
269      return IsStaticStable(item, position) && IsWeightSupported(item, position);
270    }
271
272    /// <summary>
273    /// Checks if a given item has any point lieing on another item.
274    /// </summary>
275    /// <param name="item"></param>
276    /// <param name="position"></param>
277    /// <returns></returns>
[15462]278    private bool HasOnePointWithAnItemBelow(PackingItem item, PackingPosition position) {
[15454]279      bool p1, p2, p3, p4;
[15646]280      PointsLiesOnAnStackableItem(item, position, out p1, out p2, out p3, out p4);
[15454]281
282      return p1 || p2 || p3 || p4;
283    }
284
285    /// <summary>
286    /// Checks if a given item is static stable.
287    /// A item is static stable if all edges have an object below.
288    /// </summary>
289    /// <param name="item"></param>
290    /// <param name="position"></param>
291    /// <returns></returns>
292    public override bool IsStaticStable(PackingItem item, PackingPosition position) {
293      bool p1, p2, p3, p4;
[15646]294      PointsLiesOnAnStackableItem(item, position, out p1, out p2, out p3, out p4);
[15454]295      return p1 && p2 && p3 && p4;
296    }
297
298    /// <summary>
[15462]299    /// This method sets the out parameters p1 ... p4 if the point lies on another item.
[15454]300    /// p1 ... p3 represents one point on the bottom side of an given item.
301    /// +---------+
302    /// |p1     p2|
303    /// |         |
304    /// |p4     p3|
305    /// +---------+
306    /// </summary>
307    /// <param name="item">Given item</param>
308    /// <param name="position">Given item position</param>
309    /// <param name="p1"></param>
310    /// <param name="p2"></param>
311    /// <param name="p3"></param>
312    /// <param name="p4"></param>
[15646]313    private void PointsLiesOnAnStackableItem(PackingItem item, PackingPosition position, out bool p1, out bool p2, out bool p3, out bool p4) {
[15454]314      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP1;
315      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP2;
316      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP3;
317      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP4;
318
319      GetItemsUnderItemWithContact(item, position, out itemsP1, out itemsP2, out itemsP3, out itemsP4);
320
[15646]321      p1 = itemsP1.Where(x => x.Item2.IsStackabel && position.X < x.Item1.X + x.Item2.Width && position.Z < x.Item1.Z + x.Item2.Depth).Any();
322      p2 = itemsP2.Where(x => x.Item2.IsStackabel && position.X + item.Width > x.Item1.X && position.Z < x.Item1.Z + x.Item2.Depth).Any();
323      p3 = itemsP3.Where(x => x.Item2.IsStackabel && position.X + item.Width > x.Item1.X && position.Z + item.Depth > x.Item1.Z).Any();
324      p4 = itemsP4.Where(x => x.Item2.IsStackabel && position.X < x.Item1.X + x.Item2.Width && position.Z + item.Depth > x.Item1.Z).Any();
[15454]325    }
326
327    /// <summary>
[15462]328    /// This method returns a collection for the out parameters itemsP1 ... itemsP4 with the items below
329    /// itemsP1 ... itemsP4 represents one point on the bottom side of an given item.
330    /// +---------+
331    /// |p1     p2|
332    /// |         |
333    /// |p4     p3|
334    /// +---------+
[15454]335    /// </summary>
336    /// <param name="item"></param>
337    /// <param name="position"></param>
338    /// <param name="itemsP1"></param>
339    /// <param name="itemsP2"></param>
340    /// <param name="itemsP3"></param>
341    /// <param name="itemsP4"></param>
342    private void GetItemsUnderItemWithContact(PackingItem item, PackingPosition position,
343                                   out IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP1,
344                                   out IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP2,
345                                   out IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP3,
346                                   out IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP4) {
347      itemsP1 = GetItemsBelowForPosition(new PackingPosition(0, position.X, position.Y, position.Z, false));
348      itemsP2 = GetItemsBelowForPosition(new PackingPosition(0, position.X + item.Width - 1, position.Y, position.Z, false));
349      itemsP3 = GetItemsBelowForPosition(new PackingPosition(0, position.X, position.Y, position.Z + item.Depth - 1, false));
350      itemsP4 = GetItemsBelowForPosition(new PackingPosition(0, position.X + item.Width - 1, position.Y, position.Z + item.Depth - 1, false));
351
352    }
353
354    /// <summary>
355    /// Returns a collection of items which are below a given point.
356    /// The top side of every item is at the same level as the Y-coordinate of the given position.
357    /// </summary>
358    /// <param name="position"></param>
359    /// <returns></returns>
360    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelowForPosition(PackingPosition position) {
361      return GetItemsBelow(position).Where(x => (x.Item1.Y + x.Item2.Height) == position.Y);
362    }
363
[15705]364    #region Weight supported
[15770]365
[15705]366    //old implementation
[15454]367    /// <summary>
[15705]368    /// Checks if a given the weight of an given item is supported by the items below.
[15454]369    /// </summary>
370    /// <param name="item"></param>
371    /// <param name="position"></param>
372    /// <returns></returns>
[15462]373    private bool IsWeightSupported(PackingItem item, PackingPosition position) {
[15454]374      if (position.Y == 0) {
375        return true;
376      }
377
[15770]378      var itemsBelow = Items.Where(x => Positions[x.Key].Y + x.Value.Height == position.Y)
379                            .Select(x => new {
380                              ItemId = x.Key,
381                              Item = Tuple.Create<PackingPosition, PackingItem>(Positions[x.Key], x.Value),                           
382                              Overlay = CalculateOverlay(Tuple.Create<PackingPosition, PackingItem>(Positions[x.Key], x.Value),
383                                                         Tuple.Create<PackingPosition, PackingItem>(position, item))
384                            })
385                            .Where(x=> x.Overlay > 0);
[15454]386
[15770]387      var area = item.Width * item.Depth;
388      foreach (var itemBelow in itemsBelow) {
389        var factor = itemBelow.Overlay / area;
390        if (itemBelow.Item.Item2.SupportedWeightPerSquareMeter < item.Weight / area) {
391          return false;
392        }
393
394        if (!IsWeightSupportedRec(itemBelow.Item.Item2, itemBelow.ItemId, item.Weight, factor)) {
395          return false;
396        }
397      }
398      return true;
[15454]399    }
400
[15770]401    private bool IsWeightSupportedRec(PackingItem item, int itemId, double weigth, double factor) {
402      var stackedWeight = GetStackedWeightForItemId(itemId);
403      if (!item.SupportWeight(weigth * factor + stackedWeight)) {
404        return false;
405      }
406
407      var arcs = WeightDistirbution.Arcs.Where(x => ((VertexWithItemId)x.Source).ItemId == itemId);
408      foreach (var arc in arcs) {
409        var targetItemId = ((VertexWithItemId)arc.Target).ItemId;
410        var targetItem = Items[targetItemId];
411        if (!IsWeightSupportedRec(targetItem, targetItemId, weigth, factor * arc.Weight)) {
412          return false;
413        }
414      }
415
416      return true;
417    }
418   
419
420
[15705]421    private double CalculateOverlay(Tuple<PackingPosition, PackingItem> item1, Tuple<PackingPosition, PackingItem> item2) {
422      var left = item1.Item1.X <= item2.Item1.X ? item1 : item2;
423      var right = item1.Item1.X <= item2.Item1.X ? item2 : item1;
424      var behind = item1.Item1.Z <= item2.Item1.Z ? item1 : item2;
425      var inFront = item1.Item1.Z <= item2.Item1.Z ? item2 : item1;
426
427      var overlayX = right.Item2.Width;
428      if (left.Item1.X + left.Item2.Width < right.Item1.X + right.Item2.Width) {
429        overlayX = left.Item1.X + left.Item2.Width - right.Item1.X;
430      }
431
[15731]432      var overlayZ = inFront.Item2.Depth;
433      if (behind.Item1.Z + behind.Item2.Depth < inFront.Item1.Z + inFront.Item2.Depth) {
434        overlayZ = behind.Item1.Z + behind.Item2.Depth - inFront.Item1.Z;
[15705]435      }
436
437      return overlayX * overlayZ;
438    }
439
440    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsAboveAnItem(PackingPosition position, PackingItem item) {
441      var selected = Items.Select(x => new {
442        Item = x.Value,
443        Position = Positions[x.Key]
444      }).Where(x => x.Position.Y == position.Y + item.Height)
445        .Where(x => x.Position.X <= position.X && x.Position.X + x.Item.Width > position.X ||
446                    x.Position.X > position.X && x.Position.X < position.X + item.Width)
447        .Where(x => x.Position.Z <= position.Z && x.Position.Z + x.Item.Height > position.Z ||
448                    x.Position.Z > position.Z && x.Position.Z < position.Z + item.Height);
449
450      return selected.Select(x => Tuple.Create(x.Position, x.Item));
451    }
452
[15731]453    /// <summary>
454    /// Returns a collection of items and its position which have contact to an given item below
455    /// </summary>
456    /// <param name="position"></param>
457    /// <param name="item"></param>
458    /// <returns></returns>
[15705]459    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsUnderAnItem(PackingPosition position, PackingItem item) {
460      var selected = Items.Select(x => new {
461        Item = x.Value,
462        Position = Positions[x.Key]
463      }).Where(x => x.Position.Y + x.Item.Height == position.Y)
464        .Where(x => x.Position.X <= position.X && x.Position.X + x.Item.Width > position.X ||
465                    x.Position.X > position.X && x.Position.X < position.X + item.Width)
[15731]466        .Where(x => x.Position.Z <= position.Z && x.Position.Z + x.Item.Depth > position.Z ||
467                    x.Position.Z > position.Z && x.Position.Z < position.Z + item.Depth);
[15705]468
469      return selected.Select(x => Tuple.Create(x.Position, x.Item));
470    }
471
[15488]472    #endregion
473
[15705]474
475    #endregion
476
[14162]477    protected override void GenerateNewExtremePointsForNewItem(PackingItem newItem, PackingPosition position) {
[15488]478      throw new NotImplementedException();
[14162]479    }
480
[15424]481    #region Get items
[15646]482
[15454]483    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelow(PackingPosition pos) {
484      var line = new Line3D(pos, new Vector3D(0, 1, 0));
485      return Items.Select(x => new {
486        Item = x.Value,
487        Position = Positions[x.Key],
488        Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Top))
489      }).Where(x => x.Intersection != null && x.Intersection.Y <= pos.Y)
490        .Select(x => Tuple.Create(x.Position, x.Item));
491    }
492
[15770]493    public IEnumerable<PackingItem> GetItemsBelow(int itemId) {
494      var item = Items[itemId];
495      var position = Positions[itemId];
496
497      var itemsBelow = Items.Where(x => Positions[x.Key].Y + x.Value.Height == position.Y &&
498                                        CalculateOverlay(Tuple.Create<PackingPosition, PackingItem>(Positions[x.Key], x.Value),
499                                                         Tuple.Create<PackingPosition, PackingItem>(position, item)) > 0)
500                            .Select(x => x.Value);
501      return itemsBelow;
502    }
503
[15424]504    #endregion
[14162]505  }
[15230]506}
Note: See TracBrowser for help on using the repository browser.