Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/PackingPlans/BinPacking3D.cs @ 13032

Last change on this file since 13032 was 13032, checked in by gkronber, 8 years ago

#1966:

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