1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022018 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 


22  using System;


23  using System.Collections.Generic;


24  using System.Linq;


25  using System.Threading;


26 


27  using HeuristicLab.Common;


28  using HeuristicLab.Core;


29  using HeuristicLab.Data;


30  using HeuristicLab.Encodings.PermutationEncoding;


31  using HeuristicLab.Optimization;


32  using HeuristicLab.Parameters;


33  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


34  using HeuristicLab.Problems.BinPacking3D.Packer;


35  using HeuristicLab.Problems.BinPacking3D.Encoding;


36  using HeuristicLab.Problems.BinPacking3D.Sorting;


37  using HeuristicLab.Problems.BinPacking3D.Evaluators;


38 


39  namespace 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("Extremepointbased Bin Packing (3d)", "An implementation of the extremepoint based packing described in Crainic, T. G., Perboli, G., & Tadei, R. (2008). Extreme pointbased heuristics for threedimensional bin packing. Informs Journal on computing, 20(3), 368384.")]


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 result = 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 (double.IsNaN(result.Item2)  double.IsInfinity(result.Item2)) {


242  continue;


243  }


244 


245  if (double.IsNaN(best)  Problem.Maximization && result.Item2 > best  !Problem.Maximization && result.Item2 < best) {


246  bestSolution = result.Item1;


247  best = result.Item2;


248  bestSorting = sort;


249  bestFitting = fit;


250  bestEPCreation = epCreation;


251  }


252  if (token.IsCancellationRequested) {


253  return Tuple.Create(bestSolution, best, bestSorting, bestFitting, bestEPCreation);


254  }


255  }


256  }


257  }


258  if (double.IsNaN(best)) {


259  return null;


260  }


261  return Tuple.Create(bestSolution, best, bestSorting, bestFitting, bestEPCreation);


262  }


263 


264  /// <summary>


265  /// Returns a tuple with the solution and the packing ratio depending on the given parameters


266  /// </summary>


267  /// <param name="parameters"></param>


268  /// <returns></returns>


269  private static Tuple<Solution, double> Optimize(OptimaizationParamters parameters) {


270 


271  var sol = parameters.Decoder.Decode(parameters.SortedItems, parameters.Bin, parameters.Items, parameters.StackingConstraints);


272  var fit = parameters.Evaluator.Evaluate(sol);


273 


274  return Tuple.Create(sol, fit);


275  }


276 


277  private class OptimaizationParamters {


278  public Permutation SortedItems { get; set; }


279  public PackingShape Bin { get; set; }


280  public IList<PackingItem> Items { get; set; }


281  public bool StackingConstraints { get; set; }


282  public IDecoder<Permutation> Decoder { get; set; }


283  public IEvaluator Evaluator { get; set; }


284  public ExtremePointCreationMethod ExtremePointGeneration { get; set; }


285  }


286 


287 


288  /// <summary>


289  /// Returns a new permutation of the given items depending on the sorting method


290  /// </summary>


291  /// <param name="bin"></param>


292  /// <param name="items"></param>


293  /// <param name="sortingMethod"></param>


294  /// <param name="delta"></param>


295  /// <returns></returns>


296  private Permutation SortItemsBySortingMethod(PackingShape bin, IList<PackingItem> items, SortingMethod sortingMethod, double delta) {


297  Permutation sorted = null;


298 


299  switch (sortingMethod) {


300  case SortingMethod.Given:


301  sorted = new Permutation(PermutationTypes.Absolute, Enumerable.Range(0, items.Count).ToArray());


302  break;


303  case SortingMethod.VolumeHeight:


304  sorted = items.SortByVolumeHeight();


305  break;


306  case SortingMethod.HeightVolume:


307  sorted = items.SortByMaterialHeightVolume();


308  break;


309  case SortingMethod.AreaHeight:


310  sorted = items.SortByMaterialAreaHeight();


311  break;


312  case SortingMethod.HeightArea:


313  sorted = items.SortByMaterialHeightArea();


314  break;


315  case SortingMethod.ClusteredAreaHeight:


316  sorted = items.SortByMaterialClusteredAreaHeight(bin, delta);


317  break;


318  case SortingMethod.ClusteredHeightArea:


319  sorted = items.SortByMaterialClusteredHeightArea(bin, delta);


320  break;


321  default:


322  throw new ArgumentException("Unknown sorting method: " + sortingMethod);


323  }


324  return sorted;


325  }


326 


327  /// <summary>


328  /// Returns a new permutation of the given items depending on the material and sorting method


329  /// </summary>


330  /// <param name="bin"></param>


331  /// <param name="items"></param>


332  /// <param name="sortingMethod"></param>


333  /// <param name="delta"></param>


334  /// <returns></returns>


335  private Permutation SortItemsByMaterialAndSortingMethod(PackingShape bin, IList<PackingItem> items, SortingMethod sortingMethod, double delta) {


336  Permutation sorted = null;


337 


338  switch (sortingMethod) {


339  case SortingMethod.Given:


340  sorted = new Permutation(PermutationTypes.Absolute, Enumerable.Range(0, items.Count).ToArray());


341  break;


342  case SortingMethod.VolumeHeight:


343  sorted = items.SortByVolumeHeight();


344  break;


345  case SortingMethod.HeightVolume:


346  sorted = items.SortByHeightVolume();


347  break;


348  case SortingMethod.AreaHeight:


349  sorted = items.SortByAreaHeight();


350  break;


351  case SortingMethod.HeightArea:


352  sorted = items.SortByHeightArea();


353  break;


354  case SortingMethod.ClusteredAreaHeight:


355  sorted = items.SortByClusteredAreaHeight(bin, delta);


356  break;


357  case SortingMethod.ClusteredHeightArea:


358  sorted = items.SortByClusteredHeightArea(bin, delta);


359  break;


360  default:


361  throw new ArgumentException("Unknown sorting method: " + sortingMethod);


362  }


363  return sorted;


364  }


365  }


366  }

