Changeset 15230 for trunk/sources/HeuristicLab.Problems.BinPacking/3.3/3D
- Timestamp:
- 07/13/17 15:25:11 (7 years ago)
- Location:
- trunk/sources/HeuristicLab.Problems.BinPacking
- Files:
-
- 6 edited
- 7 copied
Legend:
- Unmodified
- Added
- Removed
-
trunk/sources/HeuristicLab.Problems.BinPacking
-
Property
svn:mergeinfo
set to
/branches/BinPackingExtension/HeuristicLab.Problems.BinPacking merged eligible
-
Property
svn:mergeinfo
set to
-
trunk/sources/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs
r14916 r15230 20 20 #endregion 21 21 22 using System; 22 23 using System.Collections.Generic; 23 24 using System.Linq; … … 35 36 : base(binShape) { 36 37 ExtremePoints = new SortedSet<PackingPosition>(); 37 ExtremePoints.Add(binShape.Origin); 38 ResidualSpace = new Dictionary<PackingPosition, Tuple<int,int,int>>(); 39 AddExtremePoint(binShape.Origin); 38 40 InitializeOccupationLayers(); 39 41 } … … 43 45 : base(original, cloner) { 44 46 this.ExtremePoints = new SortedSet<PackingPosition>(original.ExtremePoints.Select(p => cloner.Clone(p))); 47 this.ResidualSpace = new Dictionary<PackingPosition, Tuple<int, int, int>>(); 48 foreach (var o in original.ResidualSpace) 49 this.ResidualSpace.Add(cloner.Clone(o.Key), Tuple.Create(o.Value.Item1, o.Value.Item2, o.Value.Item3)); 45 50 } 46 51 public override IDeepCloneable Clone(Cloner cloner) { … … 60 65 current = PackingPosition.MoveDown(current); 61 66 } 62 ExtremePoints.Add((PackingPosition)current.Clone());67 AddExtremePoint((PackingPosition)current.Clone()); 63 68 while (current.X > 0 && !IsPointOccupied(PackingPosition.MoveLeft(current))) { 64 69 current = PackingPosition.MoveLeft(current); 65 70 } 66 ExtremePoints.Add(current);71 AddExtremePoint(current); 67 72 68 73 //Traversing down the z-axis … … 71 76 current = PackingPosition.MoveBack(current); 72 77 } 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 AddExtremePoint((PackingPosition)current.Clone()); 79 while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) { 80 current = PackingPosition.MoveDown(current); 81 } 82 AddExtremePoint(current); 78 83 } 79 84 … … 86 91 current = PackingPosition.MoveLeft(current); 87 92 } 88 ExtremePoints.Add((PackingPosition)current.Clone());89 while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) { 90 current = PackingPosition.MoveDown(current); 91 } 92 ExtremePoints.Add(current);93 AddExtremePoint((PackingPosition)current.Clone()); 94 while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) { 95 current = PackingPosition.MoveDown(current); 96 } 97 AddExtremePoint(current); 93 98 94 99 //Traversing down the z-axis … … 97 102 current = PackingPosition.MoveBack(current); 98 103 } 99 ExtremePoints.Add((PackingPosition)current.Clone());100 while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) { 101 current = PackingPosition.MoveDown(current); 102 } 103 ExtremePoints.Add(current);104 AddExtremePoint((PackingPosition)current.Clone()); 105 while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) { 106 current = PackingPosition.MoveDown(current); 107 } 108 AddExtremePoint(current); 104 109 } 105 110 … … 112 117 current = PackingPosition.MoveLeft(current); 113 118 } 114 ExtremePoints.Add((PackingPosition)current.Clone());115 while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) { 116 current = PackingPosition.MoveDown(current); 117 } 118 ExtremePoints.Add(current);119 AddExtremePoint((PackingPosition)current.Clone()); 120 while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) { 121 current = PackingPosition.MoveDown(current); 122 } 123 AddExtremePoint(current); 119 124 120 125 //Traversing down the y-axis … … 123 128 current = PackingPosition.MoveDown(current); 124 129 } 125 ExtremePoints.Add((PackingPosition)current.Clone());130 AddExtremePoint((PackingPosition)current.Clone()); 126 131 while (current.X > 0 && !IsPointOccupied(PackingPosition.MoveLeft(current))) { 127 132 current = PackingPosition.MoveLeft(current); 128 133 } 129 ExtremePoints.Add(current); 134 AddExtremePoint(current); 135 } 136 } 137 138 private void AddExtremePoint(PackingPosition current) { 139 if (ExtremePoints.Add(current)) { 140 var tuple = Tuple.Create(BinShape.Width - current.X, BinShape.Height - current.Y, BinShape.Depth - current.Z); 141 ResidualSpace.Add(current, tuple); 130 142 } 131 143 } 132 144 133 145 public override PackingPosition FindExtremePointForItem(PackingItem item, bool rotated, bool stackingConstraints) { 134 135 146 PackingItem newItem = new PackingItem( 136 147 rotated ? item.Depth : item.Width, … … 139 150 item.TargetBin, item.Weight, item.Material); 140 151 141 int epIndex = 0; 142 while (epIndex < ExtremePoints.Count && ( 143 !IsPositionFeasible(newItem, ExtremePoints.ElementAt(epIndex)) 144 || !IsSupportedByAtLeastOnePoint(newItem, ExtremePoints.ElementAt(epIndex)) 145 || (stackingConstraints && !IsStaticStable(newItem, ExtremePoints.ElementAt(epIndex))) 146 || (stackingConstraints && !IsWeightSupported(newItem, ExtremePoints.ElementAt(epIndex))) 147 )) { epIndex++; } 148 149 if (epIndex < ExtremePoints.Count) { 150 var origPoint = ExtremePoints.ElementAt(epIndex); 151 var result = new PackingPosition(origPoint.AssignedBin, origPoint.X, origPoint.Y, origPoint.Z, rotated); 152 var ep = ExtremePoints.Where(x => IsPositionFeasible(newItem, x, stackingConstraints)).FirstOrDefault(); 153 if (ep != null) { 154 var result = new PackingPosition(ep.AssignedBin, ep.X, ep.Y, ep.Z, rotated); 152 155 return result; 153 156 } … … 155 158 } 156 159 157 public override PackingPosition FindPositionBySliding(PackingItem item, bool rotated) { 158 //TODO: does not support stacking constraints yet 160 public override bool IsPositionFeasible(PackingItem item, PackingPosition position, bool stackingConstraints) { 161 var feasible = base.IsPositionFeasible(item, position, stackingConstraints); 162 return feasible 163 && IsSupportedByAtLeastOnePoint(item, position) 164 && (!stackingConstraints || (IsStaticStable(item, position) && IsWeightSupported(item, position))); 165 } 166 167 public override PackingPosition FindPositionBySliding(PackingItem item, bool rotated, bool stackingConstraints) { 159 168 //Starting-position at upper right corner (=left bottom point of item-rectangle is at position item.width,item.height) 160 169 PackingPosition currentPosition = new PackingPosition(0, … … 163 172 BinShape.Depth - (rotated ? item.Width : item.Depth), rotated); 164 173 //Slide the item as far as possible to the bottom 165 while (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition) )166 || IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition) )167 || IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition) )) {174 while (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition), stackingConstraints) 175 || IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints) 176 || IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition), stackingConstraints)) { 168 177 //Slide the item as far as possible to the left 169 while (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition) )170 || IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition) )) {178 while (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints) 179 || IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition), stackingConstraints)) { 171 180 //Slide the item as far as possible to the back 172 while (IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition) )) {181 while (IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition), stackingConstraints)) { 173 182 currentPosition = PackingPosition.MoveBack(currentPosition); 174 183 } 175 if (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition) ))184 if (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints)) 176 185 currentPosition = PackingPosition.MoveLeft(currentPosition); 177 186 } 178 if (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition) ))187 if (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition), stackingConstraints)) 179 188 currentPosition = PackingPosition.MoveDown(currentPosition); 180 189 } 181 190 182 return IsPositionFeasible(item, currentPosition ) ? currentPosition : null;183 } 184 185 public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items ) {191 return IsPositionFeasible(item, currentPosition, stackingConstraints) ? currentPosition : null; 192 } 193 194 public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) { 186 195 var temp = new List<int>(sequence); 187 196 for (int i = 0; i < temp.Count; i++) { 188 197 var item = items[temp[i]]; 189 var position = FindPositionBySliding(item, false );198 var position = FindPositionBySliding(item, false, stackingConstraints); 190 199 if (position != null) { 191 200 PackItem(temp[i], item, position); … … 194 203 } 195 204 } 196 public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, Dictionary<int, bool> rotationArray ) {205 public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, Dictionary<int, bool> rotationArray, bool stackingConstraints) { 197 206 var temp = new List<int>(sequence); 198 207 for (int i = 0; i < temp.Count; i++) { 199 208 var item = items[temp[i]]; 200 var position = FindPositionBySliding(item, rotationArray[i] );209 var position = FindPositionBySliding(item, rotationArray[i], stackingConstraints); 201 210 if (position != null) { 202 211 PackItem(temp[i], item, position); … … 212 221 if (positionFound != null) { 213 222 PackItem(itemID, item, positionFound); 223 if (!(positionFound.X == 0 && positionFound.Y == 0 && positionFound.Z == 0)) { 224 UpdateResidualSpace(item, positionFound); 225 } 214 226 sequence.Remove(itemID); 215 227 } … … 227 239 } 228 240 } 229 230 241 public override int ShortestPossibleSideFromPoint(PackingPosition position) { 231 242 … … 297 308 } 298 309 299 300 310 protected override void InitializeOccupationLayers() { 301 311 for (int i = 0; i * 10 <= BinShape.Depth; i += 1) { … … 320 330 for (int i = z1; i <= z2; i++) 321 331 result.AddRange(OccupationLayers[i]); 322 323 332 return result; 324 333 } 334 335 public void UpdateResidualSpace(PackingItem item, PackingPosition pos) { 336 foreach (var ep in ExtremePoints) { 337 if (ep.Z >= pos.Z && ep.Z <= pos.Z + item.Depth) { 338 if (ep.X <= pos.X && ep.Y > pos.Y && ep.Y < pos.Y + item.Height) { 339 var diff = pos.X - ep.X; 340 var newRSX = ResidualSpace[ep].Item1 < diff ? ResidualSpace[ep].Item1 : diff; 341 ResidualSpace[ep] = Tuple.Create(newRSX, ResidualSpace[ep].Item2, ResidualSpace[ep].Item3); 342 } 343 if (ep.Y <= pos.Y && ep.X > pos.X && ep.X < pos.X + item.Width) { 344 var diff = pos.Y - ep.Y; 345 var newRSY = ResidualSpace[ep].Item2 < diff ? ResidualSpace[ep].Item2 : diff; 346 ResidualSpace[ep] = Tuple.Create(ResidualSpace[ep].Item1, newRSY, ResidualSpace[ep].Item3); 347 } 348 } 349 if (ep.Z <= pos.Z && 350 ep.Y > pos.Y && ep.Y < pos.Y + item.Height && 351 ep.X > pos.X && ep.X < pos.X + item.Width) { 352 var diff = pos.Z - ep.Z; 353 var newRSZ = ResidualSpace[ep].Item3 < diff ? ResidualSpace[ep].Item3 : diff; 354 ResidualSpace[ep] = Tuple.Create(ResidualSpace[ep].Item1, ResidualSpace[ep].Item2, newRSZ); 355 } 356 } 357 return; 358 } 325 359 } 326 327 360 } -
trunk/sources/HeuristicLab.Problems.BinPacking/3.3/3D/IntegerVectorEncoding/BottomLeftIntegerVectorDecoder.cs
r14167 r15230 54 54 55 55 protected override PackingPosition FindPositionForItem(BinPacking3D bp, PackingItem item, bool useStackingConstraints) { 56 return bp.FindPositionBySliding(item, rotated: false );56 return bp.FindPositionBySliding(item, rotated: false, stackingConstraints: useStackingConstraints); 57 57 } 58 58 … … 61 61 ref IList<int> remainingIDs, IList<PackingItem> items, bool useStackingConstraints) { 62 62 var bp = new BinPacking3D(partialSolution.BinShape); 63 bp.SlidingBasedPacking(ref remainingIDs, items );63 bp.SlidingBasedPacking(ref remainingIDs, items, useStackingConstraints); 64 64 return bp; 65 65 } -
trunk/sources/HeuristicLab.Problems.BinPacking/3.3/3D/PermutationEncoding/BottomLeftPermutationDecoder.cs
r14167 r15230 46 46 while (remainingIDs.Count > 0) { 47 47 var bp = new BinPacking3D(binShape); 48 bp.SlidingBasedPacking(ref remainingIDs, items );48 bp.SlidingBasedPacking(ref remainingIDs, items, useStackingConstraints); 49 49 result.Bins.Add(bp); 50 50 } -
trunk/sources/HeuristicLab.Problems.BinPacking/3.3/3D/PermutationEncoding/ExtremePointPermutationDecoder.cs
r14167 r15230 20 20 #endregion 21 21 22 using System; 22 23 using HeuristicLab.Core; 23 24 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; … … 25 26 using System.Collections.Generic; 26 27 using HeuristicLab.Encodings.PermutationEncoding; 28 using System.Linq; 29 27 30 28 31 namespace HeuristicLab.Problems.BinPacking3D { 29 32 [Item("Extreme-point Permutation Decoder (3d)", "Decodes the permutation and creates a packing solution candidate")] 30 33 [StorableClass] 31 public class ExtremePointPermutationDecoder : Item, IDecoder<Permutation>{34 public class ExtremePointPermutationDecoder : ExtremePointPermutationDecoderBase { 32 35 33 36 [StorableConstructor] … … 41 44 } 42 45 43 public Solution Decode(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) { 46 public override Solution Decode(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) { 47 return Apply(permutation, binShape, items, useStackingConstraints); 48 } 49 50 public static Solution Apply(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) { 44 51 Solution result = new Solution(binShape, useExtremePoints: true, stackingConstraints: useStackingConstraints); 45 52 IList<int> remainingIDs = new List<int>(permutation); -
trunk/sources/HeuristicLab.Problems.BinPacking/3.3/3D/ProblemBase.cs
r14162 r15230 175 175 public override bool Maximization { get { return true; } } 176 176 177 178 177 public override double Evaluate(Individual individual, IRandom random) { 179 178 var encodedSolutionCand = (TSol)individual[EncodedSolutionName]; … … 237 236 BinShape = data.BinShape; 238 237 var items = new ItemList<PackingItem>(data.Items); 239 items.Sort((x, y) => y.CompareTo(x));240 238 Items = items.AsReadOnly(); 241 239
Note: See TracChangeset
for help on using the changeset viewer.