Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/PackingPlans/PackingPlan.cs @ 9593

Last change on this file since 9593 was 9593, checked in by jhelm, 11 years ago

#1966: Applied some heavy refactoring on the decoder-classes and cleaned up the code a bit;
File size: 19.2 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2012 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 System.Text;
26using HeuristicLab.Problems.BinPacking.Interfaces;
27using HeuristicLab.Problems.BinPacking.PackingItem;
28using HeuristicLab.Problems.BinPacking.Shapes;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30using HeuristicLab.Core;
31using HeuristicLab.Common;
32using HeuristicLab.Parameters;
33using HeuristicLab.Data;
34using HeuristicLab.Collections;
35using HeuristicLab.Problems.BinPacking.Dimensions;
36using HeuristicLab.Problems.BinPacking.PackingBin;
37
38namespace HeuristicLab.Encodings.PackingEncoding.PackingPlan {
39  [Item("PackingPlan", "Represents a concrete solution for a bin-packing problem.")]
40  [StorableClass]
41  public class PackingPlan<D, B, I> : ParameterizedNamedItem, IPackingPlan
42    where D : class, IPackingDimensions
43    where B : PackingShape<D>, IPackingBin
44    where I : PackingShape<D>, IPackingItem {
45
46    #region Properties
47    public int NrOfBins {
48      get {
49        if (BinPackings != null)
50          return BinPackings.Count;
51        else return 0;
52      }
53    }
54
55    [Storable]
56    public ObservableList<BinPacking<D, B, I>> BinPackings { get; set; }
57
58    [Storable]
59    private DoubleValue quality;
60    public DoubleValue Quality {
61      get { return quality; }
62      set {
63        if (quality != value) {
64          if (quality != null) DeregisterQualityEvents();
65          quality = value;
66          if (quality != null) RegisterQualityEvents();
67          OnQualityChanged();
68        }
69      }
70    }
71    #endregion
72
73    public PackingPlan(B binMeasures)
74      : this(){
75      //this.BinPackings.Add(new BinPacking<D,B,I> ());
76    }
77    public PackingPlan()
78      : base() {
79      this.BinPackings = new ObservableList<BinPacking<D, B,I>>();
80    }
81
82    [StorableConstructor]
83    protected PackingPlan(bool deserializing) : base(deserializing) { }
84    protected PackingPlan(PackingPlan<D,B,I> original, Cloner cloner)
85      : base(original, cloner) {
86        this.BinPackings = new ObservableList<BinPacking<D, B, I>>(original.BinPackings);
87    }
88    public override IDeepCloneable Clone(Cloner cloner) {
89      return new PackingPlan<D,B,I>(this, cloner);
90    }
91         
92
93    #region Events
94    public event EventHandler QualityChanged;
95    private void OnQualityChanged() {
96      var changed = QualityChanged;
97      if (changed != null)
98        changed(this, EventArgs.Empty);
99    }
100    private void RegisterQualityEvents() {
101      Quality.ValueChanged += new EventHandler(Quality_ValueChanged);
102    }
103    private void DeregisterQualityEvents() {
104      Quality.ValueChanged -= new EventHandler(Quality_ValueChanged);
105    }
106    private void Quality_ValueChanged(object sender, EventArgs e) {
107      OnQualityChanged();
108    }
109
110    public event EventHandler BinPackingsChanged;
111    private void OnBinPackingsChanged() {
112      var changed = BinPackingsChanged;
113      if (changed != null)
114        changed(this, EventArgs.Empty);
115    }
116    private void RegisterBinPackingsEvents() {
117      BinPackings.PropertyChanged += new System.ComponentModel.PropertyChangedEventHandler(BinPackings_PropertyChanged);
118    }
119    private void DeregisterBinPackingsEvents() {
120      BinPackings.PropertyChanged -= new System.ComponentModel.PropertyChangedEventHandler(BinPackings_PropertyChanged);
121    }
122    private void BinPackings_PropertyChanged(object sender, EventArgs e) {
123      OnBinPackingsChanged();
124    }
125    #endregion
126  }
127
128  [Item("BinPacking", "Represents a single-bin packing for a bin-packing problem.")]
129  [StorableClass]
130  public abstract class BinPacking<D,B,I>  : Item
131    where D : class, IPackingDimensions
132    where B : PackingShape<D>, IPackingBin
133    where I : PackingShape<D>, IPackingItem {
134 
135    [Storable]
136    public ObservableDictionary<int, D> ItemPositions { get; private set; }
137
138    [Storable]
139    public B BinMeasures { get; private set; }
140
141    [Storable]
142    public ObservableDictionary<int, I> ItemMeasures { get; private set; }
143
144    [Storable]
145    public HashSet<D> ExtremePoints { get; protected set; }
146
147    [Storable]
148    public OccupiedPoints<D, I> OccupiedPoints { get; protected set; }
149
150    public BinPacking(B binMeasures) : base() {   
151      ItemPositions = new ObservableDictionary<int, D>();
152      ItemMeasures = new ObservableDictionary<int, I>();
153      BinMeasures = (B)binMeasures.Clone();
154      ExtremePoints = new HashSet<D>();
155      ExtremePoints.Add(binMeasures.Origin);
156    }
157
158    [StorableConstructor]
159    protected BinPacking(bool deserializing) : base(deserializing) { }
160    protected BinPacking(BinPacking<D,B,I> original, Cloner cloner)
161      : base(original, cloner) {
162      this.ItemPositions = new ObservableDictionary<int, D>(original.ItemPositions);
163      this.ItemMeasures = new ObservableDictionary<int, I>(original.ItemMeasures);
164        this.BinMeasures = (B)original.BinMeasures.Clone(cloner);
165    }
166   
167
168    protected abstract void GenerateNewExtremePointsForNewItem(I measures, D position);
169    public abstract D FindExtremePointForItem(I measures, bool rotated, bool stackingConstraint);
170    public abstract D FindPositionBySliding(I measures, bool rotated);
171    public void PackItem(int itemID, I measures, D position) {
172      ItemMeasures[itemID] = measures;
173      ItemPositions[itemID] = position;
174      ExtremePoints.Remove(position);
175      GenerateNewExtremePointsForNewItem(measures, position);
176      OccupiedPoints.OccupyPoints(measures, position, itemID);
177    }
178
179
180    public double PackingDensity {
181      get {
182        double result = 0;
183        foreach (var entry in ItemMeasures)
184          result += entry.Value.MultipliedMeasures;
185        result /= BinMeasures.MultipliedMeasures;
186        return result;
187      }
188    }
189
190    public bool IsPositionFeasible1(I currentItem, D currentPosition) {
191      //In this case feasability is defined as following: 1. the item fits into the bin-borders; 2. the item does not collide with another already packed item
192      if (!BinMeasures.Encloses(currentPosition, currentItem))
193        return false;
194
195      foreach (var ipEntry in ItemPositions) {
196        if (ItemMeasures[ipEntry.Key].Overlaps(ipEntry.Value, currentPosition, currentItem))
197          return false;
198      }
199
200      return true;
201    }
202    public bool IsPositionFeasible(I currentItem, D position) {
203      if (!BinMeasures.Encloses(position, currentItem))
204        return false;
205
206      return OccupiedPoints.IsPositionFeasible (currentItem, position);
207    }
208  }
209
210
211
212
213
214  [Item("BinPacking2D", "Represents a single-bin packing for a 2D bin-packing problem.")]
215  [StorableClass]
216  public class BinPacking2D : BinPacking<TwoDimensionalPacking, RectangularPackingBin, RectangularPackingItem> {
217
218    public BinPacking2D(RectangularPackingBin binMeasures) : base(binMeasures) {
219      OccupiedPoints = new OccupiedPoints2D(binMeasures);
220    }
221    [StorableConstructor]
222    protected BinPacking2D(bool deserializing) : base(deserializing) { }
223    protected BinPacking2D(BinPacking2D original, Cloner cloner)
224      : base(original, cloner) {
225    }
226    public override IDeepCloneable Clone(Cloner cloner) {
227      return new BinPacking2D(this, cloner);
228    }
229                     
230    protected override void GenerateNewExtremePointsForNewItem(RectangularPackingItem newItem, TwoDimensionalPacking position) {
231
232      int newWidth = position.Rotated ? newItem.Height : newItem.Width;
233      int newHeight = position.Rotated ? newItem.Width : newItem.Height;
234
235      //Find ExtremePoints beginning from sourcepointX
236      var sourcePointX = new TwoDimensionalPacking(0, position.X + newWidth, position.Y);
237      if (sourcePointX.X < BinMeasures.Width && sourcePointX.Y < BinMeasures.Height) {
238        //Traversing down the y-axis       
239        while (sourcePointX.Y > 0 && !OccupiedPoints.IsPointOccupied(new TwoDimensionalPacking(0, sourcePointX.X, sourcePointX.Y - 1))) {
240          sourcePointX.Y--;
241        }
242        ExtremePoints.Add(new TwoDimensionalPacking(0, sourcePointX.X, sourcePointX.Y));
243      }
244
245
246
247
248      //Find ExtremePoints beginning from sourcepointY
249      var sourcePointY = new TwoDimensionalPacking(0, position.X, position.Y + newItem.Height);
250      if (sourcePointY.X < BinMeasures.Width && sourcePointY.Y < BinMeasures.Height) {
251        //Traversing down the x-axis 
252        while (sourcePointY.X > 0 && !OccupiedPoints.IsPointOccupied(new TwoDimensionalPacking (0,sourcePointY.X - 1, sourcePointY.Y))) {
253          sourcePointY.X--;
254        }
255        ExtremePoints.Add(new TwoDimensionalPacking(0, sourcePointY.X, sourcePointY.Y));
256      }
257
258      ExtremePoints = new HashSet<TwoDimensionalPacking>(ExtremePoints.
259        OrderBy(ep => ep.AssignedBin).
260        ThenBy(ep => ep.X).
261        ThenBy(ep => ep.Y).
262        ThenBy(ep => OccupiedPoints.ShortestPossibleSideFromEP(ep)));
263    }
264
265    public override TwoDimensionalPacking FindExtremePointForItem(RectangularPackingItem measures, bool rotated, bool stackingConstraint) {
266      RectangularPackingItem item = new RectangularPackingItem(
267        rotated ? measures.Height : measures.Width,
268        rotated ? measures.Width : measures.Height,
269        measures.TargetBin);
270
271      int epIndex = 0;
272      while (epIndex < ExtremePoints.Count && (!IsPositionFeasible(item, ExtremePoints.ElementAt(epIndex)))) { epIndex++; }
273
274      if (epIndex < ExtremePoints.Count) {
275        var result = ExtremePoints.ElementAt(epIndex);
276        result.Rotated = rotated;
277        return result;
278      }
279      return null;
280    }
281    public override TwoDimensionalPacking FindPositionBySliding(RectangularPackingItem measures, bool rotated) {
282      TwoDimensionalPacking currentPosition = new TwoDimensionalPacking(0,
283        BinMeasures.Width - (rotated ? measures.Height : measures.Width),
284        BinMeasures.Height - (rotated ? measures.Width : measures.Height), rotated);
285      //Slide the item as far as possible to the left
286      while (IsPositionFeasible(measures, MoveLeft(currentPosition))
287        || IsPositionFeasible(measures, MoveDown(currentPosition))) {
288        //Slide the item as far as possible to the bottom
289        while (IsPositionFeasible(measures, MoveDown(currentPosition))) {
290          currentPosition = MoveDown(currentPosition);
291        }
292        if (IsPositionFeasible(measures, MoveLeft(currentPosition)))
293          currentPosition = MoveLeft(currentPosition);
294      }
295
296      return IsPositionFeasible(measures, currentPosition) ? currentPosition : null;
297    }
298    private static TwoDimensionalPacking MoveLeft(TwoDimensionalPacking original) {
299      return new TwoDimensionalPacking(original.AssignedBin, original.X - 1, original.Y, original.Rotated);
300    }
301    private static TwoDimensionalPacking MoveDown(TwoDimensionalPacking original) {
302      return new TwoDimensionalPacking(original.AssignedBin, original.X, original.Y - 1, original.Rotated);
303    }
304  }
305
306
307
308  [Item("BinPacking3D", "Represents a single-bin packing for a 3D bin-packing problem.")]
309  [StorableClass]
310  public class BinPacking3D : BinPacking<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> {
311
312   
313    public BinPacking3D(CuboidPackingBin binMeasures) : base(binMeasures) {
314      OccupiedPoints = new OccupiedPoints3D(binMeasures);
315    }
316    [StorableConstructor]
317    protected BinPacking3D(bool deserializing) : base(deserializing) { }
318    protected BinPacking3D(BinPacking3D original, Cloner cloner)
319      : base(original, cloner) {
320    }
321    public override IDeepCloneable Clone(Cloner cloner) {
322      return new BinPacking3D(this, cloner);
323    }
324                                       
325    protected override void GenerateNewExtremePointsForNewItem(CuboidPackingItem newItem, ThreeDimensionalPacking position) {
326      int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
327      int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
328
329      //Find ExtremePoints beginning from sourcepointX
330      var sourcePointX = new ThreeDimensionalPacking(0, position.X + newWidth, position.Y, position.Z);
331      if (sourcePointX.X < BinMeasures.Width && sourcePointX.Y < BinMeasures.Height && sourcePointX.Z < BinMeasures.Depth) {
332        //Traversing down the y-axis                                                                           
333        int currentYValue = sourcePointX.Y;
334        while (currentYValue > 0 && !OccupiedPoints.IsPointOccupied(new ThreeDimensionalPacking (0, sourcePointX.X, currentYValue, sourcePointX.Z))) {
335          currentYValue--;
336        }
337        ExtremePoints.Add(new ThreeDimensionalPacking(0, sourcePointX.X, currentYValue, sourcePointX.Z));
338
339        //Traversing down the z-axis
340        int currentZValue = sourcePointX.Z;
341        while (currentZValue > 0 && !OccupiedPoints.IsPointOccupied(new ThreeDimensionalPacking (0, sourcePointX.X, sourcePointX.Y, currentZValue - 1))) {
342          currentZValue--;
343        }
344        ExtremePoints.Add(new ThreeDimensionalPacking(0, sourcePointX.X, sourcePointX.Y, currentZValue));
345      }
346
347
348
349
350      //Find ExtremePoints beginning from sourcepointY
351      var sourcePointY = new ThreeDimensionalPacking(0, position.X, position.Y + newItem.Height, position.Z);
352      if (sourcePointY.X < BinMeasures.Width && sourcePointY.Y < BinMeasures.Height && sourcePointY.Z < BinMeasures.Depth) {
353        //Traversing down the x-axis 
354        int currentXValue = sourcePointY.X;
355        while (currentXValue > 0 && !OccupiedPoints.IsPointOccupied(new ThreeDimensionalPacking (0, currentXValue - 1, sourcePointY.Y, sourcePointY.Z))) {
356          currentXValue--;
357        }
358        ExtremePoints.Add(new ThreeDimensionalPacking(0, currentXValue, sourcePointY.Y, sourcePointY.Z));
359
360        //Traversing down the z-axis
361        int currentZValue = sourcePointY.Z;
362        while (currentZValue > 0 && !OccupiedPoints.IsPointOccupied(new ThreeDimensionalPacking (0, sourcePointY.X, sourcePointY.Y, currentZValue - 1))) {
363          currentZValue--;
364        }
365        ExtremePoints.Add(new ThreeDimensionalPacking(0, sourcePointY.X, sourcePointY.Y, currentZValue));
366      }
367
368
369
370
371
372      //Find ExtremePoints beginning from sourcepointZ
373      var sourcePointZ = new ThreeDimensionalPacking(0, position.X, position.Y, position.Z + newDepth);
374      if (sourcePointZ.X < BinMeasures.Width && sourcePointZ.Y < BinMeasures.Height && sourcePointZ.Z < BinMeasures.Depth) {
375        //Traversing down the x-axis 
376        int currentXValue = sourcePointZ.X;
377        while (currentXValue > 0 && !OccupiedPoints.IsPointOccupied(new ThreeDimensionalPacking (0, currentXValue - 1, sourcePointZ.Y, sourcePointZ.Z))) {
378          currentXValue--;
379        }
380        ExtremePoints.Add(new ThreeDimensionalPacking(0, currentXValue, sourcePointZ.Y, sourcePointZ.Z));
381
382        //Traversing down the y-axis                                                                           
383        int currentYValue = sourcePointZ.Y;
384        while (currentYValue > 0 && !OccupiedPoints.IsPointOccupied(new ThreeDimensionalPacking (0, sourcePointZ.X, currentYValue, sourcePointZ.Z))) {
385          currentYValue--;
386        }
387        ExtremePoints.Add(new ThreeDimensionalPacking(0, sourcePointZ.X, currentYValue, sourcePointZ.Z));
388      }
389
390      ExtremePoints = new HashSet<ThreeDimensionalPacking>(ExtremePoints.
391        OrderBy(ep => ep.AssignedBin).
392        ThenBy(ep => ep.Z).
393        ThenBy(ep => ep.X).
394        ThenBy(ep => ep.Y).
395        ThenBy(ep => OccupiedPoints.ShortestPossibleSideFromEP(ep)));
396    }
397
398    public override ThreeDimensionalPacking FindExtremePointForItem(CuboidPackingItem measures, bool rotated, bool stackingConstraint) {
399
400      CuboidPackingItem item = new CuboidPackingItem(
401        rotated ? measures.Depth : measures.Width,
402        measures.Height,
403        rotated ? measures.Width : measures.Depth,
404        measures.TargetBin);
405
406      int epIndex = 0;
407      while (epIndex < ExtremePoints.Count && (
408        !IsPositionFeasible(item, ExtremePoints.ElementAt(epIndex)) || (stackingConstraint && !OccupiedPoints.IsStaticStable(item, ExtremePoints.ElementAt(epIndex)))
409      )) { epIndex++; }
410
411      if (epIndex < ExtremePoints.Count) {
412        var result = ExtremePoints.ElementAt(epIndex);
413        result.Rotated = rotated;
414        return result;
415      }
416      return null;
417    }
418    public override ThreeDimensionalPacking FindPositionBySliding(CuboidPackingItem measures, bool rotated) {
419      //Starting-position at upper right corner (=left bottom point of item-rectangle is at position item.width,item.height)
420      ThreeDimensionalPacking currentPosition = new ThreeDimensionalPacking(0,
421        BinMeasures.Width - (rotated ? measures.Depth : measures.Width),
422        BinMeasures.Height - measures.Height,
423        BinMeasures.Depth - (rotated ? measures.Width : measures.Depth), rotated);
424      //Slide the item as far as possible to the bottom
425      while (IsPositionFeasible(measures, MoveDown(currentPosition))
426        || IsPositionFeasible(measures, MoveLeft(currentPosition))
427        || IsPositionFeasible(measures, MoveBack(currentPosition))) {
428        //Slide the item as far as possible to the left
429        while (IsPositionFeasible(measures, MoveLeft(currentPosition))
430        || IsPositionFeasible(measures, MoveBack(currentPosition))) {
431          //Slide the item as far as possible to the back
432          while (IsPositionFeasible(measures, MoveBack(currentPosition))) {
433            currentPosition = MoveBack(currentPosition);
434          }
435          if (IsPositionFeasible(measures, MoveLeft(currentPosition)))
436            currentPosition = MoveLeft(currentPosition);
437        }
438        if (IsPositionFeasible(measures, MoveDown(currentPosition)))
439          currentPosition = MoveDown(currentPosition);
440      }
441
442      return IsPositionFeasible(measures, currentPosition) ? currentPosition : null;
443    }
444    private static ThreeDimensionalPacking MoveLeft(ThreeDimensionalPacking original) {
445      return new ThreeDimensionalPacking(original.AssignedBin, original.X - 1, original.Y, original.Z, original.Rotated);
446    }
447    private static ThreeDimensionalPacking MoveDown(ThreeDimensionalPacking original) {
448      return new ThreeDimensionalPacking(original.AssignedBin, original.X, original.Y - 1, original.Z, original.Rotated);
449    }
450    private static ThreeDimensionalPacking MoveBack(ThreeDimensionalPacking original) {
451      return new ThreeDimensionalPacking(original.AssignedBin, original.X, original.Y, original.Z - 1, original.Rotated);
452    }
453  }
454
455
456
457}
Note: See TracBrowser for help on using the repository browser.