模拟退火算法求解MIP问题时如何处理模型约束条件？

你对标准SA原生逻辑的判断是准确的——原生模拟退火的迭代框架本身只围绕目标函数值做Metropolis接受判断，没有内置约束校验模块，但这绝不是说用SA求解MIP问题时不需要考虑约束，学界和工业界针对元启发式求解带约束MIP问题已经形成了非常成熟的落地方法，针对你做的2E-OLRP这类强约束组合优化问题，常用的处理思路可以按需组合使用：

• 编码与邻域操作层强制满足硬约束
  这是求解LRP类问题性价比最高的约束处理方式，别上来就全靠惩罚项兜底。你可以先把问题的所有约束做拆分：对于「每个客户仅分配给一个二级配送点」「开放路径不形成闭环」「设施选中后才能承接配送需求」这类逻辑上可以卡死的硬约束，直接通过解的编码规则、邻域扰动算子的生成规则保证满足——从根源上就不生成违反这类约束的候选解。比如给2E-OLRP做解编码时，可以拆成三层结构：第一层是一、二级备选设施的选中状态0-1向量，第二层是客户点到二级设施的分配映射表，第三层是各层级的开放路径节点序列；写交换客户点、增删选中设施、路径片段重连这类邻域算子时，每生成一个新解先做硬约束校验，违反就直接废弃这次扰动重新生成，不让这类无效解进入后续的目标值计算和接受判断流程。
• 动态惩罚函数处理软约束
  对于少数没法通过编码和邻域规则100%规避的约束（比如车辆临时超载、单条路径长度超出上限），不需要直接把对应解判死刑，可以把约束违反的程度量化为惩罚项叠加到目标函数中。注意惩罚系数不要设成固定值：迭代初期温度高时把系数设低，允许算法暂时跳出可行域扩大搜索范围，避免过早卡在局部最优；迭代后期温度逐步降低时同步拉高惩罚系数，保证最终收敛的解完全落在可行域内。MATLAB中对应的目标函数计算逻辑可以参考如下写法：

  % 2E-OLRP目标值计算：基础成本+动态惩罚项
  function total_cost = calc_total_cost(sol, problem_param, current_iter, max_iter)
      % 基础成本：设施建设成本+两级路径运输成本
      base_cost = sol.facility_open_cost + sol.first_echelon_cost + sol.second_echelon_cost;
      % 动态惩罚系数：迭代初期为10，末期线性增长到1000
      penalty_coef = 10 + (1000 - 10) * (current_iter / max_iter);
      % 计算各约束违反量
      cap_violation = sum(max(0, sol.node_load - problem_param.node_capacity));
      route_len_violation = sum(max(0, sol.route_length - problem_param.max_route_len));
      % 叠加惩罚
      total_cost = base_cost + penalty_coef * (cap_violation + route_len_violation);
  end
  

  这里要避开两个常见坑：一是初始惩罚系数不要设得极大，不然算法会直接退化成贪心，极容易卡在局部最优；二是惩罚系数不要全程保持低值，不然最后跑出来的解看起来目标值很低，实际上全是违反约束的无效解。
• 不可行解快速修复算子
  如果邻域扰动生成了违反硬约束的解，不一定直接丢弃，可以针对每类高频出现的不可行场景写专门的修复逻辑，把不可行解拉回可行域后再进入接受判断流程。比如2E-OLRP扰动后如果出现某条二级路径超载的情况，就直接把路径上距离当前所属二级点最远的几个客户，拆分到相邻的未满负荷的二级点对应路径中；如果出现未选中的设施承接了配送需求，就直接把对应需求分配给距离最近的已选中同层级设施。这种方式比直接丢弃不可行解的搜索效率高很多，尤其是邻域扰动步长设置较大的时候。
• 接受准则层适配约束判断
  可以对原生SA的Metropolis接受准则做小幅修改：如果候选新解是可行解、当前旧解是不可行解，不管两者目标值差多少、当前温度多高，都直接接受新解；如果新旧解都是不可行解，就把约束违反程度也纳入接受概率的计算，约束违反程度越高的解，被接受的概率越低。

针对2E-OLRP的SA实现实操建议：这类问题70%以上的约束都可以通过编码和邻域规则强制满足，剩下20%左右的容量、路径长度类约束搭配动态惩罚+修复算子处理就足够，不要所有约束都靠惩罚项处理，不然调参会耗费大量无意义的时间。

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