Opened 19 months ago
Last modified 5 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 19 months ago by abeham
- Status changed from new to accepted
comment:2 Changed 19 months ago by abeham
comment:3 Changed 19 months ago by abeham
- 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 19 months ago by abeham
- Avoided generating unnecessary extreme points
- Added vector calculation code for line/plane intersection
comment:5 Changed 19 months ago by abeham
- 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 19 months ago by abeham
- 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 19 months ago by abeham
- fixed remaining bugs
comment:8 Changed 18 months ago by abeham
- Version changed from 3.3.14 to branch
comment:9 Changed 17 months ago by rhanghof
- Owner changed from abeham to rhanghof
- Status changed from accepted to assigned
comment:10 Changed 17 months ago by rhanghof
- Status changed from assigned to accepted
comment:11 Changed 17 months ago by rhanghof
- 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 16 months ago by rhanghof
- 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 16 months ago by rhanghof
- 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 16 months ago by rhanghof
- 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 15 months ago by rhanghof
- Added some unit tests
- Enhanced the documentation
comment:16 Changed 15 months ago by rhanghof
- Added unit tests
- Refactoring of bp 3D
comment:17 Changed 15 months ago by rhanghof
- Added line projection based bin packing
- Added residual spaces to the view
comment:18 Changed 14 months ago by rhanghof
- 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 14 months ago by rhanghof
- Unittests
- Bugfixes on the line projection based extreme point creation method.
comment:20 Changed 14 months ago by rhanghof
- Bugfixes for the line projection based extreme point creation
- Bugfixes for the tests
comment:21 Changed 13 months ago by rhanghof
- 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 13 months ago by rhanghof
- 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 13 months ago by rhanghof
- Dealing with stackable items
- Enhanced the Evaluator
- Added parameters some paramters to the packing items
comment:24 Changed 13 months ago by rhanghof
- Little changes on the packer
comment:25 Changed 13 months ago by rhanghof
- Former material is now the layer.
- Added material enumeration
- Modification at the minimum residual space left bin packer
comment:26 Changed 13 months ago by rhanghof
- 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 12 months ago by rhanghof
- Added a graph to the BinPacking3D for calculating the weight distribution.
- Added some materials.
comment:28 Changed 12 months ago by rhanghof
- Little changes on the packer
comment:29 Changed 12 months ago by rhanghof
- Fixes for pruning
comment:30 Changed 12 months ago by rhanghof
- Added the property SequenceGroup to the PackingItem
- Fixed a bug related to the sequence group
comment:31 Changed 11 months ago by rhanghof
- Fixed a bug at creating the extreme points with the point projection based method.
comment:32 Changed 11 months ago by rhanghof
- Some bug fixes at the placing algorithm
comment:33 Changed 8 months ago by rhanghof
- Refactoring BinPackerFormClosure.cs -> BinPackerWidthBestFit.cs
- Changes on the unit tests
comment:34 Changed 8 months ago by rhanghof
- Adjusted the unit tests
- Refactoring of the sorter
- Bugfix on the BinPackerResidualSpaceBestFit packer
comment:35 Changed 5 months ago by abeham
Note: See
TracTickets for help on using
tickets.
r15303: created branch