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

Last change on this file since 15520 was 15520, checked in by rhanghof, 21 months ago

#2817:

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