Changeset 15229 for branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/PermutationEncoding/ResidualSpaceBestFitExtremePointPermutationDecoder.cs
- Timestamp:
- 07/13/17 15:22:59 (7 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/PermutationEncoding/ResidualSpaceBestFitExtremePointPermutationDecoder.cs
r14976 r15229 44 44 45 45 public override Solution Decode(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) { 46 return Apply(permutation, binShape, items, useStackingConstraints); 47 } 48 49 public static Solution Apply(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) { 46 50 Solution result = new Solution(binShape, useExtremePoints: true, stackingConstraints: useStackingConstraints); 47 51 IList<int> remainingIDs = new List<int>(permutation); 48 Dictionary<Tuple<BinPacking3D,PackingPosition>, int> points = new Dictionary<Tuple<BinPacking3D,PackingPosition>,int>();49 52 var bpg = new BinPacking3D(binShape); 50 53 bpg.ExtremePointBasedPacking(ref remainingIDs, items, stackingConstraints: useStackingConstraints); 51 54 result.Bins.Add(bpg); 52 55 foreach (int ID in remainingIDs) { 53 points = GetResidualSpaceAllPoints(result, items[ID]); 54 var sortedPoints = points.OrderByDescending(x => x.Value).ToDictionary(x => x.Key, x => x.Value); 55 if (!ExtremePointBasedPacking(sortedPoints, ID, items, stackingConstraints: useStackingConstraints)) { 56 var item = items[ID]; 57 var points = GetResidualSpaceAllPoints(result, item); 58 var sortedPoints = points.OrderBy(x => x.Item3); 59 var packed = false; 60 foreach (var p in sortedPoints) { 61 packed = p.Item1.PackItemIfFeasible(ID, item, p.Item2, useStackingConstraints); 62 if (packed) break; 63 } 64 if (!packed) { 65 // pack item in a new bin 56 66 var bp = new BinPacking3D(binShape); 57 bp.ExtremePointBasedPacking(ID, items, stackingConstraints: useStackingConstraints); 67 var positionFound = bp.FindExtremePointForItem(item, false, useStackingConstraints); 68 if (positionFound != null) { 69 bp.PackItem(ID, item, positionFound); 70 } else throw new InvalidOperationException("Item " + ID + " cannot be packed in an empty bin."); 58 71 result.Bins.Add(bp); 59 72 } … … 62 75 return result; 63 76 } 77 78 public static IList<Tuple<BinPacking3D, PackingPosition, int>> GetResidualSpaceAllPoints(Solution solution, PackingItem item) { 79 var result = new List<Tuple<BinPacking3D, PackingPosition, int>>(); 80 foreach (BinPacking3D bp in solution.Bins) { 81 foreach (var ep in bp.ExtremePoints) { 82 var rs = bp.ResidualSpace[ep]; 83 if (rs.Item1 < item.Width || rs.Item2 < item.Height || rs.Item3 < item.Depth) continue; 84 result.Add(Tuple.Create(bp, ep, GetResidualMerit(rs, item, ep))); 85 } 86 } 87 return result; 88 } 89 90 private static int GetResidualMerit(Tuple<int, int, int> rs, PackingItem item, PackingPosition ep) { 91 return ((rs.Item1 - item.Width) + 92 (rs.Item2 - item.Height) + 93 (rs.Item3 - item.Depth)); 94 } 64 95 } 65 96 }
Note: See TracChangeset
for help on using the changeset viewer.