如何在Google OR-Tools的CVRP中设置行程时间软约束（达标率要求）

OR-Tools没有内置的直接约束来表达「至少XX%路径符合时间限制」这类需求，但完全不需要反复调整硬约束值试错，有两种更精准的实现方式：

方式一：将合规要求转化为带惩罚的软约束 #

给每条违反最长行程时间的路径设定一个惩罚成本（根据业务损失、优先级自定义数值），把惩罚项加入总目标函数。求解器会在总代价（比如总行驶距离+违规惩罚）最优的前提下，自动平衡合规路径数量与整体运营成本：

• 给每辆车定义布尔辅助变量，标记是否违规（1=违规，0=合规）
• 通过约束关联辅助变量与车辆行驶时间：当车辆行驶时间超过上限，辅助变量设为1；反之设为0
• 将「违规车辆数×惩罚系数」加入目标函数，系数越大，求解器越倾向于减少违规路径

示例伪代码（CP-SAT）：

# 自定义违规惩罚系数（根据业务场景调整）
penalty_per_violation = 1500
# 创建车辆违规标记变量
violation_vars = [model.NewBoolVar(f"vehicle_violate_{i}") for i in range(num_vehicles)]

for vehicle_idx in range(num_vehicles):
    # 关联行驶时间与违规标记
    model.Add(vehicle_total_time[vehicle_idx] > MAX_TRIP_TIME).OnlyEnforceIf(violation_vars[vehicle_idx])
    model.Add(vehicle_total_time[vehicle_idx] <= MAX_TRIP_TIME).OnlyEnforceIf(violation_vars[vehicle_idx].Not())

# 总目标：最小化总行驶距离 + 违规惩罚
model.Minimize(total_distance + sum(violation_vars) * penalty_per_violation)

方式二：采用多目标优化思路 #

把「合规路径占比」作为第二个优化目标，与原有的总行驶距离/成本目标结合优化。OR-Tools的CP-SAT求解器支持多目标优化，可以通过设置优先级或权重匹配业务需求：

• 优先保证至少XX%的路径合规，再优化总成本
• 给两个目标分配权重，比如「合规路径数量×权重A + 总距离×权重B」，通过调整权重平衡两者优先级

这种方式能更直接地把业务要求转化为优化目标，避免手动调整硬约束的繁琐。

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