Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 14977 was 14977, checked in by dsouravl, 7 years ago

#2762: worked on best fit heuristics, update of residual space heuristic

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