Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2913_MatlabScriptProblemInstanceProvider/HeuristicLab.Problems.BinPacking/3.3/Algorithms/3D/ExtremePointAlgorithm.cs @ 18242

Last change on this file since 18242 was 15583, checked in by swagner, 7 years ago

#2640: Updated year of copyrights in license headers

File size: 11.7 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2018 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 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;
34
35namespace HeuristicLab.Problems.BinPacking3D {
36 
37  public enum SortingMethod { All, Given, VolumeHeight, HeightVolume, AreaHeight, HeightArea, ClusteredAreaHeight, ClusteredHeightArea }
38  public enum FittingMethod { All, FirstFit, ResidualSpaceBestFit, FreeVolumeBestFit }
39
40  [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.")]
41  [StorableClass]
42  [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms, Priority = 180)]
43  public sealed class ExtremePointAlgorithm : BasicAlgorithm {
44
45    public override Type ProblemType {
46      get { return typeof(PermutationProblem); }
47    }
48
49    public new PermutationProblem Problem {
50      get { return (PermutationProblem)base.Problem; }
51      set { base.Problem = value; }
52    }
53
54    public override bool SupportsPause {
55      get { return false; }
56    }
57
58    [Storable]
59    private readonly IValueParameter<EnumValue<SortingMethod>> sortingMethodParameter;
60    public IValueParameter<EnumValue<SortingMethod>> SortingMethodParameter {
61      get { return sortingMethodParameter; }
62    }
63
64    [Storable]
65    private readonly IValueParameter<EnumValue<FittingMethod>> fittingMethodParameter;
66    public IValueParameter<EnumValue<FittingMethod>> FittingMethodParameter {
67      get { return fittingMethodParameter; }
68    }
69
70    [Storable]
71    private readonly IValueParameter<PercentValue> deltaParameter;
72    public IValueParameter<PercentValue> DeltaParameter {
73      get { return deltaParameter; }
74    }
75
76    [StorableConstructor]
77    private ExtremePointAlgorithm(bool deserializing) : base(deserializing) { }
78    private ExtremePointAlgorithm(ExtremePointAlgorithm original, Cloner cloner)
79      : base(original, cloner) {
80      sortingMethodParameter = cloner.Clone(original.sortingMethodParameter);
81      fittingMethodParameter = cloner.Clone(original.fittingMethodParameter);
82      deltaParameter = cloner.Clone(original.deltaParameter);
83    }
84    public ExtremePointAlgorithm() {
85      Parameters.Add(sortingMethodParameter = new ValueParameter<EnumValue<SortingMethod>>("SortingMethod", "In which order the items should be packed.", new EnumValue<SortingMethod>(SortingMethod.All)));
86      Parameters.Add(fittingMethodParameter = new ValueParameter<EnumValue<FittingMethod>>("FittingMethod", "Which method to fit should be used.", new EnumValue<FittingMethod>(FittingMethod.All)));
87      Parameters.Add(deltaParameter = new ValueParameter<PercentValue>("Delta", "[1;100]% Clustered sorting methods use a delta parameter to determine the clusters.", new PercentValue(.1)));
88     
89      Problem = new PermutationProblem();
90    }
91
92    public override IDeepCloneable Clone(Cloner cloner) {
93      return new ExtremePointAlgorithm(this, cloner);
94    }
95   
96    [StorableHook(HookType.AfterDeserialization)]
97    private void AfterDeserialization() {
98    }
99
100    protected override void Run(CancellationToken token) {
101      var items = Problem.Items;
102      var bin = Problem.BinShape;
103      var sorting = new[] { SortingMethodParameter.Value.Value };
104      if (sorting[0] == SortingMethod.All) {
105        sorting = Enum.GetValues(typeof(SortingMethod)).Cast<SortingMethod>().Where(x => x != SortingMethod.All).ToArray();
106      }
107      var fitting = new[] { fittingMethodParameter.Value.Value };
108      if (fitting[0] == FittingMethod.All) {
109        fitting = Enum.GetValues(typeof(FittingMethod)).Cast<FittingMethod>().Where(x => x != FittingMethod.All).ToArray();
110      }
111      var result = GetBest(bin, items, sorting, fitting, token);
112      if (result == null) throw new InvalidOperationException("No result obtained!");
113
114      Results.Add(new Result("Best Solution",
115        "The best found solution",
116        result.Item1));
117      Results.Add(new Result("Best Solution Quality",
118        "The quality of the best found solution according to the evaluator",
119        new DoubleValue(result.Item2)));
120
121      var binUtil = new BinUtilizationEvaluator();
122      var packRatio = new PackingRatioEvaluator();
123      Results.Add(new Result("Best Solution Bin Count",
124        "The number of bins in the best found solution",
125        new IntValue(result.Item1.NrOfBins)));
126      Results.Add(new Result("Best Solution Bin Utilization",
127        "The utilization given in percentage as calculated by the BinUtilizationEvaluator (total used space / total available space)",
128        new PercentValue(Math.Round(binUtil.Evaluate(result.Item1), 3))));
129
130      if (result.Item3.HasValue && sorting.Length > 1)
131        Results.Add(new Result("Best Sorting Method",
132          "The sorting method that found the best solution",
133          new EnumValue<SortingMethod>(result.Item3.Value)));
134      if (result.Item4.HasValue && fitting.Length > 1)
135        Results.Add(new Result("Best Fitting Method",
136          "The fitting method that found the best solution",
137          new EnumValue<FittingMethod>(result.Item4.Value)));
138    }
139
140    private Tuple<Solution, double, SortingMethod?, FittingMethod?> GetBest(PackingShape bin, IList<PackingItem> items, SortingMethod[] sortings, FittingMethod[] fittings, CancellationToken token) {
141      SortingMethod? bestSorting = null;
142      FittingMethod? bestFitting = null;
143      var best = double.NaN;
144      Solution bestSolution = null;
145      foreach (var fit in fittings) {
146        foreach (var sort in sortings) {
147          var result = Optimize(bin, items, sort, fit, DeltaParameter.Value.Value, Problem.UseStackingConstraints, Problem.SolutionEvaluator, token);
148          if (double.IsNaN(result.Item2) || double.IsInfinity(result.Item2)) continue;
149          if (double.IsNaN(best)
150            || Problem.Maximization && result.Item2 > best
151            || !Problem.Maximization && result.Item2 < best) {
152            bestSolution = result.Item1;
153            best = result.Item2;
154            bestSorting = sort;
155            bestFitting = fit;
156          }
157          if (token.IsCancellationRequested) return Tuple.Create(bestSolution, best, bestSorting, bestFitting);
158        }
159      }
160      if (double.IsNaN(best)) return null;
161      return Tuple.Create(bestSolution, best, bestSorting, bestFitting);
162    }
163
164    private static Tuple<Solution, double> Optimize(PackingShape bin, IList<PackingItem> items, SortingMethod sorting, FittingMethod fitting, double delta, bool stackingConstraints, IEvaluator evaluator, CancellationToken token) {
165      Permutation sorted = null;
166      switch (sorting) {
167        case SortingMethod.Given:
168          sorted = new Permutation(PermutationTypes.Absolute, Enumerable.Range(0, items.Count).ToArray());
169          break;
170        case SortingMethod.VolumeHeight:
171          sorted = new Permutation(PermutationTypes.Absolute,
172                    items.Select((v, i) => new { Index = i, Item = v })
173                         .OrderByDescending(x => x.Item.Depth * x.Item.Width * x.Item.Height)
174                         .ThenByDescending(x => x.Item.Height)
175                         .Select(x => x.Index).ToArray());
176          break;
177        case SortingMethod.HeightVolume:
178          sorted = new Permutation(PermutationTypes.Absolute,
179                    items.Select((v, i) => new { Index = i, Item = v })
180                         .OrderByDescending(x => x.Item.Height)
181                         .ThenByDescending(x => x.Item.Depth * x.Item.Width * x.Item.Height)
182                         .Select(x => x.Index).ToArray());
183          break;
184        case SortingMethod.AreaHeight:
185          sorted = new Permutation(PermutationTypes.Absolute,
186                    items.Select((v, i) => new { Index = i, Item = v })
187                         .OrderByDescending(x => x.Item.Depth * x.Item.Width)
188                         .ThenByDescending(x => x.Item.Height)
189                         .Select(x => x.Index).ToArray());
190          break;
191        case SortingMethod.HeightArea:
192          sorted = new Permutation(PermutationTypes.Absolute,
193                    items.Select((v, i) => new { Index = i, Item = v })
194                         .OrderByDescending(x => x.Item.Height)
195                         .ThenByDescending(x => x.Item.Depth * x.Item.Width)
196                         .Select(x => x.Index).ToArray());
197          break;
198        case SortingMethod.ClusteredAreaHeight:
199          double clusterRange = bin.Width * bin.Depth * delta;
200          sorted = new Permutation(PermutationTypes.Absolute,
201                    items.Select((v, i) => new { Index = i, Item = v, ClusterId = (int)(Math.Ceiling(v.Width * v.Depth / clusterRange)) })
202                        .GroupBy(x => x.ClusterId)
203                        .Select(x => new { Cluster = x.Key, Items = x.OrderByDescending(y => y.Item.Height).ToList() })
204                        .OrderByDescending(x => x.Cluster)
205                        .SelectMany(x => x.Items)
206                        .Select(x => x.Index).ToArray());
207          break;
208        case SortingMethod.ClusteredHeightArea:
209          double clusterRange2 = bin.Height * delta;
210          sorted = new Permutation(PermutationTypes.Absolute,
211                    items.Select((v, i) => new { Index = i, Item = v, ClusterId = (int)(Math.Ceiling(v.Height / clusterRange2)) })
212                        .GroupBy(x => x.ClusterId)
213                        .Select(x => new { Cluster = x.Key, Items = x.OrderByDescending(y => y.Item.Depth * y.Item.Width).ToList() })
214                        .OrderByDescending(x => x.Cluster)
215                        .SelectMany(x => x.Items)
216                        .Select(x => x.Index).ToArray());
217          break;
218        default: throw new ArgumentException("Unknown sorting method: " + sorting);
219      }
220     
221      ExtremePointPermutationDecoderBase decoder = null;
222      switch (fitting) {
223        case FittingMethod.FirstFit:
224          decoder = new ExtremePointPermutationDecoder();
225          break;
226        case FittingMethod.FreeVolumeBestFit:
227          decoder = new FreeVolumeBestFitExtremePointPermutationDecoder();
228          break;
229        case FittingMethod.ResidualSpaceBestFit:
230          decoder = new ResidualSpaceBestFitExtremePointPermutationDecoder();
231          break;
232        default: throw new ArgumentException("Unknown fitting method: " + fitting);
233      }
234
235      var sol = decoder.Decode(sorted, bin, items, stackingConstraints);
236      var fit = evaluator.Evaluate(sol);
237
238      return Tuple.Create(sol, fit);
239    }
240  }
241}
Note: See TracBrowser for help on using the repository browser.