记录一段关于三维装箱问题的算法
本代码基于组合启发式算法,利用模拟退火的思想进行结果的拟合
代码分为四个部分:
1.判定两个物体是否重叠
2.将指定顺序、给定方向(长、宽、高固定)的物体排列进指定长、宽、高的容器内
3.模拟退火,获得最佳装箱方案
4.输出图像(利用matplotlib库)
重叠判定算法
基本全盘照抄的CSDN的一段代码
主体思想是分别判断两个物体的正视图、侧视图和俯视图是否重叠,若三者有二者甚至三者发生重叠,则这两个物体一定重叠
if item1[0] + position[0] <= box_length and item1[1] + position[1] <= box_width and item1[2] + position[2] <= box_height: # 先特判一下该物品是否在容器内 for item2 in putted_items: # 也许有更高效的方法吧,但我暂且就暴力遍历了 if item2['position'] == position: # 特判两物体重合的情况 return False overlap = 0 if item2['position'][0] < item1[0] + position[0] and position[0] < item2['position'][0] + item2['volume'][0] and item2['position'][1] < item1[1] + position[1] and position[1] < item2['position'][1] + item2['volume'][1]: # 判定xOy面是否重合 overlap = 1 if item2['position'][0] < item1[0] + position[0] and position[0] < item2['position'][0] + item2['volume'][0] and item2['position'][2] < item1[2] + position[2] and position[2] < item2['position'][2] + item2['volume'][2]: # 判定xOz面是否重合 overlap += 1 if item2['position'][1] < item1[1] + position[1] and position[1] < item2['position'][1] + item2['volume'][1] and item2['position'][2] < item1[2] + position[2] and position[2] < item2['position'][2] + item2['volume'][2]: # 判定yOz面是否重合 overlap += 1 if overlap > 1: # 若多于一面重合,则这两个物体在三维上是相交的 return False return True
定向装箱算法
主要参考自这篇论文
为简便起见,下称物体的坐标为(x₀, y₀, z₀),物体的长、宽、高为l, w, h
首先设一个可放置点为(0,0,0),之后每成功放置一个物体,删除这个物体的放置点并增加三个可放置点(x₀ + l, y₀, z₀)(x₀, y₀ + w, z₀)(x₀, y₀, z₀ + h)
设两条参考线rx,rz重合于x轴,z轴;优先考虑将物体放置于两条参考线内,若无法放置则再尝试拓展参考线,若仍无法放置则放置失败
拓展参考线的四种情况
(1)两条线与坐标轴重合(初始情况)时,判断物体能否放置于坐标原点,若能,拓展两条参考线为x = l与z = h
(2)x轴可进行拓展时,优先拓展x轴,并拓展rx为x = x₀ + l
(3)rx再怎么拓展也无法放下新物体时,判断物体能否放置于(0, 0, rz),若能,拓展rz为z = z₀ + h
(4)rz再怎么拓展也无法放下新物体时,拓展两条参考线为最大值(容器的长于高)(若此时依旧无法放下新物体,则装箱告终)
# 判定物品是否能在参考线内容纳下
def isInnerReference(item):
global x, y, z
for position in available_points: # 遍历所有可用点
if item[0] + position[0] <= x_reference and item[2] + position[2] <= z_reference and isRoomEnough(item, position) == True: # 判定该点是否可用且不与任何参考线重合
x, y, z = position[0], position[1], position[2]
return True
# 拓展参考线,并判定物品能否被容纳
def expandReference(item):
global x_reference, z_reference, x, y, z
if x_reference == 0 or x_reference == box_length: # 如果这是第一个物品或者x参考线已经最大,那么这个物体就有放不下的可能
if isRoomEnough(item, (0, 0, z_reference)) == True: # 若z轴上能放物体,就不用大刀阔斧地修改参考线
x, y, z, x_reference = 0, 0, z_reference, item[0]
z_reference += item[2]
return True
elif z_reference < box_height: # 如果z参考线还能动的话,直接把俩参考线加到最大
x_reference, z_reference = box_length, box_height
return isInnerReference(item) or expandReference(item)
else:
for position in available_points: # 遍历所有可用点
if position[0] == x_reference and position[1] == 0 and item[2] + position[2] <= z_reference and isRoomEnough(item, position) == True: # 判定所有在x参考线上的点是否可用且不与z参考线重合
x, y, z = position[0], position[1], position[2]
x_reference += item[0]
return True
x_reference = box_length
return isInnerReference(item) or expandReference(item)
# 将指定方向的一批物品以固定顺序放入容器中
def pack(items):
global available_points, putted_items, x_reference, z_reference
available_points = {(0, 0, 0)}
positions = []
putted_items = []
sizes = []
item_volume = x_reference = z_reference = 0
for item in items: # 顺序遍历所有物体
if (isInnerReference(item) or expandReference(item)) and isRoomEnough(item, (x, y, z)): # 若一切顺利,放下物体
putted_items.append({
'position': (x, y, z),
'volume': item,
}) # putted_items同时储存有物体的位置和大小
available_points.remove((x, y, z))
available_points.add(((x + item[0], y, z)))
available_points.add(((x, y + item[1], z)))
available_points.add(((x, y, z + item[2])))
positions.append((x, y, z))
sizes.append(item)
item_volume += item[0] * item[1] * item[2]
'''print('有一个长', item[0], '宽', item[1], '高', item[2], '的物品成功放置于', (x, y, z))
else:
print('有一个长', item[0], '宽', item[1], '高', item[2], '的物品放置失败')'''
return item_volume / box_length / box_width / box_height, positions, sizes模拟退火算法
还是参考自这篇论文
装箱时,装箱的顺序与物体的方向均会对装箱的填充率产生影响,因此在退货时随机打乱这两个值进行计算
for i in range(2): # 2次退火 temperature, area_length = 0.92, items_kind while temperature >= 0.01: # 在温度降至足够低之前不断循环 for j in range(area_length): # 循环次数由邻域长度决定 new_items = items for k, item in enumerate(new_items): # tuple不能直接shuffle,所以要先化成list再shuffle再化回tuple l = list(item) shuffle(l) new_items[k] = tuple(l) shuffle(new_items) new_filling_rate, new_positions, new_sizes = pack(new_items) if new_filling_rate > filling_rate or exp((new_filling_rate - filling_rate) * 10 / temperature) > random(): # 若满足更优解或满足Metropolis准则,则选取该解,这是模拟退火算法的核心 filling_rate, items, positions, sizes = new_filling_rate, new_items, new_positions, new_sizes if new_filling_rate > max_filling_rate: # 记录最优解 max_filling_rate, best_items, best_positions, best_sizes = new_filling_rate, new_items, new_positions, new_sizes area_length += items_kind temperature *= 0.92 print(i + 1, '次退火填充率:', max_filling_rate, '放置数量:', len(best_sizes))
图像输出算法
参考自stackoverflow的一篇问答及其翻译
其实我看不懂这段鬼画符写的是啥,就不献丑了
subplot = figure().add_subplot(projection='3d') subplot.set_box_aspect((box_length, box_width, box_height)) arr = [] for position, size in zip(positions, sizes): # 其实我完全看不懂这一段……这段代码是从StackOverFlow上偷来的 a = array([[[0, 1, 0], [0, 0, 0], [1, 0, 0], [1, 1, 0]], [[0, 0, 0], [0, 0, 1], [1, 0, 1], [1, 0, 0]], [[1, 0, 1], [1, 0, 0], [1, 1, 0], [1, 1, 1]], [[0, 0, 1], [0, 0, 0], [0, 1, 0], [0, 1, 1]], [[0, 1, 0], [0, 1, 1], [1, 1, 1], [1, 1, 0]], [[0, 1, 1], [0, 0, 1], [1, 0, 1], [1, 1, 1]]]).astype(float) for i in range(3): a[:, :, i] *= size[i] arr.append(a + array(position)) subplot.add_collection3d(Poly3DCollection(concatenate(arr), edgecolor='k', facecolors=repeat(sample(CSS4_COLORS.keys(), item_number), 6))) subplot.set_xlim([0, box_length]) subplot.set_ylim([0, box_width]) subplot.set_zlim([0, box_height]) show()
一些坑点
(1)figure().gca的参数即将被淘汰,因此改用figure().add_subplot()
(2)要按照容器的长、宽、高设置图像的比例,否则图像会变形
总结
好吧也没啥可总结的,这篇写于15年前的论文确实帮了我很大的忙,本文一半都是我重新复述一遍这篇论文的话,剩下一半是从CSDN与stackoverflow上偷的代码,稍微改吧改吧(配合我奇怪的码风),就是自己的了
谨此作为一个记录,防止出现那种”写的时候只有我和上帝看得懂,现在只有上帝能看懂”的悲剧
全文代码
from math import exp
from matplotlib.colors import CSS4_COLORS
from matplotlib.pyplot import figure, show
from mpl_toolkits.mplot3d.art3d import Poly3DCollection
from numpy import array, concatenate, repeat
from random import random, sample, shuffle
available_points = {} # 可供放置物体的点
putted_items = [] # 已放置的物体的大小与位置
x_reference, z_reference, box_length, box_width, box_height, x, y, z = 0, 0, 0, 0, 0, 0, 0, 0
# 判定空间是否足够容纳下物品
def isRoomEnough(item1, position):
if item1[0] + position[0] <= box_length and item1[1] + position[1] <= box_width and item1[2] + position[2] <= box_height: # 先特判一下该物品是否在容器内
for item2 in putted_items: # 也许有更高效的方法吧,但我暂且就暴力遍历了
if item2['position'] == position: # 特判两物体重合的情况
return False
overlap = 0
if item2['position'][0] < item1[0] + position[0] and position[0] < item2['position'][0] + item2['volume'][0] and item2['position'][1] < item1[1] + position[1] and position[1] < item2['position'][1] + item2['volume'][1]: # 判定xOy面是否重合
overlap = 1
if item2['position'][0] < item1[0] + position[0] and position[0] < item2['position'][0] + item2['volume'][0] and item2['position'][2] < item1[2] + position[2] and position[2] < item2['position'][2] + item2['volume'][2]: # 判定xOz面是否重合
overlap += 1
if item2['position'][1] < item1[1] + position[1] and position[1] < item2['position'][1] + item2['volume'][1] and item2['position'][2] < item1[2] + position[2] and position[2] < item2['position'][2] + item2['volume'][2]: # 判定yOz面是否重合
overlap += 1
if overlap > 1: # 若多于一面重合,则这两个物体在三维上是相交的
return False
return True
# 判定物品是否能在参考线内容纳下
def isInnerReference(item):
global x, y, z
for position in available_points: # 遍历所有可用点
if item[0] + position[0] <= x_reference and item[2] + position[2] <= z_reference and isRoomEnough(item, position) == True: # 判定该点是否可用且不与任何参考线重合
x, y, z = position[0], position[1], position[2]
return True
# 拓展参考线,并判定物品能否被容纳
def expandReference(item):
global x_reference, z_reference, x, y, z
if x_reference == 0 or x_reference == box_length: # 如果这是第一个物品或者x参考线已经最大,那么这个物体就有放不下的可能
if isRoomEnough(item, (0, 0, z_reference)) == True: # 若z轴上能放物体,就不用大刀阔斧地修改参考线
x, y, z, x_reference = 0, 0, z_reference, item[0]
z_reference += item[2]
return True
elif z_reference < box_height: # 如果z参考线还能动的话,直接把俩参考线加到最大
x_reference, z_reference = box_length, box_height
return isInnerReference(item) or expandReference(item)
else:
for position in available_points: # 遍历所有可用点
if position[0] == x_reference and position[1] == 0 and item[2] + position[2] <= z_reference and isRoomEnough(item, position) == True: # 判定所有在x参考线上的点是否可用且不与z参考线重合
x, y, z = position[0], position[1], position[2]
x_reference += item[0]
return True
x_reference = box_length
return isInnerReference(item) or expandReference(item)
# 将指定方向的一批物品以固定顺序放入容器中
def pack(items):
global available_points, putted_items, x_reference, z_reference
available_points = {(0, 0, 0)}
positions = []
putted_items = []
sizes = []
item_volume = x_reference = z_reference = 0
for item in items: # 顺序遍历所有物体
if (isInnerReference(item) or expandReference(item)) and isRoomEnough(item, (x, y, z)): # 若一切顺利,放下物体
putted_items.append({
'position': (x, y, z),
'volume': item,
}) # putted_items同时储存有物体的位置和大小
available_points.remove((x, y, z))
available_points.add(((x + item[0], y, z)))
available_points.add(((x, y + item[1], z)))
available_points.add(((x, y, z + item[2])))
positions.append((x, y, z))
sizes.append(item)
item_volume += item[0] * item[1] * item[2]
'''print('有一个长', item[0], '宽', item[1], '高', item[2], '的物品成功放置于', (x, y, z))
else:
print('有一个长', item[0], '宽', item[1], '高', item[2], '的物品放置失败')'''
return item_volume / box_length / box_width / box_height, positions, sizes
# 读取容器的长、宽、高
def read():
try: # 如果输错了就再输一遍
box_length, box_width, box_height = map(int, input('请依次输入箱子的长、宽、高(整数),以空格分隔:').split())
if box_length > 0 and box_width > 0 and box_height > 0: # 确保输入的是正数
return box_length, box_width, box_height
else:
print('输入了非正数')
except ValueError:
print('输入的不是三个数')
return read()
while True: # main()
items = [] # 一组顺序固定、方向固定的物体
items_kind = 0
box_length, box_width, box_height = read()
while True: # 读取物体的长、宽、高、个数
try: # 多组输入
items_length, items_width, items_height, number = map(int, (input('请依次输入物品的长、宽、高、个数(整数),以空格分隔。每行一组物品。若输入完毕请输入Ctrl+Z并回车:').split()))
if items_length > 0 and items_width > 0 and items_height > 0 and number > 0: # 确保正数
item = tuple(sorted((items_length, items_width, items_height), reverse=True))
for i in range(number): # 放入number个物体
items.append(item)
items_kind += 1
else:
print('输入了非正数')
except EOFError:
break
except ValueError:
print('输入的不是四个数')
items.sort(key=lambda item: item[0] * item[1] * item[2], reverse=True)
filling_rate, positions, sizes = pack(items)
print('0 次退火填充率:', filling_rate, '放置数量:', len(sizes))
best_items, best_positions, best_sizes, max_filling_rate = items, positions, sizes, filling_rate
for i in range(2): # 2次退火
temperature, area_length = 0.92, items_kind
while temperature >= 0.01: # 在温度降至足够低之前不断循环
for j in range(area_length): # 循环次数由邻域长度决定
new_items = items
for k, item in enumerate(new_items): # tuple不能直接shuffle,所以要先化成list再shuffle再化回tuple
l = list(item)
shuffle(l)
new_items[k] = tuple(l)
shuffle(new_items)
new_filling_rate, new_positions, new_sizes = pack(new_items)
if new_filling_rate > filling_rate or exp((new_filling_rate - filling_rate) * 10 / temperature) > random(): # 若满足更优解或满足Metropolis准则,则选取该解,这是模拟退火算法的核心
filling_rate, items, positions, sizes = new_filling_rate, new_items, new_positions, new_sizes
if new_filling_rate > max_filling_rate: # 记录最优解
max_filling_rate, best_items, best_positions, best_sizes = new_filling_rate, new_items, new_positions, new_sizes
area_length += items_kind
temperature *= 0.92
print(i + 1, '次退火填充率:', max_filling_rate, '放置数量:', len(best_sizes))
item_number = len(best_sizes)
if item_number > 0: # 若解存在,则画图展示
subplot = figure().add_subplot(projection='3d')
subplot.set_box_aspect((box_length, box_width, box_height))
arr = []
for position, size in zip(positions, sizes): # 其实我完全看不懂这一段……这段代码是从StackOverFlow上偷来的
a = array([[[0, 1, 0], [0, 0, 0], [1, 0, 0], [1, 1, 0]], [[0, 0, 0], [0, 0, 1], [1, 0, 1], [1, 0, 0]], [[1, 0, 1], [1, 0, 0], [1, 1, 0], [1, 1, 1]], [[0, 0, 1], [0, 0, 0], [0, 1, 0], [0, 1, 1]], [[0, 1, 0], [0, 1, 1], [1, 1, 1], [1, 1, 0]], [[0, 1, 1], [0, 0, 1], [1, 0, 1], [1, 1, 1]]]).astype(float)
for i in range(3):
a[:, :, i] *= size[i]
arr.append(a + array(position))
subplot.add_collection3d(Poly3DCollection(concatenate(arr), edgecolor='k', facecolors=repeat(sample(CSS4_COLORS.keys(), item_number), 6)))
subplot.set_xlim([0, box_length])
subplot.set_ylim([0, box_width])
subplot.set_zlim([0, box_height])
show()