Changeset 15229


Ignore:
Timestamp:
07/13/17 15:22:59 (2 months ago)
Author:
abeham
Message:

#2762:

  • Implemented review comments
  • Fixed ResidualSpaceBestFitExtremePointPermutationDecoder by sorting from smallest to largest (merit function should be minimized)
  • Some restructuring of the methods
Location:
branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3
Files:
14 edited
2 moved

Legend:

Unmodified
Added
Removed
  • branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/2D/BinPacking2D.cs

    r15182 r15229  
    8888      };
    8989
    90       int epIndex = 0;
    91       while (epIndex < ExtremePoints.Count && (!IsPositionFeasible(rotatedItem, ExtremePoints.ElementAt(epIndex)))) { epIndex++; }
    92 
    93       if (epIndex < ExtremePoints.Count) {
    94         var currentPoint = ExtremePoints.ElementAt(epIndex);
    95 
    96         var result = new PackingPosition(currentPoint.AssignedBin, currentPoint.X, currentPoint.Y, rotated);
     90      var ep = ExtremePoints.Where(x => IsPositionFeasible(rotatedItem, x, stackingConstraints)).FirstOrDefault();
     91      if (ep != null) {
     92        var result = new PackingPosition(ep.AssignedBin, ep.X, ep.Y, rotated);
    9793        return result;
    9894      }
    9995      return null;
    10096    }
    101     public override PackingPosition FindPositionBySliding(PackingItem item, bool rotated) {
     97    public override PackingPosition FindPositionBySliding(PackingItem item, bool rotated, bool stackingConstraints) {
    10298      PackingPosition currentPosition = new PackingPosition(0,
    10399        BinShape.Width - (rotated ? item.Height : item.Width),
    104100        BinShape.Height - (rotated ? item.Width : item.Height), rotated);
    105101      //Slide the item as far as possible to the left
    106       while (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition))
    107         || IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition))) {
     102      while (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints)
     103        || IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition), stackingConstraints)) {
    108104        //Slide the item as far as possible to the bottom
    109         while (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition))) {
     105        while (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition), stackingConstraints)) {
    110106          currentPosition = PackingPosition.MoveDown(currentPosition);
    111107        }
    112         if (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition)))
     108        if (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints))
    113109          currentPosition = PackingPosition.MoveLeft(currentPosition);
    114110      }
    115111
    116       return IsPositionFeasible(item, currentPosition) ? currentPosition : null;
    117     }
    118 
    119     public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items) {
     112      return IsPositionFeasible(item, currentPosition, stackingConstraints) ? currentPosition : null;
     113    }
     114
     115    public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) {
    120116      var temp = new List<int>(sequence);
    121117      for (int i = 0; i < temp.Count; i++) {
    122118        var item = items[temp[i]];
    123         var position = FindPositionBySliding(item, false);
     119        var position = FindPositionBySliding(item, false, stackingConstraints);
    124120        if (position != null) {
    125121          PackItem(temp[i], item, position);
     
    128124      }
    129125    }
    130     public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, Dictionary<int, bool> rotationArray) {
     126    public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, Dictionary<int, bool> rotationArray, bool stackingConstraints) {
    131127      var temp = new List<int>(sequence);
    132128      for (int i = 0; i < temp.Count; i++) {
    133129        var item = items[temp[i]];
    134         var position = FindPositionBySliding(item, rotationArray[temp[i]]);
     130        var position = FindPositionBySliding(item, rotationArray[temp[i]], stackingConstraints);
    135131        if (position != null) {
    136132          PackItem(temp[i], item, position);
     
    150146      }
    151147    }
    152     public override bool ExtremePointBasedPacking(int itemID, IList<PackingItem> items, bool stackingConstraints) {
    153       var item = items[itemID];
    154       var positionFound = FindExtremePointForItem(item, false, stackingConstraints);
    155       if (positionFound != null) {
    156         PackItem(itemID, item, positionFound);
    157         return true;
    158       }
    159       return false;
    160     }
    161148   
    162149    public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints, Dictionary<int, bool> rotationArray) {
  • branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/2D/IntegerVectorEncoding/BottomLeftIntegerVectorDecoder.cs

    r14167 r15229  
    4747
    4848    protected override PackingPosition FindPositionForItem(BinPacking2D bp, PackingItem item) {
    49       return bp.FindPositionBySliding(item, rotated: false);
     49      return bp.FindPositionBySliding(item, rotated: false, stackingConstraints: false);
    5050    }
    5151
     
    5454      ref IList<int> remainingIDs, IList<PackingItem> items) {
    5555      var bp = new BinPacking2D(partialSolution.BinShape);
    56       bp.SlidingBasedPacking(ref remainingIDs, items);
     56      bp.SlidingBasedPacking(ref remainingIDs, items, stackingConstraints: false);
    5757      return bp;
    5858    }
  • branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/2D/PermutationEncoding/BottomLeftPermutationDecoder.cs

    r14167 r15229  
    4646      while (remainingIDs.Count > 0) {
    4747        var bp = new BinPacking2D(binShape);
    48         bp.SlidingBasedPacking(ref remainingIDs, items);
     48        bp.SlidingBasedPacking(ref remainingIDs, items, stackingConstraints: false);
    4949        result.Bins.Add(bp);
    5050      }
  • branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs

    r14977 r15229  
    144144
    145145    public override PackingPosition FindExtremePointForItem(PackingItem item, bool rotated, bool stackingConstraints) {
    146 
    147146      PackingItem newItem = new PackingItem(
    148147        rotated ? item.Depth : item.Width,
     
    151150        item.TargetBin, item.Weight, item.Material);
    152151
    153       int epIndex = 0;
    154       while (epIndex < ExtremePoints.Count && (
    155         !IsPositionFeasible(newItem, ExtremePoints.ElementAt(epIndex))
    156         || !IsSupportedByAtLeastOnePoint(newItem, ExtremePoints.ElementAt(epIndex))
    157         || (stackingConstraints && !IsStaticStable(newItem, ExtremePoints.ElementAt(epIndex)))
    158         || (stackingConstraints && !IsWeightSupported(newItem, ExtremePoints.ElementAt(epIndex)))
    159       )) { epIndex++; }
    160 
    161       if (epIndex < ExtremePoints.Count) {
    162         var origPoint = ExtremePoints.ElementAt(epIndex);
    163         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);
    164155        return result;
    165156      }
     
    167158    }
    168159
    169     public override PackingPosition FindPositionBySliding(PackingItem item, bool rotated) {
    170       //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) {
    171168      //Starting-position at upper right corner (=left bottom point of item-rectangle is at position item.width,item.height)
    172169      PackingPosition currentPosition = new PackingPosition(0,
     
    175172        BinShape.Depth - (rotated ? item.Width : item.Depth), rotated);
    176173      //Slide the item as far as possible to the bottom
    177       while (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition))
    178         || IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition))
    179         || 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)) {
    180177        //Slide the item as far as possible to the left
    181         while (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition))
    182       || IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition))) {
     178        while (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints)
     179      || IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition), stackingConstraints)) {
    183180          //Slide the item as far as possible to the back
    184           while (IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition))) {
     181          while (IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition), stackingConstraints)) {
    185182            currentPosition = PackingPosition.MoveBack(currentPosition);
    186183          }
    187           if (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition)))
     184          if (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints))
    188185            currentPosition = PackingPosition.MoveLeft(currentPosition);
    189186        }
    190         if (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition)))
     187        if (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition), stackingConstraints))
    191188          currentPosition = PackingPosition.MoveDown(currentPosition);
    192189      }
    193190
    194       return IsPositionFeasible(item, currentPosition) ? currentPosition : null;
    195     }
    196 
    197     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) {
    198195      var temp = new List<int>(sequence);
    199196      for (int i = 0; i < temp.Count; i++) {
    200197        var item = items[temp[i]];
    201         var position = FindPositionBySliding(item, false);
     198        var position = FindPositionBySliding(item, false, stackingConstraints);
    202199        if (position != null) {
    203200          PackItem(temp[i], item, position);
     
    206203      }
    207204    }
    208     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) {
    209206      var temp = new List<int>(sequence);
    210207      for (int i = 0; i < temp.Count; i++) {
    211208        var item = items[temp[i]];
    212         var position = FindPositionBySliding(item, rotationArray[i]);
     209        var position = FindPositionBySliding(item, rotationArray[i], stackingConstraints);
    213210        if (position != null) {
    214211          PackItem(temp[i], item, position);
     
    231228      }
    232229    }
    233     public override bool ExtremePointBasedPacking(int itemID, IList<PackingItem> items, bool stackingConstraints) {
    234       var item = items[itemID];
    235       var positionFound = FindExtremePointForItem(item, false, stackingConstraints);
    236       if (positionFound != null) {
    237        PackItem(itemID, item, positionFound);
    238        return true;
    239       }
    240       return false;
    241     }
    242230    public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints, Dictionary<int, bool> rotationArray) {
    243231      var temp = new List<int>(sequence);
     
    319307      return false;
    320308    }
    321 
    322309
    323310    protected override void InitializeOccupationLayers() {
     
    370357      return;
    371358    }
    372     public int GetResidualSpace(PackingItem item, PackingPosition ep) {
    373       return ((ResidualSpace[ep].Item1 - item.Width) +
    374           (ResidualSpace[ep].Item2 - item.Height) +
    375           (ResidualSpace[ep].Item3 - item.Depth));
    376       }
    377     }
    378359  }
     360}
  • branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/RealWorldContainerPackingInstanceProvider.cs

    r15228 r15229  
    3030
    3131namespace HeuristicLab.Problems.BinPacking3D {
    32   public class RealisticInstanceProvider : ProblemInstanceProvider<BPPData> {
    33     protected virtual string FileName { get { return "3D-Instances"; } }
    34 
    35     protected int binWidth, binHeight, binDepth;
    36 
     32  public sealed class RealWorldContainerPackingInstanceProvider : ProblemInstanceProvider<BPPData> {
     33    private string FileName { get { return "ContainerPackingInstances"; } }
     34   
    3735    public override string Name {
    38       get { return "Realistic"; }
     36      get { return "Real-world Container Packing"; }
    3937    }
    4038
    4139    public override string Description {
    42       get { return "Problem instances derived from real-world data."; }
     40      get { return "Problem instances derived from real-world container packing data."; }
    4341    }
    4442
     
    5149    }
    5250
    53     public RealisticInstanceProvider() : base() { }
     51    public RealWorldContainerPackingInstanceProvider() : base() { }
    5452
    5553    public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
  • branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/ThreeDInstanceParser.cs

    r14838 r15229  
    3434    public void Parse(Stream stream) {
    3535      var reader = new StreamReader(stream);
    36       var length = GetNextInteger(reader).Value;
    37       var width = GetNextInteger(reader).Value;
    38       var height = GetNextInteger(reader).Value;
    39       var maxWeight = GetNextInteger(reader).Value;
     36      var length = GetNextInteger(reader);
     37      var width = GetNextInteger(reader);
     38      var height = GetNextInteger(reader);
     39      var maxWeight = GetNextInteger(reader);
    4040      Bin = new PackingShape(width, height, length);
    4141      Items = new List<PackingItem>();
    4242      while (true) {
    4343        try {
    44           var id = GetNextInteger(reader).Value;
    45           var pieces = GetNextInteger(reader).Value;
    46           length = GetNextInteger(reader).Value;
    47           width = GetNextInteger(reader).Value;
    48           height = GetNextInteger(reader).Value;
    49           var weight = GetNextInteger(reader).Value;
    50           var stack = GetNextInteger(reader).Value;
    51           var rotate = GetNextInteger(reader).Value;
    52           var tilt = GetNextInteger(reader).Value;
     44          var id = GetNextInteger(reader);
     45          var pieces = GetNextInteger(reader);
     46          length = GetNextInteger(reader);
     47          width = GetNextInteger(reader);
     48          height = GetNextInteger(reader);
     49          var weight = GetNextInteger(reader);
     50          var stack = GetNextInteger(reader);
     51          var material = GetNextInteger(reader);
     52          var rotate = GetNextInteger(reader);
     53          var tilt = GetNextInteger(reader);
    5354          for (var i = 0; i < pieces; i++) {
    54             Items.Add(new PackingItem(width, height, length, Bin, weight, 1));
     55            Items.Add(new PackingItem(width, height, length, Bin, weight, material));
    5556          }
    5657        } catch (InvalidOperationException) {
     
    6061    }
    6162
    62     private int? GetNextInteger(StreamReader reader) {
     63    private int GetNextInteger(StreamReader reader) {
    6364      var next = reader.Read();
    6465      var builder = new StringBuilder();
    6566      while (next >= 0 && !char.IsDigit((char)next)) next = reader.Read();
    66       if (next == -1) return null;
     67      if (next == -1) throw new InvalidOperationException("No further integer available");
    6768      while (char.IsDigit((char)next)) {
    6869        builder.Append((char)next);
  • branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/IntegerVectorEncoding/BottomLeftIntegerVectorDecoder.cs

    r14167 r15229  
    5454
    5555    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);
    5757    }
    5858
     
    6161      ref IList<int> remainingIDs, IList<PackingItem> items, bool useStackingConstraints) {
    6262      var bp = new BinPacking3D(partialSolution.BinShape);
    63       bp.SlidingBasedPacking(ref remainingIDs, items);
     63      bp.SlidingBasedPacking(ref remainingIDs, items, useStackingConstraints);
    6464      return bp;
    6565    }
  • branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/PermutationEncoding/BottomLeftPermutationDecoder.cs

    r14167 r15229  
    4646      while (remainingIDs.Count > 0) {
    4747        var bp = new BinPacking3D(binShape);
    48         bp.SlidingBasedPacking(ref remainingIDs, items);
     48        bp.SlidingBasedPacking(ref remainingIDs, items, useStackingConstraints);
    4949        result.Bins.Add(bp);
    5050      }
  • branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/PermutationEncoding/ExtremePointPermutationDecoder.cs

    r14976 r15229  
    4545
    4646    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) {
    4751      Solution result = new Solution(binShape, useExtremePoints: true, stackingConstraints: useStackingConstraints);
    4852      IList<int> remainingIDs = new List<int>(permutation);
  • branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/PermutationEncoding/ExtremePointPermutationDecoderBase.cs

    r14976 r15229  
    1919 */
    2020#endregion
    21 
    22 using System;
     21 
    2322using System.Collections.Generic;
    24 using System.Linq;
    2523using HeuristicLab.Common;
    2624using HeuristicLab.Core;
     
    4139
    4240    public abstract Solution Decode(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints);
    43 
    44     public virtual bool FindExtremePointForItem(Dictionary<Tuple<BinPacking3D, PackingPosition>, int> PointsSpace, PackingItem item, bool rotated, bool stackingConstraints, out BinPacking3D bin, out PackingPosition pos) {
    45 
    46       PackingItem newItem = new PackingItem(
    47         rotated ? item.Depth : item.Width,
    48         item.Height,
    49         rotated ? item.Width : item.Depth,
    50         item.TargetBin, item.Weight, item.Material);
    51 
    52       var EPoints = PointsSpace.Keys.ToList();
    53       BinPacking3D bp;
    54       PackingPosition position;
    55       int epIndex = 0;
    56       while (epIndex < EPoints.Count && (
    57         !(((bp = EPoints.ElementAt(epIndex).Item1)).IsPositionFeasible(newItem, (position = EPoints.ElementAt(epIndex).Item2)))
    58         || !bp.IsSupportedByAtLeastOnePoint(newItem, position)
    59         || (stackingConstraints && !bp.IsStaticStable(newItem, position))
    60         || (stackingConstraints && !bp.IsWeightSupported(newItem, position))
    61       )) { epIndex++; }
    62 
    63       if (epIndex < EPoints.Count) {
    64         bin = EPoints.ElementAt(epIndex).Item1;
    65         var origPoint = EPoints.ElementAt(epIndex).Item2;
    66         pos = new PackingPosition(origPoint.AssignedBin, origPoint.X, origPoint.Y, origPoint.Z, rotated);
    67 
    68         return true;
    69       }
    70       bin = null;
    71       pos = null;
    72       return false;
    73     }
    74 
    75     public virtual Dictionary<Tuple<BinPacking3D, PackingPosition>, int> GetResidualSpaceAllPoints(Solution solution, PackingItem item) {
    76       Dictionary<Tuple<BinPacking3D, PackingPosition>, int> result = new Dictionary<Tuple<BinPacking3D, PackingPosition>, int>();
    77       foreach (BinPacking3D bp in solution.Bins) {
    78         foreach (var ep in bp.ExtremePoints) {
    79           result.Add(Tuple.Create(bp, ep), bp.GetResidualSpace(item, ep));
    80         }
    81       }
    82       return result;
    83     }
    84 
    85     public virtual bool ExtremePointBasedPacking(Dictionary<Tuple<BinPacking3D, PackingPosition>, int> PointsSpace, int itemID, IList<PackingItem> items, bool stackingConstraints) {
    86       BinPacking3D bp;
    87       PackingPosition positionFound;
    88       var item = items[itemID];
    89       if (FindExtremePointForItem(PointsSpace, item, false, stackingConstraints, out bp, out positionFound)) {
    90         bp.PackItem(itemID, item, positionFound);
    91         return true;
    92       }
    93       return false;
    94     }
    9541  }
    9642}
  • branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/PermutationEncoding/FreeVolumeBestFitExtremePointPermutationDecoder.cs

    r14976 r15229  
    4444
    4545    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) {
    4650      Solution result = new Solution(binShape, useExtremePoints: true, stackingConstraints: useStackingConstraints);
    4751      IList<int> remainingIDs = new List<int>(permutation);
     
    5155      foreach (int ID in remainingIDs) {
    5256        var sortedBins = result.Bins.OrderBy(x => x.FreeVolume);
    53         var notPacked = 0;
    54         foreach (BinPacking3D bp in sortedBins) {
    55           if (!bp.ExtremePointBasedPacking(ID, items, stackingConstraints: useStackingConstraints)) { notPacked++; } else break;
     57        var item = items[ID];
     58        var posFound = false;
     59        foreach (var bp in sortedBins) {
     60          var pos = bp.FindExtremePointForItem(item, false, useStackingConstraints);
     61          posFound = pos != null;
     62          if (posFound) {
     63            bp.PackItem(ID, item, pos);
     64            break;
     65          }
    5666        }
    57         if (notPacked == result.NrOfBins) {
     67        if (!posFound) {
    5868          var bp = new BinPacking3D(binShape);
    59           bp.ExtremePointBasedPacking(ID, items, stackingConstraints: useStackingConstraints);
     69          var pos = bp.FindExtremePointForItem(item, false, useStackingConstraints);
     70          if (pos == null) throw new InvalidOperationException("Item " + ID + " cannot be packed in empty bin.");
     71          bp.PackItem(ID, item, pos);
    6072          result.Bins.Add(bp);
    6173        }
  • branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/PermutationEncoding/ResidualSpaceBestFitExtremePointPermutationDecoder.cs

    r14976 r15229  
    4444
    4545    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) {
    4650      Solution result = new Solution(binShape, useExtremePoints: true, stackingConstraints: useStackingConstraints);
    4751      IList<int> remainingIDs = new List<int>(permutation);
    48       Dictionary<Tuple<BinPacking3D,PackingPosition>, int> points = new Dictionary<Tuple<BinPacking3D,PackingPosition>,int>();
    4952      var bpg = new BinPacking3D(binShape);
    5053      bpg.ExtremePointBasedPacking(ref remainingIDs, items, stackingConstraints: useStackingConstraints);
    5154      result.Bins.Add(bpg);
    5255      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
    5666          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.");
    5871          result.Bins.Add(bp);
    5972        }
     
    6275      return result;
    6376    }
     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    }
    6495  }
    6596}
  • branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/Algorithms/3D/ExtremePointAlgorithm.cs

    r15200 r15229  
    4141  [StorableClass]
    4242  [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms, Priority = 180)]
    43   public class ExtremePointAlgorithm : BasicAlgorithm {
     43  public sealed class ExtremePointAlgorithm : BasicAlgorithm {
    4444
    4545    public override Type ProblemType {
     
    5757
    5858    [Storable]
    59     private IValueParameter<EnumValue<SortingMethod>> sortingMethodParameter;
     59    private readonly IValueParameter<EnumValue<SortingMethod>> sortingMethodParameter;
    6060    public IValueParameter<EnumValue<SortingMethod>> SortingMethodParameter {
    6161      get { return sortingMethodParameter; }
     
    6363
    6464    [Storable]
    65     private IValueParameter<EnumValue<FittingMethod>> fittingMethodParameter;
     65    private readonly IValueParameter<EnumValue<FittingMethod>> fittingMethodParameter;
    6666    public IValueParameter<EnumValue<FittingMethod>> FittingMethodParameter {
    6767      get { return fittingMethodParameter; }
     
    6969
    7070    [Storable]
    71     private IValueParameter<PercentValue> deltaParameter;
     71    private readonly IValueParameter<PercentValue> deltaParameter;
    7272    public IValueParameter<PercentValue> DeltaParameter {
    7373      get { return deltaParameter; }
     
    7575
    7676    [StorableConstructor]
    77     protected ExtremePointAlgorithm(bool deserializing) : base(deserializing) { }
    78     protected ExtremePointAlgorithm(ExtremePointAlgorithm original, Cloner cloner)
     77    private ExtremePointAlgorithm(bool deserializing) : base(deserializing) { }
     78    private ExtremePointAlgorithm(ExtremePointAlgorithm original, Cloner cloner)
    7979      : base(original, cloner) {
    8080      sortingMethodParameter = cloner.Clone(original.sortingMethodParameter);
     
    112112      if (result == null) throw new InvalidOperationException("No result obtained!");
    113113
    114       Results.Add(new Result("Best Solution", result.Item1));
    115       Results.Add(new Result("Best Solution Quality", new DoubleValue(result.Item2)));
     114      Results.Add(new Result("Best Solution",
     115        "The best found solution",
     116        result.Item1));
     117      Results.Add(new Result("Best Solution Quality",
     118        "The quality of the best found solution according to the evaluator",
     119        new DoubleValue(result.Item2)));
    116120
    117121      var binUtil = new BinUtilizationEvaluator();
    118122      var packRatio = new PackingRatioEvaluator();
    119       Results.Add(new Result("Best Solution Bin Count", new IntValue(result.Item1.NrOfBins)));
    120       Results.Add(new Result("Best Solution Bin Utilization", new PercentValue(Math.Round(binUtil.Evaluate(result.Item1), 3))));
     123      Results.Add(new Result("Best Solution Bin Count",
     124        "The number of bins in the best found solution",
     125        new IntValue(result.Item1.NrOfBins)));
     126      Results.Add(new Result("Best Solution Bin Utilization",
     127        "The utilization given in percentage as calculated by the BinUtilizationEvaluator (total used space / total available space)",
     128        new PercentValue(Math.Round(binUtil.Evaluate(result.Item1), 3))));
    121129
    122130      if (result.Item3.HasValue && sorting.Length > 1)
    123         Results.Add(new Result("Best Sorting Method", new EnumValue<SortingMethod>(result.Item3.Value)));
     131        Results.Add(new Result("Best Sorting Method",
     132          "The sorting method that found the best solution",
     133          new EnumValue<SortingMethod>(result.Item3.Value)));
    124134      if (result.Item4.HasValue && fitting.Length > 1)
    125         Results.Add(new Result("Best Fitting Method", new EnumValue<FittingMethod>(result.Item4.Value)));
     135        Results.Add(new Result("Best Fitting Method",
     136          "The fitting method that found the best solution",
     137          new EnumValue<FittingMethod>(result.Item4.Value)));
    126138    }
    127139
  • branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/BinPacking.cs

    r14976 r15229  
    9090
    9191    public abstract TPos FindExtremePointForItem(TItem item, bool rotated, bool stackingConstraints);
    92     public abstract TPos FindPositionBySliding(TItem item, bool rotated);
     92    public abstract TPos FindPositionBySliding(TItem item, bool rotated, bool stackingConstraints);
    9393
    94     public abstract void SlidingBasedPacking(ref IList<int> sequence, IList<TItem> items);
    95     public abstract void SlidingBasedPacking(ref IList<int> sequence, IList<TItem> items, Dictionary<int, bool> rotationArray);
     94    public abstract void SlidingBasedPacking(ref IList<int> sequence, IList<TItem> items, bool stackingConstraints);
     95    public abstract void SlidingBasedPacking(ref IList<int> sequence, IList<TItem> items, Dictionary<int, bool> rotationArray, bool stackingConstraints);
    9696    public abstract void ExtremePointBasedPacking(ref IList<int> sequence, IList<TItem> items, bool stackingConstraints);
    97     public abstract bool ExtremePointBasedPacking(int ID, IList<TItem> items, bool stackingConstraints);
    9897    public abstract void ExtremePointBasedPacking(ref IList<int> sequence, IList<TItem> items, bool stackingConstraints, Dictionary<int, bool> rotationArray);
    9998
    100     public void PackItem(int itemID, TItem item, TPos position) {
     99    public virtual void PackItem(int itemID, TItem item, TPos position) {
    101100      Items[itemID] = item;
    102101      Positions[itemID] = position;
     
    107106     
    108107      AddNewItemToOccupationLayers(itemID, item, position);
     108    }
     109    public virtual bool PackItemIfFeasible(int itemID, TItem item, TPos position, bool stackingConstraints) {
     110      if (IsPositionFeasible(item, position, stackingConstraints)) {
     111        PackItem(itemID, item, position);
     112        return true;
     113      }
     114      return false;
    109115    }
    110116
     
    135141      return false;
    136142    }
    137     public bool IsPositionFeasible(TItem item, TPos position) {
     143    public virtual bool IsPositionFeasible(TItem item, TPos position, bool stackingConstraints) {
    138144      //In this case feasability is defined as following: 1. the item fits into the bin-borders; 2. the point is supported by something; 3. the item does not collide with another already packed item
    139145      if (!BinShape.Encloses(position, item))
     
    147153      return true;
    148154    }
     155   
    149156    public abstract int ShortestPossibleSideFromPoint(TPos position);
    150157    public abstract bool IsStaticStable(TItem measures, TPos position);
  • branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj

    r15183 r15229  
    172172    <Compile Include="3D\Instances\BPPData.cs" />
    173173    <Compile Include="3D\Instances\RandomDataDescriptor.cs" />
    174     <Compile Include="3D\Instances\RealisticInstanceProvider.cs" />
     174    <Compile Include="3D\Instances\RealWorldContainerPackingInstanceProvider.cs" />
    175175    <Compile Include="3D\Instances\RandomInstanceProvider.cs" />
    176176    <Compile Include="3D\Instances\ThreeDInstanceParser.cs" />
     
    213213  </ItemGroup>
    214214  <ItemGroup>
    215     <EmbeddedResource Include="3D\Instances\3D-Instances.zip" />
     215    <EmbeddedResource Include="3D\Instances\ContainerPackingInstances.zip" />
    216216    <None Include="HeuristicLab.snk" />
    217217    <None Include="Properties\AssemblyInfo.cs.frame" />
Note: See TracChangeset for help on using the changeset viewer.