[15618] | 1 | #region License Information
|
---|
| 2 | /* HeuristicLab
|
---|
| 3 | * Copyright (C) 2002-2018 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.Text;
|
---|
| 26 | using System.Threading.Tasks;
|
---|
| 27 | using HeuristicLab.Common;
|
---|
| 28 | using HeuristicLab.Encodings.PermutationEncoding;
|
---|
| 29 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
| 30 | using HeuristicLab.Problems.BinPacking3D.ExtremePointCreation;
|
---|
| 31 | using HeuristicLab.Problems.BinPacking3D.ExtremePointPruning;
|
---|
| 32 |
|
---|
| 33 | namespace HeuristicLab.Problems.BinPacking3D.Packer {
|
---|
| 34 | internal class BinPackerMinRSLeft : BinPacker {
|
---|
| 35 | #region Constructors for HEAL
|
---|
| 36 | [StorableConstructor]
|
---|
| 37 | protected BinPackerMinRSLeft(bool deserializing) : base(deserializing) { }
|
---|
| 38 |
|
---|
| 39 | public BinPackerMinRSLeft(BinPackerMinRSLeft original, Cloner cloner) : base(original, cloner) {
|
---|
| 40 | }
|
---|
| 41 |
|
---|
| 42 | public override IDeepCloneable Clone(Cloner cloner) {
|
---|
| 43 | return new BinPackerMinRSLeft(this, cloner);
|
---|
| 44 | }
|
---|
| 45 | #endregion
|
---|
| 46 |
|
---|
| 47 | public BinPackerMinRSLeft() : base() { }
|
---|
| 48 |
|
---|
| 49 |
|
---|
| 50 | public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, ExtremePointPruningMethod epPruningMethod, bool useStackingConstraints) {
|
---|
| 51 | var workingItems = CloneItems(items);
|
---|
| 52 | IList<BinPacking3D> packingList = new List<BinPacking3D>();
|
---|
| 53 | IList<int> remainingIds = new List<int>(sortedItems);
|
---|
| 54 |
|
---|
| 55 | try {
|
---|
| 56 | while (remainingIds.Count > 0) {
|
---|
| 57 | BinPacking3D packingBin = new BinPacking3D(binShape);
|
---|
| 58 | PackRemainingItems(ref remainingIds, ref packingBin, workingItems, epCreationMethod, useStackingConstraints);
|
---|
| 59 | packingList.Add(packingBin);
|
---|
| 60 | }
|
---|
| 61 | } catch(BinPacking3DException e) {
|
---|
| 62 | }
|
---|
| 63 |
|
---|
| 64 | ExtremePointPruningFactory.CreatePruning().PruneExtremePoints(epPruningMethod, packingList);
|
---|
| 65 | return packingList;
|
---|
| 66 | }
|
---|
| 67 |
|
---|
| 68 | /// <summary>
|
---|
| 69 | /// Tries to pack the remainig items into a given BinPacking3D object. Each item could be packed into the BinPacking3D object will be removed from the list of remaining ids
|
---|
| 70 | /// </summary>
|
---|
| 71 | /// <param name="remainingIds">List of remaining ids. After the method has been executed the list has to have less items</param>
|
---|
| 72 | /// <param name="packingBin">This object will be filled with some of the given items</param>
|
---|
| 73 | /// <param name="items">List of packing items. Some of the items will be assigned to the BinPacking3D object</param>
|
---|
| 74 | /// <param name="epCreationMethod"></param>
|
---|
| 75 | /// <param name="useStackingConstraints"></param>
|
---|
| 76 | protected void PackRemainingItems(ref IList<int> remainingIds, ref BinPacking3D packingBin, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, bool useStackingConstraints) {
|
---|
| 77 | IExtremePointCreator extremePointCreator = ExtremePointCreatorFactory.CreateExtremePointCreator(epCreationMethod, useStackingConstraints);
|
---|
| 78 | foreach (var itemId in new List<int>(remainingIds)) {
|
---|
| 79 | var item = items[itemId];
|
---|
| 80 | PackingPosition position = FindPackingPositionForItem(packingBin, item, useStackingConstraints);
|
---|
| 81 | // if a valid packing position could be found, the current item can be added to the given bin
|
---|
| 82 | if (position != null) {
|
---|
| 83 | PackItem(packingBin, itemId, item, position, extremePointCreator, useStackingConstraints);
|
---|
| 84 | remainingIds.Remove(itemId);
|
---|
| 85 | }
|
---|
| 86 | }
|
---|
| 87 | }
|
---|
| 88 |
|
---|
| 89 |
|
---|
| 90 | protected override PackingPosition FindPackingPositionForItem(BinPacking3D packingBin, PackingItem packingItem, bool useStackingConstraints) {
|
---|
| 91 | if (!CheckItemDimensions(packingBin, packingItem)) {
|
---|
| 92 | throw new BinPacking3DException($"The dimensions of the given item exceeds the bin dimensions. " +
|
---|
| 93 | $"Bin: ({packingBin.BinShape.Width} {packingBin.BinShape.Depth} {packingBin.BinShape.Height})" +
|
---|
| 94 | $"Item: ({packingItem.Width} {packingItem.Depth} {packingItem.Height})");
|
---|
| 95 | }
|
---|
| 96 |
|
---|
| 97 | var rsds = new SortedSet<ResidualSpaceDifference>();
|
---|
| 98 |
|
---|
| 99 | rsds.Add(FindResidualSpaceDifferenceForItem(packingBin, packingItem, useStackingConstraints, rotated: false, tilted: false));
|
---|
| 100 |
|
---|
| 101 | if (packingItem.TiltEnabled) {
|
---|
| 102 | rsds.Add(FindResidualSpaceDifferenceForItem(packingBin, packingItem, useStackingConstraints, rotated: false, tilted: true));
|
---|
| 103 | }
|
---|
| 104 | if (packingItem.RotateEnabled) {
|
---|
| 105 | rsds.Add(FindResidualSpaceDifferenceForItem(packingBin, packingItem, useStackingConstraints, rotated: true, tilted: false));
|
---|
| 106 | }
|
---|
| 107 | if (packingItem.RotateEnabled && packingItem.TiltEnabled) {
|
---|
| 108 | rsds.Add(FindResidualSpaceDifferenceForItem(packingBin, packingItem, useStackingConstraints, rotated: true, tilted: true));
|
---|
| 109 | }
|
---|
| 110 |
|
---|
| 111 | var rsd = rsds.Where(x => x != null).FirstOrDefault();
|
---|
| 112 |
|
---|
| 113 | if (rsd == null) {
|
---|
| 114 | return null;
|
---|
| 115 | }
|
---|
| 116 |
|
---|
| 117 | packingItem.Rotated = rsd.Item.Rotated;
|
---|
| 118 | packingItem.Tilted = rsd.Item.Tilted;
|
---|
| 119 | return rsd.Position;
|
---|
| 120 | }
|
---|
| 121 |
|
---|
| 122 | protected ResidualSpaceDifference FindResidualSpaceDifferenceForItem(BinPacking3D packingBin, PackingItem packingItem, bool useStackingConstraints, bool rotated, bool tilted) {
|
---|
| 123 | PackingItem newItem = new PackingItem(packingItem) {
|
---|
| 124 | Rotated = rotated,
|
---|
| 125 | Tilted = tilted
|
---|
| 126 | };
|
---|
| 127 |
|
---|
| 128 | var rsds = new SortedSet<ResidualSpaceDifference>();
|
---|
| 129 |
|
---|
| 130 | foreach (var ep in packingBin.ExtremePoints) {
|
---|
| 131 | var position = ep.Key;
|
---|
| 132 | if (packingBin.IsPositionFeasible(newItem, position, useStackingConstraints)) {
|
---|
| 133 | foreach (var rs in ep.Value) {
|
---|
| 134 | var rsd = ResidualSpaceDifference.Create(position, newItem, rs);
|
---|
| 135 | if (rsd != null) {
|
---|
| 136 | rsds.Add(rsd);
|
---|
| 137 | }
|
---|
| 138 | }
|
---|
| 139 | }
|
---|
| 140 | }
|
---|
| 141 | return rsds.FirstOrDefault();
|
---|
| 142 | }
|
---|
| 143 |
|
---|
| 144 | protected override bool CheckItemDimensions(BinPacking3D packingBin, PackingItem item) {
|
---|
| 145 | bool ok = false;
|
---|
| 146 | int width = item.OriginalWidth;
|
---|
| 147 | int height = item.OriginalHeight;
|
---|
| 148 | int depth = item.OriginalDepth;
|
---|
| 149 |
|
---|
| 150 | ok |= CheckItemDimensions(packingBin, width, height, depth);
|
---|
| 151 |
|
---|
| 152 | if (item.RotateEnabled && item.TiltEnabled) {
|
---|
| 153 | ok |= CheckItemDimensions(packingBin, depth, height, width);//rotated
|
---|
| 154 | ok |= CheckItemDimensions(packingBin, height, width, depth);//tilted
|
---|
| 155 | ok |= CheckItemDimensions(packingBin, depth, width, height);//rotated & tilted
|
---|
| 156 | } else if (item.RotateEnabled) {
|
---|
| 157 | ok |= CheckItemDimensions(packingBin, depth, height, width);
|
---|
| 158 | } else if (item.TiltEnabled) {
|
---|
| 159 | ok |= CheckItemDimensions(packingBin, height, width, depth);
|
---|
| 160 | }
|
---|
| 161 |
|
---|
| 162 | return ok;
|
---|
| 163 | }
|
---|
| 164 |
|
---|
| 165 | private bool CheckItemDimensions(BinPacking3D packingBin, int width, int height, int depth) {
|
---|
| 166 | return base.CheckItemDimensions(packingBin, new PackingItem() {
|
---|
| 167 | OriginalWidth = width,
|
---|
| 168 | OriginalHeight = height,
|
---|
| 169 | OriginalDepth = depth
|
---|
| 170 | });
|
---|
| 171 | }
|
---|
| 172 |
|
---|
| 173 | protected class ResidualSpaceDifference : IComparable {
|
---|
| 174 | public static ResidualSpaceDifference Create(PackingPosition position, PackingItem item, ResidualSpace rs) {
|
---|
| 175 | var x = rs.Width - item.Width;
|
---|
| 176 | var y = rs.Height - item.Height;
|
---|
| 177 | var z = rs.Depth - item.Depth;
|
---|
| 178 | // the item can't be places in the residual space
|
---|
| 179 | if (rs.IsZero() || x < 0 || y < 0 || z < 0) {
|
---|
| 180 | return null;
|
---|
| 181 | }
|
---|
| 182 |
|
---|
| 183 | return new ResidualSpaceDifference() {
|
---|
| 184 | Position = position,
|
---|
| 185 | Item = item,
|
---|
| 186 | X = x,
|
---|
| 187 | Y = y,
|
---|
| 188 | Z = z
|
---|
| 189 | };
|
---|
| 190 | }
|
---|
| 191 |
|
---|
| 192 | public ResidualSpaceDifference() { }
|
---|
| 193 |
|
---|
| 194 | public PackingItem Item { get; set; }
|
---|
| 195 |
|
---|
| 196 | public PackingPosition Position { get; set; }
|
---|
| 197 | public int X { get; set; }
|
---|
| 198 | public int Y { get; set; }
|
---|
| 199 | public int Z { get; set; }
|
---|
| 200 |
|
---|
| 201 |
|
---|
| 202 | public int CompareTo(object obj) {
|
---|
| 203 | if (!(obj is ResidualSpaceDifference)) {
|
---|
| 204 | return 0;
|
---|
| 205 | }
|
---|
| 206 | var rsd = obj as ResidualSpaceDifference;
|
---|
| 207 |
|
---|
| 208 | var x = this.X - rsd.X;
|
---|
| 209 | var y = rsd.Y - this.Y;
|
---|
| 210 | var z = this.Z - rsd.Z;
|
---|
| 211 |
|
---|
| 212 | if (x != 0) {
|
---|
| 213 | return x;
|
---|
| 214 | } else if (y != 0 ) {
|
---|
| 215 | return y;
|
---|
| 216 | } else if (z != 0) {
|
---|
| 217 | return z;
|
---|
| 218 | }
|
---|
| 219 |
|
---|
| 220 | return 0;
|
---|
| 221 | }
|
---|
| 222 | }
|
---|
| 223 |
|
---|
| 224 | }
|
---|
| 225 | }
|
---|