- Timestamp:
- 07/21/17 11:29:08 (7 years ago)
- Location:
- stable
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
stable
- Property svn:mergeinfo changed
/trunk/sources merged: 14708-14709,14971,14978-14979,15167,15230,15233,15240-15241,15276
- Property svn:mergeinfo changed
-
stable/HeuristicLab.Problems.BinPacking
-
Property
svn:mergeinfo
set to
(toggle deleted branches)
/trunk/sources/HeuristicLab.Problems.BinPacking merged eligible /branches/1721-RandomForestPersistence/HeuristicLab.Problems.BinPacking 10321-10322 /branches/Algorithms.GradientDescent/HeuristicLab.Problems.BinPacking 5516-5520 /branches/Benchmarking/sources/HeuristicLab.Problems.BinPacking 6917-7005 /branches/BinPackingExtension/HeuristicLab.Problems.BinPacking 14835-15229 /branches/CloningRefactoring/HeuristicLab.Problems.BinPacking 4656-4721 /branches/CodeEditor/HeuristicLab.Problems.BinPacking 11700-11806 /branches/DataAnalysis Refactoring/HeuristicLab.Problems.BinPacking 5471-5808 /branches/DataAnalysis SolutionEnsembles/HeuristicLab.Problems.BinPacking 5815-6180 /branches/DataAnalysis/HeuristicLab.Problems.BinPacking 4458-4459,4462,4464 /branches/DataPreprocessing/HeuristicLab.Problems.BinPacking 10085-11101 /branches/GP.Grammar.Editor/HeuristicLab.Problems.BinPacking 6284-6795 /branches/GP.Symbols (TimeLag, Diff, Integral)/HeuristicLab.Problems.BinPacking 5060 /branches/HLScript/HeuristicLab.Problems.BinPacking 10331-10358 /branches/HeuristicLab.DatasetRefactor/sources/HeuristicLab.Problems.BinPacking 11570-12508 /branches/HeuristicLab.Problems.DataAnalysis.Trading/HeuristicLab.Problems.BinPacking 6123-9799 /branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.BinPacking 11130-12721 /branches/HiveStatistics/sources/HeuristicLab.Problems.BinPacking 12440-12877 /branches/LogResidualEvaluator/HeuristicLab.Problems.BinPacking 10202-10483 /branches/NET40/sources/HeuristicLab.Problems.BinPacking 5138-5162 /branches/NSGA-II Changes/HeuristicLab.Problems.BinPacking 12033-12122 /branches/ParallelEngine/HeuristicLab.Problems.BinPacking 5175-5192 /branches/ProblemInstancesRegressionAndClassification/HeuristicLab.Problems.BinPacking 7568-7810 /branches/QAPAlgorithms/HeuristicLab.Problems.BinPacking 6350-6627 /branches/Restructure trunk solution/HeuristicLab.Problems.BinPacking 6828 /branches/RuntimeOptimizer/HeuristicLab.Problems.BinPacking 8943-9078 /branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.BinPacking 7787-8333 /branches/SlaveShutdown/HeuristicLab.Problems.BinPacking 8944-8956 /branches/SpectralKernelForGaussianProcesses/HeuristicLab.Problems.BinPacking 10204-10479 /branches/SuccessProgressAnalysis/HeuristicLab.Problems.BinPacking 5370-5682 /branches/Trunk/HeuristicLab.Problems.BinPacking 6829-6865 /branches/UnloadJobs/HeuristicLab.Problems.BinPacking 9168-9215 /branches/VNS/HeuristicLab.Problems.BinPacking 5594-5752 /branches/crossvalidation-2434/HeuristicLab.Problems.BinPacking 12948-12950 /branches/histogram/HeuristicLab.Problems.BinPacking 5959-6341 /branches/symbreg-factors-2650/HeuristicLab.Problems.BinPacking 14232-14825 /trunk/sources/HeuristicLab.Problems.TestFunctions.MultiObjective/HeuristicLab.Problems.BinPacking 14175
-
Property
svn:mergeinfo
set to
(toggle deleted branches)
-
stable/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs
r14966 r15278 20 20 #endregion 21 21 22 using System; 22 23 using System.Collections.Generic; 23 24 using System.Linq; … … 32 33 public class BinPacking3D : BinPacking<PackingPosition, PackingShape, PackingItem> { 33 34 35 [Storable] 36 public Dictionary<PackingPosition, Tuple<int, int, int>> ResidualSpace { get; protected set; } 37 34 38 public BinPacking3D(PackingShape binShape) 35 39 : base(binShape) { 36 ExtremePoints = new SortedSet<PackingPosition>();37 ExtremePoints.Add(binShape.Origin);40 ResidualSpace = new Dictionary<PackingPosition, Tuple<int,int,int>>(); 41 AddExtremePoint(binShape.Origin); 38 42 InitializeOccupationLayers(); 39 43 } … … 42 46 protected BinPacking3D(BinPacking3D original, Cloner cloner) 43 47 : base(original, cloner) { 44 this.ExtremePoints = new SortedSet<PackingPosition>(original.ExtremePoints.Select(p => cloner.Clone(p))); 48 this.ResidualSpace = new Dictionary<PackingPosition, Tuple<int, int, int>>(); 49 foreach (var o in original.ResidualSpace) 50 this.ResidualSpace.Add(cloner.Clone(o.Key), Tuple.Create(o.Value.Item1, o.Value.Item2, o.Value.Item3)); 45 51 } 46 52 public override IDeepCloneable Clone(Cloner cloner) { 47 53 return new BinPacking3D(this, cloner); 54 } 55 56 57 [StorableHook(HookType.AfterDeserialization)] 58 private void AfterDeserialization() { 59 // BackwardsCompatibility3.3 60 #region Backwards compatible code, remove with 3.4 61 if (ResidualSpace == null) 62 ResidualSpace = new Dictionary<PackingPosition, Tuple<int, int, int>>(); 63 #endregion 64 } 65 66 public override void PackItem(int itemID, PackingItem item, PackingPosition position) { 67 ResidualSpace.Remove(position); 68 base.PackItem(itemID, item, position); 48 69 } 49 70 … … 60 81 current = PackingPosition.MoveDown(current); 61 82 } 62 ExtremePoints.Add((PackingPosition)current.Clone());83 AddExtremePoint((PackingPosition)current.Clone()); 63 84 while (current.X > 0 && !IsPointOccupied(PackingPosition.MoveLeft(current))) { 64 85 current = PackingPosition.MoveLeft(current); 65 86 } 66 ExtremePoints.Add(current);87 AddExtremePoint(current); 67 88 68 89 //Traversing down the z-axis … … 71 92 current = PackingPosition.MoveBack(current); 72 93 } 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);94 AddExtremePoint((PackingPosition)current.Clone()); 95 while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) { 96 current = PackingPosition.MoveDown(current); 97 } 98 AddExtremePoint(current); 78 99 } 79 100 … … 86 107 current = PackingPosition.MoveLeft(current); 87 108 } 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);109 AddExtremePoint((PackingPosition)current.Clone()); 110 while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) { 111 current = PackingPosition.MoveDown(current); 112 } 113 AddExtremePoint(current); 93 114 94 115 //Traversing down the z-axis … … 97 118 current = PackingPosition.MoveBack(current); 98 119 } 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);120 AddExtremePoint((PackingPosition)current.Clone()); 121 while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) { 122 current = PackingPosition.MoveDown(current); 123 } 124 AddExtremePoint(current); 104 125 } 105 126 … … 112 133 current = PackingPosition.MoveLeft(current); 113 134 } 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);135 AddExtremePoint((PackingPosition)current.Clone()); 136 while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) { 137 current = PackingPosition.MoveDown(current); 138 } 139 AddExtremePoint(current); 119 140 120 141 //Traversing down the y-axis … … 123 144 current = PackingPosition.MoveDown(current); 124 145 } 125 ExtremePoints.Add((PackingPosition)current.Clone());146 AddExtremePoint((PackingPosition)current.Clone()); 126 147 while (current.X > 0 && !IsPointOccupied(PackingPosition.MoveLeft(current))) { 127 148 current = PackingPosition.MoveLeft(current); 128 149 } 129 ExtremePoints.Add(current); 150 AddExtremePoint(current); 151 } 152 } 153 154 private void AddExtremePoint(PackingPosition current) { 155 if (ExtremePoints.Add(current)) { 156 var tuple = Tuple.Create(BinShape.Width - current.X, BinShape.Height - current.Y, BinShape.Depth - current.Z); 157 ResidualSpace.Add(current, tuple); 130 158 } 131 159 } 132 160 133 161 public override PackingPosition FindExtremePointForItem(PackingItem item, bool rotated, bool stackingConstraints) { 134 135 162 PackingItem newItem = new PackingItem( 136 163 rotated ? item.Depth : item.Width, … … 139 166 item.TargetBin, item.Weight, item.Material); 140 167 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); 168 var ep = ExtremePoints.Where(x => IsPositionFeasible(newItem, x, stackingConstraints)).FirstOrDefault(); 169 if (ep != null) { 170 var result = new PackingPosition(ep.AssignedBin, ep.X, ep.Y, ep.Z, rotated); 152 171 return result; 153 172 } … … 155 174 } 156 175 157 public override PackingPosition FindPositionBySliding(PackingItem item, bool rotated) { 158 //TODO: does not support stacking constraints yet 176 public override bool IsPositionFeasible(PackingItem item, PackingPosition position, bool stackingConstraints) { 177 var feasible = base.IsPositionFeasible(item, position, stackingConstraints); 178 return feasible 179 && IsSupportedByAtLeastOnePoint(item, position) 180 && (!stackingConstraints || (IsStaticStable(item, position) && IsWeightSupported(item, position))); 181 } 182 183 public override PackingPosition FindPositionBySliding(PackingItem item, bool rotated, bool stackingConstraints) { 159 184 //Starting-position at upper right corner (=left bottom point of item-rectangle is at position item.width,item.height) 160 185 PackingPosition currentPosition = new PackingPosition(0, … … 163 188 BinShape.Depth - (rotated ? item.Width : item.Depth), rotated); 164 189 //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) )) {190 while (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition), stackingConstraints) 191 || IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints) 192 || IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition), stackingConstraints)) { 168 193 //Slide the item as far as possible to the left 169 while (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition) )170 || IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition) )) {194 while (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints) 195 || IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition), stackingConstraints)) { 171 196 //Slide the item as far as possible to the back 172 while (IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition) )) {197 while (IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition), stackingConstraints)) { 173 198 currentPosition = PackingPosition.MoveBack(currentPosition); 174 199 } 175 if (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition) ))200 if (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints)) 176 201 currentPosition = PackingPosition.MoveLeft(currentPosition); 177 202 } 178 if (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition) ))203 if (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition), stackingConstraints)) 179 204 currentPosition = PackingPosition.MoveDown(currentPosition); 180 205 } 181 206 182 return IsPositionFeasible(item, currentPosition ) ? currentPosition : null;183 } 184 185 public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items ) {207 return IsPositionFeasible(item, currentPosition, stackingConstraints) ? currentPosition : null; 208 } 209 210 public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) { 186 211 var temp = new List<int>(sequence); 187 212 for (int i = 0; i < temp.Count; i++) { 188 213 var item = items[temp[i]]; 189 var position = FindPositionBySliding(item, false );214 var position = FindPositionBySliding(item, false, stackingConstraints); 190 215 if (position != null) { 191 216 PackItem(temp[i], item, position); … … 194 219 } 195 220 } 196 public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, Dictionary<int, bool> rotationArray ) {221 public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, Dictionary<int, bool> rotationArray, bool stackingConstraints) { 197 222 var temp = new List<int>(sequence); 198 223 for (int i = 0; i < temp.Count; i++) { 199 224 var item = items[temp[i]]; 200 var position = FindPositionBySliding(item, rotationArray[i] );225 var position = FindPositionBySliding(item, rotationArray[i], stackingConstraints); 201 226 if (position != null) { 202 227 PackItem(temp[i], item, position); … … 212 237 if (positionFound != null) { 213 238 PackItem(itemID, item, positionFound); 239 if (Items.Count > 1) 240 UpdateResidualSpace(item, positionFound); 214 241 sequence.Remove(itemID); 215 242 } … … 227 254 } 228 255 } 229 230 256 public override int ShortestPossibleSideFromPoint(PackingPosition position) { 231 257 … … 297 323 } 298 324 299 300 325 protected override void InitializeOccupationLayers() { 301 326 for (int i = 0; i * 10 <= BinShape.Depth; i += 1) { … … 320 345 for (int i = z1; i <= z2; i++) 321 346 result.AddRange(OccupationLayers[i]); 322 323 347 return result; 324 348 } 349 350 public void UpdateResidualSpace(PackingItem item, PackingPosition pos) { 351 foreach (var ep in ExtremePoints) { 352 if (ep.Z >= pos.Z && ep.Z <= pos.Z + item.Depth) { 353 if (ep.X <= pos.X && ep.Y > pos.Y && ep.Y < pos.Y + item.Height) { 354 var diff = pos.X - ep.X; 355 var newRSX = ResidualSpace[ep].Item1 < diff ? ResidualSpace[ep].Item1 : diff; 356 ResidualSpace[ep] = Tuple.Create(newRSX, ResidualSpace[ep].Item2, ResidualSpace[ep].Item3); 357 } 358 if (ep.Y <= pos.Y && ep.X > pos.X && ep.X < pos.X + item.Width) { 359 var diff = pos.Y - ep.Y; 360 var newRSY = ResidualSpace[ep].Item2 < diff ? ResidualSpace[ep].Item2 : diff; 361 ResidualSpace[ep] = Tuple.Create(ResidualSpace[ep].Item1, newRSY, ResidualSpace[ep].Item3); 362 } 363 } 364 if (ep.Z <= pos.Z && 365 ep.Y > pos.Y && ep.Y < pos.Y + item.Height && 366 ep.X > pos.X && ep.X < pos.X + item.Width) { 367 var diff = pos.Z - ep.Z; 368 var newRSZ = ResidualSpace[ep].Item3 < diff ? ResidualSpace[ep].Item3 : diff; 369 ResidualSpace[ep] = Tuple.Create(ResidualSpace[ep].Item1, ResidualSpace[ep].Item2, newRSZ); 370 } 371 } 372 return; 373 } 325 374 } 326 327 375 }
Note: See TracChangeset
for help on using the changeset viewer.