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, WidthBestFit }


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 solution = 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 (solution.IsBetterThan(bestSolution, Problem.SolutionEvaluator, Problem.Maximization)) {


242  bestSolution = solution;


243  best = Problem.SolutionEvaluator.Evaluate(solution);


244  bestSorting = sort;


245  bestFitting = fit;


246  bestEPCreation = epCreation;


247  }


248 


249  if (token.IsCancellationRequested) {


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


251  }


252  }


253  }


254  }


255  if (double.IsNaN(best)) {


256  return null;


257  }


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


259  }


260 


261  /// <summary>


262  /// Returns a solution depending on the given parameters


263  /// </summary>


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


265  /// <returns></returns>


266  private static Solution Optimize(OptimaizationParamters parameters) {


267 


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


269 


270  return sol;


271  }


272 


273  private class OptimaizationParamters {


274  public Permutation SortedItems { get; set; }


275  public PackingShape Bin { get; set; }


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


277  public bool StackingConstraints { get; set; }


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


279  public IEvaluator Evaluator { get; set; }


280  public ExtremePointCreationMethod ExtremePointGeneration { get; set; }


281  }


282 


283  /// <summary>


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


285  /// </summary>


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


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


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


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


290  /// <returns></returns>


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


292  Permutation sorted = null;


293 


294  switch (sortingMethod) {


295  case SortingMethod.Given:


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


297  break;


298  case SortingMethod.VolumeHeight:


299  sorted = items.SortByVolumeHeight();


300  break;


301  case SortingMethod.HeightVolume:


302  sorted = items.SortByMaterialHeightVolume();


303  break;


304  case SortingMethod.AreaHeight:


305  sorted = items.SortByMaterialAreaHeight();


306  break;


307  case SortingMethod.HeightArea:


308  sorted = items.SortByMaterialHeightArea();


309  break;


310  case SortingMethod.ClusteredAreaHeight:


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


312  break;


313  case SortingMethod.ClusteredHeightArea:


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


315  break;


316  default:


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


318  }


319  return sorted;


320  }


321 


322  /// <summary>


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


324  /// </summary>


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


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


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


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


329  /// <returns></returns>


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


331  Permutation sorted = null;


332 


333  switch (sortingMethod) {


334  case SortingMethod.Given:


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


336  break;


337  case SortingMethod.VolumeHeight:


338  sorted = items.SortByVolumeHeight();


339  break;


340  case SortingMethod.HeightVolume:


341  sorted = items.SortByHeightVolume();


342  break;


343  case SortingMethod.AreaHeight:


344  sorted = items.SortByAreaHeight();


345  break;


346  case SortingMethod.HeightArea:


347  sorted = items.SortByHeightArea();


348  break;


349  case SortingMethod.ClusteredAreaHeight:


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


351  break;


352  case SortingMethod.ClusteredHeightArea:


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


354  break;


355  default:


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


357  }


358  return sorted;


359  }


360  }


361  }

