source: branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.3D/3.3/BinPacking3D.cs @ 14153

Last change on this file since 14153 was 14153, checked in by gkronber, 4 years ago

#1966: implemented 3d bin packing problems (using permutation and integer vector encoding) based on the 2d implementations

File size: 15.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 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.Collections.Generic;
23using System.Linq;
24using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
25using HeuristicLab.Core;
26using HeuristicLab.Common;
27using HeuristicLab.Problems.BinPacking;
28
29namespace HeuristicLab.Problems.BinPacking3D {
30  [Item("BinPacking3D", "Represents a single-bin packing for a 3D bin-packing problem.")]
31  [StorableClass]
32  public class BinPacking3D : BinPacking<PackingPosition, PackingShape, PackingItem> {
33
34    public BinPacking3D(PackingShape binMeasures)
35      : base(binMeasures) {
36      ExtremePoints = new SortedSet<PackingPosition>(new EPComparer3D());
37      ExtremePoints.Add(binMeasures.Origin);
38    }
39    [StorableConstructor]
40    protected BinPacking3D(bool deserializing) : base(deserializing) { }
41    protected BinPacking3D(BinPacking3D original, Cloner cloner)
42      : base(original, cloner) {
43      this.ExtremePoints = new SortedSet<PackingPosition>(original.ExtremePoints, new EPComparer3D());
44    }
45    public override IDeepCloneable Clone(Cloner cloner) {
46      return new BinPacking3D(this, cloner);
47    }
48
49    protected override void GenerateNewExtremePointsForNewItem(PackingItem newItem, PackingPosition position) {
50      int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
51      int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
52
53      //Find ExtremePoints beginning from sourcepointX
54      var sourcePointX = new PackingPosition(0, position.X + newWidth, position.Y, position.Z);
55      if (sourcePointX.X < BinMeasures.Width && sourcePointX.Y < BinMeasures.Height && sourcePointX.Z < BinMeasures.Depth) {
56        //Traversing down the y-axis 
57        PackingPosition current = new PackingPosition(0, sourcePointX.X, sourcePointX.Y, sourcePointX.Z);
58        while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
59          current = PackingPosition.MoveDown(current);
60        }
61        ExtremePoints.Add((PackingPosition)current.Clone());
62        while (current.X > 0 && !IsPointOccupied(PackingPosition.MoveLeft(current))) {
63          current = PackingPosition.MoveLeft(current);
64        }
65        ExtremePoints.Add(current);
66
67        //Traversing down the z-axis
68        current = new PackingPosition(0, sourcePointX.X, sourcePointX.Y, sourcePointX.Z);
69        while (current.Z > 0 && !IsPointOccupied(PackingPosition.MoveBack(current))) {
70          current = PackingPosition.MoveBack(current);
71        }
72        ExtremePoints.Add((PackingPosition)current.Clone());
73        while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
74          current = PackingPosition.MoveDown(current);
75        }
76        ExtremePoints.Add(current);
77      }
78
79      //Find ExtremePoints beginning from sourcepointY
80      var sourcePointY = new PackingPosition(0, position.X, position.Y + newItem.Height, position.Z);
81      if (sourcePointY.X < BinMeasures.Width && sourcePointY.Y < BinMeasures.Height && sourcePointY.Z < BinMeasures.Depth) {
82        //Traversing down the x-axis         
83        PackingPosition current = new PackingPosition(0, sourcePointY.X, sourcePointY.Y, sourcePointY.Z);
84        while (current.X > 0 && !IsPointOccupied(PackingPosition.MoveLeft(current))) {
85          current = PackingPosition.MoveLeft(current);
86        }
87        ExtremePoints.Add((PackingPosition)current.Clone());
88        while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
89          current = PackingPosition.MoveDown(current);
90        }
91        ExtremePoints.Add(current);
92
93        //Traversing down the z-axis
94        current = new PackingPosition(0, sourcePointY.X, sourcePointY.Y, sourcePointY.Z);
95        while (current.Z > 0 && !IsPointOccupied(PackingPosition.MoveBack(current))) {
96          current = PackingPosition.MoveBack(current);
97        }
98        ExtremePoints.Add((PackingPosition)current.Clone());
99        while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
100          current = PackingPosition.MoveDown(current);
101        }
102        ExtremePoints.Add(current);
103      }
104
105      //Find ExtremePoints beginning from sourcepointZ
106      var sourcePointZ = new PackingPosition(0, position.X, position.Y, position.Z + newDepth);
107      if (sourcePointZ.X < BinMeasures.Width && sourcePointZ.Y < BinMeasures.Height && sourcePointZ.Z < BinMeasures.Depth) {
108        //Traversing down the x-axis
109        PackingPosition current = new PackingPosition(0, sourcePointZ.X, sourcePointZ.Y, sourcePointZ.Z);
110        while (current.X > 0 && !IsPointOccupied(PackingPosition.MoveLeft(current))) {
111          current = PackingPosition.MoveLeft(current);
112        }
113        ExtremePoints.Add((PackingPosition)current.Clone());
114        while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
115          current = PackingPosition.MoveDown(current);
116        }
117        ExtremePoints.Add(current);
118
119        //Traversing down the y-axis
120        current = new PackingPosition(0, sourcePointZ.X, sourcePointZ.Y, sourcePointZ.Z);
121        while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
122          current = PackingPosition.MoveDown(current);
123        }
124        ExtremePoints.Add((PackingPosition)current.Clone());
125        while (current.X > 0 && !IsPointOccupied(PackingPosition.MoveLeft(current))) {
126          current = PackingPosition.MoveLeft(current);
127        }
128        ExtremePoints.Add(current);
129      }
130    }
131
132    public override PackingPosition FindExtremePointForItem(PackingItem measures, bool rotated, bool stackingConstraints) {
133
134      PackingItem item = new PackingItem(
135        rotated ? measures.Depth : measures.Width,
136        measures.Height,
137        rotated ? measures.Width : measures.Depth,
138        measures.TargetBin);
139
140      int epIndex = 0;
141      while (epIndex < ExtremePoints.Count && (
142        !IsPositionFeasible(item, ExtremePoints.ElementAt(epIndex))
143        || !IsSupportedByAtLeastOnePoint(item, ExtremePoints.ElementAt(epIndex))
144        || (stackingConstraints && !IsStaticStable(item, ExtremePoints.ElementAt(epIndex)))
145        || (stackingConstraints && !IsWeightSupported(item, ExtremePoints.ElementAt(epIndex)))
146      )) { epIndex++; }
147
148      if (epIndex < ExtremePoints.Count) {
149        var origPoint = ExtremePoints.ElementAt(epIndex);
150        var result = new PackingPosition(origPoint.AssignedBin, origPoint.X, origPoint.Y, origPoint.Z, rotated);
151        return result;
152      }
153      return null;
154    }
155
156    public override PackingPosition FindPositionBySliding(PackingItem measures, bool rotated) {
157      //TODO: does not support stacking constraints yet
158      //Starting-position at upper right corner (=left bottom point of item-rectangle is at position item.width,item.height)
159      PackingPosition currentPosition = new PackingPosition(0,
160        BinMeasures.Width - (rotated ? measures.Depth : measures.Width),
161        BinMeasures.Height - measures.Height,
162        BinMeasures.Depth - (rotated ? measures.Width : measures.Depth), rotated);
163      //Slide the item as far as possible to the bottom
164      while (IsPositionFeasible(measures, PackingPosition.MoveDown(currentPosition))
165        || IsPositionFeasible(measures, PackingPosition.MoveLeft(currentPosition))
166        || IsPositionFeasible(measures, PackingPosition.MoveBack(currentPosition))) {
167        //Slide the item as far as possible to the left
168        while (IsPositionFeasible(measures, PackingPosition.MoveLeft(currentPosition))
169      || IsPositionFeasible(measures, PackingPosition.MoveBack(currentPosition))) {
170          //Slide the item as far as possible to the back
171          while (IsPositionFeasible(measures, PackingPosition.MoveBack(currentPosition))) {
172            currentPosition = PackingPosition.MoveBack(currentPosition);
173          }
174          if (IsPositionFeasible(measures, PackingPosition.MoveLeft(currentPosition)))
175            currentPosition = PackingPosition.MoveLeft(currentPosition);
176        }
177        if (IsPositionFeasible(measures, PackingPosition.MoveDown(currentPosition)))
178          currentPosition = PackingPosition.MoveDown(currentPosition);
179      }
180
181      return IsPositionFeasible(measures, currentPosition) ? currentPosition : null;
182    }
183
184    public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> itemMeasures) {
185      var temp = new List<int>(sequence);
186      for (int i = 0; i < temp.Count; i++) {
187        var item = itemMeasures[temp[i]];
188        var position = FindPositionBySliding(item, false);
189        if (position != null) {
190          PackItem(temp[i], item, position);
191          sequence.Remove(temp[i]);
192        }
193      }
194    }
195    public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> itemMeasures, Dictionary<int, bool> rotationArray) {
196      var temp = new List<int>(sequence);
197      for (int i = 0; i < temp.Count; i++) {
198        var item = itemMeasures[temp[i]];
199        var position = FindPositionBySliding(item, rotationArray[i]);
200        if (position != null) {
201          PackItem(temp[i], item, position);
202          sequence.Remove(temp[i]);
203        }
204      }
205    }
206    public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> itemMeasures, bool stackingConstraints) {
207      var temp = new List<int>(sequence);
208      foreach (int itemID in temp) {
209        var item = itemMeasures[itemID];
210        var positionFound = FindExtremePointForItem(item, false, stackingConstraints);
211        if (positionFound != null) {
212          PackItem(itemID, item, positionFound);
213          sequence.Remove(itemID);
214        }
215      }
216    }
217    public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> itemMeasures, bool stackingConstraints, Dictionary<int, bool> rotationArray) {
218      var temp = new List<int>(sequence);
219      foreach (int itemID in temp) {
220        var item = itemMeasures[itemID];
221        var positionFound = FindExtremePointForItem(item, rotationArray[itemID], stackingConstraints);
222        if (positionFound != null) {
223          PackItem(itemID, item, positionFound);
224          sequence.Remove(itemID);
225        }
226      }
227    }
228
229    public override int ShortestPossibleSideFromPoint(PackingPosition position) {
230
231      int shortestSide = int.MaxValue;
232      int width = BinMeasures.Width;
233      int height = BinMeasures.Height;
234      int depth = BinMeasures.Depth;
235
236      if (position.X >= width || position.Y >= height || position.Z >= depth)
237        return shortestSide;
238
239      PackingPosition current = new PackingPosition(0, position.X, position.Y, position.Z);
240      while (current.X < width && IsPointOccupied(current)) { current = PackingPosition.MoveRight(current); }
241      if (current.X - position.X < shortestSide)
242        shortestSide = current.X - position.X;
243
244
245      current = new PackingPosition(0, position.X, position.Y, position.Z);
246      while (current.Y < height && IsPointOccupied(current)) { current = PackingPosition.MoveUp(current); }
247      if (current.Y - position.Y < shortestSide)
248        shortestSide = current.Y - position.Y;
249
250
251      current = new PackingPosition(0, position.X, position.Y, position.Z);
252      while (current.Z < depth && IsPointOccupied(current)) { current = PackingPosition.MoveFront(current); }
253      if (current.Z - position.Z < shortestSide)
254        shortestSide = current.Z - position.Z;
255
256      return shortestSide;
257    }
258    public override bool IsStaticStable(PackingItem item, PackingPosition position) {
259      //Static stability is given, if item is placed on the ground
260      if (position.Y == 0)
261        return true;
262
263      if (IsPointOccupied(new PackingPosition(0, position.X, position.Y - 1, position.Z))
264        && IsPointOccupied(new PackingPosition(0, position.X + item.Width - 1, position.Y - 1, position.Z))
265        && IsPointOccupied(new PackingPosition(0, position.X, position.Y - 1, position.Z + item.Depth - 1))
266        && IsPointOccupied(new PackingPosition(0, position.X + item.Width - 1, position.Y - 1, position.Z + item.Depth - 1)))
267        return true;
268
269      return false;
270    }
271
272
273    public bool IsSupportedByAtLeastOnePoint(PackingItem item, PackingPosition position) {
274      if (position.Y == 0)
275        return true;
276
277      int y = position.Y - 1;
278      for (int x = position.X; x < position.X + item.Width; x++)
279        for (int z = position.Z; z < position.Z + item.Depth; z++)
280          if (IsPointOccupied(new PackingPosition(0, x, y, z)))
281            return true;
282
283      return false;
284    }
285    public bool IsWeightSupported(PackingItem item, PackingPosition ep) {
286      if (ep.Y == 0)
287        return true;
288
289      if (ItemMeasures[PointOccupation(new PackingPosition(0, ep.X, ep.Y - 1, ep.Z))].SupportsStacking(item)
290        && ItemMeasures[PointOccupation(new PackingPosition(0, ep.X + item.Width - 1, ep.Y - 1, ep.Z))].SupportsStacking(item)
291        && ItemMeasures[PointOccupation(new PackingPosition(0, ep.X, ep.Y - 1, ep.Z + item.Depth - 1))].SupportsStacking(item)
292        && ItemMeasures[PointOccupation(new PackingPosition(0, ep.X + item.Width - 1, ep.Y - 1, ep.Z + item.Depth - 1))].SupportsStacking(item))
293        return true;
294
295      return false;
296    }
297
298
299    protected override void InitializeOccupationLayers() {
300      for (int i = 0; i * 10 <= BinMeasures.Depth; i += 1) {
301        OccupationLayers[i] = new List<int>();
302      }
303    }
304    protected override void AddNewItemToOccupationLayers(int itemID, PackingItem measures, PackingPosition position) {
305      int z1 = position.Z / 10;
306      int z2 = (position.Z + (position.Rotated ? measures.Width : measures.Depth)) / 10;
307
308      for (int i = z1; i <= z2; i++)
309        OccupationLayers[i].Add(itemID);
310    }
311    protected override List<int> GetLayerItemIDs(PackingPosition position) {
312      return OccupationLayers[position.Z / 10];
313    }
314    protected override List<int> GetLayerItemIDs(PackingItem measures, PackingPosition position) {
315      List<int> result = new List<int>();
316      int z1 = position.Z / 10;
317      int z2 = (position.Z + (position.Rotated ? measures.Width : measures.Depth)) / 10;
318
319      for (int i = z1; i <= z2; i++)
320        result.AddRange(OccupationLayers[i]);
321
322      return result;
323    }
324  }
325  public class EPComparer3D : IComparer<PackingPosition> {
326    public int Compare(PackingPosition a, PackingPosition b) {
327      int result = a.Z.CompareTo(b.Z);
328      if (result == 0)
329        result = a.X.CompareTo(b.X);
330      if (result == 0)
331        result = a.Y.CompareTo(b.Y);
332
333      return result;
334    }
335  }
336}
Note: See TracBrowser for help on using the repository browser.