#region License Information /* HeuristicLab * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * * This file is part of HeuristicLab. * * HeuristicLab is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * HeuristicLab is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with HeuristicLab. If not, see . */ #endregion using System; using System.Collections.Generic; using System.Linq; using System.Threading; using HeuristicLab.Common; using HeuristicLab.Core; using HeuristicLab.Data; using HeuristicLab.Encodings.PermutationEncoding; using HeuristicLab.Optimization; using HeuristicLab.Parameters; using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; using HeuristicLab.Problems.BinPacking3D.Packer; using HeuristicLab.Problems.BinPacking3D.Encoding; using HeuristicLab.Problems.BinPacking3D.Sorting; using HeuristicLab.Problems.BinPacking3D.Evaluators; namespace HeuristicLab.Problems.BinPacking3D { public enum SortingMethod { All, Given, VolumeHeight, HeightVolume, AreaHeight, HeightArea, ClusteredAreaHeight, ClusteredHeightArea } public enum FittingMethod { All, FirstFit, ResidualSpaceBestFit, FreeVolumeBestFit, MinimumResidualSpaceLeft, FormClosure } public enum ExtremePointCreationMethod { All, PointProjection, LineProjection } public enum ExtremePointPruningMethod { None, All, PruneBehind } [Item("Extreme-point-based Bin 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.")] [StorableClass] [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms, Priority = 180)] public sealed class ExtremePointAlgorithm : BasicAlgorithm { public override Type ProblemType { get { return typeof(PermutationProblem); } } public new PermutationProblem Problem { get { return (PermutationProblem)base.Problem; } set { base.Problem = value; } } public override bool SupportsPause { get { return false; } } [Storable] private readonly IValueParameter> sortingMethodParameter; public IValueParameter> SortingMethodParameter { get { return sortingMethodParameter; } } [Storable] private readonly IValueParameter> fittingMethodParameter; public IValueParameter> FittingMethodParameter { get { return fittingMethodParameter; } } [Storable] private readonly IValueParameter deltaParameter; public IValueParameter DeltaParameter { get { return deltaParameter; } } [Storable] private readonly IValueParameter sortByMaterialParameter; public IValueParameter SortByMaterialParameter { get { return sortByMaterialParameter; } } [Storable] private readonly IValueParameter> extremePointCreationMethodParameter; public IValueParameter> ExtremePointCreationMethodParameter { get { return extremePointCreationMethodParameter; } } [StorableConstructor] private ExtremePointAlgorithm(bool deserializing) : base(deserializing) { } private ExtremePointAlgorithm(ExtremePointAlgorithm original, Cloner cloner) : base(original, cloner) { sortingMethodParameter = cloner.Clone(original.sortingMethodParameter); fittingMethodParameter = cloner.Clone(original.fittingMethodParameter); deltaParameter = cloner.Clone(original.deltaParameter); } public ExtremePointAlgorithm() { Parameters.Add(sortingMethodParameter = new ValueParameter>( "SortingMethod", "In which order the items should be packed.", new EnumValue(SortingMethod.All))); Parameters.Add(fittingMethodParameter = new ValueParameter>( "FittingMethod", "Which method to fit should be used.", new EnumValue(FittingMethod.All))); Parameters.Add(extremePointCreationMethodParameter = new ValueParameter>( "ExtremePointCreationMethod", "Which method should be used for creatomg extreme points.", new EnumValue(ExtremePointCreationMethod.All))); Parameters.Add(deltaParameter = new ValueParameter( "Delta", "[1;100]% Clustered sorting methods use a delta parameter to determine the clusters.", new PercentValue(.1))); Parameters.Add(sortByMaterialParameter = new ValueParameter( "SortByMaterial", "If this parameter is set, the items will be sorted by their material first", new BoolValue(true))); Problem = new PermutationProblem(); } public override IDeepCloneable Clone(Cloner cloner) { return new ExtremePointAlgorithm(this, cloner); } [StorableHook(HookType.AfterDeserialization)] private void AfterDeserialization() { } /// /// Runs the extreme point algorithm and adds the results to the property /// /// protected override void Run(CancellationToken token) { var items = Problem.Items; var bin = Problem.BinShape; var sorting = new[] { SortingMethodParameter.Value.Value }; if (sorting[0] == SortingMethod.All) { sorting = Enum.GetValues(typeof(SortingMethod)).Cast().Where(x => x != SortingMethod.All).ToArray(); } var fitting = new[] { fittingMethodParameter.Value.Value }; if (fitting[0] == FittingMethod.All) { fitting = Enum.GetValues(typeof(FittingMethod)).Cast().Where(x => x != FittingMethod.All).ToArray(); } var extremePointCreation = new[] { ExtremePointCreationMethodParameter.Value.Value }; if (extremePointCreation[0] == ExtremePointCreationMethod.All) { extremePointCreation = Enum.GetValues(typeof(ExtremePointCreationMethod)) .Cast() .Where(x => x != ExtremePointCreationMethod.All) .ToArray(); } // var result = GetBest(bin, items, sorting, fitting, extremePointCreation, token); if (result == null) { throw new InvalidOperationException("No result obtained!"); } Results.Add(new Result("Best Solution", "The best found solution", result.Item1)); Results.Add(new Result("Best Solution Quality", "The quality of the best found solution according to the evaluator", new DoubleValue(result.Item2))); var binUtil = new BinUtilizationEvaluator(); var packRatio = new PackingRatioEvaluator(); Results.Add(new Result("Best Solution Bin Count", "The number of bins in the best found solution", new IntValue(result.Item1.NrOfBins))); Results.Add(new Result("Best Solution Bin Utilization", "The utilization given in percentage as calculated by the BinUtilizationEvaluator (total used space / total available space)", new PercentValue(Math.Round(binUtil.Evaluate(result.Item1), 3)))); if (result.Item3.HasValue && sorting.Length > 1) { Results.Add(new Result("Best Sorting Method", "The sorting method that found the best solution", new EnumValue(result.Item3.Value))); } if (result.Item4.HasValue && fitting.Length > 1) { Results.Add(new Result("Best Fitting Method", "The fitting method that found the best solution", new EnumValue(result.Item4.Value))); } if (result.Item5.HasValue && extremePointCreation.Length > 1) { Results.Add(new Result("Best extreme point creation method", "The extreme point creation method that found the best solution", new EnumValue(result.Item5.Value))); } } /// /// Retunrs the best solution for the given parameters /// /// /// /// /// /// /// private Tuple GetBest(PackingShape bin, IList items, SortingMethod[] sortings, FittingMethod[] fittings, ExtremePointCreationMethod[] epCreationMethods, CancellationToken token) { SortingMethod? bestSorting = null; FittingMethod? bestFitting = null; ExtremePointCreationMethod? bestEPCreation = null; var best = double.NaN; Solution bestSolution = null; foreach (var fit in fittings) { foreach (var sort in sortings) { foreach (var epCreation in epCreationMethods) { IDecoder decoder = new ExtremePointPermutationDecoder() { FittingMethod = fit, ExtremePointCreationMethod = epCreation }; Permutation sortedItems; if (SortByMaterialParameter.Value.Value) { sortedItems = SortItemsByMaterialAndSortingMethod(bin, items, sort, DeltaParameter.Value.Value); } else { sortedItems = SortItemsBySortingMethod(bin, items, sort, DeltaParameter.Value.Value); } var solution = Optimize(new OptimaizationParamters() { SortedItems = sortedItems, Bin = bin, Items = items, StackingConstraints = Problem.UseStackingConstraints, Decoder = decoder, Evaluator = Problem.SolutionEvaluator, ExtremePointGeneration = epCreation }); if (solution.IsBetterThan(bestSolution, Problem.SolutionEvaluator, Problem.Maximization)) { bestSolution = solution; best = Problem.SolutionEvaluator.Evaluate(solution); bestSorting = sort; bestFitting = fit; bestEPCreation = epCreation; } if (token.IsCancellationRequested) { return Tuple.Create(bestSolution, best, bestSorting, bestFitting, bestEPCreation); } } } } if (double.IsNaN(best)) { return null; } return Tuple.Create(bestSolution, best, bestSorting, bestFitting, bestEPCreation); } /// /// Returns a solution depending on the given parameters /// /// /// private static Solution Optimize(OptimaizationParamters parameters) { var sol = parameters.Decoder.Decode(parameters.SortedItems, parameters.Bin, parameters.Items, parameters.StackingConstraints); return sol; } private class OptimaizationParamters { public Permutation SortedItems { get; set; } public PackingShape Bin { get; set; } public IList Items { get; set; } public bool StackingConstraints { get; set; } public IDecoder Decoder { get; set; } public IEvaluator Evaluator { get; set; } public ExtremePointCreationMethod ExtremePointGeneration { get; set; } } /// /// Returns a new permutation of the given items depending on the sorting method /// /// /// /// /// /// private Permutation SortItemsByMaterialAndSortingMethod(PackingShape bin, IList items, SortingMethod sortingMethod, double delta) { Permutation sorted = null; switch (sortingMethod) { case SortingMethod.Given: sorted = new Permutation(PermutationTypes.Absolute, Enumerable.Range(0, items.Count).ToArray()); break; case SortingMethod.VolumeHeight: sorted = items.SortByVolumeHeight(); break; case SortingMethod.HeightVolume: sorted = items.SortByMaterialHeightVolume(); break; case SortingMethod.AreaHeight: sorted = items.SortByMaterialAreaHeight(); break; case SortingMethod.HeightArea: sorted = items.SortByMaterialHeightArea(); break; case SortingMethod.ClusteredAreaHeight: sorted = items.SortByMaterialClusteredAreaHeight(bin, delta); break; case SortingMethod.ClusteredHeightArea: sorted = items.SortByMaterialClusteredHeightArea(bin, delta); break; default: throw new ArgumentException("Unknown sorting method: " + sortingMethod); } return sorted; } /// /// Returns a new permutation of the given items depending on the material and sorting method /// /// /// /// /// /// private Permutation SortItemsBySortingMethod(PackingShape bin, IList items, SortingMethod sortingMethod, double delta) { Permutation sorted = null; switch (sortingMethod) { case SortingMethod.Given: sorted = new Permutation(PermutationTypes.Absolute, Enumerable.Range(0, items.Count).ToArray()); break; case SortingMethod.VolumeHeight: sorted = items.SortByVolumeHeight(); break; case SortingMethod.HeightVolume: sorted = items.SortByHeightVolume(); break; case SortingMethod.AreaHeight: sorted = items.SortByAreaHeight(); break; case SortingMethod.HeightArea: sorted = items.SortByHeightArea(); break; case SortingMethod.ClusteredAreaHeight: sorted = items.SortByClusteredAreaHeight(bin, delta); break; case SortingMethod.ClusteredHeightArea: sorted = items.SortByClusteredHeightArea(bin, delta); break; default: throw new ArgumentException("Unknown sorting method: " + sortingMethod); } return sorted; } } }