Free cookie consent management tool by TermsFeed Policy Generator

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

#1966: Fixed a bug which caused the stacking-contraint to be wrongly enforced; Did some cleanup;

Location:
branches/HeuristicLab.BinPacking
Files:
3 deleted
12 edited

Legend:

Unmodified
Added
Removed

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.Views/3.3/PackingPlans/PackingPlan3DView.cs

    r9593 r9598  
    4444      } else {
    4545        Content.Name = "Packing Plan";
    46         for (int i = 0; i < Content.NrOfBins; i++)
    47           binSelection.Items.Add(i);
     46        int i = 0;
     47        foreach (var bp in Content.BinPackings)
     48          binSelection.Items.Add(i++ + " (" + Math.Round(bp.PackingDensity * 100, 2) + "%)");
     49
    4850        binSelection.SelectedIndex = 0;
    4951        UpdateModel();
    … …  
    5355
    5456    private void UpdateModel() {
    55       int currentBin = (binSelection != null && binSelection.SelectedItem != null) ? (int)(binSelection.SelectedItem) : 0;
     57      int currentBin = (binSelection != null) ? (int)(binSelection.SelectedIndex) : 0;
    5658      var bin = Content.BinPackings[currentBin].BinMeasures;
    5759      packingPlan3D.InitializeContainer(bin.Width, bin.Height, bin.Depth);
    … …  
    7173      itemSelection.SelectedIndex = -1;
    7274      itemSelection.Items.Clear();
    73       int currentBin = (binSelection != null && binSelection.SelectedItem != null) ? (int)(binSelection.SelectedItem) : 0;
     75      int currentBin = (binSelection != null) ? (int)(binSelection.SelectedIndex) : 0;
    7476      //for (int i = 0; i < Content.PackingItemPositions.Count; i++) {
    7577      //  if (Content.PackingItemPositions[i].AssignedBin == currentBin)
    … …  
    106108        } else {
    107109          Content.Name = "Packing Plan";
    108           for (int i = 0; i < Content.NrOfBins; i++)
    109             binSelection.Items.Add(i);
     110          int i = 0;
     111          foreach (var bp in Content.BinPackings)
     112            binSelection.Items.Add(i++ + " (" + Math.Round(bp.PackingDensity * 100, 2) + "%)");
    110113          binSelection.SelectedIndex = 0;
    111114          UpdateModel();

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.Views/3.3/Plugin.cs

    r9596 r9598  
    2626  /// Plugin class for HeuristicLab.Problems.BinPacking.Views plugin.
    2727  /// </summary>
    28   [Plugin("HeuristicLab.Problems.BinPacking.Views", "3.3.7.9593")]
     28  [Plugin("HeuristicLab.Problems.BinPacking.Views", "3.3.7.9596")]
    2929  [PluginFile("HeuristicLab.Problems.BinPacking.Views-3.3.dll", PluginFileType.Assembly)]
    3030  [PluginDependency("HeuristicLab.Common", "3.3")]

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.Views/3.3/Properties/AssemblyInfo.cs

    r9596 r9598  
    5454// by using the '*' as shown below:
    5555[assembly: AssemblyVersion("3.3.0.0")]
    56 [assembly: AssemblyFileVersion("3.3.7.9593")]
     56[assembly: AssemblyFileVersion("3.3.7.9596")]

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Decoders/3D/EP/ISOContainerMultiComponentVectorDecoder3D.cs

    r9596 r9598  
    112112    }
    113113
    114 
    115114    public override PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> CreatePackingPlanFromEncoding(IItem encodedSolution, CuboidPackingBin binMeasures, ItemList<CuboidPackingItem> itemMeasures) {
    116115      var solution = encodedSolution as MultiComponentVectorEncoding;

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Decoders/PackingSolutionDecoder.cs

    r9596 r9598  
    7070      Parameters.Add(new LookupParameter<ItemList<I>>("PackingItemMeasures", "Packing-item data taken from the bin-packing problem-instance."));
    7171      Parameters.Add(new LookupParameter<B>("PackingBinMeasures", "Packing-bin data taken from the bin-packing problem-instance."));
    72       Parameters.Add(new ValueParameter<BoolValue>("StackingConstraint", "A flag determining whether stackingconstraints should be enforced or not."));
     72      Parameters.Add(new ValueParameter<BoolValue>("StackingConstraint", "A flag determining whether stackingconstraints should be enforced or not.", new BoolValue(true)));
    7373    }
    7474

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

    r9596 r9598  
    105105    }
    106106
     107
     108    public int PointOccupation(D position) {
     109      foreach (var ipEntry in ItemPositions) {
     110        if (ItemMeasures[ipEntry.Key].EnclosesPoint(ipEntry.Value, position))
     111          return ipEntry.Key;
     112      }
     113      return -1;
     114    }
    107115    public bool IsPointOccupied(D position) {
    108116      foreach (var ipEntry in ItemPositions) {
    … …  
    110118          return true;
    111119      }
    112 
    113120      return false;
    114121    }
    115122    public bool IsPositionFeasible(I currentItem, D position) {
    116       //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
     123      //In this case feasability is defined as following: 1. the item fits into the bin-borders; 2. the point is supported by something; 3. the item does not collide with another already packed item
    117124      if (!BinMeasures.Encloses(position, currentItem))
    118125        return false;
    … …  
    127134    public abstract int ShortestPossibleSideFromPoint (D position);
    128135    public abstract bool IsStaticStable (I item, D position);
    129    
    130     //public bool IsPositionFeasible1(I currentItem, D position) {
    131     //  if (!BinMeasures.Encloses(position, currentItem))
    132     //    return false;
    133 
    134     //  return OccupiedPoints.IsPositionFeasible (currentItem, position);
    135     //}
    136136  }   
    137137}

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

    r9596 r9598  
    6262      if (sourcePointX.X < BinMeasures.Width && sourcePointX.Y < BinMeasures.Height) {
    6363        //Traversing down the y-axis       
    64         while (sourcePointX.Y > 0 && !IsPointOccupied(new TwoDimensionalPacking(0, sourcePointX.X, sourcePointX.Y - 1))) {
     64        while (sourcePointX.Y > 0 && (-1).Equals(IsPointOccupied(new TwoDimensionalPacking(0, sourcePointX.X, sourcePointX.Y - 1)))) {
    6565          sourcePointX.Y--;
    6666        }
    … …  
    7575      if (sourcePointY.X < BinMeasures.Width && sourcePointY.Y < BinMeasures.Height) {
    7676        //Traversing down the x-axis 
    77         while (sourcePointY.X > 0 && !IsPointOccupied(new TwoDimensionalPacking (0,sourcePointY.X - 1, sourcePointY.Y))) {
     77        while (sourcePointY.X > 0 && (-1).Equals(IsPointOccupied(new TwoDimensionalPacking (0,sourcePointY.X - 1, sourcePointY.Y)))) {
    7878          sourcePointY.X--;
    7979        }
    … …  
    166166    }
    167167
    168 
    169168    public override int ShortestPossibleSideFromPoint(TwoDimensionalPacking position) {
    170169      int shortestSide = int.MaxValue;

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

    r9596 r9598  
    6161      var sourcePointX = new ThreeDimensionalPacking(0, position.X + newWidth, position.Y, position.Z);
    6262      if (sourcePointX.X < BinMeasures.Width && sourcePointX.Y < BinMeasures.Height && sourcePointX.Z < BinMeasures.Depth) {
    63         //Traversing down the y-axis                                                                           
    64         int currentYValue = sourcePointX.Y;
    65         while (currentYValue > 0 && !IsPointOccupied(new ThreeDimensionalPacking (0, sourcePointX.X, currentYValue, sourcePointX.Z))) {
    66           currentYValue--;
    67         }
    68         ExtremePoints.Add(new ThreeDimensionalPacking(0, sourcePointX.X, currentYValue, sourcePointX.Z));
    69 
    70         //Traversing down the z-axis
    71         int currentZValue = sourcePointX.Z;
    72         while (currentZValue > 0 && !IsPointOccupied(new ThreeDimensionalPacking (0, sourcePointX.X, sourcePointX.Y, currentZValue - 1))) {
    73           currentZValue--;
    74         }
    75         ExtremePoints.Add(new ThreeDimensionalPacking(0, sourcePointX.X, sourcePointX.Y, currentZValue));
     63        //Traversing down the y-axis           
     64        ThreeDimensionalPacking current = new ThreeDimensionalPacking(0, sourcePointX.X, sourcePointX.Y, sourcePointX.Z);
     65        while (current.Y > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveDown (current))) {
     66          current = ThreeDimensionalPacking.MoveDown(current);
     67        }
     68        ExtremePoints.Add((ThreeDimensionalPacking)current.Clone());
     69        while (current.X > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveLeft(current))) {
     70          current = ThreeDimensionalPacking.MoveLeft(current);
     71        }
     72        ExtremePoints.Add(current);
     73
     74        //Traversing down the z-axis                 
     75        current = new ThreeDimensionalPacking(0, sourcePointX.X, sourcePointX.Y, sourcePointX.Z);
     76        while (current.Z > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveBack (current))) {
     77          current = ThreeDimensionalPacking.MoveBack(current);
     78        }
     79        ExtremePoints.Add((ThreeDimensionalPacking)current.Clone());
     80        while (current.Y > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveDown(current))) {
     81          current = ThreeDimensionalPacking.MoveDown(current);
     82        }
     83        ExtremePoints.Add(current);
    7684      }
    7785
    … …  
    8290      var sourcePointY = new ThreeDimensionalPacking(0, position.X, position.Y + newItem.Height, position.Z);
    8391      if (sourcePointY.X < BinMeasures.Width && sourcePointY.Y < BinMeasures.Height && sourcePointY.Z < BinMeasures.Depth) {
    84         //Traversing down the x-axis 
    85         int currentXValue = sourcePointY.X;
    86         while (currentXValue > 0 && !IsPointOccupied(new ThreeDimensionalPacking (0, currentXValue - 1, sourcePointY.Y, sourcePointY.Z))) {
    87           currentXValue--;
    88         }
    89         ExtremePoints.Add(new ThreeDimensionalPacking(0, currentXValue, sourcePointY.Y, sourcePointY.Z));
    90 
    91         //Traversing down the z-axis
    92         int currentZValue = sourcePointY.Z;
    93         while (currentZValue > 0 && !IsPointOccupied(new ThreeDimensionalPacking (0, sourcePointY.X, sourcePointY.Y, currentZValue - 1))) {
    94           currentZValue--;
    95         }
    96         ExtremePoints.Add(new ThreeDimensionalPacking(0, sourcePointY.X, sourcePointY.Y, currentZValue));
     92        //Traversing down the x-axis         
     93        ThreeDimensionalPacking current = new ThreeDimensionalPacking(0, sourcePointY.X, sourcePointY.Y, sourcePointY.Z);
     94        while (current.X > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveLeft(current))) {
     95          current = ThreeDimensionalPacking.MoveLeft(current);
     96        }
     97        ExtremePoints.Add((ThreeDimensionalPacking)current.Clone());
     98        while (current.Y > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveDown(current))) {
     99          current = ThreeDimensionalPacking.MoveDown(current);
     100        }
     101        ExtremePoints.Add(current);
     102
     103        //Traversing down the z-axis                                                                   
     104        current = new ThreeDimensionalPacking(0, sourcePointY.X, sourcePointY.Y, sourcePointY.Z);
     105        while (current.Z > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveBack(current))) {
     106          current = ThreeDimensionalPacking.MoveBack(current);
     107        }
     108        ExtremePoints.Add((ThreeDimensionalPacking)current.Clone());
     109        while (current.Y > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveDown(current))) {
     110          current = ThreeDimensionalPacking.MoveDown(current);
     111        }
     112        ExtremePoints.Add(current);
    97113      }
    98114
    … …  
    104120      var sourcePointZ = new ThreeDimensionalPacking(0, position.X, position.Y, position.Z + newDepth);
    105121      if (sourcePointZ.X < BinMeasures.Width && sourcePointZ.Y < BinMeasures.Height && sourcePointZ.Z < BinMeasures.Depth) {
    106         //Traversing down the x-axis 
    107         int currentXValue = sourcePointZ.X;
    108         while (currentXValue > 0 && !IsPointOccupied(new ThreeDimensionalPacking (0, currentXValue - 1, sourcePointZ.Y, sourcePointZ.Z))) {
    109           currentXValue--;
    110         }
    111         ExtremePoints.Add(new ThreeDimensionalPacking(0, currentXValue, sourcePointZ.Y, sourcePointZ.Z));
    112 
    113         //Traversing down the y-axis                                                                           
    114         int currentYValue = sourcePointZ.Y;
    115         while (currentYValue > 0 && !IsPointOccupied(new ThreeDimensionalPacking (0, sourcePointZ.X, currentYValue, sourcePointZ.Z))) {
    116           currentYValue--;
    117         }
    118         ExtremePoints.Add(new ThreeDimensionalPacking(0, sourcePointZ.X, currentYValue, sourcePointZ.Z));
     122        //Traversing down the x-axis                                                                             
     123        ThreeDimensionalPacking current = new ThreeDimensionalPacking(0, sourcePointZ.X, sourcePointZ.Y, sourcePointZ.Z);
     124        while (current.X > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveLeft(current))) {
     125          current = ThreeDimensionalPacking.MoveLeft(current);
     126        }
     127        ExtremePoints.Add((ThreeDimensionalPacking)current.Clone());
     128        while (current.Y > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveDown(current))) {
     129          current = ThreeDimensionalPacking.MoveDown(current);
     130        }
     131        ExtremePoints.Add(current);
     132
     133        //Traversing down the y-axis                                                                     
     134        current = new ThreeDimensionalPacking(0, sourcePointZ.X, sourcePointZ.Y, sourcePointZ.Z);
     135        while (current.Y > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveDown(current))) {
     136          current = ThreeDimensionalPacking.MoveDown(current);
     137        }
     138        ExtremePoints.Add((ThreeDimensionalPacking)current.Clone());
     139        while (current.X > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveLeft(current))) {
     140          current = ThreeDimensionalPacking.MoveLeft(current);
     141        }
     142        ExtremePoints.Add(current);
    119143      }
    120144
    … …  
    122146        OrderBy(ep => ep.Z).
    123147        ThenBy(ep => ep.X).
    124         ThenBy(ep => ep.Y).
    125         ThenBy(ep => ShortestPossibleSideFromPoint(ep)));
     148        ThenBy(ep => ep.Y)//.ThenBy(ep => ShortestPossibleSideFromPoint(ep))
     149        );
    126150    }
    127151
    … …  
    136160      int epIndex = 0;
    137161      while (epIndex < ExtremePoints.Count && (
    138         !IsPositionFeasible(item, ExtremePoints.ElementAt(epIndex)) || (stackingConstraints && !IsStaticStable(item, ExtremePoints.ElementAt(epIndex)))
     162        !IsPositionFeasible(item, ExtremePoints.ElementAt(epIndex))
     163        || !IsSupportedByAtLeastOnePoint(item, ExtremePoints.ElementAt(epIndex))
     164        || (stackingConstraints && !IsStaticStable(item, ExtremePoints.ElementAt(epIndex)))
     165        || (stackingConstraints && !IsWeightSupported(item, ExtremePoints.ElementAt(epIndex)))
    139166      )) { epIndex++; }
    140167
    … …  
    146173      return null;
    147174    }
     175
    148176    public override ThreeDimensionalPacking FindPositionBySliding(CuboidPackingItem measures, bool rotated) {
    149177      //Starting-position at upper right corner (=left bottom point of item-rectangle is at position item.width,item.height)
    … …  
    217245      }
    218246    }
    219    
    220 
    221     [Storable]
    222     private bool depthWasDoubled = false;
    223     public void DoubleDepth() {
    224       if (!depthWasDoubled) {
    225         var oldDepth = BinMeasures.Depth;
    226         BinMeasures.Depth = BinMeasures.Depth * 2;
    227         //OccupiedPoints.ChangeBinMeasures(BinMeasures);
    228         depthWasDoubled = true;
    229       }
    230     }
    231 
     247                                                   
    232248    public override int ShortestPossibleSideFromPoint(ThreeDimensionalPacking position) {
    233249
    … …  
    265281
    266282      if (IsPointOccupied (new ThreeDimensionalPacking (0, position.X, position.Y - 1, position.Z))
    267         && IsPointOccupied (new ThreeDimensionalPacking (0, position.X + item.Width - 1, position.Y - 1, position.Z))
    268         && IsPointOccupied (new ThreeDimensionalPacking (0, position.X, position.Y - 1, position.Z + item.Depth - 1))
    269         && IsPointOccupied (new ThreeDimensionalPacking (0, position.X + item.Width - 1, position.Y - 1, position.Z + item.Depth - 1)))
     283        && IsPointOccupied (new ThreeDimensionalPacking (0, position.X + item.Width, position.Y - 1, position.Z))
     284        && IsPointOccupied (new ThreeDimensionalPacking (0, position.X, position.Y - 1, position.Z + item.Depth))
     285        && IsPointOccupied (new ThreeDimensionalPacking (0, position.X + item.Width, position.Y - 1, position.Z + item.Depth)))
    270286        return true;
    271287
    … …  
    290306      return false;
    291307    }
     308
     309
     310    [Storable]
     311    private bool depthWasDoubled = false;
     312    public void DoubleDepth() {
     313      if (!depthWasDoubled) {
     314        var oldDepth = BinMeasures.Depth;
     315        BinMeasures.Depth = BinMeasures.Depth * 2;
     316        //OccupiedPoints.ChangeBinMeasures(BinMeasures);
     317        depthWasDoubled = true;
     318      }
     319    }
     320         
     321    public bool IsSupportedByAtLeastOnePoint(CuboidPackingItem item, ThreeDimensionalPacking position) {
     322      if (position.Y == 0)
     323        return true;
     324
     325      int y = position.Y - 1;
     326      for (int x = position.X; x < position.X + item.Width; x++)
     327        for (int z = position.Z; z < position.Z + item.Depth; z++)
     328          if (IsPointOccupied(new ThreeDimensionalPacking(0, x, y, z)))
     329            return true;
     330     
     331      return false;
     332    }
     333    public bool IsWeightSupported(CuboidPackingItem item, ThreeDimensionalPacking ep) {
     334      if (ep.Y == 0)
     335        return true;
     336
     337      if (ItemMeasures[PointOccupation(new ThreeDimensionalPacking(0, ep.X, ep.Y - 1, ep.Z))].SupportsStacking(item)
     338        && ItemMeasures[PointOccupation(new ThreeDimensionalPacking(0, ep.X + item.Width, ep.Y - 1, ep.Z))].SupportsStacking(item)
     339        && ItemMeasures[PointOccupation(new ThreeDimensionalPacking(0, ep.X, ep.Y - 1, ep.Z + item.Depth))].SupportsStacking(item)
     340        && ItemMeasures[PointOccupation(new ThreeDimensionalPacking(0, ep.X + item.Width, ep.Y - 1, ep.Z + item.Depth))].SupportsStacking(item))
     341        return true;
     342
     343      return false;
     344    }
    292345  }
    293346}

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Plugin.cs

    r9596 r9598  
    2626  /// Plugin class for HeuristicLab.Problems.BinPacking plugin.
    2727  /// </summary>
    28   [Plugin("HeuristicLab.Problems.BinPacking", "3.3.7.9593")]
     28  [Plugin("HeuristicLab.Problems.BinPacking", "3.3.7.9596")]
    2929  [PluginFile("HeuristicLab.Problems.BinPacking-3.3.dll", PluginFileType.Assembly)]
    3030  [PluginDependency("HeuristicLab.Common", "3.3")]

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Problem/CuboidIdenticalBinPackingProblem.cs

    r9563 r9598  
    145145      Load(DefaultInstance);
    146146    }
     147
     148    protected override void RemoveTooBigItems() {
     149      PackingItemMeasures.RemoveAll(pi =>
     150        !PackingBinMeasures.Encloses (new ThreeDimensionalPacking(0, 0, 0, 0, false), pi) &&
     151        !PackingBinMeasures.Encloses(new ThreeDimensionalPacking(0, 0, 0, 0, true), pi));
     152    }
    147153    #endregion
    148154  }

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Problem/RectangularIdenticalBinPackingProblem.cs

    r9563 r9598  
    139139      Load(DefaultInstance);
    140140    }
     141
     142    protected override void RemoveTooBigItems() {
     143      PackingItemMeasures.RemoveAll(pi =>
     144        !PackingBinMeasures.Encloses(new TwoDimensionalPacking(0, 0, 0, false), pi) &&
     145        !PackingBinMeasures.Encloses(new TwoDimensionalPacking(0, 0, 0, true), pi));
     146    }
    141147    #endregion
    142148  }

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Problem/RegularIdenticalBinPackingProblem.cs

    r9563 r9598  
    4343using HeuristicLab.Problems.Instances;
    4444using HeuristicLab.Encodings.PackingEncoding.MultiComponentVector;
     45using HeuristicLab.Problems.BinPacking.Dimensions;
    4546
    4647namespace HeuristicLab.Problems.BinPacking.Problem {
    … …  
    100101      ApplyHorizontalOrientation();
    101102      SortItems();
     103      RemoveTooBigItems();
    102104      PackingItemsParameter.Value.Value = PackingItemMeasures.Count;
    103105      LowerBoundParameter.Value.Value = CalculateLowerBound();
    104106    }
     107    protected abstract void RemoveTooBigItems();
    105108    protected abstract void InitializeProblemData();
    106109    protected abstract IPackingPlanEvaluator CreateDefaultEvaluator();
Note: See TracChangeset for help on using the changeset viewer.