Changeset 14976


Ignore:
Timestamp:
05/12/17 14:10:55 (4 years ago)
Author:
dsouravl
Message:

#2762: worked on best fit heuristics

Location:
branches/BinPackingExtension
Files:
3 added
1 deleted
8 edited

Legend:

Unmodified
Added
Removed
  • branches/BinPackingExtension/HeuristicLab.Problems.BinPacking.Views/3.3/BinPacking3DProblemView.Designer.cs

    r14876 r14976  
    128128            this.heuristicComboBox.Size = new System.Drawing.Size(208, 21);
    129129            this.heuristicComboBox.TabIndex = 20;
    130             this.heuristicComboBox.SelectedIndexChanged += new System.EventHandler(this.heuristicComboBox_SelectedIndexChanged);
     130            //this.heuristicComboBox.SelectedIndexChanged += new System.EventHandler(this.heuristicComboBox_SelectedIndexChanged);
    131131            //
    132132            // BinPacking3DProblemView
  • branches/BinPackingExtension/HeuristicLab.Problems.BinPacking.Views/3.3/BinPacking3DProblemView.cs

    r14876 r14976  
    3434      }
    3535
    36       private void heuristicComboBox_SelectedIndexChanged(object sender, EventArgs e) {
     36      /*private void heuristicComboBox_SelectedIndexChanged(object sender, EventArgs e) {
    3737        if (Content == null) return;
    3838        if (heuristicComboBox.SelectedItem.ToString().CompareTo("Best Fit (Free Volume)") == 0) {
    39          
    4039        }
    41       }
     40      }*/
    4241
    4342      private void sortingComboBox_SelectedIndexChanged(object sender, EventArgs e) {
  • branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/2D/BinPacking2D.cs

    r14162 r14976  
    147147      }
    148148    }
     149    public override bool ExtremePointBasedPacking(int itemID, IList<PackingItem> items, bool stackingConstraints) {
     150      var item = items[itemID];
     151      var positionFound = FindExtremePointForItem(item, false, stackingConstraints);
     152      if (positionFound != null) {
     153        PackItem(itemID, item, positionFound);
     154        return true;
     155      }
     156      return false;
     157    }
     158   
    149159    public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints, Dictionary<int, bool> rotationArray) {
    150160      var temp = new List<int>(sequence);
     
    183193      throw new NotSupportedException();
    184194    }
    185 
    186195    protected override void InitializeOccupationLayers() {
    187196      for (int i = 0; i * 10 <= BinShape.Width; i += 1) {
  • branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs

    r14162 r14976  
    2020#endregion
    2121
     22using System;
    2223using System.Collections.Generic;
    2324using System.Linq;
     
    3536      : base(binShape) {
    3637      ExtremePoints = new SortedSet<PackingPosition>();
    37       ExtremePoints.Add(binShape.Origin);
     38      ResidualSpace = new Dictionary<PackingPosition, Tuple<int,int,int>>();
     39      AddExtremePoint(binShape.Origin);
    3840      InitializeOccupationLayers();
    3941    }
     
    4345      : base(original, cloner) {
    4446      this.ExtremePoints = new SortedSet<PackingPosition>(original.ExtremePoints.Select(p => cloner.Clone(p)));
     47      this.ResidualSpace = new Dictionary<PackingPosition, Tuple<int, int, int>>();
     48      foreach (var o in original.ResidualSpace)
     49        this.ResidualSpace.Add(cloner.Clone(o.Key), Tuple.Create(o.Value.Item1, o.Value.Item2, o.Value.Item3));
    4550    }
    4651    public override IDeepCloneable Clone(Cloner cloner) {
     
    6065          current = PackingPosition.MoveDown(current);
    6166        }
    62         ExtremePoints.Add((PackingPosition)current.Clone());
     67        AddExtremePoint((PackingPosition)current.Clone());
    6368        while (current.X > 0 && !IsPointOccupied(PackingPosition.MoveLeft(current))) {
    6469          current = PackingPosition.MoveLeft(current);
    6570        }
    66         ExtremePoints.Add(current);
     71        AddExtremePoint(current);
    6772
    6873        //Traversing down the z-axis
     
    7176          current = PackingPosition.MoveBack(current);
    7277        }
    73         ExtremePoints.Add((PackingPosition)current.Clone());
    74         while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
    75           current = PackingPosition.MoveDown(current);
    76         }
    77         ExtremePoints.Add(current);
     78        AddExtremePoint((PackingPosition)current.Clone());
     79        while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
     80          current = PackingPosition.MoveDown(current);
     81        }
     82        AddExtremePoint(current);
    7883      }
    7984
     
    8691          current = PackingPosition.MoveLeft(current);
    8792        }
    88         ExtremePoints.Add((PackingPosition)current.Clone());
    89         while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
    90           current = PackingPosition.MoveDown(current);
    91         }
    92         ExtremePoints.Add(current);
     93        AddExtremePoint((PackingPosition)current.Clone());
     94        while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
     95          current = PackingPosition.MoveDown(current);
     96        }
     97        AddExtremePoint(current);
    9398
    9499        //Traversing down the z-axis
     
    97102          current = PackingPosition.MoveBack(current);
    98103        }
    99         ExtremePoints.Add((PackingPosition)current.Clone());
    100         while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
    101           current = PackingPosition.MoveDown(current);
    102         }
    103         ExtremePoints.Add(current);
     104        AddExtremePoint((PackingPosition)current.Clone());
     105        while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
     106          current = PackingPosition.MoveDown(current);
     107        }
     108        AddExtremePoint(current);
    104109      }
    105110
     
    112117          current = PackingPosition.MoveLeft(current);
    113118        }
    114         ExtremePoints.Add((PackingPosition)current.Clone());
    115         while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
    116           current = PackingPosition.MoveDown(current);
    117         }
    118         ExtremePoints.Add(current);
     119        AddExtremePoint((PackingPosition)current.Clone());
     120        while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
     121          current = PackingPosition.MoveDown(current);
     122        }
     123        AddExtremePoint(current);
    119124
    120125        //Traversing down the y-axis
     
    123128          current = PackingPosition.MoveDown(current);
    124129        }
    125         ExtremePoints.Add((PackingPosition)current.Clone());
     130        AddExtremePoint((PackingPosition)current.Clone());
    126131        while (current.X > 0 && !IsPointOccupied(PackingPosition.MoveLeft(current))) {
    127132          current = PackingPosition.MoveLeft(current);
    128133        }
    129         ExtremePoints.Add(current);
     134        AddExtremePoint(current);
     135      }
     136    }
     137
     138    private void AddExtremePoint(PackingPosition current) {
     139      if (ExtremePoints.Add(current)) {
     140        var tuple = Tuple.Create(BinShape.Width - current.X, BinShape.Height - current.Y, BinShape.Depth - current.Z);
     141        ResidualSpace.Add(current, tuple);
    130142      }
    131143    }
     
    137149        item.Height,
    138150        rotated ? item.Width : item.Depth,
    139         item.TargetBin);
     151        item.TargetBin, item.Weight, item.Material);
    140152
    141153      int epIndex = 0;
     
    212224        if (positionFound != null) {
    213225          PackItem(itemID, item, positionFound);
     226          if (!(positionFound.X == 0 && positionFound.Y == 0 && positionFound.Z == 0)) {
     227            UpdateResidualSpace(item, positionFound);
     228          }
    214229          sequence.Remove(itemID);
    215230        }
    216231      }
     232    }
     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;
    217241    }
    218242    public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints, Dictionary<int, bool> rotationArray) {
     
    227251      }
    228252    }
    229 
    230253    public override int ShortestPossibleSideFromPoint(PackingPosition position) {
    231254
     
    320343      for (int i = z1; i <= z2; i++)
    321344        result.AddRange(OccupationLayers[i]);
    322 
    323345      return result;
    324346    }
     347   
     348    public void UpdateResidualSpace(PackingItem item, PackingPosition pos) {
     349      foreach (var ep in ExtremePoints) {
     350        if (ep.Z >= pos.Z && ep.Z <= pos.Z + item.Depth) {
     351          if (ep.X <= pos.X && ep.Y >= pos.Y && ep.Y <= pos.Y + item.Height) {
     352            var diff = pos.X - ep.X;
     353            var newRSX = ResidualSpace[ep].Item1 < diff ? ResidualSpace[ep].Item1 : diff;
     354            ResidualSpace[ep] = Tuple.Create(newRSX, ResidualSpace[ep].Item2, ResidualSpace[ep].Item3);
     355          }
     356          if (ep.Y <= pos.Y && ep.X >= pos.X && ep.X <= pos.X + item.Width) {
     357            var diff = pos.Y - ep.Y;
     358            var newRSY = ResidualSpace[ep].Item2 < diff ? ResidualSpace[ep].Item2 : diff;
     359            ResidualSpace[ep] = Tuple.Create(ResidualSpace[ep].Item1, newRSY, ResidualSpace[ep].Item3);
     360          }
     361        }
     362        if (ep.Z <= pos.Z &&
     363          ep.Y >= pos.Y && ep.Y <= pos.Y + item.Height &&
     364          ep.X >= pos.X && ep.X <= pos.X + item.Width) {
     365            var diff = pos.Z - ep.Z;
     366            var newRSZ = ResidualSpace[ep].Item3 < diff ? ResidualSpace[ep].Item3 : diff;
     367            ResidualSpace[ep] = Tuple.Create(ResidualSpace[ep].Item1, ResidualSpace[ep].Item2, newRSZ);
     368        }
     369      }
     370      return;
     371    }
     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    }
    325378  }
    326 
    327 }
  • branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/PermutationEncoding/ExtremePointPermutationDecoder.cs

    r14167 r14976  
    2020#endregion
    2121
     22using System;
    2223using HeuristicLab.Core;
    2324using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     
    2526using System.Collections.Generic;
    2627using HeuristicLab.Encodings.PermutationEncoding;
     28using System.Linq;
     29
    2730
    2831namespace HeuristicLab.Problems.BinPacking3D {
    2932  [Item("Extreme-point Permutation Decoder (3d)", "Decodes the permutation and creates a packing solution candidate")]
    3033  [StorableClass]
    31   public class ExtremePointPermutationDecoder : Item, IDecoder<Permutation> {
     34  public class ExtremePointPermutationDecoder : ExtremePointPermutationDecoderBase {
    3235
    3336    [StorableConstructor]
     
    4144    }
    4245
    43     public Solution Decode(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
     46    public override Solution Decode(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
    4447      Solution result = new Solution(binShape, useExtremePoints: true, stackingConstraints: useStackingConstraints);
    4548      IList<int> remainingIDs = new List<int>(permutation);
  • branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/ProblemBase.cs

    r14162 r14976  
    175175    public override bool Maximization { get { return true; } }
    176176
    177 
    178177    public override double Evaluate(Individual individual, IRandom random) {
    179178      var encodedSolutionCand = (TSol)individual[EncodedSolutionName];
     
    237236      BinShape = data.BinShape;
    238237      var items = new ItemList<PackingItem>(data.Items);
    239       items.Sort((x, y) => y.CompareTo(x));
    240238      Items = items.AsReadOnly();
    241239
  • branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/BinPacking.cs

    r14876 r14976  
    5151    protected Dictionary<int, List<int>> OccupationLayers { get; set; }
    5252
     53    [Storable]
     54    public Dictionary<TPos, Tuple<int,int,int>> ResidualSpace { get; protected set; }
     55
    5356    #endregion Properties
    5457
     
    6467      OccupationLayers = new Dictionary<int, List<int>>();
    6568    }
    66 
    6769
    6870    [StorableConstructor]
     
    9395    public abstract void SlidingBasedPacking(ref IList<int> sequence, IList<TItem> items, Dictionary<int, bool> rotationArray);
    9496    public abstract void ExtremePointBasedPacking(ref IList<int> sequence, IList<TItem> items, bool stackingConstraints);
     97    public abstract bool ExtremePointBasedPacking(int ID, IList<TItem> items, bool stackingConstraints);
    9598    public abstract void ExtremePointBasedPacking(ref IList<int> sequence, IList<TItem> items, bool stackingConstraints, Dictionary<int, bool> rotationArray);
    9699
     
    99102      Positions[itemID] = position;
    100103      ExtremePoints.Remove(position);
     104      if (ResidualSpace != null) ResidualSpace.Remove(position);
    101105      foreach (int id in Items.Select(x => x.Key))
    102106        GenerateNewExtremePointsForNewItem(Items[id], Positions[id]);
    103 
     107     
    104108      AddNewItemToOccupationLayers(itemID, item, position);
    105109    }
     
    146150    public abstract bool IsStaticStable(TItem measures, TPos position);
    147151
    148 
    149152    protected abstract void InitializeOccupationLayers();
    150153    protected abstract void AddNewItemToOccupationLayers(int itemID, TItem item, TPos position);
  • branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj

    r14876 r14976  
    155155    <Compile Include="2D\ProblemBase.cs" />
    156156    <Compile Include="2D\Solution.cs" />
    157     <Compile Include="3D\BestFitHeuristic.cs" />
    158157    <Compile Include="3D\BinPacking3D.cs" />
    159158    <Compile Include="3D\Evaluators\BinUtilizationEvaluator.cs" />
     
    177176    <Compile Include="3D\PackingShape.cs" />
    178177    <Compile Include="3D\PermutationEncoding\BottomLeftPermutationDecoder.cs" />
     178    <Compile Include="3D\PermutationEncoding\ResidualSpaceBestFitExtremePointPermutationDecoder.cs" />
     179    <Compile Include="3D\PermutationEncoding\FreeVolumeBestFitExtremePointPermutationDecoder.cs" />
     180    <Compile Include="3D\PermutationEncoding\ExtremePointPermutationDecoderBase.cs" />
    179181    <Compile Include="3D\PermutationEncoding\ExtremePointPermutationDecoder.cs" />
    180182    <Compile Include="3D\PermutationEncoding\PermutationProblem.cs" />
Note: See TracChangeset for help on using the changeset viewer.