Free cookie consent management tool by TermsFeed Policy Generator

Changeset 14153


Ignore:
Timestamp:
07/21/16 14:33:53 (8 years ago)
Author:
gkronber
Message:

#1966: implemented 3d bin packing problems (using permutation and integer vector encoding) based on the 2d implementations

Location:
branches/HeuristicLab.BinPacking
Files:
19 added
19 edited

Legend:

Unmodified
Added
Removed

  • branches/HeuristicLab.BinPacking/HeuristicLab.BinPacking.sln

    r14038 r14153  
    11
    22Microsoft Visual Studio Solution File, Format Version 12.00
    3 # Visual Studio 14
    4 VisualStudioVersion = 14.0.25123.0
    5 MinimumVisualStudioVersion = 10.0.40219.1
     3# Visual Studio 2012
    64Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.BinPacking-3.3", "HeuristicLab.Problems.BinPacking\3.3\HeuristicLab.Problems.BinPacking-3.3.csproj", "{F8A55094-3CD5-4034-B0CA-5BD7FFB016D4}"
    75EndProject
    … …  
    97  ProjectSection(SolutionItems) = preProject
    108    ..\Build.cmd = ..\Build.cmd
    11     Performance1.psess = Performance1.psess
    129    ..\PreBuildEvent.cmd = ..\PreBuildEvent.cmd
    1310  EndProjectSection

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/IntegerVectorEncoding/BottomLeftIntegerVectorDecoder.cs

    r14151 r14153  
    4646    }
    4747
    48     protected override PackingPosition FindPositionForItem(BinPacking.BinPacking<PackingPosition, PackingShape, PackingItem> bp, PackingItem item) {
     48    protected override PackingPosition FindPositionForItem(BinPacking2D bp, PackingItem item) {
    4949      return bp.FindPositionBySliding(item, rotated: false);
    5050    }
    5151
    52     protected override BinPacking.BinPacking<PackingPosition, PackingShape, PackingItem> CreatePacking(
     52    protected override BinPacking2D CreatePacking(
    5353      Solution partialSolution,
    5454      ref IList<int> remainingIDs, IList<PackingItem> items) {
    55       var bp = partialSolution.NewBinPacking();
     55      var bp = new BinPacking2D(partialSolution.BinMeasures);
    5656      bp.SlidingBasedPacking(ref remainingIDs, items);
    5757      return bp;

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/IntegerVectorEncoding/ExtremePointIntegerVectorDecoder.cs

    r14151 r14153  
    4646    }
    4747
    48     protected override PackingPosition FindPositionForItem(BinPacking.BinPacking<PackingPosition, PackingShape, PackingItem> bp, PackingItem item) {
     48    protected override PackingPosition FindPositionForItem(BinPacking2D bp, PackingItem item) {
    4949      return bp.FindExtremePointForItem(item, false, stackingConstraints: false);
    5050    }
    5151
    52     protected override BinPacking.BinPacking<PackingPosition, PackingShape, PackingItem> CreatePacking(
     52    protected override BinPacking2D CreatePacking(
    5353      Solution partialSolution,
    5454      ref IList<int> remainingIDs, IList<PackingItem> items) {
    55       var bp = partialSolution.NewBinPacking();
     55      var bp = new BinPacking2D(partialSolution.BinMeasures);
    5656      bp.ExtremePointBasedPacking(ref remainingIDs, items, stackingConstraints: false);
    5757      return bp;

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/IntegerVectorEncoding/IntegerVectorDecoderBase.cs

    r14151 r14153  
    3939
    4040
    41     public Solution Decode(IntegerVector intVec, PackingShape binShape, IList<PackingItem> items) {
     41    public virtual Solution Decode(IntegerVector intVec, PackingShape binShape, IList<PackingItem> items) {
    4242      var sequenceMatrix = IntegerVectorProblem.GenerateSequenceMatrix(intVec);
    4343      Solution result = CreateSolution(binShape);
    … …  
    5454      var temp = new List<int>(remainingIDs);
    5555      foreach (int id in temp) {
    56         foreach (var bp in result.BinPackings) {
     56        foreach (BinPacking2D bp in result.BinPackings) {
    5757          var position = FindPositionForItem(bp, items[id]);
    5858          if (position != null) {
    … …  
    7070      result.UpdateBinPackings();
    7171
    72       // gkronber: original implementation also updates the encoded solution
     72      // gkronber: original implementation by Helm also updates the encoded solution (TODO)
    7373      // var newSolution = new int[intVec.Length];
    7474      // int binIndex = 0;
    … …  
    8484
    8585    protected abstract Solution CreateSolution(PackingShape binShape);
    86     protected abstract PackingPosition FindPositionForItem(BinPacking.BinPacking<PackingPosition, PackingShape, PackingItem> bp, PackingItem item);
    87     protected abstract BinPacking.BinPacking<PackingPosition, PackingShape, PackingItem> CreatePacking(Solution partialSolution, ref IList<int> remainingIDs, IList<PackingItem> items);
     86    protected abstract PackingPosition FindPositionForItem(BinPacking2D bp, PackingItem item);
     87    protected abstract BinPacking2D CreatePacking(Solution partialSolution, ref IList<int> remainingIDs, IList<PackingItem> items);
    8888  }
    8989}

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/IntegerVectorEncoding/IntegerVectorProblem.cs

    r14151 r14153  
    6666    private void AddOperators() {
    6767
    68       // move operators are not yet supported
     68      // move operators are not yet supported (TODO)
    6969      Operators.RemoveAll(x => x is SingleObjectiveMoveGenerator);
    7070      Operators.RemoveAll(x => x is SingleObjectiveMoveMaker);
    7171      Operators.RemoveAll(x => x is SingleObjectiveMoveEvaluator);
    7272
    73       Encoding.ConfigureOperators(Operators.OfType<IOperator>());
     73      Encoding.ConfigureOperators(Operators.OfType<IOperator>()); // gkronber: not strictly necessary (only when customer ops are added)
    7474    }
    7575

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/Interfaces/IDecoder.cs

    r14149 r14153  
    2020#endregion
    2121
    22 using System.Collections;
    2322using System.Collections.Generic;
    2423using HeuristicLab.Core;
    25 using HeuristicLab.Encodings.PermutationEncoding;
    26 using HeuristicLab.Problems.BinPacking;
    2724
    2825namespace HeuristicLab.Problems.BinPacking2D {

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/MoveEvaluatorBase.cs

    r14149 r14153  
    2323using HeuristicLab.Core;
    2424using HeuristicLab.Data;
    25 using HeuristicLab.Encodings.PermutationEncoding;
    2625using HeuristicLab.Operators;
    2726using HeuristicLab.Optimization;

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/PermutationEncoding/BottomLeftPermutationDecoder.cs

    r14149 r14153  
    4545      IList<int> remainingIDs = new List<int>(permutation);
    4646      while (remainingIDs.Count > 0) {
    47         var bp = result.NewBinPacking();
     47        var bp = new BinPacking2D(binShape);
    4848        bp.SlidingBasedPacking(ref remainingIDs, items);
    4949        result.BinPackings.Add(bp);

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/PermutationEncoding/ExtremePointPermutationDecoder.cs

    r14149 r14153  
    4545      IList<int> remainingIDs = new List<int>(permutation);
    4646      while (remainingIDs.Count > 0) {
    47         var bp = result.NewBinPacking();
     47        var bp = new BinPacking2D(binShape);
    4848        bp.ExtremePointBasedPacking(ref remainingIDs, items, stackingConstraints: false);
    4949        result.BinPackings.Add(bp);

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/PermutationEncoding/PermutationProblem.cs

    r14151 r14153  
    7171
    7272      Encoding.ConfigureOperators(Operators.OfType<IOperator>());
     73
     74      // TODO: configure the move evaluators (add interface for my move evaluators)
    7375    }
    7476

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/ProblemBase.cs

    r14149 r14153  
    3737    where TEnc : class, IEncoding
    3838    where TSol : class, IItem {
    39     private readonly string SolutionEvaluatorParameterName = "SolutionEvaluator";
     39    protected readonly string SolutionEvaluatorParameterName = "SolutionEvaluator";
    4040    public readonly string EncodedSolutionName = "EncodedSolution";
    4141    #region Default Instance
    42     private static readonly BPPData DefaultInstance = new BPPData() {
     42    private readonly BPPData defaultInstance = new BPPData() {
    4343      Name = "2D BPP Default Instance",
    4444      Description = "The default instance for 2D Bin Packing.",
    … …  
    155155      Parameters.Add(new FixedValueParameter<IntValue>("LowerBound", "A lower bound for the number of bins that is necessary to pack all items"));
    156156
    157       Load(DefaultInstance);
     157      Load(defaultInstance);
    158158    }
    159159

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/Solution.cs

    r14151 r14153  
    3939      return new Solution(this, cloner);
    4040    }
    41     public override BinPacking<PackingPosition, PackingShape, PackingItem> NewBinPacking() {
    42       return new BinPacking2D(BinMeasures);
    43     }
    4441  }
    4542}

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.3D/3.3/BinPacking3D.cs

    r14151 r14153  
    4141    protected BinPacking3D(BinPacking3D original, Cloner cloner)
    4242      : base(original, cloner) {
    43       this.depthWasDoubled = original.depthWasDoubled;
    4443      this.ExtremePoints = new SortedSet<PackingPosition>(original.ExtremePoints, new EPComparer3D());
    4544    }
    … …  
    7776        ExtremePoints.Add(current);
    7877      }
    79 
    80 
    81 
    8278
    8379      //Find ExtremePoints beginning from sourcepointY
    … …  
    9591        ExtremePoints.Add(current);
    9692
    97         //Traversing down the z-axis                                                                   
     93        //Traversing down the z-axis
    9894        current = new PackingPosition(0, sourcePointY.X, sourcePointY.Y, sourcePointY.Z);
    9995        while (current.Z > 0 && !IsPointOccupied(PackingPosition.MoveBack(current))) {
    … …  
    107103      }
    108104
    109 
    110 
    111 
    112 
    113105      //Find ExtremePoints beginning from sourcepointZ
    114106      var sourcePointZ = new PackingPosition(0, position.X, position.Y, position.Z + newDepth);
    115107      if (sourcePointZ.X < BinMeasures.Width && sourcePointZ.Y < BinMeasures.Height && sourcePointZ.Z < BinMeasures.Depth) {
    116         //Traversing down the x-axis                                                                             
     108        //Traversing down the x-axis
    117109        PackingPosition current = new PackingPosition(0, sourcePointZ.X, sourcePointZ.Y, sourcePointZ.Z);
    118110        while (current.X > 0 && !IsPointOccupied(PackingPosition.MoveLeft(current))) {
    … …  
    125117        ExtremePoints.Add(current);
    126118
    127         //Traversing down the y-axis                                                                     
     119        //Traversing down the y-axis
    128120        current = new PackingPosition(0, sourcePointZ.X, sourcePointZ.Y, sourcePointZ.Z);
    129121        while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
    … …  
    136128        ExtremePoints.Add(current);
    137129      }
    138 
    139       //ExtremePoints.RemoveWhere(ep => IsPointOccupied (ep));
    140 
    141       //ExtremePoints = new HashSet<ThreeDimensionalPacking>(ExtremePoints.
    142       //  OrderBy(ep => ep.Z).
    143       //  ThenBy(ep => ep.X).
    144       //  ThenBy(ep => ep.Y)//.ThenBy(ep => ShortestPossibleSideFromPoint(ep))
    145       //  );
    146130    }
    147131
    … …  
    171155
    172156    public override PackingPosition FindPositionBySliding(PackingItem measures, bool rotated) {
     157      //TODO: does not support stacking constraints yet
    173158      //Starting-position at upper right corner (=left bottom point of item-rectangle is at position item.width,item.height)
    174159      PackingPosition currentPosition = new PackingPosition(0,
    … …  
    282267        return true;
    283268
    284 
    285       //if (occupiedPoints[position.X, position.Y - 1, position.Z] != -1
    286       //  && occupiedPoints[position.X + item.Width - 1, position.Y - 1, position.Z] != -1
    287       //  && occupiedPoints[position.X, position.Y - 1, position.Z + item.Depth - 1] != -1
    288       //  && occupiedPoints[position.X + item.Width - 1, position.Y - 1, position.Z + item.Depth - 1] != -1)
    289       //  return true;
    290 
    291       //int groundCount = 0;
    292       //for (int x = ep.X; x < ep.X + item.Width - 1; x++) {
    293       //  for (int z = ep.Z; z < ep.Z + item.Depth - 1; z++) {
    294       //    if (occupiedPoints[x,ep.Y-1, z] != -1)                                                     
    295       //      groundCount++;
    296       //  }
    297       //}
    298       //double stableGround = (double)(groundCount) / (double)(item.Width * item.Depth);
    299       //if (stableGround > 0.75)
    300       //  return true;
    301 
    302269      return false;
    303270    }
    304271
    305     [Storable]
    306     private bool depthWasDoubled = false; // TODO ???
    307     public void DoubleDepth() {
    308       if (!depthWasDoubled) {
    309         var oldDepth = BinMeasures.Depth;
    310         BinMeasures.Depth = BinMeasures.Depth * 2;
    311         //OccupiedPoints.ChangeBinMeasures(BinMeasures);
    312         depthWasDoubled = true;
    313       }
    314     }
    315272
    316273    public bool IsSupportedByAtLeastOnePoint(PackingItem item, PackingPosition position) {

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.3D/3.3/HeuristicLab.Problems.BinPacking3D-3.3.csproj

    r14146 r14153  
    163163  <ItemGroup>
    164164    <Compile Include="BinPacking3D.cs" />
    165     <Compile Include="I3DOperator.cs" />
     165    <Compile Include="Evaluators\BinUtilizationEvaluator.cs" />
     166    <Compile Include="Evaluators\PackingRatioEvaluator.cs" />
    166167    <Compile Include="Instances\BPPData.cs" />
    167168    <Compile Include="Instances\RandomDataDescriptor.cs" />
    168169    <Compile Include="Instances\RandomInstanceProvider.cs" />
     170    <Compile Include="IntegerVectorEncoding\BottomLeftIntegerVectorDecoder.cs" />
     171    <Compile Include="IntegerVectorEncoding\ExtremePointIntegerVectorDecoder.cs" />
     172    <Compile Include="IntegerVectorEncoding\IntegerVectorDecoderBase.cs" />
     173    <Compile Include="IntegerVectorEncoding\IntegerVectorProblem.cs" />
     174    <Compile Include="Interfaces\IDecoder.cs" />
     175    <Compile Include="Interfaces\IEvaluator.cs" />
     176    <Compile Include="MoveEvaluatorBase.cs" />
    169177    <Compile Include="PackingItem.cs" />
    170178    <Compile Include="PackingPosition.cs" />
    171179    <Compile Include="PackingShape.cs" />
     180    <Compile Include="PermutationEncoding\BottomLeftPermutationDecoder.cs" />
     181    <Compile Include="PermutationEncoding\ExtremePointPermutationDecoder.cs" />
     182    <Compile Include="PermutationEncoding\PermutationProblem.cs" />
     183    <Compile Include="PermutationEncoding\Swap2MoveEvaluator.cs" />
     184    <Compile Include="PermutationEncoding\TranslocationMoveEvaluator.cs" />
    172185    <Compile Include="Plugin.cs" />
     186    <Compile Include="ProblemBase.cs" />
    173187    <Compile Include="Properties\AssemblyInfo.cs" />
    174188    <Compile Include="Solution.cs" />

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.3D/3.3/PackingItem.cs

    r14049 r14153  
    103103
    104104    private void RegisterEvents() {
    105       // only because of ToString override
     105      // NOTE: only because of ToString override
    106106      WeightParameter.Value.ValueChanged += (sender, args) => OnToStringChanged();
    107107      MaterialParameter.Value.ValueChanged += (sender, args) => OnToStringChanged();

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.3D/3.3/Solution.cs

    r14151 r14153  
    1818      return new Solution(this, cloner);
    1919    }
    20     public override BinPacking<PackingPosition, PackingShape, PackingItem> NewBinPacking() {
    21       return new BinPacking3D(BinMeasures);
    22     }
    2320  }
    2421}

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.Views/3.3/Container3DView.xaml

    r13605 r14153  
    3535        <Viewport3D Name="viewport3D1" >
    3636            <Viewport3D.Camera>
    37                 <PerspectiveCamera x:Name="camMain" Position="0.5 5 5" LookDirection="0 -1 -1"> <!-- camera position for design time-->
     37                <PerspectiveCamera x:Name="camMain" Position="0.5 8 8" LookDirection="0 -1 -1"> <!-- camera position for design time-->
    3838                </PerspectiveCamera>
    3939            </Viewport3D.Camera>
    … …  
    128128                        </RotateTransform3D>
    129129                        <TranslateTransform3D OffsetX="0.5" OffsetY="0.5" OffsetZ="0.5" />
    130                         <ScaleTransform3D x:Name="scaleZoom" CenterX="0.5" CenterY="0.5" CenterZ="0.5" ScaleX="1" ScaleY="1" ScaleZ="1"/>
     130                        <ScaleTransform3D x:Name="scaleZoom" CenterX="0.5" CenterY="0.5" CenterZ="0.5" ScaleX="0.6" ScaleY="0.6" ScaleZ="0.6"/>
    131131                    </Transform3DGroup>
    132132                </ModelVisual3D.Transform>

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

    r14151 r14153  
    2929
    3030namespace HeuristicLab.Problems.BinPacking {
    31   [Item("PackingPlan", "Represents a concrete solution for a bin-packing problem.")]
    3231  [StorableClass]
    33   public abstract class PackingPlan<D, B, I> : Item, IPackingPlan
     32  public abstract class PackingPlan<D, B, I> : Item
    3433    where D : class, IPackingPosition
    3534    where B : PackingShape<D>
    … …  
    8685
    8786
    88     public abstract BinPacking<D, B, I> NewBinPacking();
    8987    public void UpdateBinPackings() {
    9088      BinPackings.RemoveAll(x => x.ItemPositions.Count == 0);

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj

    r14151 r14153  
    179179    <Compile Include="PackingDimensions.cs" />
    180180    <Compile Include="Interfaces\IPackingItem.cs" />
    181     <Compile Include="Interfaces\IPackingPlan.cs" />
    182181    <Compile Include="PackingShape.cs" />
    183182    <Compile Include="PackingSolutionDecoder.cs" />
Note: See TracChangeset for help on using the changeset viewer.