source: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ProblemBase.cs @ 15617

Last change on this file since 15617 was 15617, checked in by rhanghof, 21 months ago

#2817:

  • The items can be rotated and tilted now.
  • Added pruning of extreme points in packed bins.
  • Added new packer which packs items by positioning them on the point with the minimum of wasted space. He uses rotating and tilting of items.
  • Added classes for sorting given items.
File size: 12.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2018 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.Linq;
23using HeuristicLab.Common;
24using HeuristicLab.Core;
25using HeuristicLab.Data;
26using HeuristicLab.Optimization;
27using HeuristicLab.Parameters;
28using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
29using HeuristicLab.Problems.Instances;
30using HeuristicLab.Problems.BinPacking3D.Encoding;
31using HeuristicLab.Problems.BinPacking3D.Evaluators;
32using HeuristicLab.Problems.BinPacking3D.Instances;
33
34namespace HeuristicLab.Problems.BinPacking3D {
35  // in comparison to the 2d problem the 3d problem implementation also supports checking stacking constraints
36  [StorableClass]
37  public abstract class ProblemBase<TEnc, TSol> :
38    SingleObjectiveBasicProblem<TEnc>, IProblemInstanceConsumer<BPPData>, IProblemInstanceExporter<BPPData>
39    where TEnc : class, IEncoding
40    where TSol : class, IItem {
41    protected readonly string SolutionEvaluatorParameterName = "SolutionEvaluator";
42    protected readonly string UseStackingConstraintsParameterName = "UseStackingConstraints";
43
44    public readonly string EncodedSolutionName = "EncodedSolution";
45    #region Default Instance
46    private readonly BPPData defaultInstance = new BPPData() {
47      Name = "3D BPP Default Instance",
48      Description = "The default instance for 3D Bin Packing.",
49      BinShape = new PackingShape(25, 25, 35),
50      Items = new PackingItem[] {
51        new PackingItem(12,5,10, new PackingShape(25,25,35)),
52        new PackingItem(10,18,20, new PackingShape(25,25,35)),
53        new PackingItem(9,7,7, new PackingShape(25,25,35)),
54        new PackingItem(21,12,4, new PackingShape(25,25,35)),
55        new PackingItem(8,8,12, new PackingShape(25,25,35)),
56        new PackingItem(3,6,14, new PackingShape(25,25,35)),
57        new PackingItem(20,4,9, new PackingShape(25,25,35)),
58        new PackingItem(5,9,8, new PackingShape(25,25,35)),
59        new PackingItem(7,17,3, new PackingShape(25,25,35)),
60        new PackingItem(13,20,15, new PackingShape(25,25,35)),
61        new PackingItem(9,11,9, new PackingShape(25,25,35)),
62        new PackingItem(10,18,20, new PackingShape(25,25,35)),
63        new PackingItem(9,7,7, new PackingShape(25,25,35)),
64        new PackingItem(21,12,4, new PackingShape(25,25,35)),
65        new PackingItem(8,8,12, new PackingShape(25,25,35)),
66        new PackingItem(3,6,14, new PackingShape(25,25,35)),
67        new PackingItem(20,4,9, new PackingShape(25,25,35)),
68        new PackingItem(5,9,8, new PackingShape(25,25,35)),
69        new PackingItem(7,17,3, new PackingShape(25,25,35)),
70        new PackingItem(13,20,15, new PackingShape(25,25,35)),
71        new PackingItem(9,11,9, new PackingShape(25,25,35)),
72        new PackingItem(10,18,20, new PackingShape(25,25,35)),
73        new PackingItem(9,7,7, new PackingShape(25,25,35)),
74        new PackingItem(21,12,4, new PackingShape(25,25,35)),
75        new PackingItem(8,8,12, new PackingShape(25,25,35)),
76        new PackingItem(3,6,14, new PackingShape(25,25,35)),
77        new PackingItem(20,4,9, new PackingShape(25,25,35)),
78        new PackingItem(5,9,8, new PackingShape(25,25,35)),
79        new PackingItem(7,17,3, new PackingShape(25,25,35)),
80        new PackingItem(13,20,15, new PackingShape(25,25,35)),
81        new PackingItem(9,11, 9,new PackingShape(25,25,35)),
82        new PackingItem(10,18,20, new PackingShape(25,25,35)),
83        new PackingItem(9,7,7, new PackingShape(25,25,35)),
84        new PackingItem(21,12,4, new PackingShape(25,25,35)),
85        new PackingItem(8,8,12, new PackingShape(25,25,35)),
86        new PackingItem(3,6,14, new PackingShape(25,25,35)),
87        new PackingItem(20,4,9, new PackingShape(25,25,35)),
88        new PackingItem(5,9,8, new PackingShape(25,25,35)),
89        new PackingItem(7,17,3, new PackingShape(25,25,35)),
90        new PackingItem(13,20,15, new PackingShape(25,25,35)),
91        new PackingItem(9,11,9, new PackingShape(25,25,35))
92      },
93    };
94    #endregion
95
96    #region parameter properties
97    public IValueParameter<IDecoder<TSol>> DecoderParameter {
98      get { return (IValueParameter<IDecoder<TSol>>)Parameters["Decoder"]; }
99    }
100    public IValueParameter<IEvaluator> SolutionEvaluatorParameter {
101      get { return (IValueParameter<IEvaluator>)Parameters[SolutionEvaluatorParameterName]; }
102    }
103    public IFixedValueParameter<BoolValue> UseStackingConstraintsParameter {
104      get { return (IFixedValueParameter<BoolValue>)Parameters[UseStackingConstraintsParameterName]; }
105    }
106    public IValueParameter<ReadOnlyItemList<PackingItem>> ItemsParameter {
107      get { return (IValueParameter<ReadOnlyItemList<PackingItem>>)Parameters["Items"]; }
108    }
109    public IValueParameter<PackingShape> BinShapeParameter {
110      get { return (IValueParameter<PackingShape>)Parameters["BinShape"]; }
111    }
112    public IValueParameter<Solution> BestKnownSolutionParameter {
113      get { return (IValueParameter<Solution>)Parameters["BestKnownSolution"]; }
114    }
115    public IFixedValueParameter<IntValue> LowerBoundParameter {
116      get { return (IFixedValueParameter<IntValue>)Parameters["LowerBound"]; }
117    }
118    #endregion
119
120    #region properties
121    public IDecoder<TSol> Decoder {
122      get { return DecoderParameter.Value; }
123      set { DecoderParameter.Value = value; }
124    }
125    public IEvaluator SolutionEvaluator {
126      get { return SolutionEvaluatorParameter.Value; }
127      set { SolutionEvaluatorParameter.Value = value; }
128    }
129    public bool UseStackingConstraints {
130      get { return UseStackingConstraintsParameter.Value.Value; }
131      set { UseStackingConstraintsParameter.Value.Value = value; }
132    }
133    public ReadOnlyItemList<PackingItem> Items {
134      get { return ItemsParameter.Value; }
135      set { ItemsParameter.Value = value; }
136    }
137    public PackingShape BinShape {
138      get { return BinShapeParameter.Value; }
139      set { BinShapeParameter.Value = value; }
140    }
141    public Solution BestKnownSolution {
142      get { return BestKnownSolutionParameter.Value; }
143      set { BestKnownSolutionParameter.Value = value; }
144    }
145    public int LowerBound {
146      get { return LowerBoundParameter.Value.Value; }
147    }
148    public int NumberOfItems {
149      get { return Items == null ? 0 : Items.Count; }
150    }
151    #endregion
152
153    // persistence
154    [StorableConstructor]
155    protected ProblemBase(bool deserializing) : base(deserializing) { }
156
157    // cloning
158    protected ProblemBase(ProblemBase<TEnc, TSol> original, Cloner cloner)
159      : base(original, cloner) {
160    }
161
162    protected ProblemBase()
163      : base() {
164      var defaultEvaluator = new PackingRatioEvaluator();
165      Parameters.Add(new ValueParameter<IDecoder<TSol>>("Decoder", "The decoder translates a permutation to a packing solution candidiates"));
166      Parameters.Add(new ValueParameter<IEvaluator>(SolutionEvaluatorParameterName, "The evaluator calculates qualities of solution candidates", defaultEvaluator));
167      Parameters.Add(new FixedValueParameter<BoolValue>(UseStackingConstraintsParameterName, "A flag that determines if stacking constraints are considered when solving the problem.", new BoolValue(false)));
168      Parameters.Add(new ValueParameter<ReadOnlyItemList<PackingItem>>("Items", "The items which must be packed into bins"));
169      Parameters.Add(new ValueParameter<PackingShape>("BinShape", "The size of bins into which items must be packed"));
170      Parameters.Add(new OptionalValueParameter<Solution>("BestKnownSolution", "The best solution found so far"));
171      Parameters.Add(new FixedValueParameter<IntValue>("LowerBound", "A lower bound for the number of bins that is necessary to pack all items"));
172
173      Load(defaultInstance);
174    }
175
176    public override bool Maximization { get { return true; } }
177
178    public override double Evaluate(Individual individual, IRandom random) {
179      var encodedSolutionCand = (TSol)individual[EncodedSolutionName];
180      var decoder = Decoder;
181      var solution = decoder.Decode(encodedSolutionCand, BinShape, Items, UseStackingConstraints);
182      return SolutionEvaluator.Evaluate(solution);
183    }
184
185    public override void Analyze(Individual[] individuals, double[] qualities, ResultCollection results, IRandom random) {
186      base.Analyze(individuals, qualities, results, random);
187      Analyze(individuals.Select(i => (TSol)i[EncodedSolutionName]).ToArray(), qualities, results, random);
188    }
189
190    // NOTE: same implementation as for 2d problem
191    public virtual void Analyze(TSol[] individuals, double[] qualities, ResultCollection results, IRandom random) {
192      var bestSolutionResultName = "Best Packing Solution";
193      var numContainersResultName = "Nr of Containers";
194      var binUtilResultName = "Overall Bin Utilization";
195
196      if (!results.ContainsKey(bestSolutionResultName)) results.Add(new Result(bestSolutionResultName, typeof(Solution)));
197      if (!results.ContainsKey(numContainersResultName)) results.Add(new Result(numContainersResultName, typeof(IntValue)));
198      if (!results.ContainsKey(binUtilResultName)) results.Add(new Result(binUtilResultName, typeof(DoubleValue)));
199
200
201      // find index of item with max quality
202      int bestIdx = 0;
203      for (int j = 1; j < qualities.Length; j++)
204        if (qualities[j] > qualities[bestIdx]) bestIdx = j;
205
206
207      // update best solution so far
208      var bestSolution = results[bestSolutionResultName].Value as Solution;
209      if (bestSolution == null ||
210        bestSolution.Quality.Value < qualities[bestIdx]) {
211
212        var newBestSolution = Decoder.Decode(individuals[bestIdx], BinShape, Items, UseStackingConstraints);
213        newBestSolution.Quality = new DoubleValue(qualities[bestIdx]);
214        results[bestSolutionResultName].Value = newBestSolution;
215        results[numContainersResultName].Value = new IntValue(newBestSolution.NrOfBins);
216        results[binUtilResultName].Value = new DoubleValue(BinUtilizationEvaluator.CalculateBinUtilization(newBestSolution));
217
218        // update best known solution
219        var bestKnownQuality = BestKnownQualityParameter.Value;
220        if (bestKnownQuality == null ||
221            bestKnownQuality.Value < qualities[bestIdx]) {
222          BestKnownQualityParameter.ActualValue = new DoubleValue(qualities[bestIdx]);
223          BestKnownSolutionParameter.ActualValue = newBestSolution;
224        }
225      }
226    }
227
228
229    #region Problem instance handling
230    public void Load(BPPData data) {
231      BestKnownSolutionParameter.Value = null;
232      BestKnownQualityParameter.Value = null;
233
234      if (data.BestKnownQuality.HasValue)
235        BestKnownQuality = data.BestKnownQuality.Value;
236
237      BinShape = data.BinShape;
238      var items = new ItemList<PackingItem>(data.Items);
239      Items = items.AsReadOnly();
240
241      ApplyHorizontalOrientation();
242      LowerBoundParameter.Value.Value = CalculateLowerBound();
243    }
244
245
246    public BPPData Export() {
247      return new BPPData {
248        Name = Name,
249        Description = Description,
250        BinShape = BinShape,
251        Items = Items.ToArray()
252      };
253    }
254    #endregion
255
256
257    #region helpers
258    private void ApplyHorizontalOrientation() {
259      BinShape.ApplyHorizontalOrientation();
260      foreach (var shape in Items) {
261        shape.ApplyHorizontalOrientation();
262      }
263    }
264
265    private int CalculateLowerBound() {
266      //This is the obvious continuous lower bound calculation; Martello and Vigo proposed a better way but it has not been implemented yet;
267      int itemsVol = Items.Select(x => x.Volume).Sum();
268      int binVol = BinShape.Volume;
269      return (itemsVol + binVol - 1) / (binVol);
270    }
271
272    #endregion
273  }
274}
Note: See TracBrowser for help on using the repository browser.