Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
11/08/17 16:30:41 (6 years ago)
Author:
rhanghof
Message:

#2817
-Added unit tests for bin packing 3d.
-The items can now be sorted by the material.

File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r15454 r15462  
    3333using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    3434using HeuristicLab.Problems.BinPacking3D.Packer;
     35using HeuristicLab.Problems.BinPacking3D.Decoder;
     36
     37using HeuristicLab.Problems.BinPacking3D.Sorting;
    3538
    3639namespace HeuristicLab.Problems.BinPacking3D {
    … …  
    7477      get { return deltaParameter; }
    7578    }
     79
     80    [Storable]
     81    private readonly IValueParameter<BoolValue> sortByMaterialParameter;
     82
     83    public IValueParameter<BoolValue> SortByMaterialParameter {
     84      get { return sortByMaterialParameter; }
     85    }   
    7686
    7787    [StorableConstructor]
    … …  
    8494    }
    8595    public ExtremePointAlgorithm() {
    86       Parameters.Add(sortingMethodParameter = new ValueParameter<EnumValue<SortingMethod>>("SortingMethod", "In which order the items should be packed.", new EnumValue<SortingMethod>(SortingMethod.All)));
    87       Parameters.Add(fittingMethodParameter = new ValueParameter<EnumValue<FittingMethod>>("FittingMethod", "Which method to fit should be used.", new EnumValue<FittingMethod>(FittingMethod.All)));
    88       Parameters.Add(deltaParameter = new ValueParameter<PercentValue>("Delta", "[1;100]% Clustered sorting methods use a delta parameter to determine the clusters.", new PercentValue(.1)));
     96      Parameters.Add(sortingMethodParameter = new ValueParameter<EnumValue<SortingMethod>>(
     97        "SortingMethod", "In which order the items should be packed.", new EnumValue<SortingMethod>(SortingMethod.All)));
     98
     99      Parameters.Add(fittingMethodParameter = new ValueParameter<EnumValue<FittingMethod>>(
     100        "FittingMethod", "Which method to fit should be used.", new EnumValue<FittingMethod>(FittingMethod.All)));
     101
     102      Parameters.Add(deltaParameter = new ValueParameter<PercentValue>(
     103        "Delta", "[1;100]% Clustered sorting methods use a delta parameter to determine the clusters.", new PercentValue(.1)));
     104
     105      Parameters.Add(sortByMaterialParameter = new ValueParameter<BoolValue>(
     106        "SortByMaterial", "If this parameter is set, the items will be sorted by their material first", new BoolValue(true)));
    89107
    90108      Problem = new PermutationProblem();
    … …  
    146164    }
    147165
     166    /// <summary>
     167    /// Retunrs the best solution for the given parameters
     168    /// </summary>
     169    /// <param name="bin"></param>
     170    /// <param name="items"></param>
     171    /// <param name="sortings"></param>
     172    /// <param name="fittings"></param>
     173    /// <param name="token"></param>
     174    /// <returns></returns>
    148175    private Tuple<Solution, double, SortingMethod?, FittingMethod?> GetBest(PackingShape bin, IList<PackingItem> items, SortingMethod[] sortings, FittingMethod[] fittings, CancellationToken token) {
    149176      SortingMethod? bestSorting = null;
    … …  
    153180      foreach (var fit in fittings) {
    154181        foreach (var sort in sortings) {
    155           var result = Optimize(bin, items, sort, fit, DeltaParameter.Value.Value, Problem.UseStackingConstraints, Problem.SolutionEvaluator, token);
     182          IDecoder<Permutation> decoder = new ExtremePointPermutationDecoder(BinPackerFactory.CreateBinPacker(fit));
     183          Permutation sortedItems;
     184          if (SortByMaterialParameter.Value.Value) {
     185            sortedItems = SortItemsByMaterialAndSortingMethod(bin, items, sort, DeltaParameter.Value.Value);
     186          } else {
     187            sortedItems = SortItemsBySortingMethod(bin, items, sort, DeltaParameter.Value.Value);
     188          }
     189                   
     190          var result = Optimize(sortedItems, bin, items, Problem.UseStackingConstraints, decoder, Problem.SolutionEvaluator);
     191
    156192          if (double.IsNaN(result.Item2) || double.IsInfinity(result.Item2)) {
    157193            continue;
    … …  
    175211    }
    176212
    177     private static Tuple<Solution, double> Optimize(PackingShape bin, IList<PackingItem> items, SortingMethod sorting, FittingMethod fitting, double delta, bool stackingConstraints, IEvaluator evaluator, CancellationToken token) {
    178       Permutation sortedItems = SortItemsBySortingMethod(bin, items, sorting, delta);
    179 
    180       if (false) {// alt
    181         ExtremePointPermutationDecoderBase decoder = GetDecoderByFittingMethod(fitting);
    182         var sol = decoder.Decode(sortedItems, bin, items, stackingConstraints);
    183         var fit = evaluator.Evaluate(sol);
    184 
    185         return Tuple.Create(sol, fit);
    186       } else {
    187         Decoder.ExtremePointPermutationDecoder decoder = new Decoder.ExtremePointPermutationDecoder(GetBinPackerByFittingMethod(fitting, sortedItems, bin, items, stackingConstraints));
    188 
    189         var sol = decoder.Decode(sortedItems, bin, items, stackingConstraints);
    190         var fit = evaluator.Evaluate(sol);
    191 
    192         return Tuple.Create(sol, fit);
    193       }
     213    /// <summary>
     214    /// Returns a tuple with the solution and the packing ratio depending on the given parameters
     215    /// </summary>
     216    /// <param name="sortedItems"></param>
     217    /// <param name="bin"></param>
     218    /// <param name="items"></param>
     219    /// <param name="stackingConstraints"></param>
     220    /// <param name="decoder"></param>
     221    /// <param name="evaluator"></param>
     222    /// <returns></returns>
     223    private static Tuple<Solution, double> Optimize(Permutation sortedItems, PackingShape bin, IList<PackingItem> items, bool stackingConstraints, IDecoder<Permutation> decoder, IEvaluator evaluator) {
    194224     
    195 
    196      
    197     }
    198 
    199 
    200 
    201     private static BinPacker GetBinPackerByFittingMethod(FittingMethod fittingMethod, Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
    202       BinPacker binPacker = null;
    203       switch (fittingMethod) {
    204         case FittingMethod.FirstFit:
    205           binPacker = new BinPackerFirstFit(sortedItems, binShape, items, useStackingConstraints);
    206           break;
    207         case FittingMethod.FreeVolumeBestFit:
    208           binPacker = new BinPackerFreeVolumeBestFit(sortedItems, binShape, items, useStackingConstraints);
    209           break;
    210         case FittingMethod.ResidualSpaceBestFit:
    211           binPacker = new BinPackerResidualSpaceBestFit(sortedItems, binShape, items, useStackingConstraints);
    212           break;
    213         default:
    214           throw new ArgumentException("Unknown fitting method: " + fittingMethod);
    215       }
    216       return binPacker;
    217     }
     225      var sol = decoder.Decode(sortedItems, bin, items, stackingConstraints);
     226      var fit = evaluator.Evaluate(sol);
     227
     228      return Tuple.Create(sol, fit);
     229    }
     230   
    218231
    219232    /// <summary>
    … …  
    225238    /// <param name="delta"></param>
    226239    /// <returns></returns>
    227     private static Permutation SortItemsBySortingMethod(PackingShape bin, IList<PackingItem> items, SortingMethod sortingMethod, double delta) {
     240    private Permutation SortItemsBySortingMethod(PackingShape bin, IList<PackingItem> items, SortingMethod sortingMethod, double delta) {
    228241      Permutation sorted = null;
     242     
    229243      switch (sortingMethod) {
    230244        case SortingMethod.Given:
    … …  
    232246          break;
    233247        case SortingMethod.VolumeHeight:
    234           sorted = new Permutation(PermutationTypes.Absolute,
    235                     items.Select((v, i) => new { Index = i, Item = v })
    236                          .OrderByDescending(x => x.Item.Depth * x.Item.Width * x.Item.Height)
    237                          .ThenByDescending(x => x.Item.Height)
    238                          .Select(x => x.Index).ToArray());
     248          sorted = items.SortByVolumeHeight();
    239249          break;
    240250        case SortingMethod.HeightVolume:
    241           sorted = new Permutation(PermutationTypes.Absolute,
    242                     items.Select((v, i) => new { Index = i, Item = v })
    243                          .OrderByDescending(x => x.Item.Height)
    244                          .ThenByDescending(x => x.Item.Depth * x.Item.Width * x.Item.Height)
    245                          .Select(x => x.Index).ToArray());
     251          sorted = items.SortByMaterialHeightVolume();
    246252          break;
    247253        case SortingMethod.AreaHeight:
    248           sorted = new Permutation(PermutationTypes.Absolute,
    249                     items.Select((v, i) => new { Index = i, Item = v })
    250                          .OrderByDescending(x => x.Item.Depth * x.Item.Width)
    251                          .ThenByDescending(x => x.Item.Height)
    252                          .Select(x => x.Index).ToArray());
     254          sorted = items.SortByMaterialAreaHeight();
    253255          break;
    254256        case SortingMethod.HeightArea:
    255           sorted = new Permutation(PermutationTypes.Absolute,
    256                     items.Select((v, i) => new { Index = i, Item = v })
    257                          .OrderByDescending(x => x.Item.Height)
    258                          .ThenByDescending(x => x.Item.Depth * x.Item.Width)
    259                          .Select(x => x.Index).ToArray());
     257          sorted = items.SortByMaterialHeightArea();
    260258          break;
    261259        case SortingMethod.ClusteredAreaHeight:
    262           double clusterRange = bin.Width * bin.Depth * delta;
    263           sorted = new Permutation(PermutationTypes.Absolute,
    264                     items.Select((v, i) => new { Index = i, Item = v, ClusterId = (int)(Math.Ceiling(v.Width * v.Depth / clusterRange)) })
    265                         .GroupBy(x => x.ClusterId)
    266                         .Select(x => new { Cluster = x.Key, Items = x.OrderByDescending(y => y.Item.Height).ToList() })
    267                         .OrderByDescending(x => x.Cluster)
    268                         .SelectMany(x => x.Items)
    269                         .Select(x => x.Index).ToArray());
     260          sorted = items.SortByMaterialClusteredAreaHeight(bin, delta);
    270261          break;
    271262        case SortingMethod.ClusteredHeightArea:
    272           double clusterRange2 = bin.Height * delta;
    273           sorted = new Permutation(PermutationTypes.Absolute,
    274                     items.Select((v, i) => new { Index = i, Item = v, ClusterId = (int)(Math.Ceiling(v.Height / clusterRange2)) })
    275                         .GroupBy(x => x.ClusterId)
    276                         .Select(x => new { Cluster = x.Key, Items = x.OrderByDescending(y => y.Item.Depth * y.Item.Width).ToList() })
    277                         .OrderByDescending(x => x.Cluster)
    278                         .SelectMany(x => x.Items)
    279                         .Select(x => x.Index).ToArray());
     263          sorted = items.SortByMaterialClusteredHeightArea(bin, delta);
    280264          break;
    281265        default:
    … …  
    286270
    287271    /// <summary>
    288     /// Returns a decoder depending on the given fitting method
    289     /// </summary>
    290     /// <param name="fittingMethod"></param>
     272    /// Returns a new permutation of the given items depending on the material and sorting method
     273    /// </summary>
     274    /// <param name="bin"></param>
     275    /// <param name="items"></param>
     276    /// <param name="sortingMethod"></param>
     277    /// <param name="delta"></param>
    291278    /// <returns></returns>
    292     private static ExtremePointPermutationDecoderBase GetDecoderByFittingMethod(FittingMethod fittingMethod) {
    293       ExtremePointPermutationDecoderBase decoder = null;
    294       switch (fittingMethod) {
    295         case FittingMethod.FirstFit:
    296           decoder = new ExtremePointPermutationDecoder();
    297           break;
    298         case FittingMethod.FreeVolumeBestFit:
    299           decoder = new FreeVolumeBestFitExtremePointPermutationDecoder();
    300           break;
    301         case FittingMethod.ResidualSpaceBestFit:
    302           decoder = new ResidualSpaceBestFitExtremePointPermutationDecoder();
     279    private Permutation SortItemsByMaterialAndSortingMethod(PackingShape bin, IList<PackingItem> items, SortingMethod sortingMethod, double delta) {
     280      Permutation sorted = null;
     281
     282      switch (sortingMethod) {
     283        case SortingMethod.Given:
     284          sorted = new Permutation(PermutationTypes.Absolute, Enumerable.Range(0, items.Count).ToArray());
     285          break;
     286        case SortingMethod.VolumeHeight:
     287          sorted = items.SortByVolumeHeight();
     288          break;
     289        case SortingMethod.HeightVolume:
     290          sorted = items.SortByHeightVolume();
     291          break;
     292        case SortingMethod.AreaHeight:
     293          sorted = items.SortByAreaHeight();
     294          break;
     295        case SortingMethod.HeightArea:
     296          sorted = items.SortByHeightArea();
     297          break;
     298        case SortingMethod.ClusteredAreaHeight:
     299          sorted = items.SortByClusteredAreaHeight(bin, delta);
     300          break;
     301        case SortingMethod.ClusteredHeightArea:
     302          sorted = items.SortByClusteredHeightArea(bin, delta);
    303303          break;
    304304        default:
    305           throw new ArgumentException("Unknown fitting method: " + fittingMethod);
    306       }
    307       return decoder;
    308     }
     305          throw new ArgumentException("Unknown sorting method: " + sortingMethod);
     306      }
     307      return sorted;
     308    }
     309
     310
     311
     312    #region Sorting methods   
     313
     314    #endregion
    309315  }
    310316}
Note: See TracChangeset for help on using the changeset viewer.