[15473] | 1 | #region License Information
|
---|
| 2 | /* HeuristicLab
|
---|
[15617] | 3 | * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
|
---|
[15473] | 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 }
|
---|
[15731] | 42 | public enum FittingMethod { All, FirstFit, ResidualSpaceBestFit, FreeVolumeBestFit, MinimumResidualSpaceLeft, FormClosure }
|
---|
[15473] | 43 |
|
---|
[15488] | 44 | public enum ExtremePointCreationMethod { All, PointProjection, LineProjection }
|
---|
| 45 |
|
---|
[15617] | 46 | public enum ExtremePointPruningMethod { None, All, PruneBehind }
|
---|
| 47 |
|
---|
[15473] | 48 | [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.")]
|
---|
| 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; }
|
---|
[15488] | 89 | }
|
---|
[15473] | 90 |
|
---|
[15488] | 91 | [Storable]
|
---|
| 92 | private readonly IValueParameter<EnumValue<ExtremePointCreationMethod>> extremePointCreationMethodParameter;
|
---|
| 93 | public IValueParameter<EnumValue<ExtremePointCreationMethod>> ExtremePointCreationMethodParameter {
|
---|
| 94 | get { return extremePointCreationMethodParameter; }
|
---|
| 95 | }
|
---|
| 96 |
|
---|
[15473] | 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 |
|
---|
[15488] | 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 |
|
---|
[15473] | 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;
|
---|
[15488] | 139 |
|
---|
[15473] | 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 | }
|
---|
[15488] | 144 |
|
---|
[15473] | 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 |
|
---|
[15488] | 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 |
|
---|
[15473] | 158 | //
|
---|
[15488] | 159 | var result = GetBest(bin, items, sorting, fitting, extremePointCreation, token);
|
---|
[15473] | 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 | }
|
---|
[15488] | 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 | }
|
---|
[15473] | 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>
|
---|
[15646] | 204 | private Tuple<Solution, double, SortingMethod?, FittingMethod?, ExtremePointCreationMethod?>
|
---|
| 205 | GetBest(PackingShape bin,
|
---|
| 206 | IList<PackingItem> items,
|
---|
| 207 | SortingMethod[] sortings,
|
---|
[15488] | 208 | FittingMethod[] fittings,
|
---|
[15585] | 209 | ExtremePointCreationMethod[] epCreationMethods,
|
---|
[15488] | 210 | CancellationToken token) {
|
---|
[15473] | 211 | SortingMethod? bestSorting = null;
|
---|
| 212 | FittingMethod? bestFitting = null;
|
---|
[15488] | 213 | ExtremePointCreationMethod? bestEPCreation = null;
|
---|
[15473] | 214 | var best = double.NaN;
|
---|
| 215 | Solution bestSolution = null;
|
---|
| 216 | foreach (var fit in fittings) {
|
---|
| 217 | foreach (var sort in sortings) {
|
---|
[15585] | 218 | foreach (var epCreation in epCreationMethods) {
|
---|
[15488] | 219 | IDecoder<Permutation> decoder = new ExtremePointPermutationDecoder() {
|
---|
| 220 | FittingMethod = fit,
|
---|
| 221 | ExtremePointCreationMethod = epCreation
|
---|
| 222 | };
|
---|
| 223 | Permutation sortedItems;
|
---|
[15646] | 224 |
|
---|
[15488] | 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 |
|
---|
[15646] | 231 | var solution = Optimize(new OptimaizationParamters() {
|
---|
[15488] | 232 | SortedItems = sortedItems,
|
---|
| 233 | Bin = bin,
|
---|
| 234 | Items = items,
|
---|
| 235 | StackingConstraints = Problem.UseStackingConstraints,
|
---|
| 236 | Decoder = decoder,
|
---|
| 237 | Evaluator = Problem.SolutionEvaluator,
|
---|
| 238 | ExtremePointGeneration = epCreation
|
---|
| 239 | });
|
---|
[15646] | 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 |
|
---|
[15488] | 249 | if (token.IsCancellationRequested) {
|
---|
| 250 | return Tuple.Create(bestSolution, best, bestSorting, bestFitting, bestEPCreation);
|
---|
| 251 | }
|
---|
[15473] | 252 | }
|
---|
| 253 | }
|
---|
| 254 | }
|
---|
| 255 | if (double.IsNaN(best)) {
|
---|
| 256 | return null;
|
---|
| 257 | }
|
---|
[15488] | 258 | return Tuple.Create(bestSolution, best, bestSorting, bestFitting, bestEPCreation);
|
---|
[15473] | 259 | }
|
---|
| 260 |
|
---|
| 261 | /// <summary>
|
---|
[15838] | 262 | /// Returns a solution depending on the given parameters
|
---|
[15473] | 263 | /// </summary>
|
---|
[15488] | 264 | /// <param name="parameters"></param>
|
---|
[15473] | 265 | /// <returns></returns>
|
---|
[15646] | 266 | private static Solution Optimize(OptimaizationParamters parameters) {
|
---|
| 267 |
|
---|
[15488] | 268 | var sol = parameters.Decoder.Decode(parameters.SortedItems, parameters.Bin, parameters.Items, parameters.StackingConstraints);
|
---|
[15473] | 269 |
|
---|
[15838] | 270 | return sol;
|
---|
[15473] | 271 | }
|
---|
[15488] | 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 | }
|
---|
[15838] | 282 |
|
---|
[15473] | 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>
|
---|
[15646] | 291 | private Permutation SortItemsByMaterialAndSortingMethod(PackingShape bin, IList<PackingItem> items, SortingMethod sortingMethod, double delta) {
|
---|
[15473] | 292 | Permutation sorted = null;
|
---|
[15646] | 293 |
|
---|
[15473] | 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>
|
---|
[15646] | 330 | private Permutation SortItemsBySortingMethod(PackingShape bin, IList<PackingItem> items, SortingMethod sortingMethod, double delta) {
|
---|
[15473] | 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 | }
|
---|