mardi 6 avril 2021

Designing a 2D Bin-Packing Algorithm, which supports arbitrary item weights and limits

I'm trying to develop an algorithm for a complex sorting issue that ultimately seems to be a two-layer 2D Bin-Packing-Problem, but I'm having trouble drafting out a high-level approach because of the amount of many variables involved. This seems like something that shipping/logistics industries would have developed - so I welcome any insights.

Goal I have several rectangular items provided in a priority order. These items must be sorted into rectangular bins, and those bins must be subsequently sorted such that they can fit into a final fixed-size rectangular area.

The goal is to sort as many of the items as possible (with respect to their priority), into as few bins as possible - effectively to provide the most efficient layout. Alongside the two-layer issue, where it more interesting is the additional properties of the items and bins themselves.

Items

  • Have a fixed 2D size.
  • Cannot be rotated.
  • Cannot be spliced.
  • Have a "Mass" property (total mass must not exceed mass-capacity of a bin).
  • Have a "Cost" property (total cost must not exceed cost-limit of a bin).
  • Items may specify whether they are compatible with a given "class" of bin (or vice-versa).
  • Items may specify a "group" index. Where possible these items should be grouped into the same bins, but this is non-essential.

Bins

  • Have a variable 2D size, between a fixed min and max.
  • Have a fixed "Mass" limit.
  • Have a fixed "Cost" limit.
  • Have their own "Cost" property (lower is preferable, but fewer bins preferable still).

Area

  • A fixed-size area which the bins must ultimately fit into.
  • Potentially, it's own "Mass" and "Cost" limits too.

The final objective is to sort the items such that as many as possible can be inserted into as few bins as possible, and also in a way that respects their priority.

This is a game-design problem, so is somewhat self-inflicted and may just need to be simplified. I mention this because factors such as randomness or non-closed-form solutions aren't an option, however the expected number of items and bins is relatively low, probably 5-30 items, and around 2-3 bins on average.

Is there a way to convert this from a two-stage BPP problem into only a single stage, by thinking about the issue as one with additional dimensions? In addition, is there a general approach to combining additional, arbitrary weights and/or hard-limits to the items that are being sorted?

Aucun commentaire:

Enregistrer un commentaire