source: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Algorithms/ExtremePointAlgorithm.cs @ 15646

Last change on this file since 15646 was 15646, checked in by rhanghof, 3 years ago

#2817:

  • Dealing with stackable items
  • Enhanced the Evaluator
  • Added parameters some paramters to the packing items
File size: 15.8 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;
23using System.Collections.Generic;
24using System.Linq;
25using System.Threading;
26
27using HeuristicLab.Common;
28using HeuristicLab.Core;
29using HeuristicLab.Data;
30using HeuristicLab.Encodings.PermutationEncoding;
31using HeuristicLab.Optimization;
32using HeuristicLab.Parameters;
33using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
34using HeuristicLab.Problems.BinPacking3D.Packer;
35using HeuristicLab.Problems.BinPacking3D.Encoding;
36using HeuristicLab.Problems.BinPacking3D.Sorting;
37using HeuristicLab.Problems.BinPacking3D.Evaluators;
38
39namespace HeuristicLab.Problems.BinPacking3D {
40
41  public enum SortingMethod { All, Given, VolumeHeight, HeightVolume, AreaHeight, HeightArea, ClusteredAreaHeight, ClusteredHeightArea }
42  public enum FittingMethod { All, FirstFit, ResidualSpaceBestFit, FreeVolumeBestFit, MinimumResidualSpaceLeft }
43
44  public enum ExtremePointCreationMethod { All, PointProjection, LineProjection }
45
46  public enum ExtremePointPruningMethod { None, All, PruneBehind }
47
48  [Item("Extreme-point-based Bin Packing (3d)", "An implementation of the extreme-point based packing described in Crainic, T. G., Perboli, G., & Tadei, R. (2008). Extreme point-based heuristics for three-dimensional bin packing. Informs Journal on computing, 20(3), 368-384.")]
49  [StorableClass]
50  [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms, Priority = 180)]
51  public sealed class ExtremePointAlgorithm : BasicAlgorithm {
52
53    public override Type ProblemType {
54      get { return typeof(PermutationProblem); }
55    }
56
57    public new PermutationProblem Problem {
58      get { return (PermutationProblem)base.Problem; }
59      set { base.Problem = value; }
60    }
61
62    public override bool SupportsPause {
63      get { return false; }
64    }
65
66    [Storable]
67    private readonly IValueParameter<EnumValue<SortingMethod>> sortingMethodParameter;
68    public IValueParameter<EnumValue<SortingMethod>> SortingMethodParameter {
69      get { return sortingMethodParameter; }
70    }
71
72    [Storable]
73    private readonly IValueParameter<EnumValue<FittingMethod>> fittingMethodParameter;
74    public IValueParameter<EnumValue<FittingMethod>> FittingMethodParameter {
75      get { return fittingMethodParameter; }
76    }
77
78    [Storable]
79    private readonly IValueParameter<PercentValue> deltaParameter;
80    public IValueParameter<PercentValue> DeltaParameter {
81      get { return deltaParameter; }
82    }
83
84    [Storable]
85    private readonly IValueParameter<BoolValue> sortByMaterialParameter;
86
87    public IValueParameter<BoolValue> SortByMaterialParameter {
88      get { return sortByMaterialParameter; }
89    }
90
91    [Storable]
92    private readonly IValueParameter<EnumValue<ExtremePointCreationMethod>> extremePointCreationMethodParameter;
93    public IValueParameter<EnumValue<ExtremePointCreationMethod>> ExtremePointCreationMethodParameter {
94      get { return extremePointCreationMethodParameter; }
95    }
96
97    [StorableConstructor]
98    private ExtremePointAlgorithm(bool deserializing) : base(deserializing) { }
99    private ExtremePointAlgorithm(ExtremePointAlgorithm original, Cloner cloner)
100      : base(original, cloner) {
101      sortingMethodParameter = cloner.Clone(original.sortingMethodParameter);
102      fittingMethodParameter = cloner.Clone(original.fittingMethodParameter);
103      deltaParameter = cloner.Clone(original.deltaParameter);
104    }
105    public ExtremePointAlgorithm() {
106      Parameters.Add(sortingMethodParameter = new ValueParameter<EnumValue<SortingMethod>>(
107        "SortingMethod", "In which order the items should be packed.", new EnumValue<SortingMethod>(SortingMethod.All)));
108
109      Parameters.Add(fittingMethodParameter = new ValueParameter<EnumValue<FittingMethod>>(
110        "FittingMethod", "Which method to fit should be used.", new EnumValue<FittingMethod>(FittingMethod.All)));
111
112      Parameters.Add(extremePointCreationMethodParameter = new ValueParameter<EnumValue<ExtremePointCreationMethod>>(
113        "ExtremePointCreationMethod", "Which method should be used for creatomg extreme points.", new EnumValue<ExtremePointCreationMethod>(ExtremePointCreationMethod.All)));
114
115      Parameters.Add(deltaParameter = new ValueParameter<PercentValue>(
116        "Delta", "[1;100]% Clustered sorting methods use a delta parameter to determine the clusters.", new PercentValue(.1)));
117
118      Parameters.Add(sortByMaterialParameter = new ValueParameter<BoolValue>(
119        "SortByMaterial", "If this parameter is set, the items will be sorted by their material first", new BoolValue(true)));
120
121      Problem = new PermutationProblem();
122    }
123
124    public override IDeepCloneable Clone(Cloner cloner) {
125      return new ExtremePointAlgorithm(this, cloner);
126    }
127
128    [StorableHook(HookType.AfterDeserialization)]
129    private void AfterDeserialization() {
130    }
131
132    /// <summary>
133    /// Runs the extreme point algorithm and adds the results to the property <see cref="Result"/>
134    /// </summary>
135    /// <param name="token"></param>
136    protected override void Run(CancellationToken token) {
137      var items = Problem.Items;
138      var bin = Problem.BinShape;
139
140      var sorting = new[] { SortingMethodParameter.Value.Value };
141      if (sorting[0] == SortingMethod.All) {
142        sorting = Enum.GetValues(typeof(SortingMethod)).Cast<SortingMethod>().Where(x => x != SortingMethod.All).ToArray();
143      }
144
145      var fitting = new[] { fittingMethodParameter.Value.Value };
146      if (fitting[0] == FittingMethod.All) {
147        fitting = Enum.GetValues(typeof(FittingMethod)).Cast<FittingMethod>().Where(x => x != FittingMethod.All).ToArray();
148      }
149
150      var extremePointCreation = new[] { ExtremePointCreationMethodParameter.Value.Value };
151      if (extremePointCreation[0] == ExtremePointCreationMethod.All) {
152        extremePointCreation = Enum.GetValues(typeof(ExtremePointCreationMethod))
153                                     .Cast<ExtremePointCreationMethod>()
154                                     .Where(x => x != ExtremePointCreationMethod.All)
155                                     .ToArray();
156      }
157
158      //
159      var result = GetBest(bin, items, sorting, fitting, extremePointCreation, token);
160      if (result == null) {
161        throw new InvalidOperationException("No result obtained!");
162      }
163
164      Results.Add(new Result("Best Solution", "The best found solution", result.Item1));
165      Results.Add(new Result("Best Solution Quality", "The quality of the best found solution according to the evaluator", new DoubleValue(result.Item2)));
166
167      var binUtil = new BinUtilizationEvaluator();
168      var packRatio = new PackingRatioEvaluator();
169      Results.Add(new Result("Best Solution Bin Count",
170        "The number of bins in the best found solution",
171        new IntValue(result.Item1.NrOfBins)));
172      Results.Add(new Result("Best Solution Bin Utilization",
173        "The utilization given in percentage as calculated by the BinUtilizationEvaluator (total used space / total available space)",
174        new PercentValue(Math.Round(binUtil.Evaluate(result.Item1), 3))));
175
176      if (result.Item3.HasValue && sorting.Length > 1) {
177        Results.Add(new Result("Best Sorting Method",
178          "The sorting method that found the best solution",
179          new EnumValue<SortingMethod>(result.Item3.Value)));
180      }
181
182      if (result.Item4.HasValue && fitting.Length > 1) {
183        Results.Add(new Result("Best Fitting Method",
184          "The fitting method that found the best solution",
185          new EnumValue<FittingMethod>(result.Item4.Value)));
186      }
187
188      if (result.Item5.HasValue && extremePointCreation.Length > 1) {
189        Results.Add(new Result("Best extreme point creation method",
190          "The extreme point creation method that found the best solution",
191          new EnumValue<ExtremePointCreationMethod>(result.Item5.Value)));
192      }
193    }
194
195    /// <summary>
196    /// Retunrs the best solution for the given parameters
197    /// </summary>
198    /// <param name="bin"></param>
199    /// <param name="items"></param>
200    /// <param name="sortings"></param>
201    /// <param name="fittings"></param>
202    /// <param name="token"></param>
203    /// <returns></returns>
204    private Tuple<Solution, double, SortingMethod?, FittingMethod?, ExtremePointCreationMethod?>
205          GetBest(PackingShape bin,
206                  IList<PackingItem> items,
207                  SortingMethod[] sortings,
208                  FittingMethod[] fittings,
209                  ExtremePointCreationMethod[] epCreationMethods,
210                  CancellationToken token) {
211      SortingMethod? bestSorting = null;
212      FittingMethod? bestFitting = null;
213      ExtremePointCreationMethod? bestEPCreation = null;
214      var best = double.NaN;
215      Solution bestSolution = null;
216      foreach (var fit in fittings) {
217        foreach (var sort in sortings) {
218          foreach (var epCreation in epCreationMethods) {
219            IDecoder<Permutation> decoder = new ExtremePointPermutationDecoder() {
220              FittingMethod = fit,
221              ExtremePointCreationMethod = epCreation
222            };
223            Permutation sortedItems;
224
225            if (SortByMaterialParameter.Value.Value) {
226              sortedItems = SortItemsByMaterialAndSortingMethod(bin, items, sort, DeltaParameter.Value.Value);
227            } else {
228              sortedItems = SortItemsBySortingMethod(bin, items, sort, DeltaParameter.Value.Value);
229            }
230
231            var solution = Optimize(new OptimaizationParamters() {
232              SortedItems = sortedItems,
233              Bin = bin,
234              Items = items,
235              StackingConstraints = Problem.UseStackingConstraints,
236              Decoder = decoder,
237              Evaluator = Problem.SolutionEvaluator,
238              ExtremePointGeneration = epCreation
239            });
240
241            if (solution.IsBetterThan(bestSolution, Problem.SolutionEvaluator, Problem.Maximization)) {
242              bestSolution = solution;
243              best = Problem.SolutionEvaluator.Evaluate(solution);
244              bestSorting = sort;
245              bestFitting = fit;
246              bestEPCreation = epCreation;
247            }
248
249
250            var x = Problem.SolutionEvaluator.Evaluate1(solution);
251
252            /*
253            if (double.IsNaN(result.Item2) || double.IsInfinity(result.Item2)) {
254              continue;
255            }
256
257            if (double.IsNaN(best) || Problem.Maximization && result.Item2 > best || !Problem.Maximization && result.Item2 < best) {
258              bestSolution = result.Item1;
259              best = result.Item2;
260              bestSorting = sort;
261              bestFitting = fit;
262              bestEPCreation = epCreation;
263            }
264            return true;*/
265
266            if (token.IsCancellationRequested) {
267              return Tuple.Create(bestSolution, best, bestSorting, bestFitting, bestEPCreation);
268            }
269          }
270        }
271      }
272      if (double.IsNaN(best)) {
273        return null;
274      }
275      return Tuple.Create(bestSolution, best, bestSorting, bestFitting, bestEPCreation);
276    }
277
278    /// <summary>
279    /// Returns a tuple with the solution and the packing ratio depending on the given parameters
280    /// </summary>
281    /// <param name="parameters"></param>
282    /// <returns></returns>
283    private static Solution Optimize(OptimaizationParamters parameters) {
284
285      var sol = parameters.Decoder.Decode(parameters.SortedItems, parameters.Bin, parameters.Items, parameters.StackingConstraints);
286      //var fit = parameters.Evaluator.Evaluate(sol);
287
288      return sol; //Tuple.Create(sol, fit);
289    }
290
291    private class OptimaizationParamters {
292      public Permutation SortedItems { get; set; }
293      public PackingShape Bin { get; set; }
294      public IList<PackingItem> Items { get; set; }
295      public bool StackingConstraints { get; set; }
296      public IDecoder<Permutation> Decoder { get; set; }
297      public IEvaluator Evaluator { get; set; }
298      public ExtremePointCreationMethod ExtremePointGeneration { get; set; }
299    }
300
301
302    /// <summary>
303    /// Returns a new permutation of the given items depending on the sorting method
304    /// </summary>
305    /// <param name="bin"></param>
306    /// <param name="items"></param>
307    /// <param name="sortingMethod"></param>
308    /// <param name="delta"></param>
309    /// <returns></returns>
310    private Permutation SortItemsByMaterialAndSortingMethod(PackingShape bin, IList<PackingItem> items, SortingMethod sortingMethod, double delta) {
311      Permutation sorted = null;
312
313      switch (sortingMethod) {
314        case SortingMethod.Given:
315          sorted = new Permutation(PermutationTypes.Absolute, Enumerable.Range(0, items.Count).ToArray());
316          break;
317        case SortingMethod.VolumeHeight:
318          sorted = items.SortByVolumeHeight();
319          break;
320        case SortingMethod.HeightVolume:
321          sorted = items.SortByMaterialHeightVolume();
322          break;
323        case SortingMethod.AreaHeight:
324          sorted = items.SortByMaterialAreaHeight();
325          break;
326        case SortingMethod.HeightArea:
327          sorted = items.SortByMaterialHeightArea();
328          break;
329        case SortingMethod.ClusteredAreaHeight:
330          sorted = items.SortByMaterialClusteredAreaHeight(bin, delta);
331          break;
332        case SortingMethod.ClusteredHeightArea:
333          sorted = items.SortByMaterialClusteredHeightArea(bin, delta);
334          break;
335        default:
336          throw new ArgumentException("Unknown sorting method: " + sortingMethod);
337      }
338      return sorted;
339    }
340
341    /// <summary>
342    /// Returns a new permutation of the given items depending on the material and sorting method
343    /// </summary>
344    /// <param name="bin"></param>
345    /// <param name="items"></param>
346    /// <param name="sortingMethod"></param>
347    /// <param name="delta"></param>
348    /// <returns></returns>
349    private Permutation SortItemsBySortingMethod(PackingShape bin, IList<PackingItem> items, SortingMethod sortingMethod, double delta) {
350      Permutation sorted = null;
351
352      switch (sortingMethod) {
353        case SortingMethod.Given:
354          sorted = new Permutation(PermutationTypes.Absolute, Enumerable.Range(0, items.Count).ToArray());
355          break;
356        case SortingMethod.VolumeHeight:
357          sorted = items.SortByVolumeHeight();
358          break;
359        case SortingMethod.HeightVolume:
360          sorted = items.SortByHeightVolume();
361          break;
362        case SortingMethod.AreaHeight:
363          sorted = items.SortByAreaHeight();
364          break;
365        case SortingMethod.HeightArea:
366          sorted = items.SortByHeightArea();
367          break;
368        case SortingMethod.ClusteredAreaHeight:
369          sorted = items.SortByClusteredAreaHeight(bin, delta);
370          break;
371        case SortingMethod.ClusteredHeightArea:
372          sorted = items.SortByClusteredHeightArea(bin, delta);
373          break;
374        default:
375          throw new ArgumentException("Unknown sorting method: " + sortingMethod);
376      }
377      return sorted;
378    }
379  }
380}
Note: See TracBrowser for help on using the repository browser.