First time on this exchange, so giving this a title was already a challenge. So let's start at the beginning. This kind professor Güneş Erdoğan has published an CLP (Container Loading Problem) solver. His solution is made in a spreadsheet so it is VBA for Applications.
I have manually converted his code to a PHP script. I have everything working and running. But he has stated himself that there is room for improvement.
His algorithm has a while loop where it keeps making solutions based on random sorting. If the new solution is better than the current, the current gets replaced. Since the algorithm has a given time as input, for example 30, the code will keep doing this for 30 seconds and then return the best solution.
So I took the challenge to improve the code and try to get more iterations within the 30 seconds.
Using a profiling tool it shows me that the method called addItemToContainer
takes up most of the time. I've already spend quite some time on this method to try and improve it but I honestly can't find anything.
Then I found this exchange and I'm curious if anyone here can help me any further.
addItemToContainer
code:
public function addItemToContainer(Solution $solution, int $containerIndex, int $itemTypeIndex, int $addType): bool
{
$currentContainer = $solution->containers[$containerIndex];
$currentItemType = $this->itemTypeList[$itemTypeIndex];
$minX = $currentContainer->width + 1;
$minY = $currentContainer->height + 1;
$minZ = $currentContainer->length + 1;
$candidatePosition = -1;
$additionPointsCount = \count($currentContainer->addition_points);
// Checks if the item is able to fit into the current container based on volume
if (($currentContainer->volume_packed + $currentItemType->volume) > $currentContainer->volume_capacity) {
goto addItemToContainerFinish;
}
// Checks if the item is able to fit into the current container based on weight
if (($currentContainer->weight_packed + $currentItemType->weight) > $currentContainer->weight_capacity) {
goto addItemToContainerFinish;
}
// Checks each rotation, based on the rotation order of the solution
for ($i = 0; $i < 6; $i++) {
$rotationIndex = $i;
if ($candidatePosition !== -1) {
goto addItemToContainerFinish;
}
$currentRotation = $solution->rotation_order[$itemTypeIndex][$rotationIndex];
// Forbidden rotations
if ((($currentRotation === 3) || ($currentRotation === 4)) && ($currentItemType->xy_rotatable === false)) {
continue;
}
if ((($currentRotation === 5) || ($currentRotation === 6)) && ($currentItemType->yz_rotatable === false)) {
continue;
}
// Symmetry breaking
if (($currentRotation === 2) && (\abs($currentItemType->width - $currentItemType->length) < $this->epsilon)) {
continue;
}
if (($currentRotation === 4) && (\abs($currentItemType->width - $currentItemType->height) < $this->epsilon)) {
continue;
}
if (($currentRotation === 6) && (\abs($currentItemType->height - $currentItemType->length) < $this->epsilon)) {
continue;
}
// Loops through each addition point to find the next gap to put a new item
for ($j = 0; $j < $currentContainer->addition_point_count; $j++) {
if ($additionPointsCount - 1 >= $j) {
$additionPoint = $currentContainer->addition_points[$j];
$originX = $additionPoint->origin_x;
$originY = $additionPoint->origin_y;
$originZ = $additionPoint->origin_z;
} else {
$originX = 0;
$originY = 0;
$originZ = 0;
}
// set opposite positions based on the rotation which is calculated above
switch ($currentRotation) {
case 1:
$oppositeX = $originX + $currentItemType->width;
$oppositeY = $originY + $currentItemType->height;
$oppositeZ = $originZ + $currentItemType->length;
break;
case 2:
$oppositeX = $originX + $currentItemType->length;
$oppositeY = $originY + $currentItemType->height;
$oppositeZ = $originZ + $currentItemType->width;
break;
case 3:
$oppositeX = $originX + $currentItemType->width;
$oppositeY = $originY + $currentItemType->length;
$oppositeZ = $originZ + $currentItemType->height;
break;
case 4:
$oppositeX = $originX + $currentItemType->height;
$oppositeY = $originY + $currentItemType->length;
$oppositeZ = $originZ + $currentItemType->width;
break;
case 5:
$oppositeX = $originX + $currentItemType->height;
$oppositeY = $originY + $currentItemType->width;
$oppositeZ = $originZ + $currentItemType->length;
break;
case 6:
$oppositeX = $originX + $currentItemType->length;
$oppositeY = $originY + $currentItemType->width;
$oppositeZ = $originZ + $currentItemType->height;
break;
default:
$oppositeX = 0;
$oppositeY = 0;
$oppositeZ = 0;
break;
}
// Check the feasibility of all four corners, w.r.t. to the other items
if (($oppositeX > $currentContainer->width + $this->epsilon) || ($oppositeY > $currentContainer->height + $this->epsilon) || ($oppositeZ > $currentContainer->length + $this->epsilon)) {
continue;
}
// Check if there is conflict with other items within the container
foreach ($currentContainer->items as $item) {
if (
($oppositeX < $item->origin_x + $this->epsilon) ||
($item->opposite_x < $originX + $this->epsilon) ||
($oppositeY < $item->origin_y + $this->epsilon) ||
($item->opposite_y < $originY + $this->epsilon) ||
($oppositeZ < $item->origin_z + $this->epsilon) ||
($item->opposite_z < $originZ + $this->epsilon)
) {
// No conflict
} else {
// Conflict
continue 2 ;
}
}
// Support
if ($originY < $this->epsilon) {
$support = true;
} else {
$areaSupported = 0;
$support = false;
$containerItemsCount = \count($currentContainer->items);
for ($k = $containerItemsCount - 1; $k >= 0; $k--) {
$item = $currentContainer->items[$k];
if (\abs($originY - $item->opposite_y) < $this->epsilon) {
// Check for intersection
$intersectionRight = $oppositeX;
if ($intersectionRight > $item->opposite_x) {
$intersectionRight = $item->opposite_x;
}
$intersectionLeft = $originX;
if ($intersectionLeft < $item->origin_x) {
$intersectionLeft = $item->origin_x;
}
$intersectionTop = $oppositeZ;
if ($intersectionTop > $item->opposite_z) {
$intersectionTop = $item->opposite_z;
}
$intersectionBottom = $originZ;
if ($intersectionBottom < $item->origin_z) {
$intersectionBottom = $item->origin_z;
}
if (($intersectionRight > $intersectionLeft) && ($intersectionTop > $intersectionBottom)) {
$areaSupported += (($intersectionRight - $intersectionLeft) * ($intersectionTop - $intersectionBottom));
if ($areaSupported > (($oppositeX - $originX) * ($oppositeZ - $originZ)) - $this->epsilon) {
$support = true;
break;
}
}
}
}
}
if (!$support) {
continue;
}
// No conflicts at this point
if (
($originZ < $minZ) ||
(($originZ <= $minZ + $this->epsilon) && ($originY < $minY)) ||
(($originZ <= $minZ + $this->epsilon) && ($originY <= $minY + $this->epsilon) && ($originX < $minX))
) {
$minX = $originX;
$minY = $originY;
$minZ = $originZ;
$candidatePosition = $j;
$candidateRotation = $currentRotation;
}
}
}
// Portion of the function where the item gets added to the container
addItemToContainerFinish :
// If the candidate position is equal to -1 return
if ($candidatePosition === -1) {
return false;
} else {
$newItem = new Item();
$newItem->item_type = $itemTypeIndex;
if ($additionPointsCount - 1 >= $candidatePosition) {
$newItem->origin_x = $currentContainer->addition_points[$candidatePosition]->origin_x;
$newItem->origin_y = $currentContainer->addition_points[$candidatePosition]->origin_y;
$newItem->origin_z = $currentContainer->addition_points[$candidatePosition]->origin_z;
} else {
$newItem->origin_x = 0;
$newItem->origin_y = 0;
$newItem->origin_z = 0;
}
$newItem->rotation = $candidateRotation;
$newItem->mandatory = $currentItemType->mandatory;
// Based on the resulted rotation set the opposite position
switch ($candidateRotation) {
case 1:
$newItem->opposite_x = $newItem->origin_x + $currentItemType->width;
$newItem->opposite_y = $newItem->origin_y + $currentItemType->height;
$newItem->opposite_z = $newItem->origin_z + $currentItemType->length;
break;
case 2:
$newItem->opposite_x = $newItem->origin_x + $currentItemType->length;
$newItem->opposite_y = $newItem->origin_y + $currentItemType->height;
$newItem->opposite_z = $newItem->origin_z + $currentItemType->width;
break;
case 3:
$newItem->opposite_x = $newItem->origin_x + $currentItemType->width;
$newItem->opposite_y = $newItem->origin_y + $currentItemType->length;
$newItem->opposite_z = $newItem->origin_z + $currentItemType->height;
break;
case 4:
$newItem->opposite_x = $newItem->origin_x + $currentItemType->height;
$newItem->opposite_y = $newItem->origin_y + $currentItemType->length;
$newItem->opposite_z = $newItem->origin_z + $currentItemType->width;
break;
case 5:
$newItem->opposite_x = $newItem->origin_x + $currentItemType->height;
$newItem->opposite_y = $newItem->origin_y + $currentItemType->width;
$newItem->opposite_z = $newItem->origin_z + $currentItemType->length;
break;
case 6:
$newItem->opposite_x = $newItem->origin_x + $currentItemType->length;
$newItem->opposite_y = $newItem->origin_y + $currentItemType->width;
$newItem->opposite_z = $newItem->origin_z + $currentItemType->height;
break;
}
\array_push($solution->containers[$containerIndex]->items, $newItem);
// Update the volume and weight of the container
$currentContainer->volume_packed += $currentItemType->volume;
$currentContainer->weight_packed += $currentItemType->weight;
if ($addType === 2) {
$currentContainer->repack_item_count[$itemTypeIndex] = $currentContainer->repack_item_count[$itemTypeIndex] - 1;
}
// Update the addition points
for ($i = $candidatePosition; $i < $currentContainer->addition_point_count - 1; $i++) {
$currentContainer->addition_points[$i] = clone($currentContainer->addition_points[$i + 1]);
}
$currentContainer->addition_point_count = $currentContainer->addition_point_count - 1;
$itemsCount = \count($currentContainer->items);
$lastItem = $currentContainer->items[$itemsCount - 1];
// Add a new addition point to the container based on the last item
if (($lastItem->opposite_x < $currentContainer->width - $this->epsilon) &&
($lastItem->origin_y < $currentContainer->height - $this->epsilon) &&
($lastItem->origin_z < $currentContainer->length - $this->epsilon)) {
$currentContainer->addition_point_count = $currentContainer->addition_point_count + 1;
$additionPoint = new ItemLocation();
$additionPoint->origin_x = $lastItem->opposite_x;
$additionPoint->origin_y = $lastItem->origin_y;
$additionPoint->origin_z = $lastItem->origin_z;
if (\count($currentContainer->addition_points) < $currentContainer->addition_point_count) {
\array_push($currentContainer->addition_points, $additionPoint);
} else {
$currentContainer->addition_points[$currentContainer->addition_point_count - 1] = $additionPoint;
}
}
// Add a new addition point to the container based on the last item
if (($lastItem->origin_x < $currentContainer->width - $this->epsilon) &&
($lastItem->opposite_y < $currentContainer->height - $this->epsilon) &&
($lastItem->origin_z < $currentContainer->length - $this->epsilon)) {
$currentContainer->addition_point_count = $currentContainer->addition_point_count + 1;
$additionPoint = new ItemLocation();
$additionPoint->origin_x = $lastItem->origin_x;
$additionPoint->origin_y = $lastItem->opposite_y;
$additionPoint->origin_z = $lastItem->origin_z;
if (\count($currentContainer->addition_points) < $currentContainer->addition_point_count) {
\array_push($currentContainer->addition_points, $additionPoint);
} else {
$currentContainer->addition_points[$currentContainer->addition_point_count - 1] = $additionPoint;
}
}
// Add a new addition point to the container based on the last item
if (($lastItem->origin_x < $currentContainer->width - $this->epsilon) &&
($lastItem->origin_y < $currentContainer->height - $this->epsilon) &&
($lastItem->opposite_z < $currentContainer->length - $this->epsilon)) {
$currentContainer->addition_point_count = $currentContainer->addition_point_count + 1;
$additionPoint = new ItemLocation();
$additionPoint->origin_x = $lastItem->origin_x;
$additionPoint->origin_y = $lastItem->origin_y;
$additionPoint->origin_z = $lastItem->opposite_z;
if (\count($currentContainer->addition_points) < $currentContainer->addition_point_count) {
\array_push($currentContainer->addition_points, $additionPoint);
} else {
$currentContainer->addition_points[$currentContainer->addition_point_count - 1] = $additionPoint;
}
}
// Update the profit
if ($itemsCount === 1) {
$solution->net_profit += ($currentItemType->profit - $solution->containers[$containerIndex]->cost);
} else {
$solution->net_profit += $currentItemType->profit;
}
// Update the volume per container and the total volume
$solution->total_volume += $currentItemType->volume;
$solution->total_weight += $currentItemType->weight;
// Update the unpacked items
if ($addType === 1) {
$solution->unpacked_item_count[$itemTypeIndex] = $solution->unpacked_item_count[$itemTypeIndex] - 1;
}
return true;
}
}
So the main question is if maybe you can find something which possibly can improve the amount of iterations the algorithm can do.
giving this a title [is] already a challenge
that's the spirit!)(Sounds like simulated annealing might be a better strategy.) \$\endgroup\$goto
in the php docs... I've never actually seen it in the wild! \$\endgroup\$No conflicts at this point
, the condition(($originZ <= $minZ + $this->epsilon) && ($originY < $minY))
is redundant (included in the last one). \$\endgroup\$