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

Last change on this file since 15705 was 15705, checked in by rhanghof, 2 years ago

#2817

  • Former material is now the layer.
  • Added material enumeration
  • Modification at the minimum residual space left bin packer
File size: 16.5 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;
31
32namespace HeuristicLab.Problems.BinPacking3D {
33  [Item("BinPacking3D", "Represents a single-bin packing for a 3D bin-packing problem.")]
34  [StorableClass]
35  public class BinPacking3D : BinPacking<PackingPosition, PackingShape, PackingItem> {
36
37    [Storable]
38    public IDictionary<PackingPosition, IEnumerable<ResidualSpace>> ExtremePoints { get; protected set; }
39   
40
41    public BinPacking3D(PackingShape binShape)
42      : base(binShape) {
43      ExtremePoints = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();
44
45      ExtremePoints.Add(binShape.Origin, new List<ResidualSpace>() { ResidualSpace.Create(binShape.Width, binShape.Height, binShape.Depth) });
46    }
47
48    [StorableConstructor]
49    protected BinPacking3D(bool deserializing) : base(deserializing) { }
50
51    protected BinPacking3D(BinPacking3D original, Cloner cloner)
52      : base(original, cloner) {
53      this.ExtremePoints = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();
54      foreach (var extremePoint in original.ExtremePoints) {
55        var residualSpaces = new List<ResidualSpace>();
56        foreach (var residualSpace in extremePoint.Value) {
57          residualSpaces.Add(cloner.Clone(residualSpace));
58        }
59        ExtremePoints.Add(cloner.Clone(extremePoint.Key), residualSpaces);
60      }     
61    }
62
63    public override IDeepCloneable Clone(Cloner cloner) {
64      return new BinPacking3D(this, cloner);
65    }
66
67
68
69    /// <summary>
70    /// Puts a given item into the bin packing at the given position.
71    /// </summary>
72    /// <param name="itemID">Offset in the internal item array</param>
73    /// <param name="item">Item</param>
74    /// <param name="position">Position of the item in the bin packing</param>
75    public override void PackItem(int itemID, PackingItem item, PackingPosition position) {
76      Items[itemID] = item;
77      Positions[itemID] = position;
78      ExtremePoints.Remove(position);
79    }
80
81    #region MassPoint
82
83    /// <summary>
84    /// This property contains the value of the mass point for the current bin packing.
85    /// </summary>
86    public Tuple<double, double, double> MassPoint { get { return CalculateMassPoint(); } }
87
88    private Tuple<double, double, double> CalculateMassPoint() {
89      var packingMassPoint = new { X = 0.0, Y = 0.0, Z = 0.0 };
90      var totalWeight = 0.0;
91      foreach (var item in Items) {
92        var position = Positions[item.Key];
93        var w = item.Value.Width;
94        var h = item.Value.Height;
95        var d = item.Value.Depth;
96
97        var massPoint = new { X = position.X + w / 2.0, Y = position.Y + h / 2.0, Z = position.Z + d / 2.0 };
98        var weight = Math.Max(item.Value.Weight, 1);
99        if (packingMassPoint == null) {
100          packingMassPoint = massPoint;
101          totalWeight += weight;
102        } else {
103          var newTotalWeight = totalWeight + weight;
104          packingMassPoint = new {
105            X = (massPoint.X * weight + packingMassPoint.X * totalWeight) / newTotalWeight,
106            Y = (massPoint.Y * weight + packingMassPoint.Y * totalWeight) / newTotalWeight,
107            Z = (massPoint.Z * weight + packingMassPoint.Z * totalWeight) / newTotalWeight
108          };
109          totalWeight = newTotalWeight;
110        }
111      }
112
113      return Tuple.Create<double, double, double>(packingMassPoint.X, packingMassPoint.Y, packingMassPoint.Z);
114    }
115    #endregion
116
117    #region Position feasability
118
119    /// <summary>
120    /// In this case feasability is defined as following:
121    /// 1. the point is supported by something;
122    /// 2. the item does not collide with another already packed item
123    /// </summary>
124    /// <param name="item"></param>
125    /// <param name="position"></param>
126    /// <param name="stackingConstraints"></param>
127    /// <returns></returns>
128    public override bool IsPositionFeasible(PackingItem item, PackingPosition position, bool stackingConstraints) {
129      return ItemCanBePlaced(item, position) && CheckStackingConstraints(item, position, stackingConstraints);
130    }
131
132
133
134    /// <summary>
135    /// Returns true if a given item can be placed in the current bin
136    /// </summary>
137    /// <param name="givenItem"></param>
138    /// <param name="givenItemPosition"></param>
139    /// <returns></returns>
140    private bool ItemCanBePlaced(PackingItem givenItem, PackingPosition givenItemPosition) {
141      // Check if the boundings of the bin would injured
142      if (givenItemPosition.X + givenItem.Width > BinShape.Width ||
143          givenItemPosition.Y + givenItem.Height > BinShape.Height ||
144          givenItemPosition.Z + givenItem.Depth > BinShape.Depth) {
145        return false;
146      }
147
148      //if the given item collides with any other item, it can not be placed
149      foreach (var item in Items) {
150        if (ItemsCollides(new Tuple<PackingPosition, PackingItem>(Positions[item.Key], item.Value),
151                          new Tuple<PackingPosition, PackingItem>(givenItemPosition, givenItem))) {
152          return false;
153        }
154      }
155      return true;
156    }
157
158    /// <summary>
159    /// Checks if two given items in a space collides
160    /// </summary>
161    /// <param name="t1"></param>
162    /// <param name="t2"></param>
163    /// <returns></returns>
164    private bool ItemsCollides(Tuple<PackingPosition, PackingItem> t1, Tuple<PackingPosition, PackingItem> t2) {
165      var position1 = t1.Item1;
166      var item1 = t1.Item2;
167      var position2 = t2.Item1;
168      var item2 = t2.Item2;
169      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);
170      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);
171      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);
172      return cx && cy && cz;
173    }
174
175    /// <summary>
176    /// Checks the stacking constraints. This method depends that the given item can be placed at this position
177    /// </summary>
178    /// <param name="item"></param>
179    /// <param name="position"></param>
180    /// <param name="stackingConstraints"></param>
181    /// <returns></returns>
182    private bool CheckStackingConstraints(PackingItem item, PackingPosition position, bool stackingConstraints) {
183      if (position.Y == 0 || !stackingConstraints && HasOnePointWithAnItemBelow(item, position)) {
184        return true;
185      }
186
187      return IsStaticStable(item, position) && IsWeightSupported(item, position);
188    }
189
190    /// <summary>
191    /// Checks if a given item has any point lieing on another item.
192    /// </summary>
193    /// <param name="item"></param>
194    /// <param name="position"></param>
195    /// <returns></returns>
196    private bool HasOnePointWithAnItemBelow(PackingItem item, PackingPosition position) {
197      bool p1, p2, p3, p4;
198      PointsLiesOnAnStackableItem(item, position, out p1, out p2, out p3, out p4);
199
200      return p1 || p2 || p3 || p4;
201    }
202
203    /// <summary>
204    /// Checks if a given item is static stable.
205    /// A item is static stable if all edges have an object below.
206    /// </summary>
207    /// <param name="item"></param>
208    /// <param name="position"></param>
209    /// <returns></returns>
210    public override bool IsStaticStable(PackingItem item, PackingPosition position) {
211      bool p1, p2, p3, p4;
212      PointsLiesOnAnStackableItem(item, position, out p1, out p2, out p3, out p4);
213      return p1 && p2 && p3 && p4;
214    }
215
216    /// <summary>
217    /// This method sets the out parameters p1 ... p4 if the point lies on another item.
218    /// p1 ... p3 represents one point on the bottom side of an given item.
219    /// +---------+
220    /// |p1     p2|
221    /// |         |
222    /// |p4     p3|
223    /// +---------+
224    /// </summary>
225    /// <param name="item">Given item</param>
226    /// <param name="position">Given item position</param>
227    /// <param name="p1"></param>
228    /// <param name="p2"></param>
229    /// <param name="p3"></param>
230    /// <param name="p4"></param>
231    private void PointsLiesOnAnStackableItem(PackingItem item, PackingPosition position, out bool p1, out bool p2, out bool p3, out bool p4) {
232      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP1;
233      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP2;
234      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP3;
235      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP4;
236
237      GetItemsUnderItemWithContact(item, position, out itemsP1, out itemsP2, out itemsP3, out itemsP4);
238
239      p1 = itemsP1.Where(x => x.Item2.IsStackabel && position.X < x.Item1.X + x.Item2.Width && position.Z < x.Item1.Z + x.Item2.Depth).Any();
240      p2 = itemsP2.Where(x => x.Item2.IsStackabel && position.X + item.Width > x.Item1.X && position.Z < x.Item1.Z + x.Item2.Depth).Any();
241      p3 = itemsP3.Where(x => x.Item2.IsStackabel && position.X + item.Width > x.Item1.X && position.Z + item.Depth > x.Item1.Z).Any();
242      p4 = itemsP4.Where(x => x.Item2.IsStackabel && position.X < x.Item1.X + x.Item2.Width && position.Z + item.Depth > x.Item1.Z).Any();
243    }
244
245    /// <summary>
246    /// This method returns a collection for the out parameters itemsP1 ... itemsP4 with the items below
247    /// itemsP1 ... itemsP4 represents one point on the bottom side of an given item.
248    /// +---------+
249    /// |p1     p2|
250    /// |         |
251    /// |p4     p3|
252    /// +---------+
253    /// </summary>
254    /// <param name="item"></param>
255    /// <param name="position"></param>
256    /// <param name="itemsP1"></param>
257    /// <param name="itemsP2"></param>
258    /// <param name="itemsP3"></param>
259    /// <param name="itemsP4"></param>
260    private void GetItemsUnderItemWithContact(PackingItem item, PackingPosition position,
261                                   out IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP1,
262                                   out IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP2,
263                                   out IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP3,
264                                   out IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP4) {
265      itemsP1 = GetItemsBelowForPosition(new PackingPosition(0, position.X, position.Y, position.Z, false));
266      itemsP2 = GetItemsBelowForPosition(new PackingPosition(0, position.X + item.Width - 1, position.Y, position.Z, false));
267      itemsP3 = GetItemsBelowForPosition(new PackingPosition(0, position.X, position.Y, position.Z + item.Depth - 1, false));
268      itemsP4 = GetItemsBelowForPosition(new PackingPosition(0, position.X + item.Width - 1, position.Y, position.Z + item.Depth - 1, false));
269
270    }
271
272    /// <summary>
273    /// Returns a collection of items which are below a given point.
274    /// The top side of every item is at the same level as the Y-coordinate of the given position.
275    /// </summary>
276    /// <param name="position"></param>
277    /// <returns></returns>
278    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelowForPosition(PackingPosition position) {
279      return GetItemsBelow(position).Where(x => (x.Item1.Y + x.Item2.Height) == position.Y);
280    }
281
282    #region Weight supported
283    //old implementation
284    /// <summary>
285    /// Checks if a given the weight of an given item is supported by the items below.
286    /// </summary>
287    /// <param name="item"></param>
288    /// <param name="position"></param>
289    /// <returns></returns>
290    private bool IsWeightSupported(PackingItem item, PackingPosition position) {
291      if (position.Y == 0) {
292        return true;
293      }
294      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP1;
295      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP2;
296      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP3;
297      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP4;
298
299      GetItemsUnderItemWithContact(item, position, out itemsP1, out itemsP2, out itemsP3, out itemsP4);
300
301      return itemsP1.Where(x => x.Item2.SupportsStacking(item)).Any() &&
302        itemsP2.Where(x => x.Item2.SupportsStacking(item)).Any() &&
303        itemsP3.Where(x => x.Item2.SupportsStacking(item)).Any() &&
304        itemsP4.Where(x => x.Item2.SupportsStacking(item)).Any();
305    }
306
307    private double CalculateOverlay(Tuple<PackingPosition, PackingItem> item1, Tuple<PackingPosition, PackingItem> item2) {
308      var left = item1.Item1.X <= item2.Item1.X ? item1 : item2;
309      var right = item1.Item1.X <= item2.Item1.X ? item2 : item1;
310      var behind = item1.Item1.Z <= item2.Item1.Z ? item1 : item2;
311      var inFront = item1.Item1.Z <= item2.Item1.Z ? item2 : item1;
312
313      var overlayX = right.Item2.Width;
314      if (left.Item1.X + left.Item2.Width < right.Item1.X + right.Item2.Width) {
315        overlayX = left.Item1.X + left.Item2.Width - right.Item1.X;
316      }
317
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;
321      }
322
323      return overlayX * overlayZ;
324    }
325
326    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsAboveAnItem(PackingPosition position, PackingItem item) {
327      var selected = Items.Select(x => new {
328        Item = x.Value,
329        Position = Positions[x.Key]
330      }).Where(x => x.Position.Y == position.Y + item.Height)
331        .Where(x => x.Position.X <= position.X && x.Position.X + x.Item.Width > position.X ||
332                    x.Position.X > position.X && x.Position.X < position.X + item.Width)
333        .Where(x => x.Position.Z <= position.Z && x.Position.Z + x.Item.Height > position.Z ||
334                    x.Position.Z > position.Z && x.Position.Z < position.Z + item.Height);
335
336      return selected.Select(x => Tuple.Create(x.Position, x.Item));
337    }
338
339    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsUnderAnItem(PackingPosition position, PackingItem item) {
340      var selected = Items.Select(x => new {
341        Item = x.Value,
342        Position = Positions[x.Key]
343      }).Where(x => x.Position.Y + x.Item.Height == position.Y)
344        .Where(x => x.Position.X <= position.X && x.Position.X + x.Item.Width > position.X ||
345                    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);
348
349      return selected.Select(x => Tuple.Create(x.Position, x.Item));
350    }
351
352    #endregion
353
354
355    #endregion
356
357    protected override void GenerateNewExtremePointsForNewItem(PackingItem newItem, PackingPosition position) {
358      throw new NotImplementedException();
359    }
360
361    #region Get items
362
363    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelow(PackingPosition pos) {
364      var line = new Line3D(pos, new Vector3D(0, 1, 0));
365      return Items.Select(x => new {
366        Item = x.Value,
367        Position = Positions[x.Key],
368        Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Top))
369      }).Where(x => x.Intersection != null && x.Intersection.Y <= pos.Y)
370        .Select(x => Tuple.Create(x.Position, x.Item));
371    }
372
373    #endregion
374  }
375}
Note: See TracBrowser for help on using the repository browser.