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

Last change on this file since 15174 was 15174, checked in by abeham, 3 months ago

#2762:

  • Added ExtremePointAlgorithm in form of a BasicAlgorithm
  • Removed implementation in view and put sorting/fit into the algorithm
File size: 11.3 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 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.Algorithms)]
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 BinCount", new IntValue(result.Item1.NrOfBins)));
120      Results.Add(new Result("Best Solution Bin Utilization", new PercentValue(Math.Round(binUtil.Evaluate(result.Item1), 2))));
121      Results.Add(new Result("Best Solution Packing Ratio", new PercentValue(Math.Round(packRatio.Evaluate(result.Item1), 2))));
122
123      if (result.Item3.HasValue && sorting.Length > 1)
124        Results.Add(new Result("Best Sorting Method", new EnumValue<SortingMethod>(result.Item3.Value)));
125      if (result.Item4.HasValue && fitting.Length > 1)
126        Results.Add(new Result("Best Fitting Method", new EnumValue<FittingMethod>(result.Item4.Value)));
127    }
128
129    private Tuple<Solution, double, SortingMethod?, FittingMethod?> GetBest(PackingShape bin, IList<PackingItem> items, SortingMethod[] sortings, FittingMethod[] fittings, CancellationToken token) {
130      SortingMethod? bestSorting = null;
131      FittingMethod? bestFitting = null;
132      var best = double.NaN;
133      Solution bestSolution = null;
134      foreach (var fit in fittings) {
135        foreach (var sort in sortings) {
136          var result = Optimize(bin, items, sort, fit, DeltaParameter.Value.Value, Problem.UseStackingConstraints, Problem.SolutionEvaluator, token);
137          if (double.IsNaN(result.Item2) || double.IsInfinity(result.Item2)) continue;
138          if (double.IsNaN(best)
139            || Problem.Maximization && result.Item2 > best
140            || !Problem.Maximization && result.Item2 < best) {
141            bestSolution = result.Item1;
142            best = result.Item2;
143            bestSorting = sort;
144            bestFitting = fit;
145          }
146          if (token.IsCancellationRequested) return Tuple.Create(bestSolution, best, bestSorting, bestFitting);
147        }
148      }
149      if (double.IsNaN(best)) return null;
150      return Tuple.Create(bestSolution, best, bestSorting, bestFitting);
151    }
152
153    private static Tuple<Solution, double> Optimize(PackingShape bin, IList<PackingItem> items, SortingMethod sorting, FittingMethod fitting, double delta, bool stackingConstraints, IEvaluator evaluator, CancellationToken token) {
154      Permutation sorted = null;
155      switch (sorting) {
156        case SortingMethod.Given:
157          sorted = new Permutation(PermutationTypes.Absolute, Enumerable.Range(0, items.Count).ToArray());
158          break;
159        case SortingMethod.VolumeHeight:
160          sorted = new Permutation(PermutationTypes.Absolute,
161                    items.Select((v, i) => new { Index = i, Item = v })
162                         .OrderByDescending(x => x.Item.Depth * x.Item.Width * x.Item.Height)
163                         .ThenByDescending(x => x.Item.Height)
164                         .Select(x => x.Index).ToArray());
165          break;
166        case SortingMethod.HeightVolume:
167          sorted = new Permutation(PermutationTypes.Absolute,
168                    items.Select((v, i) => new { Index = i, Item = v })
169                         .OrderByDescending(x => x.Item.Height)
170                         .ThenByDescending(x => x.Item.Depth * x.Item.Width * x.Item.Height)
171                         .Select(x => x.Index).ToArray());
172          break;
173        case SortingMethod.AreaHeight:
174          sorted = new Permutation(PermutationTypes.Absolute,
175                    items.Select((v, i) => new { Index = i, Item = v })
176                         .OrderByDescending(x => x.Item.Depth * x.Item.Width)
177                         .ThenByDescending(x => x.Item.Height)
178                         .Select(x => x.Index).ToArray());
179          break;
180        case SortingMethod.HeightArea:
181          sorted = new Permutation(PermutationTypes.Absolute,
182                    items.Select((v, i) => new { Index = i, Item = v })
183                         .OrderByDescending(x => x.Item.Height)
184                         .ThenByDescending(x => x.Item.Depth * x.Item.Width)
185                         .Select(x => x.Index).ToArray());
186          break;
187        case SortingMethod.ClusteredAreaHeight:
188          double clusterRange = bin.Width * bin.Depth * delta;
189          sorted = new Permutation(PermutationTypes.Absolute,
190                    items.Select((v, i) => new { Index = i, Item = v, ClusterId = (int)(Math.Ceiling(v.Width * v.Depth / clusterRange)) })
191                        .GroupBy(x => x.ClusterId)
192                        .Select(x => new { Cluster = x.Key, Items = x.OrderByDescending(y => y.Item.Height).ToList() })
193                        .OrderByDescending(x => x.Cluster)
194                        .SelectMany(x => x.Items)
195                        .Select(x => x.Index).ToArray());
196          break;
197        case SortingMethod.ClusteredHeightArea:
198          double clusterRange2 = bin.Height * delta;
199          sorted = new Permutation(PermutationTypes.Absolute,
200                    items.Select((v, i) => new { Index = i, Item = v, ClusterId = (int)(Math.Ceiling(v.Height / clusterRange2)) })
201                        .GroupBy(x => x.ClusterId)
202                        .Select(x => new { Cluster = x.Key, Items = x.OrderByDescending(y => y.Item.Depth * y.Item.Width).ToList() })
203                        .OrderByDescending(x => x.Cluster)
204                        .SelectMany(x => x.Items)
205                        .Select(x => x.Index).ToArray());
206          break;
207        default: throw new ArgumentException("Unknown sorting method: " + sorting);
208      }
209     
210      ExtremePointPermutationDecoderBase decoder = null;
211      switch (fitting) {
212        case FittingMethod.FirstFit:
213          decoder = new ExtremePointPermutationDecoder();
214          break;
215        case FittingMethod.FreeVolumeBestFit:
216          decoder = new FreeVolumeBestFitExtremePointPermutationDecoder();
217          break;
218        case FittingMethod.ResidualSpaceBestFit:
219          decoder = new ResidualSpaceBestFitExtremePointPermutationDecoder();
220          break;
221        default: throw new ArgumentException("Unknown fitting method: " + fitting);
222      }
223
224      var sol = decoder.Decode(sorted, bin, items, stackingConstraints);
225      var fit = evaluator.Evaluate(sol);
226
227      return Tuple.Create(sol, fit);
228    }
229  }
230}
Note: See TracBrowser for help on using the repository browser.