1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022015 Joseph Helm and 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.Collections.Generic;


23  using System.Linq;


24  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


25  using HeuristicLab.Core;


26  using HeuristicLab.Common;


27  using HeuristicLab.Encodings.PackingEncoding;


28 


29  namespace HeuristicLab.Problems.BinPacking3D {


30  [Item("BinPacking3D", "Represents a singlebin packing for a 3D binpacking problem.")]


31  [StorableClass]


32  public class BinPacking3D : BinPacking<PackingPosition, PackingShape, PackingItem> {


33 


34  public BinPacking3D(PackingShape binMeasures)


35  : base(binMeasures) {


36  ExtremePoints = new SortedSet<PackingPosition>(new EPComparer3D());


37  ExtremePoints.Add(binMeasures.Origin);


38  }


39  [StorableConstructor]


40  protected BinPacking3D(bool deserializing) : base(deserializing) { }


41  protected BinPacking3D(BinPacking3D original, Cloner cloner)


42  : base(original, cloner) {


43  this.depthWasDoubled = original.depthWasDoubled;


44  this.ExtremePoints = new SortedSet<PackingPosition>(original.ExtremePoints, new EPComparer3D());


45  }


46  public override IDeepCloneable Clone(Cloner cloner) {


47  return new BinPacking3D(this, cloner);


48  }


49 


50  protected override void GenerateNewExtremePointsForNewItem(PackingItem newItem, PackingPosition position) {


51  int newWidth = position.Rotated ? newItem.Depth : newItem.Width;


52  int newDepth = position.Rotated ? newItem.Width : newItem.Depth;


53 


54  //Find ExtremePoints beginning from sourcepointX


55  var sourcePointX = new PackingPosition(0, position.X + newWidth, position.Y, position.Z);


56  if (sourcePointX.X < BinMeasures.Width && sourcePointX.Y < BinMeasures.Height && sourcePointX.Z < BinMeasures.Depth) {


57  //Traversing down the yaxis


58  PackingPosition current = new PackingPosition(0, sourcePointX.X, sourcePointX.Y, sourcePointX.Z);


59  while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {


60  current = PackingPosition.MoveDown(current);


61  }


62  ExtremePoints.Add((PackingPosition)current.Clone());


63  while (current.X > 0 && !IsPointOccupied(PackingPosition.MoveLeft(current))) {


64  current = PackingPosition.MoveLeft(current);


65  }


66  ExtremePoints.Add(current);


67 


68  //Traversing down the zaxis


69  current = new PackingPosition(0, sourcePointX.X, sourcePointX.Y, sourcePointX.Z);


70  while (current.Z > 0 && !IsPointOccupied(PackingPosition.MoveBack(current))) {


71  current = PackingPosition.MoveBack(current);


72  }


73  ExtremePoints.Add((PackingPosition)current.Clone());


74  while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {


75  current = PackingPosition.MoveDown(current);


76  }


77  ExtremePoints.Add(current);


78  }


79 


80 


81 


82 


83  //Find ExtremePoints beginning from sourcepointY


84  var sourcePointY = new PackingPosition(0, position.X, position.Y + newItem.Height, position.Z);


85  if (sourcePointY.X < BinMeasures.Width && sourcePointY.Y < BinMeasures.Height && sourcePointY.Z < BinMeasures.Depth) {


86  //Traversing down the xaxis


87  PackingPosition current = new PackingPosition(0, sourcePointY.X, sourcePointY.Y, sourcePointY.Z);


88  while (current.X > 0 && !IsPointOccupied(PackingPosition.MoveLeft(current))) {


89  current = PackingPosition.MoveLeft(current);


90  }


91  ExtremePoints.Add((PackingPosition)current.Clone());


92  while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {


93  current = PackingPosition.MoveDown(current);


94  }


95  ExtremePoints.Add(current);


96 


97  //Traversing down the zaxis


98  current = new PackingPosition(0, sourcePointY.X, sourcePointY.Y, sourcePointY.Z);


99  while (current.Z > 0 && !IsPointOccupied(PackingPosition.MoveBack(current))) {


100  current = PackingPosition.MoveBack(current);


101  }


102  ExtremePoints.Add((PackingPosition)current.Clone());


103  while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {


104  current = PackingPosition.MoveDown(current);


105  }


106  ExtremePoints.Add(current);


107  }


108 


109 


110 


111 


112 


113  //Find ExtremePoints beginning from sourcepointZ


114  var sourcePointZ = new PackingPosition(0, position.X, position.Y, position.Z + newDepth);


115  if (sourcePointZ.X < BinMeasures.Width && sourcePointZ.Y < BinMeasures.Height && sourcePointZ.Z < BinMeasures.Depth) {


116  //Traversing down the xaxis


117  PackingPosition current = new PackingPosition(0, sourcePointZ.X, sourcePointZ.Y, sourcePointZ.Z);


118  while (current.X > 0 && !IsPointOccupied(PackingPosition.MoveLeft(current))) {


119  current = PackingPosition.MoveLeft(current);


120  }


121  ExtremePoints.Add((PackingPosition)current.Clone());


122  while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {


123  current = PackingPosition.MoveDown(current);


124  }


125  ExtremePoints.Add(current);


126 


127  //Traversing down the yaxis


128  current = new PackingPosition(0, sourcePointZ.X, sourcePointZ.Y, sourcePointZ.Z);


129  while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {


130  current = PackingPosition.MoveDown(current);


131  }


132  ExtremePoints.Add((PackingPosition)current.Clone());


133  while (current.X > 0 && !IsPointOccupied(PackingPosition.MoveLeft(current))) {


134  current = PackingPosition.MoveLeft(current);


135  }


136  ExtremePoints.Add(current);


137  }


138 


139  //ExtremePoints.RemoveWhere(ep => IsPointOccupied (ep));


140 


141  //ExtremePoints = new HashSet<ThreeDimensionalPacking>(ExtremePoints.


142  // OrderBy(ep => ep.Z).


143  // ThenBy(ep => ep.X).


144  // ThenBy(ep => ep.Y)//.ThenBy(ep => ShortestPossibleSideFromPoint(ep))


145  // );


146  }


147 


148  public override PackingPosition FindExtremePointForItem(PackingItem measures, bool rotated, bool stackingConstraints) {


149 


150  PackingItem item = new PackingItem(


151  rotated ? measures.Depth : measures.Width,


152  measures.Height,


153  rotated ? measures.Width : measures.Depth,


154  measures.TargetBin);


155 


156  int epIndex = 0;


157  while (epIndex < ExtremePoints.Count && (


158  !IsPositionFeasible(item, ExtremePoints.ElementAt(epIndex))


159   !IsSupportedByAtLeastOnePoint(item, ExtremePoints.ElementAt(epIndex))


160   (stackingConstraints && !IsStaticStable(item, ExtremePoints.ElementAt(epIndex)))


161   (stackingConstraints && !IsWeightSupported(item, ExtremePoints.ElementAt(epIndex)))


162  )) { epIndex++; }


163 


164  if (epIndex < ExtremePoints.Count) {


165  var origPoint = ExtremePoints.ElementAt(epIndex);


166  var result = new PackingPosition(origPoint.AssignedBin, origPoint.X, origPoint.Y, origPoint.Z, rotated);


167  return result;


168  }


169  return null;


170  }


171 


172  public override PackingPosition FindPositionBySliding(PackingItem measures, bool rotated) {


173  //Startingposition at upper right corner (=left bottom point of itemrectangle is at position item.width,item.height)


174  PackingPosition currentPosition = new PackingPosition(0,


175  BinMeasures.Width  (rotated ? measures.Depth : measures.Width),


176  BinMeasures.Height  measures.Height,


177  BinMeasures.Depth  (rotated ? measures.Width : measures.Depth), rotated);


178  //Slide the item as far as possible to the bottom


179  while (IsPositionFeasible(measures, PackingPosition.MoveDown(currentPosition))


180   IsPositionFeasible(measures, PackingPosition.MoveLeft(currentPosition))


181   IsPositionFeasible(measures, PackingPosition.MoveBack(currentPosition))) {


182  //Slide the item as far as possible to the left


183  while (IsPositionFeasible(measures, PackingPosition.MoveLeft(currentPosition))


184   IsPositionFeasible(measures, PackingPosition.MoveBack(currentPosition))) {


185  //Slide the item as far as possible to the back


186  while (IsPositionFeasible(measures, PackingPosition.MoveBack(currentPosition))) {


187  currentPosition = PackingPosition.MoveBack(currentPosition);


188  }


189  if (IsPositionFeasible(measures, PackingPosition.MoveLeft(currentPosition)))


190  currentPosition = PackingPosition.MoveLeft(currentPosition);


191  }


192  if (IsPositionFeasible(measures, PackingPosition.MoveDown(currentPosition)))


193  currentPosition = PackingPosition.MoveDown(currentPosition);


194  }


195 


196  return IsPositionFeasible(measures, currentPosition) ? currentPosition : null;


197  }


198 


199  public override void SlidingBasedPacking(ref List<int> sequence, ItemList<PackingItem> itemMeasures) {


200  var temp = new List<int>(sequence);


201  for (int i = 0; i < temp.Count; i++) {


202  var item = itemMeasures[temp[i]];


203  var position = FindPositionBySliding(item, false);


204  if (position != null) {


205  PackItem(temp[i], item, position);


206  sequence.Remove(temp[i]);


207  }


208  }


209  }


210  public override void SlidingBasedPacking(ref List<int> sequence, ItemList<PackingItem> itemMeasures, Dictionary<int, bool> rotationArray) {


211  var temp = new List<int>(sequence);


212  for (int i = 0; i < temp.Count; i++) {


213  var item = itemMeasures[temp[i]];


214  var position = FindPositionBySliding(item, rotationArray[i]);


215  if (position != null) {


216  PackItem(temp[i], item, position);


217  sequence.Remove(temp[i]);


218  }


219  }


220  }


221  public override void ExtremePointBasedPacking(ref List<int> sequence, ItemList<PackingItem> itemMeasures, bool stackingConstraints) {


222  var temp = new List<int>(sequence);


223  foreach (int itemID in temp) {


224  var item = itemMeasures[itemID];


225  var positionFound = FindExtremePointForItem(item, false, stackingConstraints);


226  if (positionFound != null) {


227  PackItem(itemID, item, positionFound);


228  sequence.Remove(itemID);


229  }


230  }


231  }


232  public override void ExtremePointBasedPacking(ref List<int> sequence, ItemList<PackingItem> itemMeasures, bool stackingConstraints, Dictionary<int, bool> rotationArray) {


233  var temp = new List<int>(sequence);


234  foreach (int itemID in temp) {


235  var item = itemMeasures[itemID];


236  var positionFound = FindExtremePointForItem(item, rotationArray[itemID], stackingConstraints);


237  if (positionFound != null) {


238  PackItem(itemID, item, positionFound);


239  sequence.Remove(itemID);


240  }


241  }


242  }


243 


244  public override int ShortestPossibleSideFromPoint(PackingPosition position) {


245 


246  int shortestSide = int.MaxValue;


247  int width = BinMeasures.Width;


248  int height = BinMeasures.Height;


249  int depth = BinMeasures.Depth;


250 


251  if (position.X >= width  position.Y >= height  position.Z >= depth)


252  return shortestSide;


253 


254  PackingPosition current = new PackingPosition(0, position.X, position.Y, position.Z);


255  while (current.X < width && IsPointOccupied(current)) { current = PackingPosition.MoveRight(current); }


256  if (current.X  position.X < shortestSide)


257  shortestSide = current.X  position.X;


258 


259 


260  current = new PackingPosition(0, position.X, position.Y, position.Z);


261  while (current.Y < height && IsPointOccupied(current)) { current = PackingPosition.MoveUp(current); }


262  if (current.Y  position.Y < shortestSide)


263  shortestSide = current.Y  position.Y;


264 


265 


266  current = new PackingPosition(0, position.X, position.Y, position.Z);


267  while (current.Z < depth && IsPointOccupied(current)) { current = PackingPosition.MoveFront(current); }


268  if (current.Z  position.Z < shortestSide)


269  shortestSide = current.Z  position.Z;


270 


271  return shortestSide;


272  }


273  public override bool IsStaticStable(PackingItem item, PackingPosition position) {


274  //Static stability is given, if item is placed on the ground


275  if (position.Y == 0)


276  return true;


277 


278  if (IsPointOccupied(new PackingPosition(0, position.X, position.Y  1, position.Z))


279  && IsPointOccupied(new PackingPosition(0, position.X + item.Width  1, position.Y  1, position.Z))


280  && IsPointOccupied(new PackingPosition(0, position.X, position.Y  1, position.Z + item.Depth  1))


281  && IsPointOccupied(new PackingPosition(0, position.X + item.Width  1, position.Y  1, position.Z + item.Depth  1)))


282  return true;


283 


284 


285  //if (occupiedPoints[position.X, position.Y  1, position.Z] != 1


286  // && occupiedPoints[position.X + item.Width  1, position.Y  1, position.Z] != 1


287  // && occupiedPoints[position.X, position.Y  1, position.Z + item.Depth  1] != 1


288  // && occupiedPoints[position.X + item.Width  1, position.Y  1, position.Z + item.Depth  1] != 1)


289  // return true;


290 


291  //int groundCount = 0;


292  //for (int x = ep.X; x < ep.X + item.Width  1; x++) {


293  // for (int z = ep.Z; z < ep.Z + item.Depth  1; z++) {


294  // if (occupiedPoints[x,ep.Y1, z] != 1)


295  // groundCount++;


296  // }


297  //}


298  //double stableGround = (double)(groundCount) / (double)(item.Width * item.Depth);


299  //if (stableGround > 0.75)


300  // return true;


301 


302  return false;


303  }


304 


305  [Storable]


306  private bool depthWasDoubled = false; // TODO ???


307  public void DoubleDepth() {


308  if (!depthWasDoubled) {


309  var oldDepth = BinMeasures.Depth;


310  BinMeasures.Depth = BinMeasures.Depth * 2;


311  //OccupiedPoints.ChangeBinMeasures(BinMeasures);


312  depthWasDoubled = true;


313  }


314  }


315 


316  public bool IsSupportedByAtLeastOnePoint(PackingItem item, PackingPosition position) {


317  if (position.Y == 0)


318  return true;


319 


320  int y = position.Y  1;


321  for (int x = position.X; x < position.X + item.Width; x++)


322  for (int z = position.Z; z < position.Z + item.Depth; z++)


323  if (IsPointOccupied(new PackingPosition(0, x, y, z)))


324  return true;


325 


326  return false;


327  }


328  public bool IsWeightSupported(PackingItem item, PackingPosition ep) {


329  if (ep.Y == 0)


330  return true;


331 


332  if (ItemMeasures[PointOccupation(new PackingPosition(0, ep.X, ep.Y  1, ep.Z))].SupportsStacking(item)


333  && ItemMeasures[PointOccupation(new PackingPosition(0, ep.X + item.Width  1, ep.Y  1, ep.Z))].SupportsStacking(item)


334  && ItemMeasures[PointOccupation(new PackingPosition(0, ep.X, ep.Y  1, ep.Z + item.Depth  1))].SupportsStacking(item)


335  && ItemMeasures[PointOccupation(new PackingPosition(0, ep.X + item.Width  1, ep.Y  1, ep.Z + item.Depth  1))].SupportsStacking(item))


336  return true;


337 


338  return false;


339  }


340 


341 


342  protected override void InitializeOccupationLayers() {


343  for (int i = 0; i * 10 <= BinMeasures.Depth; i += 1) {


344  OccupationLayers[i] = new List<int>();


345  }


346  }


347  protected override void AddNewItemToOccupationLayers(int itemID, PackingItem measures, PackingPosition position) {


348  int z1 = position.Z / 10;


349  int z2 = (position.Z + (position.Rotated ? measures.Width : measures.Depth)) / 10;


350 


351  for (int i = z1; i <= z2; i++)


352  OccupationLayers[i].Add(itemID);


353  }


354  protected override List<int> GetLayerItemIDs(PackingPosition position) {


355  return OccupationLayers[position.Z / 10];


356  }


357  protected override List<int> GetLayerItemIDs(PackingItem measures, PackingPosition position) {


358  List<int> result = new List<int>();


359  int z1 = position.Z / 10;


360  int z2 = (position.Z + (position.Rotated ? measures.Width : measures.Depth)) / 10;


361 


362  for (int i = z1; i <= z2; i++)


363  result.AddRange(OccupationLayers[i]);


364 


365  return result;


366  }


367  }


368  public class EPComparer3D : IComparer<PackingPosition> {


369  public int Compare(PackingPosition a, PackingPosition b) {


370  int result = a.Z.CompareTo(b.Z);


371  if (result == 0)


372  result = a.X.CompareTo(b.X);


373  if (result == 0)


374  result = a.Y.CompareTo(b.Y);


375 


376  return result;


377  }


378  }


379  }

