Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
07/13/17 15:22:59 (7 years 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
File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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}
Note: See TracChangeset for help on using the changeset viewer.