如何将复杂荷兰劳工规则定义为MIP约束？

问题背景 #

核心决策变量为二进制变量x(i,j)，表示班次i是否分配给员工j。需满足荷兰标准劳工法的二选一规则：

• 7天周期规则：以每个班次开始为起点的7×24小时周期内，员工需存在至少一次≥36小时的不间断休息（休息必须完全处于周期内）
• 14天周期规则：以每个班次开始为起点的14×24小时周期内，员工需同时满足：
  1. 所有在周期内的不间断休息时长≥32小时
  2. 周期内所有合规休息的总时长≥72小时

可行建模方案 #

第一步：预计算班次时间参数 #

提前对所有班次对(i,k)（i结束时间早于k开始时间）计算以下参数：

• rest_time(i,k)：班次i结束到班次k开始的休息时长
• in_7(i,k)：布尔值，标记k是否在以i为起点的7天周期内，且对应的休息完全处于周期内
• in_14(i,k)：布尔值，标记k是否在以i为起点的14天周期内，且对应的休息完全处于周期内
• rest_end_7(i,m)：班次m结束到以i为起点的7天周期结束的时长
• rest_end_14(i,m)：班次m结束到以i为起点的14天周期结束的时长

第二步：补充决策变量 #

除核心变量x(i,j)外，新增以下变量：

1. 规则1相关：
   • has_36(i,j)：二进制，1=员工j在以i为起点的7天周期内存在≥36小时的合规休息
   • is_last_7(i,m,j)：二进制，1=员工j在以i为起点的7天周期内的最后一个班次是m
2. 规则2相关：
   • all_32(i,j)：二进制，1=员工j在以i为起点的14天周期内所有休息均≥32小时
   • total_rest_14(i,j)：连续变量，员工j在以i为起点的14天周期内的合规休息总时长
   • is_last_14(i,m,j)：二进制，1=员工j在以i为起点的14天周期内的最后一个班次是m

第三步：构建约束 #

核心二选一约束

对每个员工j、每个班次i：

has_36(i,j) + all_32(i,j) ≥ x(i,j)

解释：若员工j被分配班次i，则必须满足7天周期规则或14天周期规则。

7天周期规则约束

1. 标记周期内最后一个班次：

Σ_{m: in_7(i,m)} is_last_7(i,m,j) = x(i,j)
is_last_7(i,m,j) ≤ x(m,j)  ∀m ∈ 7天周期内的班次

2. 验证是否存在≥36小时的休息：

has_36(i,j) ≤ Σ_{k: in_7(i,k) and rest_time(i,k)≥36} x(i,j)*x(k,j) + Σ_{m: in_7(i,m) and rest_end_7(i,m)≥36} is_last_7(i,m,j) + (1 - x(i,j))

14天周期规则约束

1. 标记周期内最后一个班次：

Σ_{m: in_14(i,m)} is_last_14(i,m,j) = x(i,j)
is_last_14(i,m,j) ≤ x(m,j)  ∀m ∈ 14天周期内的班次

2. 确保所有休息≥32小时（用大M约束，M取2即可）：

x(i,j) + x(k,j) ≤ 1 + M*(1 - all_32(i,j))  ∀k ∈ 14天周期内且rest_time(i,k)<32的班次

3. 计算总休息时长：

total_rest_14(i,j) = Σ_{k: in_14(i,k)} rest_time(i,k)*x(i,j)*x(k,j) + Σ_{m: in_14(i,m)} rest_end_14(i,m)*is_last_14(i,m,j)

4. 总休息时长≥72小时：

total_rest_14(i,j) ≥ 72*all_32(i,j)

优化建议 #

• 预过滤无效班次对：提前排除休息时长明显不达标或不在周期内的班次对，减少变量和约束数量
• 大M值优化：使用最小可行的大M值（如2），避免数值求解问题
• 开启CPLEX预处理：启用CPLEX的预处理、切割平面等选项，提升求解效率

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