Free cookie consent management tool by TermsFeed Policy Generator

source: branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/Algorithms/3D/ExtremePointAlgorithm.cs @ 15200

Last change on this file since 15200 was 15200, checked in by abeham, 7 years ago

#2762: small changes to the results output

File size: 11.2 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2016 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 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 IValueParameter<EnumValue<SortingMethod>> sortingMethodParameter;
60    public IValueParameter<EnumValue<SortingMethod>> SortingMethodParameter {
61      get { return sortingMethodParameter; }
62    }
63
64    [Storable]
65    private IValueParameter<EnumValue<FittingMethod>> fittingMethodParameter;
66    public IValueParameter<EnumValue<FittingMethod>> FittingMethodParameter {
67      get { return fittingMethodParameter; }
68    }
69
70    [Storable]
71    private IValueParameter<PercentValue> deltaParameter;
72    public IValueParameter<PercentValue> DeltaParameter {
73      get { return deltaParameter; }
74    }
75
76    [StorableConstructor]
77    protected ExtremePointAlgorithm(bool deserializing) : base(deserializing) { }
78    protected 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", result.Item1));
115      Results.Add(new Result("Best Solution Quality", new DoubleValue(result.Item2)));
116
117      var binUtil = new BinUtilizationEvaluator();
118      var packRatio = new PackingRatioEvaluator();
119      Results.Add(new Result("Best Solution Bin Count", new IntValue(result.Item1.NrOfBins)));
120      Results.Add(new Result("Best Solution Bin Utilization", new PercentValue(Math.Round(binUtil.Evaluate(result.Item1), 3))));
121
122      if (result.Item3.HasValue && sorting.Length > 1)
123        Results.Add(new Result("Best Sorting Method", new EnumValue<SortingMethod>(result.Item3.Value)));
124      if (result.Item4.HasValue && fitting.Length > 1)
125        Results.Add(new Result("Best Fitting Method", new EnumValue<FittingMethod>(result.Item4.Value)));
126    }
127
128    private Tuple<Solution, double, SortingMethod?, FittingMethod?> GetBest(PackingShape bin, IList<PackingItem> items, SortingMethod[] sortings, FittingMethod[] fittings, CancellationToken token) {
129      SortingMethod? bestSorting = null;
130      FittingMethod? bestFitting = null;
131      var best = double.NaN;
132      Solution bestSolution = null;
133      foreach (var fit in fittings) {
134        foreach (var sort in sortings) {
135          var result = Optimize(bin, items, sort, fit, DeltaParameter.Value.Value, Problem.UseStackingConstraints, Problem.SolutionEvaluator, token);
136          if (double.IsNaN(result.Item2) || double.IsInfinity(result.Item2)) continue;
137          if (double.IsNaN(best)
138            || Problem.Maximization && result.Item2 > best
139            || !Problem.Maximization && result.Item2 < best) {
140            bestSolution = result.Item1;
141            best = result.Item2;
142            bestSorting = sort;
143            bestFitting = fit;
144          }
145          if (token.IsCancellationRequested) return Tuple.Create(bestSolution, best, bestSorting, bestFitting);
146        }
147      }
148      if (double.IsNaN(best)) return null;
149      return Tuple.Create(bestSolution, best, bestSorting, bestFitting);
150    }
151
152    private static Tuple<Solution, double> Optimize(PackingShape bin, IList<PackingItem> items, SortingMethod sorting, FittingMethod fitting, double delta, bool stackingConstraints, IEvaluator evaluator, CancellationToken token) {
153      Permutation sorted = null;
154      switch (sorting) {
155        case SortingMethod.Given:
156          sorted = new Permutation(PermutationTypes.Absolute, Enumerable.Range(0, items.Count).ToArray());
157          break;
158        case SortingMethod.VolumeHeight:
159          sorted = new Permutation(PermutationTypes.Absolute,
160                    items.Select((v, i) => new { Index = i, Item = v })
161                         .OrderByDescending(x => x.Item.Depth * x.Item.Width * x.Item.Height)
162                         .ThenByDescending(x => x.Item.Height)
163                         .Select(x => x.Index).ToArray());
164          break;
165        case SortingMethod.HeightVolume:
166          sorted = new Permutation(PermutationTypes.Absolute,
167                    items.Select((v, i) => new { Index = i, Item = v })
168                         .OrderByDescending(x => x.Item.Height)
169                         .ThenByDescending(x => x.Item.Depth * x.Item.Width * x.Item.Height)
170                         .Select(x => x.Index).ToArray());
171          break;
172        case SortingMethod.AreaHeight:
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)
176                         .ThenByDescending(x => x.Item.Height)
177                         .Select(x => x.Index).ToArray());
178          break;
179        case SortingMethod.HeightArea:
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)
184                         .Select(x => x.Index).ToArray());
185          break;
186        case SortingMethod.ClusteredAreaHeight:
187          double clusterRange = bin.Width * bin.Depth * delta;
188          sorted = new Permutation(PermutationTypes.Absolute,
189                    items.Select((v, i) => new { Index = i, Item = v, ClusterId = (int)(Math.Ceiling(v.Width * v.Depth / clusterRange)) })
190                        .GroupBy(x => x.ClusterId)
191                        .Select(x => new { Cluster = x.Key, Items = x.OrderByDescending(y => y.Item.Height).ToList() })
192                        .OrderByDescending(x => x.Cluster)
193                        .SelectMany(x => x.Items)
194                        .Select(x => x.Index).ToArray());
195          break;
196        case SortingMethod.ClusteredHeightArea:
197          double clusterRange2 = bin.Height * delta;
198          sorted = new Permutation(PermutationTypes.Absolute,
199                    items.Select((v, i) => new { Index = i, Item = v, ClusterId = (int)(Math.Ceiling(v.Height / clusterRange2)) })
200                        .GroupBy(x => x.ClusterId)
201                        .Select(x => new { Cluster = x.Key, Items = x.OrderByDescending(y => y.Item.Depth * y.Item.Width).ToList() })
202                        .OrderByDescending(x => x.Cluster)
203                        .SelectMany(x => x.Items)
204                        .Select(x => x.Index).ToArray());
205          break;
206        default: throw new ArgumentException("Unknown sorting method: " + sorting);
207      }
208     
209      ExtremePointPermutationDecoderBase decoder = null;
210      switch (fitting) {
211        case FittingMethod.FirstFit:
212          decoder = new ExtremePointPermutationDecoder();
213          break;
214        case FittingMethod.FreeVolumeBestFit:
215          decoder = new FreeVolumeBestFitExtremePointPermutationDecoder();
216          break;
217        case FittingMethod.ResidualSpaceBestFit:
218          decoder = new ResidualSpaceBestFitExtremePointPermutationDecoder();
219          break;
220        default: throw new ArgumentException("Unknown fitting method: " + fitting);
221      }
222
223      var sol = decoder.Decode(sorted, bin, items, stackingConstraints);
224      var fit = evaluator.Evaluate(sol);
225
226      return Tuple.Create(sol, fit);
227    }
228  }
229}
Note: See TracBrowser for help on using the repository browser.