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

Last change on this file since 14146 was 14146, checked in by gkronber, 5 years ago

#1966: new implementation for 2d bin packing problem with permutation encoding

File size: 8.9 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.Linq;
24using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
25using HeuristicLab.Core;
26using HeuristicLab.Common;
27using HeuristicLab.Data;
28using HeuristicLab.Collections;
29using HeuristicLab.Problems.BinPacking;
30
31namespace HeuristicLab.Encodings.PackingEncoding {
32  [Item("PackingPlan", "Represents a concrete solution for a bin-packing problem.")]
33  [StorableClass]
34  public abstract class PackingPlan<D, B, I> : Item, IPackingPlan
35    where D : class, IPackingPosition
36    where B : PackingShape<D>
37    where I : PackingShape<D>, IPackingItem {
38
39    #region Properties
40    public int NrOfBins {
41      get {
42        if (BinPackings != null)
43          return BinPackings.Count;
44        else return 0;
45      }
46    }
47    [Storable]
48    protected bool StackingConstraints { get; set; }
49    [Storable]
50    protected bool UseExtremePoints { get; set; }
51
52    [Storable]
53    public B BinMeasures { get; private set; }
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    protected PackingPlan(B binMeasures, bool useExtremePoints, bool stackingConstraints)
74      : base() {
75      BinMeasures = (B)binMeasures.Clone();
76      StackingConstraints = stackingConstraints;
77      UseExtremePoints = useExtremePoints;
78      BinPackings = new ObservableList<BinPacking<D, B, I>>();
79    }
80
81    [StorableConstructor]
82    protected PackingPlan(bool deserializing) : base(deserializing) { }
83    protected PackingPlan(PackingPlan<D, B, I> original, Cloner cloner)
84      : base(original, cloner) {
85      this.BinPackings = new ObservableList<BinPacking<D, B, I>>(original.BinPackings);
86    }
87
88
89    public abstract BinPacking<D, B, I> NewBinPacking();
90    public void UpdateBinPackings() {
91      BinPackings.RemoveAll(x => x.ItemPositions.Count == 0);
92      BinPackings = new ObservableList<BinPacking<D, B, I>>(BinPackings.OrderByDescending(bp => bp.PackingDensity));
93    }
94
95    /*
96    public void Pack(MultiComponentVectorEncoding solution, ItemList<I> itemMeasures) {
97      var sequenceMatrix = solution.GenerateSequenceMatrix();
98      Dictionary<int, bool> rotated = solution.GenerateRotationArray();
99
100      //Fill bins according to grouping vector
101      List<int> remainingIDs = new List<int>();
102      foreach (var sequence in sequenceMatrix) {
103        remainingIDs = remainingIDs.Concat(sequence).ToList();
104        var bp = NewBinPacking();
105        if (!UseExtremePoints)
106          bp.SlidingBasedPacking(ref remainingIDs, itemMeasures, rotated);
107        else
108          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints, rotated);
109        BinPackings.Add(bp);
110      }
111      UpdateBinPackings();
112
113      //Try to put remaining items in existing bins
114      var temp = new List<int>(remainingIDs);
115      foreach (int id in temp) {
116        foreach (var bp in BinPackings) {
117          var position = UseExtremePoints ? bp.FindExtremePointForItem(itemMeasures[id], rotated[id], StackingConstraints) : bp.FindPositionBySliding(itemMeasures[id], rotated[id]);
118          if (position != null) {
119            bp.PackItem(id, itemMeasures[id], position);
120            remainingIDs.Remove(id);
121            break;
122          }
123        }
124      }
125
126      //Put still remaining items in new bins
127      while (remainingIDs.Count > 0) {
128        var bp = NewBinPacking();
129        if (!UseExtremePoints)
130          bp.SlidingBasedPacking(ref remainingIDs, itemMeasures, rotated);
131        else
132          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints, rotated);
133        BinPackings.Add(bp);
134      }
135      UpdateBinPackings();
136
137      var newSolution = new ObservableDictionary<int, ItemList<PackingInformation>>();
138      foreach (var bp in BinPackings) {
139        int binIndex = newSolution.Count;
140        newSolution[binIndex] = new ItemList<PackingInformation>();
141        foreach (var entry in bp.ItemPositions)
142          newSolution[binIndex].Add(new PackingInformation(entry.Key, entry.Value.Rotated));
143      }
144      solution.PackingInformations = newSolution;
145    }
146    public void Pack(GroupingVectorEncoding solution, ItemList<I> itemMeasures) {
147      var sequenceMatrix = solution.GenerateSequenceMatrix();
148
149      //Fill bins according to grouping vector
150      List<int> remainingIDs = new List<int>();
151      foreach (var sequence in sequenceMatrix) {
152        remainingIDs = remainingIDs.Concat(sequence).ToList();
153        var bp = NewBinPacking();
154        if (!UseExtremePoints)
155          bp.SlidingBasedPacking(ref remainingIDs, itemMeasures);
156        else
157          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints);
158        BinPackings.Add(bp);
159      }
160      UpdateBinPackings();
161
162      //Try to put remaining items in existing bins
163      var temp = new List<int>(remainingIDs);
164      foreach (int id in temp) {
165        foreach (var bp in BinPackings) {
166          var position = UseExtremePoints ? bp.FindExtremePointForItem(itemMeasures[id], false, StackingConstraints) : bp.FindPositionBySliding(itemMeasures[id], false);
167          if (position != null) {
168            bp.PackItem(id, itemMeasures[id], position);
169            remainingIDs.Remove(id);
170            break;
171          }
172        }
173      }
174
175      //Put still remaining items in new bins
176      while (remainingIDs.Count > 0) {
177        var bp = NewBinPacking();
178        if (!UseExtremePoints)
179          bp.SlidingBasedPacking(ref remainingIDs, itemMeasures);
180        else
181          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints);
182        BinPackings.Add(bp);
183      }
184      UpdateBinPackings();
185
186      var newSolution = new int[solution.GroupingVector.Length];
187      int binIndex = 0;
188      foreach (var bp in BinPackings) {
189        foreach (var entry in bp.ItemPositions)
190          newSolution[entry.Key] = binIndex;
191        binIndex++;
192      }
193      solution.GroupingVector = new IntegerVector(newSolution);
194    }
195     *
196     
197    public void Pack(Permutation solution, ItemList<I> itemMeasures) {
198      List<int> remainingIDs = new List<int>(solution);
199      while (remainingIDs.Count > 0) {
200        var bp = NewBinPacking();
201        if (!UseExtremePoints)
202          bp.SlidingBasedPacking(ref remainingIDs, itemMeasures);
203        else
204          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints);
205        BinPackings.Add(bp);
206      }
207      UpdateBinPackings();
208    }
209
210    */
211    #region Events
212    public event EventHandler QualityChanged;
213    private void OnQualityChanged() {
214      var changed = QualityChanged;
215      if (changed != null)
216        changed(this, EventArgs.Empty);
217    }
218    private void RegisterQualityEvents() {
219      Quality.ValueChanged += new EventHandler(Quality_ValueChanged);
220    }
221    private void DeregisterQualityEvents() {
222      Quality.ValueChanged -= new EventHandler(Quality_ValueChanged);
223    }
224    private void Quality_ValueChanged(object sender, EventArgs e) {
225      OnQualityChanged();
226    }
227
228    public event EventHandler BinPackingsChanged;
229    private void OnBinPackingsChanged() {
230      var changed = BinPackingsChanged;
231      if (changed != null)
232        changed(this, EventArgs.Empty);
233    }
234    private void RegisterBinPackingsEvents() {
235      BinPackings.PropertyChanged += new System.ComponentModel.PropertyChangedEventHandler(BinPackings_PropertyChanged);
236    }
237    private void DeregisterBinPackingsEvents() {
238      BinPackings.PropertyChanged -= new System.ComponentModel.PropertyChangedEventHandler(BinPackings_PropertyChanged);
239    }
240    private void BinPackings_PropertyChanged(object sender, EventArgs e) {
241      OnBinPackingsChanged();
242    }
243    #endregion
244  }
245}
Note: See TracBrowser for help on using the repository browser.