hschneid / xflp

xflp is a heuristic solver for container loading problems in 3D with real world constraints

xflp

xflp is a solver for truck loading problems in 3D with real world constraints

It supports:

• single or multiple bin packing
• rotating of items for 1 axis
• simulation of loading and unloading of items
• Constraints:
  • Max height of loading space
  • Max weight of loading space
  • Max bearing weight of each item
  • last in, first out condition
• consideration of stacking groups
• consideration of container types
• consideration of immersive depth during stacking
• consideration of permissible axle load (2 axles)

Optimization:

• Construction heuristic
• GRASP heuristic
  • Swap and relocate neighborhood search

Usage

XFLP xflp = new XFLP();
xflp.addContainer().setLength(13500).setWidth(2500).setHeight(3000).setMaxWeight(25000);
xflp.addItem().setExternID("Packet 1").setLength(13500).setWidth(2500).setHeight(3000).setWeight(25000);
xflp.addItem().setExternID("Packet 2").setLength(13500).setWidth(2500).setHeight(3000).setWeight(25000);
xflp.addItem().setExternID("Packet 3").setLength(13500).setWidth(2500).setHeight(3000).setWeight(25000);

xflp.executeLoadPlanning();

LPReport report = xflp.getReport();
int nbrOfUnloadedPackages = report.getSummary().getNbrOfUnLoadedPackages();

License

This software is released under [MIT License] (https://opensource.org/licenses/MIT)

Change log

0.6.1 - Fixed Location feature

• User can set loading and unloading location for each item. This is useful during Vehicle Routing, when sequences of loading and unloading need to be checked. Here was a bug in code, where locations were not sorted in correct order. This is fixed now, but there are prerequisits:
  • The name of a location (load or unload) must correspond with the ordering in sequence.
  • The LIFO loading constraint must be activated as it is not default.
  • Example for infeasible solution

  XFLP xflp = new XFLP()
  xflp.getParameter().setLifoImportance(1)
  
  xflp.addItem().setExternID("P1").setLoadingLocation("Loc 1").setUnloadingLocation("Loc 3")
  xflp.addItem().setExternID("P2").setLoadingLocation("Loc 2").setUnloadingLocation("Loc 4")
  
  xflp.executeLoadPlanning()
  assert xflp.getReport().getUnplannedPackages().size() > 0
  

0.6.0 - Update to Java 17, permissible axle load and more

• Changed xflp to Java 17. Due to use of records, xflp is not compatible with Java < 17 anymore.
• Add space-based checking when items are added and removed in a container. This improves the planning performance and reduces the code complexity.
• Add constraint: permissible axle load for 2 axles

0.5.2 - Performance upgrade

• Improved bearing check by storing bearing capacities during container-adding.
  • For big problems the runtime improves by 43%.
• Refactored and removed old code

0.5.1 - Performance upgrade

• Add spaces for faster checking of possible insert positions
  • Each position defines a list of spaces, where items might fit into.
  • Adding new item means complex calculation/correction of spaces
  • Check, whether item fits at a certain position is reduced from O(n) to O(1)
    • For big problems the runtime improves by factor 3.
• Refactorings of optimization types
• Minor refactoring of ground contact checking
• Internal refactorings

0.5.0 - Performance upgrade

• Refactoring of container code
  • Split algorithmic functions to service classes
  • Add general definition of containers
  • Have at least 2 implementations of container:
    • Items can be added and removed (current implementation)
    • Items can only be added. Implementation can be way simpler and performance is better.
• Refactoring of current container service methods, which improves performance
• Added check for duplicate positions, which maybe bring a bit of performance
• Import function checks, which type of container is necessary.
• After import, some values of items are checked for validity.

0.4.1

• Add immersive depth

0.4.0 - More restrictions

• Add restriction, that one item must be fully placed on top of one item
  • Business motivation: Certain packages may have restriction due to shoulder or feet forms, that stacking on multiple items is not possible.
• Fixed copyright information
• Refactored import classes
• Use specific exception instead of runtime exceptions

0.3.2

• Added SpotBugs in build process to find smellies
• Fixed some smellies
  • In many cases a XFLPException is thrown instead of IllegalArgumentExceptions

0.3.1

• "Fast Fixed solver" uses new width proportion factor for choosing the next insert position

0.3.0 - Stacking groups

• Fix of stacking group feature
• Added a priorization criteria for choosing the next insert position. It takes the proportion of the item to the container into account.
• More reasonable structure of planning heuristics

0.2.0

• First stable release

xflp's Issues

your opinion about port it to PHP 8.2

Hello,
Great job, thanks for sharing. it is likely that we will need to port it to PHP 8.2, do you think that the algo part will be complicated to re-write in PHP? Does this seem possible to you in this language, or do you think that certain difficulties will be difficult to solve?
thanks again

Tests are not running

For some reason on my machine tests are not run unless I add this

test {
useJUnitPlatform()
}

to the build.gradle

I've made a quick investigation and it seems that this is a quite common issue.
Am I missing something?

I tried on a clean project latests spock-core version available (2.4-M1-groovy-4.0) and it is not working w/o useJUnitPlatform instruction

Spaces for AddRemove

Currently the space checking can be done only, when load-items are available.

It would be cool to have it also for AddRemoveContainer.

But effort is high, because during remove it would be necessary to check spaces of every position, the uncovered positions and maybe the projected positions.

Failing test

ContainerRemoveSpec.randomly add and remove items

with 1000 iterations it is breaking!

The positionMaps are deleted somehow

maxNbrOfContainer is not working for NContainerOntTypeAddPacker

The local variable "containerIdx" is not in cremented in the loop

Performance - bearing propagation

Currently every search for possible insert positions, checks the bearing capacity of items. Therefore all lower items are checked.

If there would be an additional data structure, which remembers the still open bearing capacity of upper items, there check would be faster. Only a little bit more effort in adding an item, because the bearing of lower items must be checked.

This features should be available first only for AddContainer.

Performance - Projection of positions

When checking for projected positions, use xMap and yMap instead of iteration over all items.

Performance - Prevent duplicate positions in AddRemove

Currently it happens, that positions are created multiple times. So the search for possible insert positions checks duplicate positions, which increases the effort.

During creation of new positions it shall be checked, if position is already in place. There is no easy hashing function, so ListMap would be needed. Something like 2 * x + 1 * y + -1 * z

Add this function only for AddContainer.

Grouping Boxes

"Hello,
I was wondering, does the project have any features to group boxes of the same 'type' to ensure that all these boxes are adjacent to each other in each container?

Documentations

Dear author:
Thanks for your sharing! Are there any documents or paper speaking of your methods?

Performance - Spaces

Currently for every search of possible insert positions, all other items are checked, if there are collisions. This was reduced by using xMap, yMap and zMap.

Instead we would try to add the concept of spaces. A space is the room, where new items can be inserted. It has length, width and heigth. So it is very easy to check, it a certain item fits into such a space. Every position defines its own space.

When item is added, new positions are searched. In this case, the covered space of new item will be deleted and new spaces needs to be created. It is very easy to define new spaces from the sliced old space.

Only it is necessary to check, if there are other spaces, which will be cropped.

This feature shall be created only for AddContainer.

BestFit Algorithm

For each Item and Position find the next entry to be inserted.

Use decision criterias from real life: First stacking, then nivellating the height with neighbor items, then rest.

Search effort is increased! So first we need faster algorithm for checking.

output

how to output which boxes in the container and the location of boxes in the container

Add parameter for single stacking

• Add a parameter, that each item can be stack only on top of one single item

Unloading Location Not working correctly

Hello,
I want to load item from a single location and unload them on multiple locations in single container. Also the order would be the first unloading location item must be loaded last in the container. I want to group items according to unloading location. I have tried setting unloading location but some how all the co-ordinates are 0. Please help me resolve this.

Here is my code
XFLP xflp = new XFLP();
xflp.setTypeOfOptimization(XFLPOptType.BEST_FIXED_CONTAINER_PACKER);
xflp.getParameter().setLifoImportance(1);
xflp.addContainer().setLength(1350000).setWidth(2500).setHeight(3000).setMaxWeight(25000000);

xflp.addItem().setExternID("Packet1").setLength(13500).setWidth(2500).setHeight(3000).setWeight(25000).setUnloadingLocation("location 1");
xflp.addItem().setExternID("Packet2").setLength(13500).setWidth(2500).setHeight(3000).setWeight(25000).setUnloadingLocation("location 2");
xflp.addItem().setExternID("Packet3").setLength(13500).setWidth(2500).setHeight(3000).setWeight(25000).setUnloadingLocation("location 1");

xflp.executeLoadPlanning();
LPReport report = xflp.getReport();

NContainerOneTypeAddPacker#execute may cause OOM

Hi.
If there is not any item can be add into container, the local variable 'containerList' may cause OOM.

I think we should concern on the size of 'unpackedItem'. If it's size not change after 'createLoadingPlan', it should break the loop

Update licence and copyright

Year must be set correctly
Check if all files have copyright text

Update to Java 17

Todo

• Update to Java 17
• Use records for Positions
• Use sealed classes for Algorithms and data objects

Permissible Axle Load

Add the real world constraint "Axle Load" to XFLP.

It means, that even if the whole container (truck vessel) can load up to X kilogramm, the distribution of weight between multiple axle must be considered.

Unable to build project

unable to build project as property osshrusername not found

Could you specify the reference paper you used to implement this project?

It may be helpful for me to read the code. Thank you.