Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
01/24/18 13:17:00 (6 years ago)
Author:
rhanghof
Message:

#2817:

  • Dealing with stackable items
  • Enhanced the Evaluator
  • Added parameters some paramters to the packing items
File:
1 edited

Legend:

Unmodified
Added
Removed

  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs

    r15617 r15646  
    3434  [StorableClass]
    3535  public class BinPacking3D : BinPacking<PackingPosition, PackingShape, PackingItem> {
    36    
     36
    3737    [Storable]
    3838    public IDictionary<PackingPosition, IEnumerable<ResidualSpace>> ExtremePoints { get; protected set; }
    … …  
    4242      : base(binShape) {
    4343      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) });
    4646    }
    4747
    … …  
    6666    }
    6767
    68    
     68
    6969
    7070    /// <summary>
    … …  
    9696
    9797
    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
    117152
    118153    #region Position feasability
    … …  
    128163    /// <returns></returns>
    129164    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
    136169
    137170    /// <summary>
    … …  
    142175    /// <returns></returns>
    143176    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;
    146177      // Check if the boundings of the bin would injured
    147       if (givenItemPosition.X + width > BinShape.Width ||
     178      if (givenItemPosition.X + givenItem.Width > BinShape.Width ||
    148179          givenItemPosition.Y + givenItem.Height > BinShape.Height ||
    149           givenItemPosition.Z + depth > BinShape.Depth) {
     180          givenItemPosition.Z + givenItem.Depth > BinShape.Depth) {
    150181        return false;
    151182      }
    … …  
    201232    private bool HasOnePointWithAnItemBelow(PackingItem item, PackingPosition position) {
    202233      bool p1, p2, p3, p4;
    203       PointsLiesOnAnItem(item, position, out p1, out p2, out p3, out p4);
     234      PointsLiesOnAnStackableItem(item, position, out p1, out p2, out p3, out p4);
    204235
    205236      return p1 || p2 || p3 || p4;
    … …  
    215246    public override bool IsStaticStable(PackingItem item, PackingPosition position) {
    216247      bool p1, p2, p3, p4;
    217       PointsLiesOnAnItem(item, position, out p1, out p2, out p3, out p4);
     248      PointsLiesOnAnStackableItem(item, position, out p1, out p2, out p3, out p4);
    218249      return p1 && p2 && p3 && p4;
    219250    }
    … …  
    234265    /// <param name="p3"></param>
    235266    /// <param name="p4"></param>
    236     private void PointsLiesOnAnItem(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) {
    237268      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP1;
    238269      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP2;
    … …  
    242273      GetItemsUnderItemWithContact(item, position, out itemsP1, out itemsP2, out itemsP3, out itemsP4);
    243274
    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();
    248279    }
    249280
    … …  
    315346
    316347    #region Get items
    317    
     348
    318349    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelow(PackingPosition pos) {
    319350      var line = new Line3D(pos, new Vector3D(0, 1, 0));
Note: See TracChangeset for help on using the changeset viewer.