Free cookie consent management tool by TermsFeed Policy Generator

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

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

#1966: PackingPlan is just an Item not a ParameterizedNamedItem

File size: 11.4 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;
23using System.Collections.Generic;
24using System.Linq;
25using HeuristicLab.Problems.BinPacking.Interfaces;
26using HeuristicLab.Problems.BinPacking.PackingItem;
27using HeuristicLab.Problems.BinPacking.Shapes;
28using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
29using HeuristicLab.Core;
30using HeuristicLab.Common;
31using HeuristicLab.Data;
32using HeuristicLab.Collections;
33using HeuristicLab.Problems.BinPacking.Dimensions;
34using HeuristicLab.Problems.BinPacking.PackingBin;
35using HeuristicLab.Encodings.PackingEncoding.MultiComponentVector;
36using HeuristicLab.Encodings.PackingEncoding.GroupingVector;
37using HeuristicLab.Encodings.PackingEncoding.PackingSequence;
38using HeuristicLab.Encodings.IntegerVectorEncoding;
39
40namespace HeuristicLab.Encodings.PackingEncoding.PackingPlan {
41  [Item("PackingPlan", "Represents a concrete solution for a bin-packing problem.")]
42  [StorableClass]
43  public abstract class PackingPlan<D, B, I> :Item, IPackingPlan
44    where D : class, IPackingDimensions
45    where B : PackingShape<D>, IPackingBin
46    where I : PackingShape<D>, IPackingItem {
47
48    #region Properties
49    public int NrOfBins {
50      get {
51        if (BinPackings != null)
52          return BinPackings.Count;
53        else return 0;
54      }
55    }
56    [Storable]
57    protected bool StackingConstraints { get; set; }
58    [Storable]
59    protected bool UseExtremePoints { get; set; }
60
61    [Storable]
62    public B BinMeasures { get; private set; }
63
64    [Storable]
65    public ObservableList<BinPacking<D, B, I>> BinPackings { get; set; }
66
67    [Storable]
68    private DoubleValue quality;
69    public DoubleValue Quality {
70      get { return quality; }
71      set {
72        if (quality != value) {
73          if (quality != null) DeregisterQualityEvents();
74          quality = value;
75          if (quality != null) RegisterQualityEvents();
76          OnQualityChanged();
77        }
78      }
79    }
80    #endregion
81
82    protected PackingPlan(B binMeasures, bool useExtremePoints, bool stackingConstraints)
83      : base(){
84        BinMeasures = (B)binMeasures.Clone();
85        StackingConstraints = stackingConstraints;
86        UseExtremePoints = useExtremePoints;
87        BinPackings = new ObservableList<BinPacking<D, B, I>>();
88    }
89
90    [StorableConstructor]
91    protected PackingPlan(bool deserializing) : base(deserializing) { }
92    protected PackingPlan(PackingPlan<D,B,I> original, Cloner cloner)
93      : base(original, cloner) {
94        this.BinPackings = new ObservableList<BinPacking<D, B, I>>(original.BinPackings);
95    }
96   
97
98    public abstract BinPacking<D, B, I> NewBinPacking();
99    public void UpdateBinPackings() {
100      BinPackings.RemoveAll(x => x.ItemPositions.Count == 0);
101      BinPackings = new ObservableList<BinPacking<D, B, I>>(BinPackings.OrderByDescending (bp => bp.PackingDensity));
102    }
103
104    public void Pack(MultiComponentVectorEncoding solution, ItemList<I> itemMeasures) {
105      var sequenceMatrix = solution.GenerateSequenceMatrix();
106      Dictionary<int, bool> rotated = solution.GenerateRotationArray();
107
108      //Fill bins according to grouping vector
109      List<int> remainingIDs = new List<int>();
110      foreach (var sequence in sequenceMatrix) {
111        remainingIDs = remainingIDs.Concat(sequence).ToList();
112        var bp = NewBinPacking();
113        if (!UseExtremePoints)
114          bp.SlidingBasedPacking(ref remainingIDs, itemMeasures, rotated);
115        else
116          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints, rotated);
117        BinPackings.Add(bp);
118      }
119      UpdateBinPackings();
120
121      //Try to put remaining items in existing bins
122      var temp = new List<int>(remainingIDs);
123      foreach (int id in temp) {
124        foreach (var bp in BinPackings) {
125          var position = UseExtremePoints ? bp.FindExtremePointForItem(itemMeasures[id], rotated[id], StackingConstraints) : bp.FindPositionBySliding(itemMeasures[id], rotated[id]);
126          if (position != null) {
127            bp.PackItem(id, itemMeasures[id], position);
128            remainingIDs.Remove(id);
129            break;
130          }
131        }
132      }
133
134      //Put still remaining items in new bins
135      while (remainingIDs.Count > 0) {
136        var bp = NewBinPacking();
137        if (!UseExtremePoints)
138          bp.SlidingBasedPacking(ref remainingIDs, itemMeasures, rotated);
139        else
140          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints, rotated);
141        BinPackings.Add(bp);
142      }
143      UpdateBinPackings();
144
145      var newSolution = new ObservableDictionary<int,ItemList<PackingInformation>> ();
146      foreach (var bp in BinPackings) {
147        int binIndex = newSolution.Count;
148        newSolution[binIndex] = new ItemList<PackingInformation>();
149        foreach (var entry in bp.ItemPositions)
150          newSolution[binIndex].Add(new PackingInformation (entry.Key, entry.Value.Rotated));
151      }
152      solution.PackingInformations = newSolution;
153    }
154    public void Pack(GroupingVectorEncoding solution, ItemList<I> itemMeasures) {
155      var sequenceMatrix = solution.GenerateSequenceMatrix();
156
157      //Fill bins according to grouping vector
158      List<int> remainingIDs = new List<int>();
159      foreach (var sequence in sequenceMatrix) {
160        remainingIDs = remainingIDs.Concat(sequence).ToList();
161        var bp = NewBinPacking();
162        if (!UseExtremePoints)
163          bp.SlidingBasedPacking(ref remainingIDs, itemMeasures);
164        else
165          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints);
166        BinPackings.Add(bp);
167      }
168      UpdateBinPackings();
169
170      //Try to put remaining items in existing bins
171      var temp = new List<int>(remainingIDs);
172      foreach (int id in temp) {
173        foreach (var bp in BinPackings) { 
174          var position = UseExtremePoints ? bp.FindExtremePointForItem (itemMeasures[id], false, StackingConstraints) : bp.FindPositionBySliding(itemMeasures[id], false);
175          if (position != null) {
176            bp.PackItem(id, itemMeasures[id], position);
177            remainingIDs.Remove(id);
178            break;
179          }
180        }
181      }
182
183      //Put still remaining items in new bins
184      while (remainingIDs.Count > 0) {
185        var bp = NewBinPacking();
186        if (!UseExtremePoints)
187          bp.SlidingBasedPacking(ref remainingIDs, itemMeasures);
188        else
189          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints);
190        BinPackings.Add(bp);
191      }
192      UpdateBinPackings();
193
194      var newSolution = new int[solution.GroupingVector.Length];
195      int binIndex = 0;
196      foreach (var bp in BinPackings) {
197        foreach (var entry in bp.ItemPositions)
198          newSolution[entry.Key] = binIndex;
199        binIndex++;
200      }
201      solution.GroupingVector = new IntegerVector (newSolution);
202    }
203    public void Pack(PackingSequenceEncoding solution, ItemList<I> itemMeasures) {
204      List<int> remainingIDs = new List<int>(solution.PackingSequence);
205      while (remainingIDs.Count > 0) {
206        var bp = NewBinPacking();
207        if (!UseExtremePoints)
208          bp.SlidingBasedPacking(ref remainingIDs, itemMeasures);
209        else
210          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints);
211        BinPackings.Add(bp);
212      }
213      UpdateBinPackings();
214    }
215
216
217    #region Events
218    public event EventHandler QualityChanged;
219    private void OnQualityChanged() {
220      var changed = QualityChanged;
221      if (changed != null)
222        changed(this, EventArgs.Empty);
223    }
224    private void RegisterQualityEvents() {
225      Quality.ValueChanged += new EventHandler(Quality_ValueChanged);
226    }
227    private void DeregisterQualityEvents() {
228      Quality.ValueChanged -= new EventHandler(Quality_ValueChanged);
229    }
230    private void Quality_ValueChanged(object sender, EventArgs e) {
231      OnQualityChanged();
232    }
233
234    public event EventHandler BinPackingsChanged;
235    private void OnBinPackingsChanged() {
236      var changed = BinPackingsChanged;
237      if (changed != null)
238        changed(this, EventArgs.Empty);
239    }
240    private void RegisterBinPackingsEvents() {
241      BinPackings.PropertyChanged += new System.ComponentModel.PropertyChangedEventHandler(BinPackings_PropertyChanged);
242    }
243    private void DeregisterBinPackingsEvents() {
244      BinPackings.PropertyChanged -= new System.ComponentModel.PropertyChangedEventHandler(BinPackings_PropertyChanged);
245    }
246    private void BinPackings_PropertyChanged(object sender, EventArgs e) {
247      OnBinPackingsChanged();
248    }
249    #endregion
250  }
251
252
253
254
255  [Item("PackingPlan2D", "Represents a solution for a 2D bin packing problem.")]
256  [StorableClass]
257  public class PackingPlan2D : PackingPlan<TwoDimensionalPacking, RectangularPackingBin, RectangularPackingItem> {
258    public PackingPlan2D(RectangularPackingBin binMeasures) : this(binMeasures, false, false) { }
259    public PackingPlan2D(RectangularPackingBin binMeasures, bool useExtremePoints, bool stackingConstraints) : base(binMeasures, useExtremePoints, stackingConstraints) { }
260    [StorableConstructor]
261    protected PackingPlan2D(bool deserializing) : base(deserializing) { }
262    protected PackingPlan2D(PackingPlan2D original, Cloner cloner)
263      : base(original, cloner) {
264    }
265    public override IDeepCloneable Clone(Cloner cloner) {
266      return new PackingPlan2D(this, cloner);
267    }
268    public override BinPacking<TwoDimensionalPacking, RectangularPackingBin, RectangularPackingItem> NewBinPacking() {
269      return new BinPacking2D(BinMeasures);
270    }
271  }
272
273
274
275
276
277  [Item("PackingPlan3D", "Represents a solution for a 3D bin packing problem.")]
278  [StorableClass]
279  public class PackingPlan3D : PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> {
280    public PackingPlan3D(CuboidPackingBin binMeasures) : this(binMeasures, false, false) { }
281    public PackingPlan3D(CuboidPackingBin binMeasures, bool useExtremePoints, bool stackingConstraints) : base(binMeasures, useExtremePoints, stackingConstraints) { }
282    [StorableConstructor]
283    protected PackingPlan3D(bool deserializing) : base(deserializing) { }
284    protected PackingPlan3D(PackingPlan3D original, Cloner cloner)
285      : base(original, cloner) {
286    }
287    public override IDeepCloneable Clone(Cloner cloner) {
288      return new PackingPlan3D(this, cloner);
289    }
290    public override BinPacking<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> NewBinPacking() {
291      return new BinPacking3D(BinMeasures);
292    }
293  }
294
295}
Note: See TracBrowser for help on using the repository browser.