Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
06/07/13 01:20:12 (11 years ago)
Author:
jhelm
Message:

#1966: More refactoring; Added more sophisticated structures for packing-plan and bin-packing representation; Transferred parts of the decoding-algorithms to these structures; Did some more refactoring and cleanup;

Location:
branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings
Files:
3 added
2 deleted
5 edited

Legend:

Unmodified
Added
Removed

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/GroupingVector/GroupingVectorEncoding.cs

    r9348 r9596  
    2020#endregion
    2121
     22using System.Collections.Generic;
     23using System.Linq;
    2224using System.Text;
    2325using HeuristicLab.Common;
    … …  
    5052        GroupingVector = new IntegerVector();
    5153    }
     54
     55    public List<List<int>> GenerateSequenceMatrix() {
     56      List<List<int>> result = new List<List<int>>();
     57      int nrOfBins = GroupingVector.Max() + 1;
     58      for (int i = 0; i < nrOfBins; i++)
     59        result.Add(new List<int>());
     60      for (int i = 0; i < GroupingVector.Length; i++) {
     61        result[GroupingVector[i]].Add(i);
     62      }
     63      return result;
     64    }
     65   
     66
    5267
    5368    public override string ToString() {

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/MultiComponentVector/BinBasedMultiComponentVectorCrossover.cs

    r9563 r9596  
    3333  public class BinBasedMultiComponentVectorCrossover :  MultiComponentVectorCrossover {
    3434    [StorableConstructor]
    35     protected BinBasedMultiComponentVectorCrossover (bool deserializing) : base(deserializing) { }
    36     protected BinBasedMultiComponentVectorCrossover (BinBasedMultiComponentVectorCrossover original, Cloner cloner) : base(original, cloner) { }
    37     public BinBasedMultiComponentVectorCrossover ()
     35    protected BinBasedMultiComponentVectorCrossover(bool deserializing) : base(deserializing) { }
     36    protected BinBasedMultiComponentVectorCrossover(BinBasedMultiComponentVectorCrossover original, Cloner cloner) : base(original, cloner) { }
     37    public BinBasedMultiComponentVectorCrossover()
    3838      : base() {
    3939    }
    4040    public override IDeepCloneable Clone(Cloner cloner) {
    41       return new BinBasedMultiComponentVectorCrossover (this, cloner);
     41      return new BinBasedMultiComponentVectorCrossover(this, cloner);
    4242    }
    4343
    4444    public override MultiComponentVectorEncoding Cross(IRandom random, MultiComponentVectorEncoding parent1, MultiComponentVectorEncoding parent2) {
    45       MultiComponentVectorEncoding child = new MultiComponentVectorEncoding();
     45      MultiComponentVectorEncoding child = new MultiComponentVectorEncoding ();
     46
    4647      int nrOfItems = parent1.NrOfItems;
    4748      bool[] itemAlreadyAssigned = new bool[nrOfItems];
    48 
    49       bool useParent2 = false;
    5049      int nrOfBins = parent1.NrOfBins > parent2.NrOfBins ? parent2.NrOfBins : parent1.NrOfBins;
    5150
     51      //Add one bin from parent1
     52      int swappedBinNr = random.Next(nrOfBins);
     53      var swappedBin = new ItemList<PackingInformation>();
     54      for (int i = 0; i < parent1.PackingInformations[swappedBinNr].Count; i++) {
     55        PackingInformation pi = new PackingInformation(parent1.PackingInformations[swappedBinNr][i]);
     56        if (!itemAlreadyAssigned[pi.ItemID]) {
     57          itemAlreadyAssigned[pi.ItemID] = true;
     58          swappedBin.Add(new PackingInformation(pi));
     59        }
     60      }
     61      child.PackingInformations[swappedBinNr] = swappedBin;
    5262
     63      //Get the remaining bins from parent2
    5364      for (int binNr = 0; binNr < nrOfBins; binNr++) {
    54         MultiComponentVectorEncoding currentParent1 = useParent2 ? parent2 : parent1;
    55         MultiComponentVectorEncoding currentParent2 = useParent2 ? parent1 : parent2;
    56 
    57 
    58         var newBin = new ItemList<PackingInformation>();
    59         double crossPointPercent = 0;
    60 
    61         int nrOfItems1 = currentParent1.PackingInformations[binNr].Count;
    62         if (nrOfItems1 > 0) {
    63           double crossPoint1 = random.Next(nrOfItems1);
    64           crossPointPercent = crossPoint1 / nrOfItems1;
    65           for (int i = 0; i < crossPoint1; i++) {
    66             PackingInformation pi = new PackingInformation(currentParent1.PackingInformations[binNr][i]);
     65        if (binNr != swappedBinNr) {
     66          var newBin = new ItemList<PackingInformation>();
     67          var currentParent = parent2;
     68          int nrOfItemsInBin = currentParent.PackingInformations[binNr].Count;
     69          for (int i = 0; i < nrOfItemsInBin; i++) {
     70            PackingInformation pi = new PackingInformation(currentParent.PackingInformations[binNr][i]);
    6771            if (!itemAlreadyAssigned[pi.ItemID]) {
    6872              itemAlreadyAssigned[pi.ItemID] = true;
    … …  
    7074            }
    7175          }
     76          child.PackingInformations[binNr] = newBin;
    7277        }
    73 
    74         int nrOfItems2 = currentParent2.PackingInformations[binNr].Count;
    75         if (nrOfItems2 > 0) {
    76           int crossPoint2 = Convert.ToInt32(nrOfItems2 * crossPointPercent);
    77           for (int i = crossPoint2; i < nrOfItems2; i++) {
    78             PackingInformation pi = new PackingInformation(currentParent2.PackingInformations[binNr][i]);
    79             if (!itemAlreadyAssigned[pi.ItemID]) {
    80               itemAlreadyAssigned[pi.ItemID] = true;
    81               newBin.Add(new PackingInformation(pi));
    82             }
    83           }
    84         }
    85 
    86         child.PackingInformations[binNr] = newBin;
    87         useParent2 = !useParent2;
    8878      }
    8979
     80      //Pack still remaining items in bin#0
    9081      for (int itemID = 0; itemID < nrOfItems; itemID++) {
    9182        if (!itemAlreadyAssigned[itemID])
    … …  
    9384      }
    9485
    95      
     86
    9687      return child;
    9788    }       

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/MultiComponentVector/MultiComponentVectorEncoding.cs

    r9563 r9596  
    2121
    2222using System;
     23using System.Collections.Generic;
    2324using System.Text;
    2425using HeuristicLab.Collections;
    … …  
    6465      : base() {
    6566        PackingInformations = new ObservableDictionary<int, ItemList<PackingInformation>>();
    66     }       
     67    }
     68
     69    public List<List<int>> GenerateSequenceMatrix() {
     70      List<List<int>> result = new List<List<int>>();
     71      foreach (var bi in PackingInformations) {
     72        var temp = new List<int>();
     73        foreach (var piEntry in bi.Value) {
     74          temp.Add(piEntry.ItemID);
     75        }
     76        result.Add(temp);
     77      }
     78      return result;
     79    }
     80    public Dictionary<int, bool> GenerateRotationArray() {
     81      Dictionary<int, bool> result = new Dictionary<int, bool>();
     82      foreach (var bi in PackingInformations)
     83        foreach (var pi in bi.Value)
     84          result[pi.ItemID] = pi.Rotated;
     85      return result;
     86    }
     87
     88
    6789
    6890    public override string ToString() {

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/MultiComponentVector/SequenceBasedMultiComponentVectorCrossover.cs

    r9593 r9596  
    3333  public class SequenceBasedMultiComponentVectorCrossover :  MultiComponentVectorCrossover {
    3434    [StorableConstructor]
    35     protected SequenceBasedMultiComponentVectorCrossover(bool deserializing) : base(deserializing) { }
    36     protected SequenceBasedMultiComponentVectorCrossover(SequenceBasedMultiComponentVectorCrossover original, Cloner cloner) : base(original, cloner) { }
    37     public SequenceBasedMultiComponentVectorCrossover()
     35    protected SequenceBasedMultiComponentVectorCrossover (bool deserializing) : base(deserializing) { }
     36    protected SequenceBasedMultiComponentVectorCrossover (SequenceBasedMultiComponentVectorCrossover original, Cloner cloner) : base(original, cloner) { }
     37    public SequenceBasedMultiComponentVectorCrossover ()
    3838      : base() {
    3939    }
    4040    public override IDeepCloneable Clone(Cloner cloner) {
    41       return new SequenceBasedMultiComponentVectorCrossover(this, cloner);
     41      return new SequenceBasedMultiComponentVectorCrossover (this, cloner);
    4242    }
    4343
    4444    public override MultiComponentVectorEncoding Cross(IRandom random, MultiComponentVectorEncoding parent1, MultiComponentVectorEncoding parent2) {
    45       MultiComponentVectorEncoding child = new MultiComponentVectorEncoding ();
    46 
     45      MultiComponentVectorEncoding child = new MultiComponentVectorEncoding();
    4746      int nrOfItems = parent1.NrOfItems;
    4847      bool[] itemAlreadyAssigned = new bool[nrOfItems];
     48
     49      bool useParent2 = false;
    4950      int nrOfBins = parent1.NrOfBins > parent2.NrOfBins ? parent2.NrOfBins : parent1.NrOfBins;
    50       int swappedBin = random.Next(nrOfBins);
     51
    5152
    5253      for (int binNr = 0; binNr < nrOfBins; binNr++) {
     54        MultiComponentVectorEncoding currentParent1 = useParent2 ? parent2 : parent1;
     55        MultiComponentVectorEncoding currentParent2 = useParent2 ? parent1 : parent2;
     56
    5357
    5458        var newBin = new ItemList<PackingInformation>();
    55         var currentParent = binNr == swappedBin ? parent1 : parent2;
     59        double crossPointPercent = 0;
    5660
    57         int nrOfItemsInBin = currentParent.PackingInformations[binNr].Count;
    58         for (int i = 0; i < nrOfItemsInBin; i++) {
    59           PackingInformation pi = new PackingInformation(currentParent.PackingInformations[binNr][i]);
    60           if (!itemAlreadyAssigned[pi.ItemID]) {
    61             itemAlreadyAssigned[pi.ItemID] = true;
    62             newBin.Add(new PackingInformation(pi));
     61        int nrOfItems1 = currentParent1.PackingInformations[binNr].Count;
     62        if (nrOfItems1 > 0) {
     63          double crossPoint1 = random.Next(nrOfItems1);
     64          crossPointPercent = crossPoint1 / nrOfItems1;
     65          for (int i = 0; i < crossPoint1; i++) {
     66            PackingInformation pi = new PackingInformation(currentParent1.PackingInformations[binNr][i]);
     67            if (!itemAlreadyAssigned[pi.ItemID]) {
     68              itemAlreadyAssigned[pi.ItemID] = true;
     69              newBin.Add(new PackingInformation(pi));
     70            }
     71          }
     72        }
     73
     74        int nrOfItems2 = currentParent2.PackingInformations[binNr].Count;
     75        if (nrOfItems2 > 0) {
     76          int crossPoint2 = Convert.ToInt32(nrOfItems2 * crossPointPercent);
     77          for (int i = crossPoint2; i < nrOfItems2; i++) {
     78            PackingInformation pi = new PackingInformation(currentParent2.PackingInformations[binNr][i]);
     79            if (!itemAlreadyAssigned[pi.ItemID]) {
     80              itemAlreadyAssigned[pi.ItemID] = true;
     81              newBin.Add(new PackingInformation(pi));
     82            }
    6383          }
    6484        }
    6585
    6686        child.PackingInformations[binNr] = newBin;
     87        useParent2 = !useParent2;
    6788      }
    6889
    … …  
    7293      }
    7394
    74 
     95     
    7596      return child;
    7697    }       

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/PackingPlans/PackingPlan.cs

    r9593 r9596  
    3535using HeuristicLab.Problems.BinPacking.Dimensions;
    3636using HeuristicLab.Problems.BinPacking.PackingBin;
     37using HeuristicLab.Encodings.PackingEncoding.MultiComponentVector;
     38using HeuristicLab.Encodings.PackingEncoding.GroupingVector;
     39using HeuristicLab.Encodings.PackingEncoding.PackingSequence;
    3740
    3841namespace HeuristicLab.Encodings.PackingEncoding.PackingPlan {
    3942  [Item("PackingPlan", "Represents a concrete solution for a bin-packing problem.")]
    4043  [StorableClass]
    41   public class PackingPlan<D, B, I> : ParameterizedNamedItem, IPackingPlan
     44  public abstract class PackingPlan<D, B, I> : ParameterizedNamedItem, IPackingPlan
    4245    where D : class, IPackingDimensions
    4346    where B : PackingShape<D>, IPackingBin
    … …  
    5255      }
    5356    }
     57    [Storable]
     58    protected bool StackingConstraints { get; set; }
     59    [Storable]
     60    protected bool UseExtremePoints { get; set; }
     61
     62    [Storable]
     63    public B BinMeasures { get; private set; }
    5464
    5565    [Storable]
    … …  
    7181    #endregion
    7282
    73     public PackingPlan(B binMeasures)
    74       : this(){
    75       //this.BinPackings.Add(new BinPacking<D,B,I> ());
    76     }
    77     public PackingPlan()
    78       : base() {
    79       this.BinPackings = new ObservableList<BinPacking<D, B,I>>();
     83    public PackingPlan(B binMeasures, bool useExtremePoints, bool stackingConstraints)
     84      : base(){
     85        BinMeasures = (B)binMeasures.Clone();
     86        StackingConstraints = stackingConstraints;
     87        UseExtremePoints = useExtremePoints;
     88        BinPackings = new ObservableList<BinPacking<D, B, I>>();
    8089    }
    8190
    … …  
    8695        this.BinPackings = new ObservableList<BinPacking<D, B, I>>(original.BinPackings);
    8796    }
    88     public override IDeepCloneable Clone(Cloner cloner) {
    89       return new PackingPlan<D,B,I>(this, cloner);
    90     }
    91          
     97   
     98
     99    public abstract BinPacking<D, B, I> NewBinPacking();
     100    public void UpdateBinPackings() {
     101      BinPackings.RemoveAll(x => x.ItemPositions.Count == 0);
     102      BinPackings = new ObservableList<BinPacking<D, B, I>>(BinPackings.OrderByDescending (bp => bp.PackingDensity));
     103    }
     104
     105    public void Pack(MultiComponentVectorEncoding solution, ItemList<I> itemMeasures) {
     106      var sequenceMatrix = solution.GenerateSequenceMatrix();
     107      Dictionary<int, bool> rotated = solution.GenerateRotationArray();
     108
     109      //Fill bins according to grouping vector
     110      List<int> remainingIDs = new List<int>();
     111      foreach (var sequence in sequenceMatrix) {
     112        remainingIDs = remainingIDs.Concat(sequence).ToList();
     113        var bp = NewBinPacking();
     114        if (!UseExtremePoints)
     115          bp.SlidingBasedPacking(ref remainingIDs, itemMeasures, rotated);
     116        else
     117          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints, rotated);
     118        BinPackings.Add(bp);
     119      }
     120      UpdateBinPackings();
     121
     122      //Try to put remaining items in existing bins
     123      var temp = new List<int>(remainingIDs);
     124      foreach (int id in temp) {
     125        foreach (var bp in BinPackings) {
     126          var position = UseExtremePoints ? bp.FindExtremePointForItem(itemMeasures[id], rotated[id], StackingConstraints) : bp.FindPositionBySliding(itemMeasures[id], rotated[id]);
     127          if (position != null) {
     128            bp.PackItem(id, itemMeasures[id], position);
     129            remainingIDs.Remove(id);
     130          }
     131        }
     132      }
     133
     134      //Put still remaining items in new bins
     135      while (remainingIDs.Count > 0) {
     136        var bp = NewBinPacking();
     137        if (!UseExtremePoints)
     138          bp.SlidingBasedPacking(ref remainingIDs, itemMeasures, rotated);
     139        else
     140          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints, rotated);
     141        BinPackings.Add(bp);
     142      }
     143      UpdateBinPackings();
     144    }
     145    public void Pack(GroupingVectorEncoding solution, ItemList<I> itemMeasures) {
     146      var sequenceMatrix = solution.GenerateSequenceMatrix();
     147
     148      //Fill bins according to grouping vector
     149      List<int> remainingIDs = new List<int>();
     150      foreach (var sequence in sequenceMatrix) {
     151        remainingIDs = remainingIDs.Concat(sequence).ToList();
     152        var bp = NewBinPacking();
     153        if (!UseExtremePoints)
     154          bp.SlidingBasedPacking(ref remainingIDs, itemMeasures);
     155        else
     156          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints);
     157        BinPackings.Add(bp);
     158      }
     159      UpdateBinPackings();
     160
     161      //Try to put remaining items in existing bins
     162      var temp = new List<int>(remainingIDs);
     163      foreach (int id in temp) {
     164        foreach (var bp in BinPackings) { 
     165          var position = UseExtremePoints ? bp.FindExtremePointForItem (itemMeasures[id], false, StackingConstraints) : bp.FindPositionBySliding(itemMeasures[id], false);
     166          if (position != null) {
     167            bp.PackItem(id, itemMeasures[id], position);
     168            remainingIDs.Remove(id);
     169          }
     170        }
     171      }
     172
     173      //Put still remaining items in new bins
     174      while (remainingIDs.Count > 0) {
     175        var bp = NewBinPacking();
     176        if (!UseExtremePoints)
     177          bp.SlidingBasedPacking(ref remainingIDs, itemMeasures);
     178        else
     179          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints);
     180        BinPackings.Add(bp);
     181      }
     182      UpdateBinPackings();
     183    }
     184    public void Pack(PackingSequenceEncoding solution, ItemList<I> itemMeasures) {
     185      List<int> remainingIDs = new List<int>(solution.PackingSequence);
     186      while (remainingIDs.Count > 0) {
     187        var bp = NewBinPacking();
     188        if (!UseExtremePoints)
     189          bp.SlidingBasedPacking(ref remainingIDs, itemMeasures);
     190        else
     191          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints);
     192        BinPackings.Add(bp);
     193      }
     194      UpdateBinPackings();
     195    }
     196
    92197
    93198    #region Events
    … …  
    126231  }
    127232
    128   [Item("BinPacking", "Represents a single-bin packing for a bin-packing problem.")]
     233
     234
     235
     236  [Item("PackingPlan2D", "Represents a concrete solution for a 2D bin-packing problem.")]
    129237  [StorableClass]
    130   public abstract class BinPacking<D,B,I>  : Item
    131     where D : class, IPackingDimensions
    132     where B : PackingShape<D>, IPackingBin
    133     where I : PackingShape<D>, IPackingItem {
    134  
    135     [Storable]
    136     public ObservableDictionary<int, D> ItemPositions { get; private set; }
    137 
    138     [Storable]
    139     public B BinMeasures { get; private set; }
    140 
    141     [Storable]
    142     public ObservableDictionary<int, I> ItemMeasures { get; private set; }
    143 
    144     [Storable]
    145     public HashSet<D> ExtremePoints { get; protected set; }
    146 
    147     [Storable]
    148     public OccupiedPoints<D, I> OccupiedPoints { get; protected set; }
    149 
    150     public BinPacking(B binMeasures) : base() {   
    151       ItemPositions = new ObservableDictionary<int, D>();
    152       ItemMeasures = new ObservableDictionary<int, I>();
    153       BinMeasures = (B)binMeasures.Clone();
    154       ExtremePoints = new HashSet<D>();
    155       ExtremePoints.Add(binMeasures.Origin);
    156     }
    157 
     238  public class PackingPlan2D : PackingPlan<TwoDimensionalPacking, RectangularPackingBin, RectangularPackingItem> {
     239    public PackingPlan2D(RectangularPackingBin binMeasures) : this(binMeasures, false, false) { }
     240    public PackingPlan2D(RectangularPackingBin binMeasures, bool useExtremePoints, bool stackingConstraints) : base(binMeasures, useExtremePoints, stackingConstraints) { }
    158241    [StorableConstructor]
    159     protected BinPacking(bool deserializing) : base(deserializing) { }
    160     protected BinPacking(BinPacking<D,B,I> original, Cloner cloner)
     242    protected PackingPlan2D(bool deserializing) : base(deserializing) { }
     243    protected PackingPlan2D(PackingPlan2D original, Cloner cloner)
    161244      : base(original, cloner) {
    162       this.ItemPositions = new ObservableDictionary<int, D>(original.ItemPositions);
    163       this.ItemMeasures = new ObservableDictionary<int, I>(original.ItemMeasures);
    164         this.BinMeasures = (B)original.BinMeasures.Clone(cloner);
    165     }
    166    
    167 
    168     protected abstract void GenerateNewExtremePointsForNewItem(I measures, D position);
    169     public abstract D FindExtremePointForItem(I measures, bool rotated, bool stackingConstraint);
    170     public abstract D FindPositionBySliding(I measures, bool rotated);
    171     public void PackItem(int itemID, I measures, D position) {
    172       ItemMeasures[itemID] = measures;
    173       ItemPositions[itemID] = position;
    174       ExtremePoints.Remove(position);
    175       GenerateNewExtremePointsForNewItem(measures, position);
    176       OccupiedPoints.OccupyPoints(measures, position, itemID);
    177     }
    178 
    179 
    180     public double PackingDensity {
    181       get {
    182         double result = 0;
    183         foreach (var entry in ItemMeasures)
    184           result += entry.Value.MultipliedMeasures;
    185         result /= BinMeasures.MultipliedMeasures;
    186         return result;
    187       }
    188     }
    189 
    190     public bool IsPositionFeasible1(I currentItem, D currentPosition) {
    191       //In this case feasability is defined as following: 1. the item fits into the bin-borders; 2. the item does not collide with another already packed item
    192       if (!BinMeasures.Encloses(currentPosition, currentItem))
    193         return false;
    194 
    195       foreach (var ipEntry in ItemPositions) {
    196         if (ItemMeasures[ipEntry.Key].Overlaps(ipEntry.Value, currentPosition, currentItem))
    197           return false;
    198       }
    199 
    200       return true;
    201     }
    202     public bool IsPositionFeasible(I currentItem, D position) {
    203       if (!BinMeasures.Encloses(position, currentItem))
    204         return false;
    205 
    206       return OccupiedPoints.IsPositionFeasible (currentItem, position);
     245    }
     246    public override IDeepCloneable Clone(Cloner cloner) {
     247      return new PackingPlan2D(this, cloner);
     248    }
     249    public override BinPacking<TwoDimensionalPacking, RectangularPackingBin, RectangularPackingItem> NewBinPacking() {
     250      return new BinPacking2D(BinMeasures);
    207251    }
    208252  }
    … …  
    212256
    213257
    214   [Item("BinPacking2D", "Represents a single-bin packing for a 2D bin-packing problem.")]
     258  [Item("PackingPlan3D", "Represents a concrete solution for a 3D bin-packing problem.")]
    215259  [StorableClass]
    216   public class BinPacking2D : BinPacking<TwoDimensionalPacking, RectangularPackingBin, RectangularPackingItem> {
    217 
    218     public BinPacking2D(RectangularPackingBin binMeasures) : base(binMeasures) {
    219       OccupiedPoints = new OccupiedPoints2D(binMeasures);
    220     }
     260  public class PackingPlan3D : PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> {
     261    public PackingPlan3D(CuboidPackingBin binMeasures) : this(binMeasures, false, false) { }
     262    public PackingPlan3D(CuboidPackingBin binMeasures, bool useExtremePoints, bool stackingConstraints) : base(binMeasures, useExtremePoints, stackingConstraints) { }
    221263    [StorableConstructor]
    222     protected BinPacking2D(bool deserializing) : base(deserializing) { }
    223     protected BinPacking2D(BinPacking2D original, Cloner cloner)
     264    protected PackingPlan3D(bool deserializing) : base(deserializing) { }
     265    protected PackingPlan3D(PackingPlan3D original, Cloner cloner)
    224266      : base(original, cloner) {
    225267    }
    226268    public override IDeepCloneable Clone(Cloner cloner) {
    227       return new BinPacking2D(this, cloner);
    228     }
    229                      
    230     protected override void GenerateNewExtremePointsForNewItem(RectangularPackingItem newItem, TwoDimensionalPacking position) {
    231 
    232       int newWidth = position.Rotated ? newItem.Height : newItem.Width;
    233       int newHeight = position.Rotated ? newItem.Width : newItem.Height;
    234 
    235       //Find ExtremePoints beginning from sourcepointX
    236       var sourcePointX = new TwoDimensionalPacking(0, position.X + newWidth, position.Y);
    237       if (sourcePointX.X < BinMeasures.Width && sourcePointX.Y < BinMeasures.Height) {
    238         //Traversing down the y-axis       
    239         while (sourcePointX.Y > 0 && !OccupiedPoints.IsPointOccupied(new TwoDimensionalPacking(0, sourcePointX.X, sourcePointX.Y - 1))) {
    240           sourcePointX.Y--;
    241         }
    242         ExtremePoints.Add(new TwoDimensionalPacking(0, sourcePointX.X, sourcePointX.Y));
    243       }
    244 
    245 
    246 
    247 
    248       //Find ExtremePoints beginning from sourcepointY
    249       var sourcePointY = new TwoDimensionalPacking(0, position.X, position.Y + newItem.Height);
    250       if (sourcePointY.X < BinMeasures.Width && sourcePointY.Y < BinMeasures.Height) {
    251         //Traversing down the x-axis 
    252         while (sourcePointY.X > 0 && !OccupiedPoints.IsPointOccupied(new TwoDimensionalPacking (0,sourcePointY.X - 1, sourcePointY.Y))) {
    253           sourcePointY.X--;
    254         }
    255         ExtremePoints.Add(new TwoDimensionalPacking(0, sourcePointY.X, sourcePointY.Y));
    256       }
    257 
    258       ExtremePoints = new HashSet<TwoDimensionalPacking>(ExtremePoints.
    259         OrderBy(ep => ep.AssignedBin).
    260         ThenBy(ep => ep.X).
    261         ThenBy(ep => ep.Y).
    262         ThenBy(ep => OccupiedPoints.ShortestPossibleSideFromEP(ep)));
    263     }
    264 
    265     public override TwoDimensionalPacking FindExtremePointForItem(RectangularPackingItem measures, bool rotated, bool stackingConstraint) {
    266       RectangularPackingItem item = new RectangularPackingItem(
    267         rotated ? measures.Height : measures.Width,
    268         rotated ? measures.Width : measures.Height,
    269         measures.TargetBin);
    270 
    271       int epIndex = 0;
    272       while (epIndex < ExtremePoints.Count && (!IsPositionFeasible(item, ExtremePoints.ElementAt(epIndex)))) { epIndex++; }
    273 
    274       if (epIndex < ExtremePoints.Count) {
    275         var result = ExtremePoints.ElementAt(epIndex);
    276         result.Rotated = rotated;
    277         return result;
    278       }
    279       return null;
    280     }
    281     public override TwoDimensionalPacking FindPositionBySliding(RectangularPackingItem measures, bool rotated) {
    282       TwoDimensionalPacking currentPosition = new TwoDimensionalPacking(0,
    283         BinMeasures.Width - (rotated ? measures.Height : measures.Width),
    284         BinMeasures.Height - (rotated ? measures.Width : measures.Height), rotated);
    285       //Slide the item as far as possible to the left
    286       while (IsPositionFeasible(measures, MoveLeft(currentPosition))
    287         || IsPositionFeasible(measures, MoveDown(currentPosition))) {
    288         //Slide the item as far as possible to the bottom
    289         while (IsPositionFeasible(measures, MoveDown(currentPosition))) {
    290           currentPosition = MoveDown(currentPosition);
    291         }
    292         if (IsPositionFeasible(measures, MoveLeft(currentPosition)))
    293           currentPosition = MoveLeft(currentPosition);
    294       }
    295 
    296       return IsPositionFeasible(measures, currentPosition) ? currentPosition : null;
    297     }
    298     private static TwoDimensionalPacking MoveLeft(TwoDimensionalPacking original) {
    299       return new TwoDimensionalPacking(original.AssignedBin, original.X - 1, original.Y, original.Rotated);
    300     }
    301     private static TwoDimensionalPacking MoveDown(TwoDimensionalPacking original) {
    302       return new TwoDimensionalPacking(original.AssignedBin, original.X, original.Y - 1, original.Rotated);
     269      return new PackingPlan3D(this, cloner);
     270    }
     271    public override BinPacking<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> NewBinPacking() {
     272      return new BinPacking3D(BinMeasures);
    303273    }
    304274  }
    305275
    306 
    307 
    308   [Item("BinPacking3D", "Represents a single-bin packing for a 3D bin-packing problem.")]
    309   [StorableClass]
    310   public class BinPacking3D : BinPacking<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> {
    311 
    312    
    313     public BinPacking3D(CuboidPackingBin binMeasures) : base(binMeasures) {
    314       OccupiedPoints = new OccupiedPoints3D(binMeasures);
    315     }
    316     [StorableConstructor]
    317     protected BinPacking3D(bool deserializing) : base(deserializing) { }
    318     protected BinPacking3D(BinPacking3D original, Cloner cloner)
    319       : base(original, cloner) {
    320     }
    321     public override IDeepCloneable Clone(Cloner cloner) {
    322       return new BinPacking3D(this, cloner);
    323     }
    324                                        
    325     protected override void GenerateNewExtremePointsForNewItem(CuboidPackingItem newItem, ThreeDimensionalPacking position) {
    326       int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
    327       int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
    328 
    329       //Find ExtremePoints beginning from sourcepointX
    330       var sourcePointX = new ThreeDimensionalPacking(0, position.X + newWidth, position.Y, position.Z);
    331       if (sourcePointX.X < BinMeasures.Width && sourcePointX.Y < BinMeasures.Height && sourcePointX.Z < BinMeasures.Depth) {
    332         //Traversing down the y-axis                                                                           
    333         int currentYValue = sourcePointX.Y;
    334         while (currentYValue > 0 && !OccupiedPoints.IsPointOccupied(new ThreeDimensionalPacking (0, sourcePointX.X, currentYValue, sourcePointX.Z))) {
    335           currentYValue--;
    336         }
    337         ExtremePoints.Add(new ThreeDimensionalPacking(0, sourcePointX.X, currentYValue, sourcePointX.Z));
    338 
    339         //Traversing down the z-axis
    340         int currentZValue = sourcePointX.Z;
    341         while (currentZValue > 0 && !OccupiedPoints.IsPointOccupied(new ThreeDimensionalPacking (0, sourcePointX.X, sourcePointX.Y, currentZValue - 1))) {
    342           currentZValue--;
    343         }
    344         ExtremePoints.Add(new ThreeDimensionalPacking(0, sourcePointX.X, sourcePointX.Y, currentZValue));
    345       }
    346 
    347 
    348 
    349 
    350       //Find ExtremePoints beginning from sourcepointY
    351       var sourcePointY = new ThreeDimensionalPacking(0, position.X, position.Y + newItem.Height, position.Z);
    352       if (sourcePointY.X < BinMeasures.Width && sourcePointY.Y < BinMeasures.Height && sourcePointY.Z < BinMeasures.Depth) {
    353         //Traversing down the x-axis 
    354         int currentXValue = sourcePointY.X;
    355         while (currentXValue > 0 && !OccupiedPoints.IsPointOccupied(new ThreeDimensionalPacking (0, currentXValue - 1, sourcePointY.Y, sourcePointY.Z))) {
    356           currentXValue--;
    357         }
    358         ExtremePoints.Add(new ThreeDimensionalPacking(0, currentXValue, sourcePointY.Y, sourcePointY.Z));
    359 
    360         //Traversing down the z-axis
    361         int currentZValue = sourcePointY.Z;
    362         while (currentZValue > 0 && !OccupiedPoints.IsPointOccupied(new ThreeDimensionalPacking (0, sourcePointY.X, sourcePointY.Y, currentZValue - 1))) {
    363           currentZValue--;
    364         }
    365         ExtremePoints.Add(new ThreeDimensionalPacking(0, sourcePointY.X, sourcePointY.Y, currentZValue));
    366       }
    367 
    368 
    369 
    370 
    371 
    372       //Find ExtremePoints beginning from sourcepointZ
    373       var sourcePointZ = new ThreeDimensionalPacking(0, position.X, position.Y, position.Z + newDepth);
    374       if (sourcePointZ.X < BinMeasures.Width && sourcePointZ.Y < BinMeasures.Height && sourcePointZ.Z < BinMeasures.Depth) {
    375         //Traversing down the x-axis 
    376         int currentXValue = sourcePointZ.X;
    377         while (currentXValue > 0 && !OccupiedPoints.IsPointOccupied(new ThreeDimensionalPacking (0, currentXValue - 1, sourcePointZ.Y, sourcePointZ.Z))) {
    378           currentXValue--;
    379         }
    380         ExtremePoints.Add(new ThreeDimensionalPacking(0, currentXValue, sourcePointZ.Y, sourcePointZ.Z));
    381 
    382         //Traversing down the y-axis                                                                           
    383         int currentYValue = sourcePointZ.Y;
    384         while (currentYValue > 0 && !OccupiedPoints.IsPointOccupied(new ThreeDimensionalPacking (0, sourcePointZ.X, currentYValue, sourcePointZ.Z))) {
    385           currentYValue--;
    386         }
    387         ExtremePoints.Add(new ThreeDimensionalPacking(0, sourcePointZ.X, currentYValue, sourcePointZ.Z));
    388       }
    389 
    390       ExtremePoints = new HashSet<ThreeDimensionalPacking>(ExtremePoints.
    391         OrderBy(ep => ep.AssignedBin).
    392         ThenBy(ep => ep.Z).
    393         ThenBy(ep => ep.X).
    394         ThenBy(ep => ep.Y).
    395         ThenBy(ep => OccupiedPoints.ShortestPossibleSideFromEP(ep)));
    396     }
    397 
    398     public override ThreeDimensionalPacking FindExtremePointForItem(CuboidPackingItem measures, bool rotated, bool stackingConstraint) {
    399 
    400       CuboidPackingItem item = new CuboidPackingItem(
    401         rotated ? measures.Depth : measures.Width,
    402         measures.Height,
    403         rotated ? measures.Width : measures.Depth,
    404         measures.TargetBin);
    405 
    406       int epIndex = 0;
    407       while (epIndex < ExtremePoints.Count && (
    408         !IsPositionFeasible(item, ExtremePoints.ElementAt(epIndex)) || (stackingConstraint && !OccupiedPoints.IsStaticStable(item, ExtremePoints.ElementAt(epIndex)))
    409       )) { epIndex++; }
    410 
    411       if (epIndex < ExtremePoints.Count) {
    412         var result = ExtremePoints.ElementAt(epIndex);
    413         result.Rotated = rotated;
    414         return result;
    415       }
    416       return null;
    417     }
    418     public override ThreeDimensionalPacking FindPositionBySliding(CuboidPackingItem measures, bool rotated) {
    419       //Starting-position at upper right corner (=left bottom point of item-rectangle is at position item.width,item.height)
    420       ThreeDimensionalPacking currentPosition = new ThreeDimensionalPacking(0,
    421         BinMeasures.Width - (rotated ? measures.Depth : measures.Width),
    422         BinMeasures.Height - measures.Height,
    423         BinMeasures.Depth - (rotated ? measures.Width : measures.Depth), rotated);
    424       //Slide the item as far as possible to the bottom
    425       while (IsPositionFeasible(measures, MoveDown(currentPosition))
    426         || IsPositionFeasible(measures, MoveLeft(currentPosition))
    427         || IsPositionFeasible(measures, MoveBack(currentPosition))) {
    428         //Slide the item as far as possible to the left
    429         while (IsPositionFeasible(measures, MoveLeft(currentPosition))
    430         || IsPositionFeasible(measures, MoveBack(currentPosition))) {
    431           //Slide the item as far as possible to the back
    432           while (IsPositionFeasible(measures, MoveBack(currentPosition))) {
    433             currentPosition = MoveBack(currentPosition);
    434           }
    435           if (IsPositionFeasible(measures, MoveLeft(currentPosition)))
    436             currentPosition = MoveLeft(currentPosition);
    437         }
    438         if (IsPositionFeasible(measures, MoveDown(currentPosition)))
    439           currentPosition = MoveDown(currentPosition);
    440       }
    441 
    442       return IsPositionFeasible(measures, currentPosition) ? currentPosition : null;
    443     }
    444     private static ThreeDimensionalPacking MoveLeft(ThreeDimensionalPacking original) {
    445       return new ThreeDimensionalPacking(original.AssignedBin, original.X - 1, original.Y, original.Z, original.Rotated);
    446     }
    447     private static ThreeDimensionalPacking MoveDown(ThreeDimensionalPacking original) {
    448       return new ThreeDimensionalPacking(original.AssignedBin, original.X, original.Y - 1, original.Z, original.Rotated);
    449     }
    450     private static ThreeDimensionalPacking MoveBack(ThreeDimensionalPacking original) {
    451       return new ThreeDimensionalPacking(original.AssignedBin, original.X, original.Y, original.Z - 1, original.Rotated);
    452     }
    453   }
    454 
    455 
    456 
    457276}
Note: See TracChangeset for help on using the changeset viewer.