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


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 


250  var x = Problem.SolutionEvaluator.Evaluate1(solution);


251 


252  /*


253  if (double.IsNaN(result.Item2)  double.IsInfinity(result.Item2)) {


254  continue;


255  }


256 


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


258  bestSolution = result.Item1;


259  best = result.Item2;


260  bestSorting = sort;


261  bestFitting = fit;


262  bestEPCreation = epCreation;


263  }


264  return true;*/


265 


266  if (token.IsCancellationRequested) {


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


268  }


269  }


270  }


271  }


272  if (double.IsNaN(best)) {


273  return null;


274  }


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


276  }


277 


278  /// <summary>


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


280  /// </summary>


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


282  /// <returns></returns>


283  private static Solution Optimize(OptimaizationParamters parameters) {


284 


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


286  //var fit = parameters.Evaluator.Evaluate(sol);


287 


288  return sol; //Tuple.Create(sol, fit);


289  }


290 


291  private class OptimaizationParamters {


292  public Permutation SortedItems { get; set; }


293  public PackingShape Bin { get; set; }


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


295  public bool StackingConstraints { get; set; }


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


297  public IEvaluator Evaluator { get; set; }


298  public ExtremePointCreationMethod ExtremePointGeneration { get; set; }


299  }


300 


301 


302  /// <summary>


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


304  /// </summary>


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


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


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


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


309  /// <returns></returns>


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


311  Permutation sorted = null;


312 


313  switch (sortingMethod) {


314  case SortingMethod.Given:


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


316  break;


317  case SortingMethod.VolumeHeight:


318  sorted = items.SortByVolumeHeight();


319  break;


320  case SortingMethod.HeightVolume:


321  sorted = items.SortByMaterialHeightVolume();


322  break;


323  case SortingMethod.AreaHeight:


324  sorted = items.SortByMaterialAreaHeight();


325  break;


326  case SortingMethod.HeightArea:


327  sorted = items.SortByMaterialHeightArea();


328  break;


329  case SortingMethod.ClusteredAreaHeight:


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


331  break;


332  case SortingMethod.ClusteredHeightArea:


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


334  break;


335  default:


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


337  }


338  return sorted;


339  }


340 


341  /// <summary>


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


343  /// </summary>


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


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


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


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


348  /// <returns></returns>


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


350  Permutation sorted = null;


351 


352  switch (sortingMethod) {


353  case SortingMethod.Given:


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


355  break;


356  case SortingMethod.VolumeHeight:


357  sorted = items.SortByVolumeHeight();


358  break;


359  case SortingMethod.HeightVolume:


360  sorted = items.SortByHeightVolume();


361  break;


362  case SortingMethod.AreaHeight:


363  sorted = items.SortByAreaHeight();


364  break;


365  case SortingMethod.HeightArea:


366  sorted = items.SortByHeightArea();


367  break;


368  case SortingMethod.ClusteredAreaHeight:


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


370  break;


371  case SortingMethod.ClusteredHeightArea:


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


373  break;


374  default:


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


376  }


377  return sorted;


378  }


379  }


380  }

