Ignore:
Timestamp:
07/21/16 10:19:55 (5 years ago)
Author:
gkronber
Message:

#1966: new implementation for 2d bin packing problem with permutation encoding

Location:
branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/PackingPlans
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/PackingPlans/BinPacking.cs

    r14128 r14146  
    3131  [Item("BinPacking", "Represents a single-bin packing for a bin-packing problem.")]
    3232  [StorableClass]
    33   public abstract class BinPacking<D,B,I> : Item
     33  public abstract class BinPacking<D, B, I> : Item
    3434    where D : class, IPackingPosition
    3535    where B : PackingShape<D>
    36     where I : PackingShape<D>, IPackingItem {
     36    where I : PackingShape<D> {
    3737    #region Properties
    3838    [Storable]
    39     public ObservableDictionary<int, D> ItemPositions { get; private set; } 
     39    public ObservableDictionary<int, D> ItemPositions { get; private set; }
    4040
    4141    [Storable]
     
    4343
    4444    [Storable]
    45     public B BinMeasures { get; private set; } 
     45    public B BinMeasures { get; private set; }
    4646
    4747    [Storable]
     
    5353    #endregion Properties
    5454
    55     protected BinPacking(B binMeasures) : base() {   
     55    protected BinPacking(B binMeasures)
     56      : base() {
    5657      ItemPositions = new ObservableDictionary<int, D>();
    5758      ItemMeasures = new ObservableDictionary<int, I>();
     
    6465    [StorableConstructor]
    6566    protected BinPacking(bool deserializing) : base(deserializing) { }
    66     protected BinPacking(BinPacking<D,B,I> original, Cloner cloner)
     67    protected BinPacking(BinPacking<D, B, I> original, Cloner cloner)
    6768      : base(original, cloner) {
    6869      this.ItemPositions = new ObservableDictionary<int, D>(original.ItemPositions);
    6970      this.ItemMeasures = new ObservableDictionary<int, I>(original.ItemMeasures);
    70         this.BinMeasures = (B)original.BinMeasures.Clone(cloner);
    71         this.OccupationLayers = new Dictionary<int, List<int>>(original.OccupationLayers);
     71      this.BinMeasures = (B)original.BinMeasures.Clone(cloner);
     72      this.OccupationLayers = new Dictionary<int, List<int>>(original.OccupationLayers);
    7273    }
    73    
     74
    7475    protected abstract void GenerateNewExtremePointsForNewItem(I measures, D position);
    7576
     
    7778    public abstract D FindPositionBySliding(I measures, bool rotated);
    7879
    79     public abstract void SlidingBasedPacking(ref List<int> sequence, ItemList<I> itemMeasures);
    80     public abstract void SlidingBasedPacking(ref List<int> sequence, ItemList<I> itemMeasures, Dictionary<int, bool> rotationArray);
    81     public abstract void ExtremePointBasedPacking(ref List<int> sequence, ItemList<I> itemMeasures, bool stackingConstraints);
    82     public abstract void ExtremePointBasedPacking(ref List<int> sequence, ItemList<I> itemMeasures, bool stackingConstraints, Dictionary<int, bool> rotationArray);
     80    public abstract void SlidingBasedPacking(ref IList<int> sequence, IList<I> itemMeasures);
     81    public abstract void SlidingBasedPacking(ref IList<int> sequence, IList<I> itemMeasures, Dictionary<int, bool> rotationArray);
     82    public abstract void ExtremePointBasedPacking(ref IList<int> sequence, IList<I> itemMeasures, bool stackingConstraints);
     83    public abstract void ExtremePointBasedPacking(ref IList<int> sequence, IList<I> itemMeasures, bool stackingConstraints, Dictionary<int, bool> rotationArray);
    8384
    8485    public void PackItem(int itemID, I measures, D position) {
     
    8889      foreach (int id in ItemMeasures.Select(x => x.Key))
    8990        GenerateNewExtremePointsForNewItem(ItemMeasures[id], ItemPositions[id]);
    90      
    91        
    92       //GenerateNewExtremePointsForNewItem(measures, position);
    93       //OccupiedPoints.OccupyPoints(measures, position, itemID);
    9491
    9592      AddNewItemToOccupationLayers(itemID, measures, position);
    9693    }
    9794
    98     public double PackingDensity { 
     95    public double PackingDensity {
    9996      get {
    10097        double result = 0;
     
    108105
    109106    public int PointOccupation(D position) {
    110       //foreach (var ipEntry in ItemPositions) {
    111       //  if (ItemMeasures[ipEntry.Key].EnclosesPoint(ipEntry.Value, position))
    112       //    return ipEntry.Key;
    113       //}
    114107      foreach (var id in GetLayerItemIDs(position)) {
    115108        if (ItemMeasures[id].EnclosesPoint(ItemPositions[id], position))
     
    120113
    121114    public bool IsPointOccupied(D position) {
    122       //foreach (var ipEntry in ItemPositions) {
    123       //  if (ItemMeasures[ipEntry.Key].EnclosesPoint(ipEntry.Value, position))
    124       //    return true;
    125       //}     
    126115      foreach (var id in GetLayerItemIDs(position)) {
    127116        if (ItemMeasures[id].EnclosesPoint(ItemPositions[id], position))
     
    135124        return false;
    136125
    137       //foreach (var ipEntry in ItemPositions) {
    138       //  if (ItemMeasures[ipEntry.Key].Overlaps(ipEntry.Value, position, measures))
    139       //    return false;
    140       //}
    141126      foreach (var id in GetLayerItemIDs(measures, position)) {
    142127        if (ItemMeasures[id].Overlaps(ItemPositions[id], position, measures))
     
    146131      return true;
    147132    }
    148     public abstract int ShortestPossibleSideFromPoint (D position);
    149     public abstract bool IsStaticStable (I measures, D position);
     133    public abstract int ShortestPossibleSideFromPoint(D position);
     134    public abstract bool IsStaticStable(I measures, D position);
    150135
    151136
     
    154139    protected abstract List<int> GetLayerItemIDs(D position);
    155140    protected abstract List<int> GetLayerItemIDs(I measures, D position);
    156   }   
     141  }
    157142}
  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/PackingPlans/PackingPlan.cs

    r14128 r14146  
    2121
    2222using System;
    23 using System.Collections.Generic;
    2423using System.Linq;
    2524using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     
    2827using HeuristicLab.Data;
    2928using HeuristicLab.Collections;
    30 using HeuristicLab.Encodings.IntegerVectorEncoding;
    3129using HeuristicLab.Problems.BinPacking;
    32 using HeuristicLab.Encodings.PermutationEncoding;
    3330
    3431namespace HeuristicLab.Encodings.PackingEncoding {
Note: See TracChangeset for help on using the changeset viewer.