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

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

#1966: added abstract problem and move evaluator classes and implemented 2d bin packing problem based on integer vector encoding

File size: 17.0 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.depthWasDoubled = original.depthWasDoubled;
44      this.ExtremePoints = new SortedSet<PackingPosition>(original.ExtremePoints, new EPComparer3D());
45    }
46    public override IDeepCloneable Clone(Cloner cloner) {
47      return new BinPacking3D(this, cloner);
48    }
49
50    protected override void GenerateNewExtremePointsForNewItem(PackingItem newItem, PackingPosition position) {
51      int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
52      int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
53
54      //Find ExtremePoints beginning from sourcepointX
55      var sourcePointX = new PackingPosition(0, position.X + newWidth, position.Y, position.Z);
56      if (sourcePointX.X < BinMeasures.Width && sourcePointX.Y < BinMeasures.Height && sourcePointX.Z < BinMeasures.Depth) {
57        //Traversing down the y-axis 
58        PackingPosition current = new PackingPosition(0, sourcePointX.X, sourcePointX.Y, sourcePointX.Z);
59        while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
60          current = PackingPosition.MoveDown(current);
61        }
62        ExtremePoints.Add((PackingPosition)current.Clone());
63        while (current.X > 0 && !IsPointOccupied(PackingPosition.MoveLeft(current))) {
64          current = PackingPosition.MoveLeft(current);
65        }
66        ExtremePoints.Add(current);
67
68        //Traversing down the z-axis
69        current = new PackingPosition(0, sourcePointX.X, sourcePointX.Y, sourcePointX.Z);
70        while (current.Z > 0 && !IsPointOccupied(PackingPosition.MoveBack(current))) {
71          current = PackingPosition.MoveBack(current);
72        }
73        ExtremePoints.Add((PackingPosition)current.Clone());
74        while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
75          current = PackingPosition.MoveDown(current);
76        }
77        ExtremePoints.Add(current);
78      }
79
80
81
82
83      //Find ExtremePoints beginning from sourcepointY
84      var sourcePointY = new PackingPosition(0, position.X, position.Y + newItem.Height, position.Z);
85      if (sourcePointY.X < BinMeasures.Width && sourcePointY.Y < BinMeasures.Height && sourcePointY.Z < BinMeasures.Depth) {
86        //Traversing down the x-axis         
87        PackingPosition current = new PackingPosition(0, sourcePointY.X, sourcePointY.Y, sourcePointY.Z);
88        while (current.X > 0 && !IsPointOccupied(PackingPosition.MoveLeft(current))) {
89          current = PackingPosition.MoveLeft(current);
90        }
91        ExtremePoints.Add((PackingPosition)current.Clone());
92        while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
93          current = PackingPosition.MoveDown(current);
94        }
95        ExtremePoints.Add(current);
96
97        //Traversing down the z-axis                                                                   
98        current = new PackingPosition(0, sourcePointY.X, sourcePointY.Y, sourcePointY.Z);
99        while (current.Z > 0 && !IsPointOccupied(PackingPosition.MoveBack(current))) {
100          current = PackingPosition.MoveBack(current);
101        }
102        ExtremePoints.Add((PackingPosition)current.Clone());
103        while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
104          current = PackingPosition.MoveDown(current);
105        }
106        ExtremePoints.Add(current);
107      }
108
109
110
111
112
113      //Find ExtremePoints beginning from sourcepointZ
114      var sourcePointZ = new PackingPosition(0, position.X, position.Y, position.Z + newDepth);
115      if (sourcePointZ.X < BinMeasures.Width && sourcePointZ.Y < BinMeasures.Height && sourcePointZ.Z < BinMeasures.Depth) {
116        //Traversing down the x-axis                                                                             
117        PackingPosition current = new PackingPosition(0, sourcePointZ.X, sourcePointZ.Y, sourcePointZ.Z);
118        while (current.X > 0 && !IsPointOccupied(PackingPosition.MoveLeft(current))) {
119          current = PackingPosition.MoveLeft(current);
120        }
121        ExtremePoints.Add((PackingPosition)current.Clone());
122        while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
123          current = PackingPosition.MoveDown(current);
124        }
125        ExtremePoints.Add(current);
126
127        //Traversing down the y-axis                                                                     
128        current = new PackingPosition(0, sourcePointZ.X, sourcePointZ.Y, sourcePointZ.Z);
129        while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
130          current = PackingPosition.MoveDown(current);
131        }
132        ExtremePoints.Add((PackingPosition)current.Clone());
133        while (current.X > 0 && !IsPointOccupied(PackingPosition.MoveLeft(current))) {
134          current = PackingPosition.MoveLeft(current);
135        }
136        ExtremePoints.Add(current);
137      }
138
139      //ExtremePoints.RemoveWhere(ep => IsPointOccupied (ep));
140
141      //ExtremePoints = new HashSet<ThreeDimensionalPacking>(ExtremePoints.
142      //  OrderBy(ep => ep.Z).
143      //  ThenBy(ep => ep.X).
144      //  ThenBy(ep => ep.Y)//.ThenBy(ep => ShortestPossibleSideFromPoint(ep))
145      //  );
146    }
147
148    public override PackingPosition FindExtremePointForItem(PackingItem measures, bool rotated, bool stackingConstraints) {
149
150      PackingItem item = new PackingItem(
151        rotated ? measures.Depth : measures.Width,
152        measures.Height,
153        rotated ? measures.Width : measures.Depth,
154        measures.TargetBin);
155
156      int epIndex = 0;
157      while (epIndex < ExtremePoints.Count && (
158        !IsPositionFeasible(item, ExtremePoints.ElementAt(epIndex))
159        || !IsSupportedByAtLeastOnePoint(item, ExtremePoints.ElementAt(epIndex))
160        || (stackingConstraints && !IsStaticStable(item, ExtremePoints.ElementAt(epIndex)))
161        || (stackingConstraints && !IsWeightSupported(item, ExtremePoints.ElementAt(epIndex)))
162      )) { epIndex++; }
163
164      if (epIndex < ExtremePoints.Count) {
165        var origPoint = ExtremePoints.ElementAt(epIndex);
166        var result = new PackingPosition(origPoint.AssignedBin, origPoint.X, origPoint.Y, origPoint.Z, rotated);
167        return result;
168      }
169      return null;
170    }
171
172    public override PackingPosition FindPositionBySliding(PackingItem measures, bool rotated) {
173      //Starting-position at upper right corner (=left bottom point of item-rectangle is at position item.width,item.height)
174      PackingPosition currentPosition = new PackingPosition(0,
175        BinMeasures.Width - (rotated ? measures.Depth : measures.Width),
176        BinMeasures.Height - measures.Height,
177        BinMeasures.Depth - (rotated ? measures.Width : measures.Depth), rotated);
178      //Slide the item as far as possible to the bottom
179      while (IsPositionFeasible(measures, PackingPosition.MoveDown(currentPosition))
180        || IsPositionFeasible(measures, PackingPosition.MoveLeft(currentPosition))
181        || IsPositionFeasible(measures, PackingPosition.MoveBack(currentPosition))) {
182        //Slide the item as far as possible to the left
183        while (IsPositionFeasible(measures, PackingPosition.MoveLeft(currentPosition))
184      || IsPositionFeasible(measures, PackingPosition.MoveBack(currentPosition))) {
185          //Slide the item as far as possible to the back
186          while (IsPositionFeasible(measures, PackingPosition.MoveBack(currentPosition))) {
187            currentPosition = PackingPosition.MoveBack(currentPosition);
188          }
189          if (IsPositionFeasible(measures, PackingPosition.MoveLeft(currentPosition)))
190            currentPosition = PackingPosition.MoveLeft(currentPosition);
191        }
192        if (IsPositionFeasible(measures, PackingPosition.MoveDown(currentPosition)))
193          currentPosition = PackingPosition.MoveDown(currentPosition);
194      }
195
196      return IsPositionFeasible(measures, currentPosition) ? currentPosition : null;
197    }
198
199    public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> itemMeasures) {
200      var temp = new List<int>(sequence);
201      for (int i = 0; i < temp.Count; i++) {
202        var item = itemMeasures[temp[i]];
203        var position = FindPositionBySliding(item, false);
204        if (position != null) {
205          PackItem(temp[i], item, position);
206          sequence.Remove(temp[i]);
207        }
208      }
209    }
210    public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> itemMeasures, Dictionary<int, bool> rotationArray) {
211      var temp = new List<int>(sequence);
212      for (int i = 0; i < temp.Count; i++) {
213        var item = itemMeasures[temp[i]];
214        var position = FindPositionBySliding(item, rotationArray[i]);
215        if (position != null) {
216          PackItem(temp[i], item, position);
217          sequence.Remove(temp[i]);
218        }
219      }
220    }
221    public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> itemMeasures, bool stackingConstraints) {
222      var temp = new List<int>(sequence);
223      foreach (int itemID in temp) {
224        var item = itemMeasures[itemID];
225        var positionFound = FindExtremePointForItem(item, false, stackingConstraints);
226        if (positionFound != null) {
227          PackItem(itemID, item, positionFound);
228          sequence.Remove(itemID);
229        }
230      }
231    }
232    public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> itemMeasures, bool stackingConstraints, Dictionary<int, bool> rotationArray) {
233      var temp = new List<int>(sequence);
234      foreach (int itemID in temp) {
235        var item = itemMeasures[itemID];
236        var positionFound = FindExtremePointForItem(item, rotationArray[itemID], stackingConstraints);
237        if (positionFound != null) {
238          PackItem(itemID, item, positionFound);
239          sequence.Remove(itemID);
240        }
241      }
242    }
243
244    public override int ShortestPossibleSideFromPoint(PackingPosition position) {
245
246      int shortestSide = int.MaxValue;
247      int width = BinMeasures.Width;
248      int height = BinMeasures.Height;
249      int depth = BinMeasures.Depth;
250
251      if (position.X >= width || position.Y >= height || position.Z >= depth)
252        return shortestSide;
253
254      PackingPosition current = new PackingPosition(0, position.X, position.Y, position.Z);
255      while (current.X < width && IsPointOccupied(current)) { current = PackingPosition.MoveRight(current); }
256      if (current.X - position.X < shortestSide)
257        shortestSide = current.X - position.X;
258
259
260      current = new PackingPosition(0, position.X, position.Y, position.Z);
261      while (current.Y < height && IsPointOccupied(current)) { current = PackingPosition.MoveUp(current); }
262      if (current.Y - position.Y < shortestSide)
263        shortestSide = current.Y - position.Y;
264
265
266      current = new PackingPosition(0, position.X, position.Y, position.Z);
267      while (current.Z < depth && IsPointOccupied(current)) { current = PackingPosition.MoveFront(current); }
268      if (current.Z - position.Z < shortestSide)
269        shortestSide = current.Z - position.Z;
270
271      return shortestSide;
272    }
273    public override bool IsStaticStable(PackingItem item, PackingPosition position) {
274      //Static stability is given, if item is placed on the ground
275      if (position.Y == 0)
276        return true;
277
278      if (IsPointOccupied(new PackingPosition(0, position.X, position.Y - 1, position.Z))
279        && IsPointOccupied(new PackingPosition(0, position.X + item.Width - 1, position.Y - 1, position.Z))
280        && IsPointOccupied(new PackingPosition(0, position.X, position.Y - 1, position.Z + item.Depth - 1))
281        && IsPointOccupied(new PackingPosition(0, position.X + item.Width - 1, position.Y - 1, position.Z + item.Depth - 1)))
282        return true;
283
284
285      //if (occupiedPoints[position.X, position.Y - 1, position.Z] != -1
286      //  && occupiedPoints[position.X + item.Width - 1, position.Y - 1, position.Z] != -1
287      //  && occupiedPoints[position.X, position.Y - 1, position.Z + item.Depth - 1] != -1
288      //  && occupiedPoints[position.X + item.Width - 1, position.Y - 1, position.Z + item.Depth - 1] != -1)
289      //  return true;
290
291      //int groundCount = 0;
292      //for (int x = ep.X; x < ep.X + item.Width - 1; x++) {
293      //  for (int z = ep.Z; z < ep.Z + item.Depth - 1; z++) {
294      //    if (occupiedPoints[x,ep.Y-1, z] != -1)                                                     
295      //      groundCount++;
296      //  }
297      //}
298      //double stableGround = (double)(groundCount) / (double)(item.Width * item.Depth);
299      //if (stableGround > 0.75)
300      //  return true;
301
302      return false;
303    }
304
305    [Storable]
306    private bool depthWasDoubled = false; // TODO ???
307    public void DoubleDepth() {
308      if (!depthWasDoubled) {
309        var oldDepth = BinMeasures.Depth;
310        BinMeasures.Depth = BinMeasures.Depth * 2;
311        //OccupiedPoints.ChangeBinMeasures(BinMeasures);
312        depthWasDoubled = true;
313      }
314    }
315
316    public bool IsSupportedByAtLeastOnePoint(PackingItem item, PackingPosition position) {
317      if (position.Y == 0)
318        return true;
319
320      int y = position.Y - 1;
321      for (int x = position.X; x < position.X + item.Width; x++)
322        for (int z = position.Z; z < position.Z + item.Depth; z++)
323          if (IsPointOccupied(new PackingPosition(0, x, y, z)))
324            return true;
325
326      return false;
327    }
328    public bool IsWeightSupported(PackingItem item, PackingPosition ep) {
329      if (ep.Y == 0)
330        return true;
331
332      if (ItemMeasures[PointOccupation(new PackingPosition(0, ep.X, ep.Y - 1, ep.Z))].SupportsStacking(item)
333        && ItemMeasures[PointOccupation(new PackingPosition(0, ep.X + item.Width - 1, ep.Y - 1, ep.Z))].SupportsStacking(item)
334        && ItemMeasures[PointOccupation(new PackingPosition(0, ep.X, ep.Y - 1, ep.Z + item.Depth - 1))].SupportsStacking(item)
335        && ItemMeasures[PointOccupation(new PackingPosition(0, ep.X + item.Width - 1, ep.Y - 1, ep.Z + item.Depth - 1))].SupportsStacking(item))
336        return true;
337
338      return false;
339    }
340
341
342    protected override void InitializeOccupationLayers() {
343      for (int i = 0; i * 10 <= BinMeasures.Depth; i += 1) {
344        OccupationLayers[i] = new List<int>();
345      }
346    }
347    protected override void AddNewItemToOccupationLayers(int itemID, PackingItem measures, PackingPosition position) {
348      int z1 = position.Z / 10;
349      int z2 = (position.Z + (position.Rotated ? measures.Width : measures.Depth)) / 10;
350
351      for (int i = z1; i <= z2; i++)
352        OccupationLayers[i].Add(itemID);
353    }
354    protected override List<int> GetLayerItemIDs(PackingPosition position) {
355      return OccupationLayers[position.Z / 10];
356    }
357    protected override List<int> GetLayerItemIDs(PackingItem measures, PackingPosition position) {
358      List<int> result = new List<int>();
359      int z1 = position.Z / 10;
360      int z2 = (position.Z + (position.Rotated ? measures.Width : measures.Depth)) / 10;
361
362      for (int i = z1; i <= z2; i++)
363        result.AddRange(OccupationLayers[i]);
364
365      return result;
366    }
367  }
368  public class EPComparer3D : IComparer<PackingPosition> {
369    public int Compare(PackingPosition a, PackingPosition b) {
370      int result = a.Z.CompareTo(b.Z);
371      if (result == 0)
372        result = a.X.CompareTo(b.X);
373      if (result == 0)
374        result = a.Y.CompareTo(b.Y);
375
376      return result;
377    }
378  }
379}
Note: See TracBrowser for help on using the repository browser.