Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/HeuristicLab.Problems.BinPacking/3.3/Algorithms/3D/ExtremePointAlgorithm.cs

Last change on this file was 17180, checked in by swagner, 5 years ago

#2875: Removed years in copyrights

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