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

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

#2817:

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