背景

2D矩形装箱问题是指在二维平面内有若干个不同大小的矩形，如何将它们放置在一个矩形区域内，使得所需的空间最小化。

该问题涉及到矩形的排列和旋转，以及空间利用的最大化，是一个典型的NP问题。

现在尝试通过模拟退火算法 (SA) 找到 2D 矩形装箱问题解的求解器。

模拟退火算法

模拟退火（Simulated annealing）是一种通用概率算法，常用来在一定时间内寻找在一个很大搜寻空间中的近似最优解。模拟退火在1983年为S. Kirkpatrick, C. D. Gelatt和M. P. Vecchi所发明，V. Cern'y也在1985年独立发明此算法。

模拟退火来自冶金学的专有名词退火。退火是将材料加热后再经特定速率冷却，目的是增大晶粒的体积，并且减少晶格中的缺陷。材料中的原子原来会停留在使内能有局部最小值的位置，加热使能量变大，原子会离开原来位置，而随机在其他位置中移动。退火冷却时速度较慢，使得原子有较多可能可以找到内能比原先更低的位置。

模拟退火的原理也和金属退火的原理近似：我们将热力学的理论套用到统计学上，将搜寻空间内每一点想像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。算法先以搜寻空间内一个任意点作起始：每一步先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。

可以证明，模拟退火算法所得解概率收敛到全局最优解。

开源实现：rectangle-packing-solver

通过模拟退火优化找到 2D 矩形堆积问题解的求解器。序列对用于表示矩形布局。

主要功能

• 由于求解器是基于 SA 的，因此解的质量和执行时间是可调的。
• 矩形的宽度和高度不仅可以设置为整数，还可以设置为实数。
• 矩形在优化时可以旋转。
• 内置的可视化工具可以可视化平面图解决方案。

安装

pip install rectangle-packing-solver -i https://pypi.tuna.tsinghua.edu.cn/simple

示例代码

import rectangle_packing_solver as rps

# 定义一个问题
problem = rps.Problem(rectangles=[(0.1 * i, 0.1 * i) for i in range(100, 200, 5)])
print("问题:", problem)

# 寻找解决方案
print("\n=== 没有宽度/高度限制的求解 ===")
solution = rps.Solver().solve(
  problem=problem, simanneal_minutes=1.0, simanneal_steps=500, show_progress=True, seed=1234
)
print("解决方案:", solution)

# 可视化（生成 floorplan_large.png)
rps.Visualizer().visualize(solution=solution, path="./floorplan_large.png")

# 寻找解决方案 (有约束限制)
print("\n=== 解决宽度/高度约束 ===")
solution = rps.Solver().solve(
  problem=problem, simanneal_minutes=1.0, simanneal_steps=500, height_limit=50.0, show_progress=True, seed=1234
)
print("解决方案:", solution)
rps.Visualizer().visualize(solution=solution, path="./floorplan_large_limit.png")

输出结果：