Ask a question
Container sea furniture, sofas, coffee tables, chairs, etc., how many sets of furniture are there, as well as the length, width and height of each furniture will tell you.
Put all the furniture into containers and require the algorithm to calculate how many containers are needed in total.
- 1. Consider how to load it, and the minimum container is needed, because a container is very expensive.
- 2. Consider how to place it, take up the smallest volume, and find the optimal solution. For example, if the coffee table and the sofa are stacked together, there is still a spare position next to it, so whether you can put another chair in it.
How would you design an algorithm?
Decompose the problem
This is a typical three-dimensional packing problem (3D Bin Packing Problem, 3D-BPP), which is an NP-hard problem, meaning that no known algorithm can find the absolute optimal solution in polynomial time. Therefore, we usually use heuristics or approximation algorithms to find a good enough solution, that is, try to use containers as little as possible.
The following is an idea and code framework for designing heuristics using C#:
Core idea:
- Container selection:Usually, there are standard container sizes for shipping, such as 20GP, 40GP, 40HC. We need to determine which size of container to use, or allow the algorithm to choose to mix (which will be more complicated). For simplicity, we first assume that containers of the same standard size are used, such as 40HC (the inner dimension is approximately: length 12.03m, width 2.35m, height 2.69m).Note: The units must be unified!For example, use millimeters (mm) or centimeters (cm).
- Item representation:Each furniture is a three-dimensional rectangular body with length, width and height.
- Rotate:Furniture can be placed rotating to make better use of the space. A rectangle has up to 6 basic orientations (not considering the 90-degree rotation about the vertical axis, because that can be achieved by exchanging lengths and widths).
-
Placement strategy:This is the key to the algorithm. Need to decide:
- Item order:Enlarge the item first or small one? Usually, it is better to enlarge the pieces first (such as sorting by volume or longest edge) (First Fit Decreasing - FFD variant).
- Placement location:Where to place items in the container? A common strategy is to find the "most suitable" position in the optional space, such as the "lowest-left-most inner" corner.
-
Space Management:How to record and manage the remaining space in a container? This can be complicated. Common methods are:
- Layer-based method:Fill layer by layer.
- Maximal Spaces:Maintain a list of remaining space blocks.
- Three-dimensional coordinates/voxel method:Discrete container space (the calculations can be very large).
- Simple coordinate point method:Maintain a set of "anchor points" that can place items (usually the corner points of the item that has been placed or the corner points of the container).
-
Algorithm flow (heuristics - based on FFD and anchor/lowest position strategy):
-
initialization:
- Get a list of all furniture and its sizes.
- Define the container internal dimensions.
- Sort the furniture list (for example, descending by volume).
- Create an empty container list.
-
Main loop:Traversing the sorted furniture list:
- For current furniture
item:-
Try putting it in an existing container:Iterate through the currently opened container list
containers。- For each container
container:- Try to find a valid placement
item(Consider all 6 rotations). -
Finding Location (Heuristic):
- Maintain an "anchor" list of items that can be placed in this container
anchorPoints(Initially (0,0,0)). - Traversal in a certain order (such as Z coordinate ascending order, Y ascending order, X ascending order)
anchorPoints。 - For each anchor point
p,tryitemAll 6 rotationsr。 - examine
itemWith rotationrPlaced inphour:- Is it completely within the container boundary?
- Whether it is related to any other items already placed in the container
placedItemA collision occurred?
- If the first valid location is found
(p, r)：- Will
itemPlaced incontainerofpPoint, use rotationr. Record its position and size. - renew
containerofanchorPoints: Removepand according to the newly placeditemAdd new potential anchor points (for example, the upper right corner, upper front corner, front right corner, etc. of a new item). It needs to be handled carefully to avoid duplication and invalid points. - mark
itemPlaced, jump out of the current container attempt to process the next furniture.
- Will
- Maintain an "anchor" list of items that can be placed in this container
- Try to find a valid placement
- For each container
-
If the existing container cannot be placed:
- Create a new container
newContainer。 - Will
itemPut innewContainer(usually placed in the (0,0,0) position, select a suitable rotation).Must check:If the item itself is larger than the container, it cannot be placed and an error needs to be reported. - Record placement information, initialize
newContainerlist of anchor points. - Will
newContainerAdd tocontainersin the list.
- Create a new container
-
Try putting it in an existing container:Iterate through the currently opened container list
- For current furniture
-
Finish:After all the furniture is processed,
containersThe size of the list is the number of containers required.
-
initialization:
C# code framework:
using System;
using ;
using ;
// 3D Point/Vector Structure
public struct Point3D
{
public decimal X, Y, Z;
public Point3D(decimal x, decimal y, decimal z) { X = x; Y = y; Z = z; }
public override string ToString() => $"({X}, {Y}, {Z})";
}
// Dimensions Structure
public struct Dimensions
{
public decimal Length, Width, Height; // L, W, H correspond to X, Y, Z axes when placed
public decimal Volume => Length * Width * Height;
public Dimensions(decimal l, decimal w, decimal h) { Length = l; Width = w; Height = h; }
public override string ToString() => $"[{Length}x{Width}x{Height}]";
// Get dimensions for different rotations
public Dimensions GetRotation(int rotationType)
{
switch (rotationType)
{
case 0: return new Dimensions(Length, Width, Height); // LWH (XYZ)
case 1: return new Dimensions(Length, Height, Width); // LHW (XZY)
case 2: return new Dimensions(Width, Length, Height); // WLH (YXZ)
case 3: return new Dimensions(Width, Height, Length); // WHL (YZX)
case 4: return new Dimensions(Height, Length, Width); // HLW (ZXY)
case 5: return new Dimensions(Height, Width, Length); // HWL (ZYX)
default: throw new ArgumentOutOfRangeException(nameof(rotationType));
}
}
}
// Represents a furniture item
public class Item
{
public string Name { get; }
public Dimensions OriginalDimensions { get; }
public decimal Volume => ;
// Potentially add weight, fragility, stacking constraints later
public Item(string name, decimal length, decimal width, decimal height)
{
Name = name;
// Ensure non-negative dimensions
OriginalDimensions = new Dimensions(
(0, length),
(0, width),
(0, height)
);
}
public override string ToString() => $"{Name} {OriginalDimensions}";
}
// Represents an item placed inside a container
public class PlacedItem
{
public Item SourceItem { get; }
public Point3D Position { get; } // Bottom-Back-Left corner of the item in container coordinates
public Dimensions PlacedDimensions { get; } // Dimensions after rotation
// Bounding Box for collision detection
public Point3D MinCorner => Position;
public Point3D MaxCorner => new Point3D( + , + , + );
public PlacedItem(Item sourceItem, Point3D position, Dimensions placedDimensions)
{
SourceItem = sourceItem;
Position = position;
PlacedDimensions = placedDimensions;
}
// AABB Collision Check
public bool Intersects(PlacedItem other)
{
return ( < && > ) &&
( < && > ) &&
( < && > );
}
// Check if this item intersects with a potential placement
public bool Intersects(Point3D potentialPos, Dimensions potentialDims)
{
Point3D potMin = potentialPos;
Point3D potMax = new Point3D( + , + , + );
return ( < && > ) &&
( < && > ) &&
( < && > );
}
}
// Represents a single container
public class Container
{
public int Id { get; }
public Dimensions Dimensions { get; }
public List<PlacedItem> PlacedItems { get; }
public List<Point3D> AnchorPoints { get; private set; } // Potential placement corners
// Keep track of occupied volume/space for heuristics? (Optional)
public Container(int id, decimal length, decimal width, decimal height)
{
Id = id;
Dimensions = new Dimensions(length, width, height);
PlacedItems = new List<PlacedItem>();
// Start with the main corner as the only anchor point
AnchorPoints = new List<Point3D> { new Point3D(0, 0, 0) };
}
// Tries to find a position and rotation to place the item
public bool TryPlaceItem(Item item, out PlacedItem placement)
{
placement = null;
// Sort anchor points: typically Z, Y, X ascending to fill bottom-up, left-right, back-front
var sortedAnchors = (p => ).ThenBy(p => ).ThenBy(p => ).ToList();
foreach (Point3D anchor in sortedAnchors)
{
for (int rotationType = 0; rotationType < 6; rotationType++)
{
Dimensions rotatedDims = (rotationType);
// Check if item fits within container boundaries at this anchor
if ( + <= &&
+ <= &&
+ <= )
{
// Check for collisions with already placed items
bool collision = false;
foreach (PlacedItem existingItem in PlacedItems)
{
// Simple AABB check
if ((anchor, rotatedDims))
{
collision = true;
break;
}
}
if (!collision)
{
// Found a valid placement!
placement = new PlacedItem(item, anchor, rotatedDims);
return true; // Return the first valid placement found
}
}
}
}
return false; // Could not find a place for this item in this container
}
// Actually place the item and update anchors
public void PlaceItem(PlacedItem placement)
{
(placement);
// Update anchor points - this is a crucial and potentially complex step
// A simple strategy: remove the used anchor and add new potential anchors
Point3D placedPos = ;
Dimensions placedDims = ;
// Remove the anchor point that was used for placement
(p => == && == && == );
// Add new potential anchor points based on the corners of the placed item
// Only add points that are within the container bounds
// More sophisticated logic would check if these points are already covered or invalid
Point3D[] potentialNewAnchors = {
new Point3D( + , , ),
new Point3D(, + , ),
new Point3D(, , + )
};
foreach (var newAnchor in potentialNewAnchors)
{
// Basic check: is it inside the container?
if ( < && < && < )
{
// Basic check: does it overlap with the item just placed? (Shouldn't if corners are correct)
// More advanced: check if it's inside *any* existing item or outside container
// Avoid duplicates
if (!(p => == && == && == ))
{
// Further check: Is this point supported? (Simple heuristic: is Z>0 requires something below?)
// For simplicity now, just add if inside bounds and not duplicate.
(newAnchor);
}
}
}
// Optional: Refine anchor points - remove points that are now inside the newly placed item
// (p => IsInside(p, placement)); // Need IsInside check
// Optional: Sort anchors again if needed for the next TryPlaceItem call
// AnchorPoints = (p => ).ThenBy(p => ).ThenBy(p => ).ToList();
}
// Helper to check if a point is strictly inside a placed item's volume
private bool IsInside(Point3D point, PlacedItem item)
{
return > && < &&
> && < &&
> && < ;
}
}
// The main packer class
public class Packer
{
public Dimensions ContainerDimensions { get; }
public Packer(decimal containerLength, decimal containerWidth, decimal containerHeight)
{
ContainerDimensions = new Dimensions(containerLength, containerWidth, containerHeight);
}
public List<Container> PackItems(List<Item> itemsToPack)
{
// 1. Sort items (., by volume descending) - FFD heuristic
var sortedItems = (item => ).ToList();
List<Container> containers = new List<Container>();
int containerIdCounter = 1;
HashSet<Item> packedItems = new HashSet<Item>(); // Keep track of packed items
foreach (var item in sortedItems)
{
if ((item)) continue; // Should not happen with list processing, but safe check
bool placed = false;
// 2. Try placing in existing containers
foreach (var container in containers)
{
if ((item, out PlacedItem placement))
{
(placement);
($"Placed {} in Container {} at {} with rotation {}");
placed = true;
(item);
break; // Move to the next item (First Fit)
}
}
// 3. If not placed, open a new container
if (!placed)
{
// Check if the item can fit in an empty container at all (any rotation)
bool fitsAnyhow = false;
PlacedItem initialPlacement = null;
for(int r=0; r<6; ++r)
{
var dims = (r);
if( <= &&
<= &&
<= )
{
initialPlacement = new PlacedItem(item, new Point3D(0,0,0), dims);
fitsAnyhow = true;
break;
}
}
if (fitsAnyhow)
{
Container newContainer = new Container(containerIdCounter++, , , );
(initialPlacement); // Place at (0,0,0) with the found rotation
(newContainer);
(item);
($"Opened Container {} and placed {} at {} with rotation {}");
}
else
{
// Item is too large for the container
($"Error: Item {} ({}) is too large to fit in the container ({ContainerDimensions}).");
// Decide how to handle this - skip item, throw exception?
}
}
}
($"\nPacking complete. Total containers used: {}");
return containers;
}
}
// Example Usage
public class Example
{
public static void Main(string[] args)
{
// --- Configuration ---
// Use internal dimensions of a 40ft High Cube container in cm
decimal containerL = 1203m;
decimal containerW = 235m;
decimal containerH = 269m; // Use decimal for potentially better precision with cm/mm
($"Using Container Dimensions: {containerL}cm x {containerW}cm x {containerH}cm");
// --- Furniture List (Example Data in cm) ---
List<Item> furniture = new List<Item>
{
// Sofas (L x W x H)
new Item("Sofa 1", 200m, 90m, 80m),
new Item("Sofa 2", 220m, 95m, 85m),
// Coffee Tables
new Item("Coffee Table 1", 120m, 60m, 45m),
new Item("Coffee Table 2", 100m, 100m, 40m),
// Chairs
new Item("Chair 1", 60m, 60m, 90m),
new Item("Chair 2", 60m, 60m, 90m),
new Item("Chair 3", 55m, 58m, 95m),
new Item("Chair 4", 55m, 58m, 95m),
// Larger item test
new Item("Wardrobe", 150m, 60m, 200m),
// More items
new Item("Bookshelf", 80m, 30m, 180m),
new Item("Side Table 1", 40m, 40m, 60m),
new Item("Side Table 2", 40m, 40m, 60m),
new Item("Ottoman", 70m, 70m, 40m),
// Add many more small items to test filling gaps
// ... (., 20 small boxes 30x30x30)
// for (int i = 0; i < 20; i++) { (new Item($"Small Box {i+1}", 30m, 30m, 30m)); }
};
($"\nItems to pack ({} total):");
foreach(var item in furniture) ($"- {item}");
// --- Packing ---
Packer packer = new Packer(containerL, containerW, containerH);
List<Container> resultContainers = (furniture);
// --- Output Results ---
($"\n--- Packing Summary ---");
($"Total Containers Needed: {}");
for (int i = 0; i < ; i++)
{
decimal packedVolume = resultContainers[i].(p => );
decimal totalVolume = resultContainers[i].;
decimal utilization = totalVolume > 0 ? (packedVolume / totalVolume) * 100 : 0;
($"Container {resultContainers[i].Id}: Contains {resultContainers[i].} items. Volume Utilization: {utilization:F2}%");
// Optionally print items in each container
// foreach(var placed in resultContainers[i].PlacedItems) {
// ($" - {} at {} as {}");
// }
}
}
}
Key points and directions of improvement:
-
Unit consistency:Used in the code
decimaland centimeters (cm) as examples. Make sure all input sizes and container sizes use the same units. -
Anchor Management:
PlaceItemThe logic of updating anchor points in the process is very basic. More advanced algorithms manage remaining space more intelligently, such as using Maximal Spaces or more complex anchor generation/elimination rules to avoid unusable small fragmented spaces or invalid anchors. -
Heuristic Choice:
- Sort by:Sort by descending volume is a common FFD heuristic. You can also try sorting by longest edges, area, etc.
-
Anchor Point Selection:
TryPlaceItemSorting the anchor points in Z, Y, X try to fill the bottom. Other orders can be tried. - Rotate selection:The current code tries all 6 rotations. More "probably" successful rotation can be tried based on the anchor point and surrounding space.
-
performance:For large quantities of items, collision detection (
Intersects) and anchor point management will become bottlenecks. Spatial partitioned data structures such as Octree may be required to accelerate collision detection. -
Stability/Constraint:The current algorithm is purely geometric boxing. No consideration:
- weight:The heavy object should be at the bottom.
- Fragility:Do not press heavy objects on fragile items.
- Stacking Limits:Certain items cannot be stacked or can only bear limited weight.
- direction:Some furniture (such as sofas) may not be placed upside down or sideways.
- These constraints need to be added to
ItemClass andTryPlaceItemThe inspection logic will significantly increase complexity.
- Optimality:This heuristic algorithm does not guarantee the absolute minimum number of containers to be found. More complex algorithms (such as taboo search, simulated annealing, genetic algorithms) or precise algorithms (branch delimiting, but very slow) may get better results, but are much more difficult to implement.
- User Interface/Input:In practical applications, furniture lists and sizes need to be read from files, databases, or UI.
- Visualization:After outputting the coordinates, it is very helpful to use the 3D visualization tool to display the boxing results.
This framework provides a starting point. This algorithm can be further optimized and extended based on the complexity of actual requirements and the requirements for optimization.