Changeset 15646 for branches/2817-BinPackingSpeedup
- Timestamp:
- 01/24/18 13:17:00 (7 years ago)
- Location:
- branches/2817-BinPackingSpeedup
- Files:
-
- 3 added
- 16 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/Container3DView.xaml.cs
r15617 r15646 141 141 var selectedModel = new GeometryModel3D { Geometry = new MeshGeometry3D(), Material = material }; 142 142 AddSolidCube((MeshGeometry3D)selectedModel.Geometry, selectedPos.X, selectedPos.Y, selectedPos.Z, 143 selectedItem.Value. DepthInView,143 selectedItem.Value.WidthInView, 144 144 selectedItem.Value.HeightInView, 145 145 selectedItem.Value.DepthInView); -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Algorithms/ExtremePointAlgorithm.cs
r15617 r15646 202 202 /// <param name="token"></param> 203 203 /// <returns></returns> 204 private Tuple<Solution, double, SortingMethod?, FittingMethod?, ExtremePointCreationMethod?> 205 GetBest(PackingShape bin, 206 IList<PackingItem> items, 207 SortingMethod[] sortings, 204 private Tuple<Solution, double, SortingMethod?, FittingMethod?, ExtremePointCreationMethod?> 205 GetBest(PackingShape bin, 206 IList<PackingItem> items, 207 SortingMethod[] sortings, 208 208 FittingMethod[] fittings, 209 209 ExtremePointCreationMethod[] epCreationMethods, … … 222 222 }; 223 223 Permutation sortedItems; 224 224 225 225 if (SortByMaterialParameter.Value.Value) { 226 226 sortedItems = SortItemsByMaterialAndSortingMethod(bin, items, sort, DeltaParameter.Value.Value); … … 229 229 } 230 230 231 var result= Optimize(new OptimaizationParamters() {231 var solution = Optimize(new OptimaizationParamters() { 232 232 SortedItems = sortedItems, 233 233 Bin = bin, … … 238 238 ExtremePointGeneration = epCreation 239 239 }); 240 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 249 250 var x = Problem.SolutionEvaluator.Evaluate1(solution); 251 252 /* 241 253 if (double.IsNaN(result.Item2) || double.IsInfinity(result.Item2)) { 242 254 continue; … … 250 262 bestEPCreation = epCreation; 251 263 } 264 return true;*/ 265 252 266 if (token.IsCancellationRequested) { 253 267 return Tuple.Create(bestSolution, best, bestSorting, bestFitting, bestEPCreation); … … 267 281 /// <param name="parameters"></param> 268 282 /// <returns></returns> 269 private static Tuple<Solution, double> Optimize(OptimaizationParamters parameters) {270 283 private static Solution Optimize(OptimaizationParamters parameters) { 284 271 285 var sol = parameters.Decoder.Decode(parameters.SortedItems, parameters.Bin, parameters.Items, parameters.StackingConstraints); 272 var fit = parameters.Evaluator.Evaluate(sol);273 274 return Tuple.Create(sol, fit);286 //var fit = parameters.Evaluator.Evaluate(sol); 287 288 return sol; //Tuple.Create(sol, fit); 275 289 } 276 290 … … 284 298 public ExtremePointCreationMethod ExtremePointGeneration { get; set; } 285 299 } 286 300 287 301 288 302 /// <summary> 289 303 /// Returns a new permutation of the given items depending on the sorting method 304 /// </summary> 305 /// <param name="bin"></param> 306 /// <param name="items"></param> 307 /// <param name="sortingMethod"></param> 308 /// <param name="delta"></param> 309 /// <returns></returns> 310 private Permutation SortItemsByMaterialAndSortingMethod(PackingShape bin, IList<PackingItem> items, SortingMethod sortingMethod, double delta) { 311 Permutation sorted = null; 312 313 switch (sortingMethod) { 314 case SortingMethod.Given: 315 sorted = new Permutation(PermutationTypes.Absolute, Enumerable.Range(0, items.Count).ToArray()); 316 break; 317 case SortingMethod.VolumeHeight: 318 sorted = items.SortByVolumeHeight(); 319 break; 320 case SortingMethod.HeightVolume: 321 sorted = items.SortByMaterialHeightVolume(); 322 break; 323 case SortingMethod.AreaHeight: 324 sorted = items.SortByMaterialAreaHeight(); 325 break; 326 case SortingMethod.HeightArea: 327 sorted = items.SortByMaterialHeightArea(); 328 break; 329 case SortingMethod.ClusteredAreaHeight: 330 sorted = items.SortByMaterialClusteredAreaHeight(bin, delta); 331 break; 332 case SortingMethod.ClusteredHeightArea: 333 sorted = items.SortByMaterialClusteredHeightArea(bin, delta); 334 break; 335 default: 336 throw new ArgumentException("Unknown sorting method: " + sortingMethod); 337 } 338 return sorted; 339 } 340 341 /// <summary> 342 /// Returns a new permutation of the given items depending on the material and sorting method 290 343 /// </summary> 291 344 /// <param name="bin"></param> … … 296 349 private Permutation SortItemsBySortingMethod(PackingShape bin, IList<PackingItem> items, SortingMethod sortingMethod, double delta) { 297 350 Permutation sorted = null; 298 351 299 352 switch (sortingMethod) { 300 353 case SortingMethod.Given: … … 305 358 break; 306 359 case SortingMethod.HeightVolume: 307 sorted = items.SortBy MaterialHeightVolume();360 sorted = items.SortByHeightVolume(); 308 361 break; 309 362 case SortingMethod.AreaHeight: 310 sorted = items.SortBy MaterialAreaHeight();363 sorted = items.SortByAreaHeight(); 311 364 break; 312 365 case SortingMethod.HeightArea: 313 sorted = items.SortBy MaterialHeightArea();366 sorted = items.SortByHeightArea(); 314 367 break; 315 368 case SortingMethod.ClusteredAreaHeight: 316 sorted = items.SortBy MaterialClusteredAreaHeight(bin, delta);369 sorted = items.SortByClusteredAreaHeight(bin, delta); 317 370 break; 318 371 case SortingMethod.ClusteredHeightArea: 319 sorted = items.SortBy MaterialClusteredHeightArea(bin, delta);372 sorted = items.SortByClusteredHeightArea(bin, delta); 320 373 break; 321 374 default: … … 324 377 return sorted; 325 378 } 326 327 /// <summary>328 /// Returns a new permutation of the given items depending on the material and sorting method329 /// </summary>330 /// <param name="bin"></param>331 /// <param name="items"></param>332 /// <param name="sortingMethod"></param>333 /// <param name="delta"></param>334 /// <returns></returns>335 private Permutation SortItemsByMaterialAndSortingMethod(PackingShape bin, IList<PackingItem> items, SortingMethod sortingMethod, double delta) {336 Permutation sorted = null;337 338 switch (sortingMethod) {339 case SortingMethod.Given:340 sorted = new Permutation(PermutationTypes.Absolute, Enumerable.Range(0, items.Count).ToArray());341 break;342 case SortingMethod.VolumeHeight:343 sorted = items.SortByVolumeHeight();344 break;345 case SortingMethod.HeightVolume:346 sorted = items.SortByHeightVolume();347 break;348 case SortingMethod.AreaHeight:349 sorted = items.SortByAreaHeight();350 break;351 case SortingMethod.HeightArea:352 sorted = items.SortByHeightArea();353 break;354 case SortingMethod.ClusteredAreaHeight:355 sorted = items.SortByClusteredAreaHeight(bin, delta);356 break;357 case SortingMethod.ClusteredHeightArea:358 sorted = items.SortByClusteredHeightArea(bin, delta);359 break;360 default:361 throw new ArgumentException("Unknown sorting method: " + sortingMethod);362 }363 return sorted;364 }365 379 } 366 380 } -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs
r15617 r15646 34 34 [StorableClass] 35 35 public class BinPacking3D : BinPacking<PackingPosition, PackingShape, PackingItem> { 36 36 37 37 [Storable] 38 38 public IDictionary<PackingPosition, IEnumerable<ResidualSpace>> ExtremePoints { get; protected set; } … … 42 42 : base(binShape) { 43 43 ExtremePoints = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>(); 44 45 ExtremePoints.Add(binShape.Origin, new List<ResidualSpace>() { ResidualSpace.Create(binShape.Width, binShape.Height, binShape.Depth)});44 45 ExtremePoints.Add(binShape.Origin, new List<ResidualSpace>() { ResidualSpace.Create(binShape.Width, binShape.Height, binShape.Depth) }); 46 46 } 47 47 … … 66 66 } 67 67 68 68 69 69 70 70 /// <summary> … … 96 96 97 97 98 /* 99 /// <summary> 100 /// Updates the extreme points of the bin. 101 /// As there is no need to project the extreme points to the next side of an item, the extreme points are only generated for the current item. 102 /// </summary> 103 /// <param name="item"></param> 104 /// <param name="position"></param> 105 private void UpdateExtremePointsWithStackingConstriants(PackingItem newItem, PackingPosition position) { 106 int newWidth = position.Rotated ? newItem.Depth : newItem.Width; 107 int newDepth = position.Rotated ? newItem.Width : newItem.Depth; 108 var ep1 = new PackingPosition(position.AssignedBin, position.X + newWidth, position.Y, position.Z); 109 var ep2 = new PackingPosition(position.AssignedBin, position.X, position.Y + newItem.Height, position.Z); 110 var ep3 = new PackingPosition(position.AssignedBin, position.X, position.Y, position.Z + newDepth); 111 AddExtremePoint(ep1); 112 AddExtremePoint(ep2); 113 AddExtremePoint(ep3); 114 }*/ 115 116 98 /* 99 /// <summary> 100 /// Updates the extreme points of the bin. 101 /// As there is no need to project the extreme points to the next side of an item, the extreme points are only generated for the current item. 102 /// </summary> 103 /// <param name="item"></param> 104 /// <param name="position"></param> 105 private void UpdateExtremePointsWithStackingConstriants(PackingItem newItem, PackingPosition position) { 106 int newWidth = position.Rotated ? newItem.Depth : newItem.Width; 107 int newDepth = position.Rotated ? newItem.Width : newItem.Depth; 108 var ep1 = new PackingPosition(position.AssignedBin, position.X + newWidth, position.Y, position.Z); 109 var ep2 = new PackingPosition(position.AssignedBin, position.X, position.Y + newItem.Height, position.Z); 110 var ep3 = new PackingPosition(position.AssignedBin, position.X, position.Y, position.Z + newDepth); 111 AddExtremePoint(ep1); 112 AddExtremePoint(ep2); 113 AddExtremePoint(ep3); 114 }*/ 115 116 117 #region MassPoint 118 119 /// <summary> 120 /// This property contains the value of the mass point for the current bin packing. 121 /// </summary> 122 public Tuple<double, double, double> MassPoint { get { return CalculateMassPoint(); } } 123 124 private Tuple<double, double, double> CalculateMassPoint() { 125 var packingMassPoint = new { X = 0.0, Y = 0.0, Z = 0.0 }; 126 var totalWeight = 0.0; 127 foreach (var item in Items) { 128 var position = Positions[item.Key]; 129 var w = item.Value.Width; 130 var h = item.Value.Height; 131 var d = item.Value.Depth; 132 133 var massPoint = new { X = position.X + w / 2.0, Y = position.Y + h / 2.0, Z = position.Z + d / 2.0 }; 134 var weight = Math.Max(item.Value.Weight, 1); 135 if (packingMassPoint == null) { 136 packingMassPoint = massPoint; 137 totalWeight += weight; 138 } else { 139 var newTotalWeight = totalWeight + weight; 140 packingMassPoint = new { 141 X = (massPoint.X * weight + packingMassPoint.X * totalWeight) / newTotalWeight, 142 Y = (massPoint.Y * weight + packingMassPoint.Y * totalWeight) / newTotalWeight, 143 Z = (massPoint.Z * weight + packingMassPoint.Z * totalWeight) / newTotalWeight 144 }; 145 totalWeight = newTotalWeight; 146 } 147 } 148 149 return Tuple.Create<double, double, double>(packingMassPoint.X, packingMassPoint.Y, packingMassPoint.Z); 150 } 151 #endregion 117 152 118 153 #region Position feasability … … 128 163 /// <returns></returns> 129 164 public override bool IsPositionFeasible(PackingItem item, PackingPosition position, bool stackingConstraints) { 130 //var b1 = CheckItemDimensions(item, position); 131 var b2 = ItemCanBePlaced(item, position); 132 var b3 = CheckStackingConstraints(item, position, stackingConstraints); 133 134 return b2 && b3; 135 } 165 return ItemCanBePlaced(item, position) && CheckStackingConstraints(item, position, stackingConstraints); 166 } 167 168 136 169 137 170 /// <summary> … … 142 175 /// <returns></returns> 143 176 private bool ItemCanBePlaced(PackingItem givenItem, PackingPosition givenItemPosition) { 144 var width = givenItemPosition.Rotated ? givenItem.Depth : givenItem.Width;145 var depth = givenItemPosition.Rotated ? givenItem.Width : givenItem.Depth;146 177 // Check if the boundings of the bin would injured 147 if (givenItemPosition.X + width > BinShape.Width ||178 if (givenItemPosition.X + givenItem.Width > BinShape.Width || 148 179 givenItemPosition.Y + givenItem.Height > BinShape.Height || 149 givenItemPosition.Z + depth > BinShape.Depth) {180 givenItemPosition.Z + givenItem.Depth > BinShape.Depth) { 150 181 return false; 151 182 } … … 201 232 private bool HasOnePointWithAnItemBelow(PackingItem item, PackingPosition position) { 202 233 bool p1, p2, p3, p4; 203 PointsLiesOnAn Item(item, position, out p1, out p2, out p3, out p4);234 PointsLiesOnAnStackableItem(item, position, out p1, out p2, out p3, out p4); 204 235 205 236 return p1 || p2 || p3 || p4; … … 215 246 public override bool IsStaticStable(PackingItem item, PackingPosition position) { 216 247 bool p1, p2, p3, p4; 217 PointsLiesOnAn Item(item, position, out p1, out p2, out p3, out p4);248 PointsLiesOnAnStackableItem(item, position, out p1, out p2, out p3, out p4); 218 249 return p1 && p2 && p3 && p4; 219 250 } … … 234 265 /// <param name="p3"></param> 235 266 /// <param name="p4"></param> 236 private void PointsLiesOnAn Item(PackingItem item, PackingPosition position, out bool p1, out bool p2, out bool p3, out bool p4) {267 private void PointsLiesOnAnStackableItem(PackingItem item, PackingPosition position, out bool p1, out bool p2, out bool p3, out bool p4) { 237 268 IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP1; 238 269 IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP2; … … 242 273 GetItemsUnderItemWithContact(item, position, out itemsP1, out itemsP2, out itemsP3, out itemsP4); 243 274 244 p1 = itemsP1.Where(x => position.X < x.Item1.X + x.Item2.Width && position.Z < x.Item1.Z + x.Item2.Depth).Any();245 p2 = itemsP2.Where(x => position.X + item.Width > x.Item1.X && position.Z < x.Item1.Z + x.Item2.Depth).Any();246 p3 = itemsP3.Where(x => position.X + item.Width > x.Item1.X && position.Z + item.Depth > x.Item1.Z).Any();247 p4 = itemsP4.Where(x => position.X < x.Item1.X + x.Item2.Width && position.Z + item.Depth > x.Item1.Z).Any();275 p1 = itemsP1.Where(x => x.Item2.IsStackabel && position.X < x.Item1.X + x.Item2.Width && position.Z < x.Item1.Z + x.Item2.Depth).Any(); 276 p2 = itemsP2.Where(x => x.Item2.IsStackabel && position.X + item.Width > x.Item1.X && position.Z < x.Item1.Z + x.Item2.Depth).Any(); 277 p3 = itemsP3.Where(x => x.Item2.IsStackabel && position.X + item.Width > x.Item1.X && position.Z + item.Depth > x.Item1.Z).Any(); 278 p4 = itemsP4.Where(x => x.Item2.IsStackabel && position.X < x.Item1.X + x.Item2.Width && position.Z + item.Depth > x.Item1.Z).Any(); 248 279 } 249 280 … … 315 346 316 347 #region Get items 317 348 318 349 private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelow(PackingPosition pos) { 319 350 var line = new Line3D(pos, new Vector3D(0, 1, 0)); -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Evaluators/BinUtilizationEvaluator.cs
r15617 r15646 67 67 } 68 68 69 private static int GetBinCount(Solution solution) { 70 return solution.NrOfBins; 71 } 72 73 private static int GetNumberOfResidualSpaces(Solution solution) { 74 var cnt = 0; 75 foreach (var binPacking in solution.Bins) { 76 foreach (var item in ((BinPacking3D)binPacking).ExtremePoints) { 77 cnt += item.Value.Count(); 78 } 79 } 80 return cnt; 81 } 82 83 public Tuple<int, double, int> Evaluate1(Solution solution) { 84 85 86 var res = Tuple.Create<int, double, int>( 87 GetBinCount(solution), 88 CalculateBinUtilizationFirstBin(solution), 89 GetNumberOfResidualSpaces(solution) 90 ); 91 92 return res; 93 } 94 95 private static double CalculateBinUtilizationFirstBin(Solution solution) { 96 if (solution.NrOfBins <= 0) { 97 return 0.0; 98 } 99 100 double totalUsedSpace = 0; 101 double totalUsableSpace = 0; 102 103 totalUsableSpace += solution.Bins[0].BinShape.Volume; 104 totalUsedSpace += solution.Bins[0].Items.Sum(kvp => kvp.Value.Volume); 105 106 return totalUsedSpace / totalUsableSpace; 107 } 108 109 69 110 #endregion 70 111 } -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Evaluators/IEvaluator.cs
r15617 r15646 21 21 22 22 using HeuristicLab.Core; 23 using System; 23 24 24 25 namespace HeuristicLab.Problems.BinPacking3D { … … 34 35 /// <returns>Returns the value of the evaluated solution depending on the implementation</returns> 35 36 double Evaluate(Solution solution); 37 38 /// <summary> 39 /// Returns a tuple of (number of bins, bin utilization, number of residual spaces) 40 /// </summary> 41 /// <param name="solution"></param> 42 /// <returns></returns> 43 Tuple<int, double, int> Evaluate1(Solution solution); 36 44 } 37 45 } -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Evaluators/PackingRatioEvaluator.cs
r15617 r15646 84 84 } 85 85 86 private static int GetBinCount(Solution solution) { 87 return solution.NrOfBins; 88 } 89 90 private static int GetNumberOfResidualSpaces(Solution solution) { 91 var cnt = 0; 92 foreach (var binPacking in solution.Bins) { 93 foreach (var item in ((BinPacking3D)binPacking).ExtremePoints) { 94 cnt += item.Value.Count(); 95 } 96 } 97 return cnt; 98 } 99 100 public Tuple<int, double, int> Evaluate1(Solution solution) { 101 102 103 var res = Tuple.Create<int, double, int>( 104 GetBinCount(solution), 105 CalculateBinUtilizationFirstBin(solution), 106 GetNumberOfResidualSpaces(solution) 107 ); 108 109 return res; 110 } 111 112 private static double CalculateBinUtilizationFirstBin(Solution solution) { 113 if (solution.NrOfBins <= 0) { 114 return 0.0; 115 } 116 117 double totalUsedSpace = 0; 118 double totalUsableSpace = 0; 119 120 totalUsableSpace += solution.Bins[0].BinShape.Volume; 121 totalUsedSpace += solution.Bins[0].Items.Sum(kvp => kvp.Value.Volume); 122 123 return totalUsedSpace / totalUsableSpace; 124 } 125 86 126 #endregion 87 127 } -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/LineProjectionBasedEPCreator.cs
r15617 r15646 166 166 protected override void GenerateNewExtremePointsForItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) { 167 167 PointProjectionForNewItem(binPacking, newItem, position); 168 EdgeProjectionForNewItem(binPacking, newItem, position);168 //EdgeProjectionForNewItem(binPacking, newItem, position); 169 169 } 170 170 -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/ThreeDInstanceParser.cs
r15617 r15646 58 58 PackingItem item = new PackingItem(width, height, length, Bin, weight, material) { 59 59 RotateEnabled = rotate == 0 ? false : true, 60 TiltEnabled = tilt == 0 ? false : true 60 TiltEnabled = tilt == 0 ? false : true, 61 IsStackabel = stack == 0 ? false : true 61 62 }; 62 63 Items.Add(item); -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerMinRSLeft.cs
r15618 r15646 45 45 #endregion 46 46 47 48 47 49 public BinPackerMinRSLeft() : base() { } 48 50 51 /// <summary> 52 /// This proportion of the residual space left to the item height is used for deciding if a not stackable item should be placed. 53 /// </summary> 54 private const double NOT_STACKABLE_RS_LEFT_TO_ITEM_HEIGHT_PROPORTION = 1.1; 49 55 50 56 public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, ExtremePointPruningMethod epPruningMethod, bool useStackingConstraints) { … … 57 63 BinPacking3D packingBin = new BinPacking3D(binShape); 58 64 PackRemainingItems(ref remainingIds, ref packingBin, workingItems, epCreationMethod, useStackingConstraints); 59 packingList.Add(packingBin); 60 } 61 } catch (BinPacking3DException e) {62 } 63 65 packingList.Add(packingBin); 66 } 67 } catch (BinPacking3DException e) { 68 } 69 64 70 ExtremePointPruningFactory.CreatePruning().PruneExtremePoints(epPruningMethod, packingList); 71 65 72 return packingList; 66 73 } … … 76 83 protected void PackRemainingItems(ref IList<int> remainingIds, ref BinPacking3D packingBin, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, bool useStackingConstraints) { 77 84 IExtremePointCreator extremePointCreator = ExtremePointCreatorFactory.CreateExtremePointCreator(epCreationMethod, useStackingConstraints); 85 var remainingNotStackableItems = new List<int>(); 78 86 foreach (var itemId in new List<int>(remainingIds)) { 79 87 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 88 89 // If an item is not stackable it should have a minimum waste of the residual space. 90 // As long as there are stackable items left, put the non stackable items into a collection 91 // and try to find positions where they don't waste too much space. 92 // If there are no stackable items left the non stackable have to be treated as a stackable one. 93 if (!item.IsStackabel && useStackingConstraints && remainingIds.Where(x => items[x].IsStackabel).Any()) { 94 remainingNotStackableItems.Add(itemId); 95 } else { 96 PackingPosition position = FindPackingPositionForItem(packingBin, item, useStackingConstraints); 97 // if a valid packing position could be found, the current item can be added to the given bin 98 if (position != null) { 99 PackItem(packingBin, itemId, item, position, extremePointCreator, useStackingConstraints); 100 remainingIds.Remove(itemId); 101 } 102 } 103 104 // try to find a valid position for a non stackable item 105 var stackableLeft = remainingIds.Where(x => items[x].IsStackabel).Any(); 106 foreach (var saId in new List<int>(remainingNotStackableItems)) { 107 item = items[saId]; 108 PackingPosition position = null; 109 if (stackableLeft) { 110 position = FindPackingPositionForNotStackableItem(packingBin, item, useStackingConstraints); 111 } else { 112 position = FindPackingPositionForItem(packingBin, item, useStackingConstraints); 113 } 114 115 if (position != null) { 116 PackItem(packingBin, saId, item, position, extremePointCreator, useStackingConstraints); 117 remainingIds.Remove(saId); 118 remainingNotStackableItems.Remove(saId); 119 } 120 } 121 122 } 123 } 124 125 /// <summary> 126 /// Tries to find a valid position for a non stackable item. 127 /// Positions will only be valid if the height difference of its residual space is smaller then the hight of the item. 128 /// </summary> 129 /// <param name="packingBin"></param> 130 /// <param name="packingItem"></param> 131 /// <param name="useStackingConstraints"></param> 132 /// <returns></returns> 133 private PackingPosition FindPackingPositionForNotStackableItem(BinPacking3D packingBin, PackingItem packingItem, bool useStackingConstraints) { 134 if (!CheckItemDimensions(packingBin, packingItem)) { 135 throw new BinPacking3DException($"The dimensions of the given item exceeds the bin dimensions. " + 136 $"Bin: ({packingBin.BinShape.Width} {packingBin.BinShape.Depth} {packingBin.BinShape.Height})" + 137 $"Item: ({packingItem.Width} {packingItem.Depth} {packingItem.Height})"); 138 } 139 var rsds = CalculateResidalSpaceDifferences(packingBin, packingItem, useStackingConstraints).ToList(); 140 var rsd = rsds.Where(x => x != null && (x.Y / (double)x.Item.Height) < NOT_STACKABLE_RS_LEFT_TO_ITEM_HEIGHT_PROPORTION).OrderByDescending(x => x.Y % x.Item.Height).FirstOrDefault(); 141 142 if (rsd == null) { 143 return null; 144 } 145 146 packingItem.Rotated = rsd.Item.Rotated; 147 packingItem.Tilted = rsd.Item.Tilted; 148 return rsd.Position; 149 } 150 90 151 protected override PackingPosition FindPackingPositionForItem(BinPacking3D packingBin, PackingItem packingItem, bool useStackingConstraints) { 91 152 if (!CheckItemDimensions(packingBin, packingItem)) { … … 95 156 } 96 157 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 158 var rsd = CalculateResidalSpaceDifferences(packingBin, packingItem, useStackingConstraints).Where(x => x != null).FirstOrDefault(); 159 113 160 if (rsd == null) { 114 161 return null; … … 120 167 } 121 168 169 /// <summary> 170 /// 171 /// </summary> 172 /// <param name="packingBin"></param> 173 /// <param name="packingItem"></param> 174 /// <param name="useStackingConstraints"></param> 175 /// <returns></returns> 176 private SortedSet<ResidualSpaceDifference> CalculateResidalSpaceDifferences(BinPacking3D packingBin, PackingItem packingItem, bool useStackingConstraints) { 177 var rsds = new SortedSet<ResidualSpaceDifference>(); 178 179 rsds.Add(FindResidualSpaceDifferenceForItem(packingBin, packingItem, useStackingConstraints, rotated: false, tilted: false)); 180 181 if (packingItem.TiltEnabled) { 182 rsds.Add(FindResidualSpaceDifferenceForItem(packingBin, packingItem, useStackingConstraints, rotated: false, tilted: true)); 183 } 184 if (packingItem.RotateEnabled) { 185 rsds.Add(FindResidualSpaceDifferenceForItem(packingBin, packingItem, useStackingConstraints, rotated: true, tilted: false)); 186 } 187 if (packingItem.RotateEnabled && packingItem.TiltEnabled) { 188 rsds.Add(FindResidualSpaceDifferenceForItem(packingBin, packingItem, useStackingConstraints, rotated: true, tilted: true)); 189 } 190 return rsds; 191 } 192 193 /// <summary> 194 /// 195 /// </summary> 196 /// <param name="packingBin"></param> 197 /// <param name="packingItem"></param> 198 /// <param name="useStackingConstraints"></param> 199 /// <param name="rotated"></param> 200 /// <param name="tilted"></param> 201 /// <returns></returns> 122 202 protected ResidualSpaceDifference FindResidualSpaceDifferenceForItem(BinPacking3D packingBin, PackingItem packingItem, bool useStackingConstraints, bool rotated, bool tilted) { 123 203 PackingItem newItem = new PackingItem(packingItem) { … … 125 205 Tilted = tilted 126 206 }; 127 207 128 208 var rsds = new SortedSet<ResidualSpaceDifference>(); 129 130 209 foreach (var ep in packingBin.ExtremePoints) { 131 210 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 } 211 foreach (var rs in ep.Value) { 212 var rsd = ResidualSpaceDifference.Create(position, newItem, rs); 213 if (rsd != null) { 214 rsds.Add(rsd); 138 215 } 139 216 } 140 217 } 141 return rsds. FirstOrDefault();142 } 143 218 return rsds.Where(rsd => packingBin.IsPositionFeasible(rsd.Item, rsd.Position, useStackingConstraints)).FirstOrDefault(); 219 } 220 144 221 protected override bool CheckItemDimensions(BinPacking3D packingBin, PackingItem item) { 145 222 bool ok = false; … … 167 244 OriginalWidth = width, 168 245 OriginalHeight = height, 169 OriginalDepth = 246 OriginalDepth = depth 170 247 }); 171 248 } … … 212 289 if (x != 0) { 213 290 return x; 214 } else if (y != 0 291 } else if (y != 0) { 215 292 return y; 216 293 } else if (z != 0) { -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/PackingItem.cs
r15617 r15646 43 43 get { return (IFixedValueParameter<IntValue>)Parameters["Material"]; } 44 44 } 45 45 46 46 public PackingShape TargetBin { 47 47 get { return TargetBinParameter.Value; } … … 60 60 61 61 62 public IFixedValueParameter<DoubleValue> SupportedWeightParameter { 63 get { return (IFixedValueParameter<DoubleValue>)Parameters["SupportedWeight"]; } 64 } 65 public double SupportedWeight { 66 get { return SupportedWeightParameter.Value.Value; } 67 set { SupportedWeightParameter.Value.Value = value; } 68 } 69 70 public IValueParameter<BoolValue> IsStackableParameter { 71 get { return (IValueParameter<BoolValue>)Parameters["IsStackable"]; } 72 } 73 74 /// <summary> 75 /// Indicates that another item can be stacked on the current one. 76 /// </summary> 77 public bool IsStackabel { 78 get { return IsStackableParameter.Value.Value; } 79 set { IsStackableParameter.Value.Value = value; } 80 } 81 62 82 public IValueParameter<BoolValue> RotateEnabledParameter { 63 83 get { return (IValueParameter<BoolValue>)Parameters["RotateEnabled"]; } … … 75 95 get { return (IValueParameter<BoolValue>)Parameters["Tilted"]; } 76 96 } 77 97 78 98 /// <summary> 79 99 /// Enables that the current item can be rotated. … … 110 130 set { TiltedParameter.Value.Value = value; } 111 131 } 112 132 113 133 public IFixedValueParameter<IntValue> LoadSecuringHeightParameter { 114 134 get { return (IFixedValueParameter<IntValue>)Parameters["LoadSecuringHeight"]; } 115 135 } 116 136 117 137 public IFixedValueParameter<IntValue> LoadSecuringWidthParameter { 118 138 get { return (IFixedValueParameter<IntValue>)Parameters["LoadSecuringWidth"]; } … … 195 215 return WidthParameter.Value.Value; 196 216 } 197 } 217 } 198 218 } 199 219 … … 255 275 set { DepthParameter.Value.Value = value; } 256 276 } 257 277 258 278 public bool SupportsStacking(IPackingItem other) { 259 279 return ((other.Material < this.Material) || (other.Material.Equals(this.Material) && other.Weight <= this.Weight)); … … 273 293 Parameters.Add(new FixedValueParameter<DoubleValue>("Weight")); 274 294 Parameters.Add(new FixedValueParameter<IntValue>("Material")); 295 296 Parameters.Add(new FixedValueParameter<DoubleValue>("SupportedWeight")); 297 275 298 Parameters.Add(new FixedValueParameter<BoolValue>("RotateEnabled")); 276 299 Parameters.Add(new FixedValueParameter<BoolValue>("Rotated")); 277 300 Parameters.Add(new FixedValueParameter<BoolValue>("TiltEnabled")); 278 301 Parameters.Add(new FixedValueParameter<BoolValue>("Tilted")); 279 302 Parameters.Add(new FixedValueParameter<BoolValue>("IsStackable")); 303 280 304 Parameters.Add(new FixedValueParameter<IntValue>("LoadSecuringHeight")); 281 305 Parameters.Add(new FixedValueParameter<IntValue>("LoadSecuringWidth")); 282 306 Parameters.Add(new FixedValueParameter<IntValue>("LoadSecuringDepth")); 307 308 IsStackabel = true; 283 309 284 310 RegisterEvents(); … … 294 320 295 321 public PackingItem(int width, int height, int depth, PackingShape targetBin, double weight, int material) 296 : this(width, height, depth, targetBin) { 322 : this(width, height, depth, targetBin) { 297 323 this.Weight = weight; 298 324 this.Material = material; 299 325 } 300 326 301 302 303 public PackingItem(PackingItem packingItem) 304 : this() { 327 328 329 public PackingItem(PackingItem packingItem) : this() { 305 330 OriginalWidth = packingItem.OriginalWidth; 306 331 OriginalHeight = packingItem.OriginalHeight; 307 OriginalDepth = 332 OriginalDepth = packingItem.OriginalDepth; 308 333 TargetBin = (PackingShape)packingItem.TargetBin.Clone(); 309 334 Weight = packingItem.Weight; … … 311 336 Rotated = packingItem.Rotated; 312 337 Tilted = packingItem.Tilted; 338 IsStackabel = packingItem.IsStackabel; 313 339 314 340 LoadSecuringDepth = packingItem.LoadSecuringDepth; … … 337 363 return string.Format("CuboidPackingItem ({0}, {1}, {2}; weight={3}, mat={4})", this.Width, this.Height, this.Depth, this.Weight, this.Material); 338 364 } 339 365 340 366 } 341 367 } -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Solution.cs
r15617 r15646 24 24 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; 25 25 using HeuristicLab.Problems.BinPacking; 26 using System; 26 27 27 28 namespace HeuristicLab.Problems.BinPacking3D { … … 39 40 return new Solution(this, cloner); 40 41 } 42 43 public bool IsBetterThan(Solution other, IEvaluator evaluator, bool problemMaximization = true) { 44 var evaluatedThis = evaluator.Evaluate1(this); 45 46 if (double.IsInfinity(evaluatedThis.Item2) || double.IsNaN(evaluatedThis.Item2)) { 47 return false; 48 } 49 50 if (other == null) { 51 return true; 52 } 53 54 var evaluatedOther = evaluator.Evaluate1(other); 55 if (evaluatedThis.Item1 < evaluatedOther.Item1) { 56 return true; 57 } else if (evaluatedThis.Item1 > evaluatedOther.Item1) { 58 return false; 59 } 60 61 if (evaluatedThis.Item2 > evaluatedOther.Item2) { 62 return true; 63 } 64 if (evaluatedThis.Item2 < evaluatedOther.Item2) { 65 return false; 66 } 67 68 if (evaluatedThis.Item3 > evaluatedOther.Item3) { 69 return false; 70 } 71 return true; 72 73 } 41 74 } 42 75 } -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Sorting/IPackingItemClusteredSorter.cs
r15618 r15646 32 32 33 33 Permutation SortPackingItemsByMaterial(IList<PackingItem> items, PackingShape bin, double delta); 34 34 35 } 35 36 } -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Sorting/PackingItemAreaHeightSorter.cs
r15618 r15646 36 36 public Permutation SortPackingItemsByMaterial(IList<PackingItem> items, PackingShape bin) { 37 37 return items.SortByMaterialAreaHeight(); 38 } 38 } 39 39 } 40 40 } -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Sorting/PackingItemHeightVolumeSorter.cs
r15618 r15646 36 36 public Permutation SortPackingItemsByMaterial(IList<PackingItem> items, PackingShape bin) { 37 37 return items.SortByMaterialHeightVolume(); 38 } 38 } 39 39 } 40 40 } -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Sorting/PermutationPackingItemSorter.cs
r15617 r15646 136 136 return new Permutation(PermutationTypes.Absolute, 137 137 items.Select((v, i) => new { Index = i, Item = v }) 138 .OrderByDescending(x => x.Item.Material) 138 ./*OrderByDescending(x => x.Item.IsStackabel ? 1 : 0) 139 .*/OrderByDescending(x => x.Item.Material) 139 140 .ThenByDescending(x => x.Item.Depth * x.Item.Width * x.Item.Height) 140 141 .ThenByDescending(x => x.Item.Height) … … 150 151 return new Permutation(PermutationTypes.Absolute, 151 152 items.Select((v, i) => new { Index = i, Item = v }) 152 .OrderByDescending(x => x.Item.Material) 153 ./*OrderByDescending(x => x.Item.IsStackabel ? 1 : 0) 154 .*/OrderByDescending(x => x.Item.Material) 153 155 .ThenByDescending(x => x.Item.Height) 154 156 .ThenByDescending(x => x.Item.Depth * x.Item.Width * x.Item.Height) … … 164 166 return new Permutation(PermutationTypes.Absolute, 165 167 items.Select((v, i) => new { Index = i, Item = v }) 166 .OrderByDescending(x => x.Item.Material) 168 ./*OrderByDescending(x => x.Item.IsStackabel ? 1 : 0) 169 .*/OrderByDescending(x => x.Item.Material) 167 170 .ThenByDescending(x => x.Item.Depth * x.Item.Width) 168 171 .ThenByDescending(x => x.Item.Height) … … 178 181 return new Permutation(PermutationTypes.Absolute, 179 182 items.Select((v, i) => new { Index = i, Item = v }) 180 .OrderByDescending(x => x.Item.Material) 183 ./*OrderByDescending(x => x.Item.IsStackabel ? 1 : 0) 184 .*/OrderByDescending(x => x.Item.Material) 181 185 .ThenByDescending(x => x.Item.Height) 182 186 .ThenByDescending(x => x.Item.Depth * x.Item.Width) -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj
r15617 r15646 113 113 <Compile Include="3D\ExtremePointPruning\IExtremePointPruning.cs" /> 114 114 <Compile Include="3D\Geometry\Edge3D.cs" /> 115 <Compile Include="3D\Material\FrictionalCoefficientTable.cs" /> 116 <Compile Include="3D\Material\MaterialType.cs" /> 115 117 <Compile Include="3D\Packer\BinPacker.cs" /> 116 118 <Compile Include="3D\Packer\BinPackerFactory.cs" />
Note: See TracChangeset
for help on using the changeset viewer.