Opened 17 months ago

Last modified 3 months ago

#2817 accepted enhancement

Improve speed of bin packing

Reported by: abeham Owned by: rhanghof
Priority: medium Milestone: HeuristicLab 3.3.16
Component: Problems.BinPacking Version: branch
Keywords: Cc:

Description

The GenerateNewExtremePointsForNewItem method uses a rather primitive way to generate new points. Intersection between vector and plane should be used to calculate the extreme points.

Change History (35)

comment:1 Changed 17 months ago by abeham

  • Status changed from new to accepted

comment:2 Changed 17 months ago by abeham

r15303: created branch

comment:3 Changed 17 months ago by abeham

r15304:

  • Improved speed of GenerateNewExtremePointsForNewItem
  • GenerateNewExtremePointsForNewItem previously generated too many extreme points and the points were generated for each item anew each time an item was packed.
  • Some bugs are still present (generation of unnecessary extreme points, e.g. with a residual space that is a sub-space of the residual space of another extreme point)

comment:4 Changed 17 months ago by abeham

r15305:

  • Avoided generating unnecessary extreme points
  • Added vector calculation code for line/plane intersection

comment:5 Changed 17 months ago by abeham

r15306:

  • Drawing extreme points in the visualization (will add a checkbox to the view to enable/disable this)
  • Fixing some bugs:
    • Updating residual space of extreme points before generating new extreme points
    • Fixed calculation of residual space for new extreme points by calculating intersections
    • Fixed bug in UpdateResidualSpace regarding > and >=

comment:6 Changed 17 months ago by abeham

r15307:

  • Added checkbox to control showing extreme points in visualization
    • Automatically determine size of extreme point cubes
  • Fixed some bugs in extreme point generation

comment:7 Changed 17 months ago by abeham

r15308:

  • fixed remaining bugs

comment:8 Changed 16 months ago by abeham

  • Version changed from 3.3.14 to branch

comment:9 Changed 14 months ago by rhanghof

  • Owner changed from abeham to rhanghof
  • Status changed from accepted to assigned

comment:10 Changed 14 months ago by rhanghof

  • Status changed from assigned to accepted

comment:11 Changed 14 months ago by rhanghof

r15418:

  • New RandomInstanceProvider added for testing the EP-algorithm with the same instances as Silvano Martello, David Pisinger, Daniele Vigo in their paper.
  • Added some Unit Tests for the BinPacking-3D EP-algorithm

comment:12 Changed 14 months ago by rhanghof

r15423:

  • Now the new RandomInstanceProvider creates the same instances as in the specification given by Martello, Pisinger and Vigo.
  • Now the unit tests are testing the new RandomInstanceProvider.

comment:13 Changed 14 months ago by rhanghof

r15424:

  • Added some comments and regions to the source code
  • Added reference instance files created by the test algoritm of S. Martello, D. Pisinger, D. Vigo

comment:14 Changed 14 months ago by rhanghof

r15454:

  • Extreme point bin packing does not need the occupation layer anymore
  • Changes at the fitting algorithm. Now they are packing the items as in the paper of S. Martello, D. Pisinger, D. Vigo described

comment:15 Changed 13 months ago by rhanghof

r15471:

  • Added some unit tests
  • Enhanced the documentation

comment:16 Changed 13 months ago by rhanghof

r15473:

  • Added unit tests
  • Refactoring of bp 3D

comment:17 Changed 13 months ago by rhanghof

r15488:

  • Added line projection based bin packing
  • Added residual spaces to the view

comment:18 Changed 12 months ago by rhanghof

r15520:

  • Changed the calculation algorithm for creating extreme points by using line based projection
  • Changed the calculation of the residual spaces for line based projection

comment:19 Changed 12 months ago by rhanghof

r15554:

  • Unittests
  • Bugfixes on the line projection based extreme point creation method.

comment:20 Changed 11 months ago by rhanghof

r15585:

  • Bugfixes for the line projection based extreme point creation
  • Bugfixes for the tests

comment:21 Changed 11 months ago by rhanghof

r15617:

  • The items can be rotated and tilted now.
  • Added pruning of extreme points in packed bins.
  • Added new packer which packs items by positioning them on the point with the minimum of wasted space. He uses rotating and tilting of items.
  • Added classes for sorting given items.

comment:22 Changed 11 months ago by rhanghof

r15618:

  • The items can be rotated and tilted now.
  • Added pruning of extreme points in packed bins.
  • Added new packer which packs items by positioning them on the point with the minimum of wasted space. It uses rotating and tilting of items.
  • Added classes for sorting given items.

comment:23 Changed 11 months ago by rhanghof

r15646:

  • Dealing with stackable items
  • Enhanced the Evaluator
  • Added parameters some paramters to the packing items

comment:24 Changed 11 months ago by rhanghof

r15652:

  • Little changes on the packer

comment:25 Changed 11 months ago by rhanghof

r15705:

  • Former material is now the layer.
  • Added material enumeration
  • Modification at the minimum residual space left bin packer

comment:26 Changed 10 months ago by rhanghof

r15731:

  • Added a new packer.
  • Enhanced the material types.
  • Added extreme point pruning for layer support in the extrem point creators.
  • BinPacking3D: Added a graph for calculating weigth distribution of the items.

comment:27 Changed 10 months ago by rhanghof

r15770:

  • Added a graph to the BinPacking3D for calculating the weight distribution.
  • Added some materials.

comment:28 Changed 10 months ago by rhanghof

r15801:

  • Little changes on the packer

comment:29 Changed 10 months ago by rhanghof

r15820:

  • Fixes for pruning

comment:30 Changed 10 months ago by rhanghof

r15822:

  • Added the property SequenceGroup to the PackingItem
  • Fixed a bug related to the sequence group

comment:31 Changed 9 months ago by rhanghof

r15838:

  • Fixed a bug at creating the extreme points with the point projection based method.

comment:32 Changed 9 months ago by rhanghof

r15844:

  • Some bug fixes at the placing algorithm

comment:33 Changed 6 months ago by rhanghof

r15959:

  • Refactoring BinPackerFormClosure.cs -> BinPackerWidthBestFit.cs
  • Changes on the unit tests

comment:34 Changed 5 months ago by rhanghof

r15989:

  • Adjusted the unit tests
  • Refactoring of the sorter
  • Bugfix on the BinPackerResidualSpaceBestFit packer

comment:35 Changed 3 months ago by abeham

r16140: updated to trunk r15680

r16141: updated to trunk r16140

Note: See TracTickets for help on using tickets.