Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
11/14/17 15:31:22 (7 years ago)
Author:
rhanghof
Message:

#2817

  • Added some unit tests
  • Enhanced the documentation
Location:
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3
Files:
2 added
12 edited

Legend:

Unmodified
Added
Removed

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

    r15462 r15471  
    6767    #region New methods for bin packer class
    6868
     69    /// <summary>
     70    /// Puts a given item into the bin packing at the given position.
     71    /// </summary>
     72    /// <param name="itemID">Offset in the internal item array</param>
     73    /// <param name="item">Item</param>
     74    /// <param name="position">Position of the item in the bin packing</param>
    6975    public override void PackItem(int itemID, PackingItem item, PackingPosition position) {
    7076      Items[itemID] = item;
    … …  
    107113      AddExtremePoint(ep2);
    108114      AddExtremePoint(ep3);
    109 
    110       /*
    111       ExtremePoints.Add(ep1);
    112       ExtremePoints.Add(ep2);
    113       ExtremePoints.Add(ep3);
    114 
    115       var rs1 = CalculateResidualSpace(CreateRs(ep1));
    116       var rs2 = CalculateResidualSpace(CreateRs(ep2));
    117       var rs3 = CalculateResidualSpace(CreateRs(ep3));
    118       ResidualSpace.Add(ep1, rs1);
    119       ResidualSpace.Add(ep2, rs2);
    120       ResidualSpace.Add(ep3, rs3);*/
    121     }
    122 
    123 
    124     /*private bool AddExtremePoint(PackingPosition position) {
    125       if ()
    126 
    127       return true;
    128     }
    129 
    130    
    131     private bool AddExtremePoint(PackingPosition pos) {
    132       if (ExtremePoints.Add(pos)) {
    133         var rs = CalculateResidualSpace(new Vector3D(pos));
    134         ResidualSpace.Add(pos, rs);
    135         // Check if existing extreme points are shadowed by the new point
    136         // That is, their residual space fit entirely into the residual space of the new point
    137         foreach (var ep in ExtremePoints.Where(x => x != pos && new Vector3D(x).IsInside(pos, rs)).ToList()) {
    138           if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), ResidualSpace[ep], pos, rs)) {
    139             ExtremePoints.Remove(ep);
    140             ResidualSpace.Remove(ep);
    141           }
    142         }
    143         return true;
    144       }
    145       return false;
    146     }*/
    147 
    148 
     115    }
     116       
    149117    private Tuple<int, int, int> CalculateResidualSpace(Vector3D pos) {
    150118      var itemPos = Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] });
    … …  
    164132        }
    165133      }
    166 
    167      
    168134     
    169135      if (limit.X - pos.X <= 0 || limit.Y - pos.Y <= 0  || limit.Z - pos.Z <= 0) {
    170136        return Tuple.Create(0, 0, 0);
    171       }
    172 
    173 
     137      }     
    174138      return Tuple.Create(limit.X - pos.X, limit.Y - pos.Y, limit.Z - pos.Z);
    175139    }
    … …  
    491455    }
    492456
     457    /// <summary>
     458    /// Returns true if all values of a given tuple are not zero
     459    /// </summary>
     460    /// <param name="rs">Tuple with three integer values which represents a residual space</param>
     461    /// <returns></returns>
    493462    private bool IsNonZero(Tuple<int, int, int> rs) {
    494463      return rs.Item1 > 0 && rs.Item2 > 0 && rs.Item3 > 0;
    495464    }
    496465
     466    /// <summary>
     467    ///
     468    /// </summary>
     469    /// <param name="pos"></param>
     470    /// <param name="residualSpace"></param>
     471    /// <returns></returns>
    497472    private bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> residualSpace) {
    498473      var eps = ExtremePoints.Where(x => !pos.Equals(x) && pos.IsInside(x, ResidualSpace[x]));
    … …  
    505480    }
    506481
     482    /// <summary>
     483    /// Adds an extrem point to the extreme point collection of the bin packing.
     484    /// </summary>
     485    /// <param name="pos">Position of the new extreme point</param>
     486    /// <returns>Retruns true if the extreme point could be added</returns>
    507487    private bool AddExtremePoint(PackingPosition pos) {
    508488      if (ExtremePoints.Add(pos)) {
    509489        var rs = CalculateResidualSpace(new Vector3D(pos));
    510490        ResidualSpace.Add(pos, rs);
    511         // Check if existing extreme points are shadowed by the new point
    512         // That is, their residual space fit entirely into the residual space of the new point
     491        // Check if the existing extreme points are shadowed by the new point
     492        // This is, their residual space fit entirely into the residual space of the new point
    513493        foreach (var ep in ExtremePoints.Where(x => x != pos && new Vector3D(x).IsInside(pos, rs)).ToList()) {
    514494          if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), ResidualSpace[ep], pos, rs)) {
    … …  
    521501      return false;
    522502    }
    523 
    524     private Tuple<int, int, int> CalculateResidualSpace1(Vector3D pos) {
    525       var itemPos = Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] });
    526       var rightLimit = ProjectRight(pos);
    527       var upLimit = ProjectUp(pos);
    528       var forwardLimit = ProjectForward(pos);
    529       return Tuple.Create(rightLimit.X - pos.X, upLimit.Y - pos.Y, forwardLimit.Z - pos.Z);
    530     }
    531 
     503       
    532504    #region Projections
    533505
    … …  
    719691
    720692
     693    /// <summary>
     694    /// Updates the resiual space for a packing item.
     695    /// </summary>
     696    /// <param name="item"></param>
     697    /// <param name="pos"></param>
    721698    public void UpdateResidualSpace(PackingItem item, PackingPosition pos) {
    722699      foreach (var ep in ExtremePoints.ToList()) {

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

    r15230 r15471  
    102102        var parser = new ThreeDInstanceParser();
    103103        parser.Parse(stream);
    104 
    105104        return new BPPData() {
    106105          Name = Path.GetFileNameWithoutExtension(path),

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

    r15463 r15471  
    6464      var next = reader.Read();
    6565      var builder = new StringBuilder();
    66       while (next >= 0 && !char.IsDigit((char)next)) next = reader.Read();
    67       if (next == -1) throw new InvalidOperationException("No further integer available");
     66      while (next >= 0 && !char.IsDigit((char)next))
     67        next = reader.Read();
     68      if (next == -1)
     69        throw new InvalidOperationException("No further integer available");
    6870      while (char.IsDigit((char)next)) {
    6971        builder.Append((char)next);
    7072        next = reader.Read();
    71         if (next == -1) break;
     73        if (next == -1)
     74          break;
    7275      }
    7376      return int.Parse(builder.ToString());

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

    r15462 r15471  
    4444    /// <param name="items">A list of packing items which should be assigned to a bin</param>
    4545    /// <param name="useStackingConstraints">Flag for using stacking constraints</param>
    46     /// <returns></returns>
     46    /// <returns>Returns a collection of bin packing 3d objects. Each object represents a bin and the packed items</returns>
    4747    public abstract IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints);
    48 
    4948   
    50 
    5149    /// <summary>
    5250    /// Pack a given item into a given bin and updates the residual space and the extreme points
    … …  
    7876        packingItem.TargetBin, packingItem.Weight, packingItem.Material);
    7977
    80       // The extremepoints are sortet by Z, X, Y
    81 
     78      // The extremepoints are sortet by Y / Z / X
    8279      return packingBin.ExtremePoints.Where(x => packingBin.IsPositionFeasible(newItem, x, useStackingConstraints)).FirstOrDefault();
    8380    }

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

    r15463 r15471  
    1616    /// </summary>
    1717    /// <param name="fittingMethod"></param>
    18     /// <returns></returns>
     18    /// <returns>Returns a new BinPacker depending on the given fitting method</returns>
    1919    public static BinPacker CreateBinPacker(FittingMethod fittingMethod) {
    2020      BinPacker binPacker = null;

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

    r15462 r15471  
    3838
    3939    /// <summary>
    40     /// Packs the items of the object by using a first fit algorithm into an amount of bins and returns them
     40    /// Packs the items of the object by using a first fit algorithm into an amount of bins and returns them.
    4141    /// </summary>
    4242    /// <returns>Returns a collection of bin packing 3d objects. Each object represents a bin and the packed items</returns>

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

    r15462 r15471  
    3636    public BinPackerFreeVolumeBestFit() : base() { }
    3737
     38    /// <summary>
     39    /// Packs all items by using a free volume best fit strategy.
     40    /// If there is no bin packing item, a new one will be created an the current item will be packed into it.
     41    /// If there exists at least on bin packing item in the packing list they are being sortet by their free volume ascending.
     42    /// The current item will be packed into the bin packing with the fewest free volume and enought space for placing it.
     43    /// If an item could not be placed in any bin packing, a new one will be created for the item.
     44    /// </summary>
     45    /// <param name="sortedItems"></param>
     46    /// <param name="binShape"></param>
     47    /// <param name="items"></param>
     48    /// <param name="useStackingConstraints"></param>
     49    /// <returns>Returns a collection of bin packing 3d objects. Each object represents a bin and the packed items</returns>
    3850    public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
    3951      IList<BinPacking3D> packingList = new List<BinPacking3D>();
    4052      IList<int> remainingIds = new List<int>(sortedItems);
    41 
    4253
    4354      foreach (int remainingId in remainingIds) {

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

    r15462 r15471  
    3434  public class BinPackerResidualSpaceBestFit : BinPacker {
    3535
    36     public BinPackerResidualSpaceBestFit() : base() { }/*
    37     public BinPackerResidualSpaceBestFit(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints)
    38       : base(permutation, binShape, items, useStackingConstraints) { }
    39       */
     36    public BinPackerResidualSpaceBestFit() : base() { }
     37
    4038    /// <summary>
    4139    /// Packs the items into the bins by using a best fit residual space algorithm.
    … …  
    4341    /// Each residual space belongs to an extreme point.
    4442    /// </summary>
    45     /// <returns></returns>
     43    /// <returns>Returns a collection of bin packing 3d objects. Each object represents a bin and the packed items</returns>
    4644    public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
    4745      IList<BinPacking3D> packingList = new List<BinPacking3D>();

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

    r15462 r15471  
    105105    /// <summary>
    106106    /// Compares two packing positions by their coordinates.
    107     /// The order of comparing is z -> x -> y.
     107    /// The order of comparing is y (height) -> z (depth) -> x (width).
    108108    /// </summary>
    109109    /// <param name="other"></param>
    110110    /// <returns></returns>
    111111    public int CompareTo(PackingPosition other) {
     112      int result = Y.CompareTo(other.Y);
     113      if (result == 0)
     114        result = Z.CompareTo(other.Z);
     115      if (result == 0)
     116        result = X.CompareTo(other.X);
     117      /*
    112118      int result = Z.CompareTo(other.Z);
    113119      if (result == 0)
    … …  
    115121      if (result == 0)
    116122        result = Y.CompareTo(other.Y);
    117      
     123      */
    118124      return result;
    119125

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

    r15276 r15471  
    236236      BinShape = data.BinShape;
    237237      var items = new ItemList<PackingItem>(data.Items);
    238       items.Sort((x, y) => y.CompareTo(x));
    239238      Items = items.AsReadOnly();
    240239

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

    r15463 r15471  
    88
    99namespace HeuristicLab.Problems.BinPacking3D.Sorting {
     10
     11  /// <summary>
     12  /// This is a extension class for sorting a permutation.
     13  /// </summary>
    1014  public static class PackingItemSorter {
     15
     16    /// <summary>
     17    /// Sorts a given permutation first by the volume and secoundly by the height.
     18    /// </summary>
     19    /// <param name="items">Permuation which should be sorted</param>
     20    /// <returns>A new sorted permutation</returns>
    1121    public static Permutation SortByVolumeHeight(this IList<PackingItem> items) {
    1222      return new Permutation(PermutationTypes.Absolute,
    … …  
    1727    }
    1828
     29    /// <summary>
     30    /// Sorts a given permutation first by the heigth and secoundly by the volume.
     31    /// </summary>
     32    /// <param name="items">Permuation which should be sorted</param>
     33    /// <returns>A new sorted permutation</returns>
    1934    public static Permutation SortByHeightVolume(this IList<PackingItem> items) {
    2035      return new Permutation(PermutationTypes.Absolute,
    … …  
    2540    }
    2641
     42    /// <summary>
     43    /// Sorts a given permutation first by the area and secondly by the height.
     44    /// </summary>
     45    /// <param name="items">Permuation which should be sorted</param>
     46    /// <returns>A new sorted permutation</returns>
    2747    public static Permutation SortByAreaHeight(this IList<PackingItem> items) {
    2848      return new Permutation(PermutationTypes.Absolute,
    … …  
    3353    }
    3454
     55    /// <summary>
     56    /// Sorts a given permuation first by the height and secoundly by the area.
     57    /// </summary>
     58    /// <param name="items">Permuation which should be sorted</param>
     59    /// <returns>A new sorted permutation</returns>
    3560    public static Permutation SortByHeightArea(this IList<PackingItem> items) {
    3661      return new Permutation(PermutationTypes.Absolute,
    … …  
    4166    }
    4267
     68    /// <summary>
     69    /// Sorts a given permutation. The items are being grouped by the cluster id.
     70    /// The cluster id is calulated as followed: clusterId = Ceiling( (width * depth) / (width * depth * delta))
     71    /// The permutation is first being sorted by the area and secoundly by the height.
     72    /// </summary>
     73    /// <param name="items">Permuation which should be sorted</param>
     74    /// <param name="bin">The bin is needed for building the cluster</param>
     75    /// <param name="delta">The delta is needed for building the cluster</param>
     76    /// <returns>A new sorted permutation</returns>
    4377    public static Permutation SortByClusteredAreaHeight(this IList<PackingItem> items, PackingShape bin, double delta) {
    4478      double clusterRange = bin.Width * bin.Depth * delta;
    … …  
    5286    }
    5387
     88    /// <summary>
     89    /// Sorts a given permutation. The items are being grouped by the cluster id.
     90    /// The cluster id is calulated as followed: clusterId = Ceiling( (height) / (height * delta))
     91    /// The permutation is first being sorted by the height and secoundly by the area.
     92    /// </summary>
     93    /// <param name="items">Permuation which should be sorted</param>
     94    /// <param name="bin">The bin is needed for building the cluster</param>
     95    /// <param name="delta">The delta is needed for building the cluster</param>
     96    /// <returns>A new sorted permutation</returns>
    5497    public static Permutation SortByClusteredHeightArea(this IList<PackingItem> items, PackingShape bin, double delta) {
    5598      double clusterRange2 = bin.Height * delta;
    … …  
    63106    }
    64107
     108    /// <summary>
     109    /// Sorts a given permutation first by the material, secoundly by the volume and finally by the height.
     110    /// </summary>
     111    /// <param name="items">Permuation which should be sorted</param>
     112    /// <returns>A new sorted permutation</returns>
    65113    public static Permutation SortByMaterialVolumeHeight(this IList<PackingItem> items) {
    66114      return new Permutation(PermutationTypes.Absolute,
    … …  
    72120    }
    73121
     122    /// <summary>
     123    /// Sorts a given permutation first by the material, secoundly by the heigth and finally by the volume.
     124    /// </summary>
     125    /// <param name="items">Permuation which should be sorted</param>
     126    /// <returns>A new sorted permutation</returns>
    74127    public static Permutation SortByMaterialHeightVolume(this IList<PackingItem> items) {
    75128      return new Permutation(PermutationTypes.Absolute,
    … …  
    81134    }
    82135
     136    /// <summary>
     137    /// Sorts a given permutation first by the material, secoundly by the area and finally by the height.
     138    /// </summary>
     139    /// <param name="items">Permuation which should be sorted</param>
     140    /// <returns>A new sorted permutation</returns>
    83141    public static Permutation SortByMaterialAreaHeight(this IList<PackingItem> items) {
    84142      return new Permutation(PermutationTypes.Absolute,
    … …  
    90148    }
    91149
     150    /// <summary>
     151    /// Sorts a given permuation first by the material, secoundly by the height and finally by the area.
     152    /// </summary>
     153    /// <param name="items">Permuation which should be sorted</param>
     154    /// <returns>A new sorted permutation</returns>
    92155    public static Permutation SortByMaterialHeightArea(this IList<PackingItem> items) {
    93156      return new Permutation(PermutationTypes.Absolute,
    … …  
    99162    }
    100163
     164    /// <summary>
     165    /// Sorts a given permutation. The items are being grouped by the cluster id.
     166    /// The cluster id is calulated as followed: clusterId = Ceiling( (width * depth) / (width * depth * delta))
     167    /// The permutation is being clusterd by the area, first sorted by the material, secoundly by the height.
     168    /// </summary>
     169    /// <param name="items">Permuation which should be sorted</param>
     170    /// <param name="bin">The bin is needed for building the cluster</param>
     171    /// <param name="delta">The delta is needed for building the cluster</param>
     172    /// <returns>A new sorted permutation</returns>
    101173    public static Permutation SortByMaterialClusteredAreaHeight(this IList<PackingItem> items, PackingShape bin, double delta) {
    102174      double clusterRange = bin.Width * bin.Depth * delta;
    … …  
    104176                items.Select((v, i) => new { Index = i, Item = v, ClusterId = (int)(Math.Ceiling(v.Width * v.Depth / clusterRange)) })
    105177                    .GroupBy(x => x.ClusterId)
    106                     .Select(x => new { Cluster = x.Key, Items = x.OrderByDescending(y => y.Item.Height).ToList() })
    107                     .OrderByDescending(x => x.Cluster)
    108                     .SelectMany(x => x.Items)
    109                     .Select(x => x.Index).ToArray());
    110     }
    111 
     178                    .Select(x => new { Cluster = x.Key, Items = x.OrderByDescending(z => z.Item.Material).ThenByDescending(y => y.Item.Height).ToList() })
     179                    .OrderByDescending(x => x.Cluster)
     180                    .SelectMany(x => x.Items)
     181                    .Select(x => x.Index).ToArray());
     182    }
     183
     184    /// <summary>
     185    /// Sorts a given permutation. The items are being grouped by the cluster id.
     186    /// The cluster id is calulated as followed: clusterId = Ceiling( (height) / (height * delta))
     187    /// The permutation is being clusterd by the height, first sorted by the material, secoundly by the area.
     188    /// </summary>
     189    /// <param name="items">Permuation which should be sorted</param>
     190    /// <param name="bin">The bin is needed for building the cluster</param>
     191    /// <param name="delta">The delta is needed for building the cluster</param>
     192    /// <returns>A new sorted permutation</returns>
    112193    public static Permutation SortByMaterialClusteredHeightArea(this IList<PackingItem> items, PackingShape bin,  double delta) {
    113194      double clusterRange2 = bin.Height * delta;
    … …  
    115196                items.Select((v, i) => new { Index = i, Item = v, ClusterId = (int)(Math.Ceiling(v.Height / clusterRange2)) })
    116197                    .GroupBy(x => x.ClusterId)
    117                     .Select(x => new { Cluster = x.Key, Items = x.OrderByDescending(y => y.Item.Depth * y.Item.Width).ToList() })
     198                    .Select(x => new { Cluster = x.Key, Items = x.OrderByDescending(z => z.Item.Material).ThenByDescending(y => y.Item.Depth * y.Item.Width).ToList() })
    118199                    .OrderByDescending(x => x.Cluster)
    119200                    .SelectMany(x => x.Items)

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

    r15462 r15471  
    182182          IDecoder<Permutation> decoder = new ExtremePointPermutationDecoder(BinPackerFactory.CreateBinPacker(fit));
    183183          Permutation sortedItems;
     184                   
    184185          if (SortByMaterialParameter.Value.Value) {
    185186            sortedItems = SortItemsByMaterialAndSortingMethod(bin, items, sort, DeltaParameter.Value.Value);
    … …  
    187188            sortedItems = SortItemsBySortingMethod(bin, items, sort, DeltaParameter.Value.Value);
    188189          }
    189                    
     190         
    190191          var result = Optimize(sortedItems, bin, items, Problem.UseStackingConstraints, decoder, Problem.SolutionEvaluator);
    191 
     192         
    192193          if (double.IsNaN(result.Item2) || double.IsInfinity(result.Item2)) {
    193194            continue;
Note: See TracChangeset for help on using the changeset viewer.