最小成本存储分配优化问题的最优解决方案咨询

问题描述 #

我正在尝试解决以下分配优化问题：

• 存在S个存储室，每个存储室s的容量为C_s；
• 存在P个包裹，每个包裹p的尺寸为Z_p；
• 将包裹p存入存储室s的成本为T_{ps}；
• 单个存储室可存放多个包裹，只要所有存入包裹的总尺寸不超过其容量C_s；
• 单个包裹不可拆分存入多个存储室。

问题目标：将所有包裹分配至存储室，最小化总成本。

我的现有思路 #

• 已构建好成本矩阵；
• 考虑过用匈牙利算法求解，但因为存储室有容量上限，每个存储室可容纳多个包裹，而匈牙利算法适用于一对一的分配场景，所以判断该算法不适用；
• 考虑过将其视为运输优化问题，但运输问题允许货物拆分分配，而这里包裹不可拆分，因此也不适用。

可行解决方案思路 #

这个问题本质是带容量约束的0-1整数规划问题，也属于多背包问题（最小成本变种），以下是几种可行的解决方向：

1. 整数规划建模直接求解 #

可以构建0-1整数规划模型来精准描述问题：

• 决策变量：x_{ps} = 1 代表包裹p存入存储室s，否则x_{ps}=0
• 目标函数：minimize Σ(p=1到P) Σ(s=1到S) T_{ps} * x_{ps}
• 约束条件：
  • 每个包裹必须且只能分配到一个存储室：Σ(s=1到S) x_{ps} = 1，对所有p=1..P
  • 每个存储室总包裹尺寸不超容量：Σ(p=1到P) Z_p * x_{ps} ≤ C_s，对所有s=1..S
  • 变量取值限制：x_{ps} ∈ {0,1}

你可以用PuLP、OR-Tools这类开源工具，或者Gurobi、CPLEX这类商用求解器来求解。如果问题规模不大（比如包裹数、存储室数在几百以内），求解速度通常能满足需求。

2. 启发式算法（应对大规模问题） #

如果问题规模很大（比如包裹数或存储室数上千），整数规划求解器可能效率不够，这时可以用启发式算法找近似最优解：

• 贪心算法：按包裹的成本优先级（比如单位尺寸成本T_{ps}/Z_p从低到高）排序，依次把包裹分配到当前成本最低且还有剩余容量的存储室；
• 遗传算法/模拟退火：通过迭代优化的方式逐步改进解的质量，适合复杂的大规模组合优化场景；
• 局部搜索：先构造一个初始可行解，再通过交换不同存储室的包裹等方式迭代优化。

3. 调整运输问题适配（仅适合小规模） #

如果想基于运输问题的思路，可以把每个存储室拆分成多个“虚拟存储室”：比如容量为C_s的存储室，拆成k_s个虚拟室，每个虚拟室的容量设为单个包裹的最大尺寸，确保每个虚拟室最多放一个包裹。但这种方法会大幅增加变量数量，只适合小规模问题。

内容的提问来源于stack exchange，提问作者os12