基于Optaplanner/Timefold的VRP高车辆利用率优化惩罚函数咨询

针对你用Optaplanner/Timefold求解VRP时，希望最小化在用车辆数+最大化在用车辆满载率的需求，以下是比现有方案更精准的优化思路：

1. 分阶段分层求解 #

先锁定最少车辆数，再优化满载率，避免两个目标互相干扰：

• 第一阶段：仅以「减少在用车辆数」为核心优化目标，把行驶成本、负载率设为次要约束（甚至暂时忽略）。比如将“每多用1辆车”的软惩罚权重设为极高（如10000分），行驶成本惩罚设为极低（如1分/公里）。这一步先得到满足所有任务的最少车辆数。
• 第二阶段：固定第一阶段得出的车辆数（设为硬约束，禁止超过该数量），再重点优化「车辆满载率」和行驶成本。此时将“车辆负载与满载差值”的惩罚权重调高，迫使solver将任务集中到已启用的车辆上，尽量填满。

2. 非线性满载率惩罚函数 #

线性惩罚对“半载”和“接近满载”的区分度不足，改用非线性惩罚放大低负载的代价：

• 计算车辆负载率 r = 实际负载 / 最大负载，惩罚值采用平方或指数形式，比如：惩罚 = (1 - r)^2 * 权重。这样负载率从90%降到50%时，惩罚从0.01倍权重飙升至0.25倍权重，solver会更倾向于让车辆尽量接近满载。
• 在Optaplanner/Timefold的ConstraintProvider或EasyScoreCalculator中直接实现该逻辑即可。

3. 约束权重的优先级明确排序 #

确保约束的优先级完全匹配你的业务目标：

• 硬约束：车辆负载不超过最大容量、所有任务必须分配。
• 软约束优先级（从高到低）：
  • 每多用1辆车，惩罚10000分（权重最高，优先保证少用车）
  • 车辆负载与满载的差值，惩罚100分/单位（次高，保证在用车辆尽量满）
  • 总行驶距离/时间，惩罚1分/公里（最低，在满足前两个目标的前提下优化行驶成本）
• 权重数值需根据实际场景调整，但必须保证前两项权重远高于第三项。

4. 自定义构造启发式策略 #

默认构造启发式可能随机分配任务，导致初始解就出现多辆半载车。自定义构造策略，优先装满一辆车再启用下一辆：

• 实现CustomConstructionHeuristicPhaseConfig，在构造阶段采用「批量分配任务至同一车辆，直到接近满载，再切换下一辆」的逻辑。这样初始解更接近你的理想状态，后续局部搜索更容易收敛到最优解。

5. 惩罚负载率方差 #

通过约束减少在用车辆的负载差异，避免多辆半载车的情况：

• 用影子变量跟踪每辆车的实际负载率，计算所有在用车辆负载率的方差。方差越大，说明车辆负载越分散（多辆半载），施加越高的惩罚。
• 该约束会引导solver将任务集中到部分车辆（尽量满载），剩余任务集中到少数车辆，闲置车辆则直接关闭。

对现有方案的优化建议 #

• 你之前的「线性惩罚至阈值加固定惩罚」方案，可结合非线性惩罚优化，让阈值以下的惩罚更陡峭，强化“接近满载”的激励。
• 「直接惩罚在用车辆」的方案，需确保该惩罚权重远高于行驶成本，同时搭配满载率惩罚，避免solver为了少用车而违反负载硬约束。

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