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

Last change on this file since 14048 was 14048, checked in by gkronber, 3 years ago

#1966: renamed *PackingDimension -> PackingPosition

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