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> sortBySequenceGroupParameter;


86 


87  public IValueParameter<BoolValue> SortBySequenceGroupParameter {


88  get { return sortBySequenceGroupParameter; }


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(sortBySequenceGroupParameter = new ValueParameter<BoolValue>(


119  "SortBySequenceGroup", "If this parameter is set, the items will be sorted by their sequence group 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 


212  SortingMethod? bestSorting = null;


213  FittingMethod? bestFitting = null;


214  ExtremePointCreationMethod? bestEPCreation = null;


215  var best = double.NaN;


216  Solution bestSolution = null;


217  foreach (var fit in fittings) {


218  foreach (var sort in sortings) {


219  foreach (var epCreation in epCreationMethods) {


220  IDecoder<Permutation> decoder = new ExtremePointPermutationDecoder() {


221  FittingMethod = fit,


222  ExtremePointCreationMethod = epCreation


223  };


224  Permutation sortedItems;


225 


226  sortedItems = SortItems(bin, items, sort, DeltaParameter.Value.Value, SortBySequenceGroupParameter.Value.Value);


227 


228  var solution = Optimize(new OptimaizationParamters() {


229  SortedItems = sortedItems,


230  Bin = bin,


231  Items = items,


232  StackingConstraints = Problem.UseStackingConstraints,


233  Decoder = decoder,


234  Evaluator = Problem.SolutionEvaluator,


235  ExtremePointGeneration = epCreation


236  });


237 


238  if (solution.IsBetterThan(bestSolution, Problem.SolutionEvaluator, Problem.Maximization)) {


239  bestSolution = solution;


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


241  bestSorting = sort;


242  bestFitting = fit;


243  bestEPCreation = epCreation;


244  }


245 


246  if (token.IsCancellationRequested) {


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


248  }


249  }


250  }


251  }


252  if (double.IsNaN(best)) {


253  return null;


254  }


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


256  }


257 


258  /// <summary>


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


260  /// </summary>


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


262  /// <returns></returns>


263  private static Solution Optimize(OptimaizationParamters parameters) {


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


265 


266  return sol;


267  }


268 


269  private class OptimaizationParamters {


270  public Permutation SortedItems { get; set; }


271  public PackingShape Bin { get; set; }


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


273  public bool StackingConstraints { get; set; }


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


275  public IEvaluator Evaluator { get; set; }


276  public ExtremePointCreationMethod ExtremePointGeneration { get; set; }


277  }


278 


279 


280  private Permutation SortItems(PackingShape bin, IList<PackingItem> items, SortingMethod sortingMethod, double delta, bool sortBySequenceGroup) {


281  Permutation sortedItems;


282 


283  var sorter = PackingItemSorterFactory.CreatePackingItemSorter(sortingMethod);


284  if (sorter is IPackingItemClusteredSorter) {


285  if (sortBySequenceGroup) {


286  sortedItems = (sorter as IPackingItemClusteredSorter).SortPackingItemsBySequenceGroup(items, bin, delta);


287  } else {


288  sortedItems = (sorter as IPackingItemClusteredSorter).SortPackingItems(items, bin, delta);


289  }


290  } else {


291  if (sortBySequenceGroup) {


292  sortedItems = sorter.SortPackingItemsBySequenceGroup(items, bin);


293  } else {


294  sortedItems = sorter.SortPackingItems(items, bin);


295  }


296  }


297  return sortedItems;


298  }


299  }


300  }

