基于OR-Tools的学校拼车问题约束定义技术求助

我在实际场景中遇到学校拼车调度问题，计划用OR-Tools工具解决。学校分两个校区，部分孩子整周固定去校区1，其余固定去校区2。目前已完成基础模型定义，代码如下：

from ortools.sat.python import cp_model

def main():
    # Data.
    num_parents = 12
    num_children = 20
    num_days = 5
    num_locations = 2
    all_parents = range(num_parents)
    all_children = range(num_children)
    all_days = range(num_days)
    all_locations = range(num_locations)

    # Creates the model.
    model = cp_model.CpModel()
    # Creates ride variables.
    # rides[(n, d, c, l)]: parent 'n' takes child 'c' on day 'd' to location l.
    rides = {}
    for n in all_parents:
        for d in all_days:
            for c in all_children:
                for l in all_locations:
                    rides[(n, d, c, l)] = model.NewBoolVar(f'ride_n{n}d{d}c{c}l{l}')

以下是所有约束的建模实现，重点解决亲子关联和孩子-校区关联的约束：

约束建模实现 #

1. 每位家长单次行程最多搭载4名孩子（支持按家长调整载客量） #

先定义辅助变量标记家长是否执行某校区的行程，再关联载客量限制：

# 辅助变量：parent_trip[(n, d, l)] = 1 表示家长n在d天前往l校区执行一次行程
parent_trip = {}
for n in all_parents:
    for d in all_days:
        for l in all_locations:
            parent_trip[(n, d, l)] = model.NewBoolVar(f'parent_trip_n{n}d{d}l{l}')

# 关联行程与载客：如果家长带某孩子去某校区，说明该行程存在
for n in all_parents:
    for d in all_days:
        for c in all_children:
            for l in all_locations:
                model.AddImplication(rides[(n, d, c, l)], parent_trip[(n, d, l)])

# 单次行程载客量限制：可替换为按家长定义的载客量列表（比如[4,5,3,...]）
max_passengers = 4
for n in all_parents:
    for d in all_days:
        for l in all_locations:
            total_kids = sum(rides[(n, d, c, l)] for c in all_children)
            # 行程存在时，载客量不超过上限
            model.Add(total_kids <= max_passengers).OnlyEnforceIf(parent_trip[(n, d, l)])

2. 每位家长单次行程仅能前往一个校区 #

同一家长同一天的行程，最多对应一个校区：

for n in all_parents:
    for d in all_days:
        # 同一天内，家长前往不同校区的行程数之和 ≤1
        model.Add(sum(parent_trip[(n, d, l)] for l in all_locations) <= 1)

3. 每位家长每日最多执行2次行程（含接送） #

这里默认往返算两次行程，限制每日总行程数不超过2：

for n in all_parents:
    for d in all_days:
        model.Add(sum(parent_trip[(n, d, l)] for l in all_locations) <= 2)

4. 家长执行行程时至少搭载一名自己的孩子 #

先定义亲子关系映射，再添加约束：

# 亲子关系映射：key为家长ID，value为该家长的孩子ID列表（需根据实际数据调整）
parent_child_map = {
    0: [0, 1],
    1: [2, 3],
    2: [4, 5],
    3: [6, 7],
    4: [8, 9],
    5: [10, 11],
    6: [12, 13],
    7: [14, 15],
    8: [16, 17],
    9: [18, 19],
    10: [],  # 若有家长无孩子，需调整约束逻辑
    11: []
}

# 约束：家长执行行程时，必须带至少一名自己的孩子
for n in all_parents:
    # 跳过无孩子的家长，或根据实际需求处理
    if not parent_child_map[n]:
        continue
    for d in all_days:
        for l in all_locations:
            own_kids_count = sum(rides[(n, d, c, l)] for c in parent_child_map[n])
            model.Add(own_kids_count >= 1).OnlyEnforceIf(parent_trip[(n, d, l)])

5. 每个孩子固定前往一个校区，整周地点不变 #

先定义每个孩子的固定校区，再添加约束确保孩子仅前往该校区：

# 孩子固定校区映射：索引为孩子ID，值为固定校区（0或1，需根据实际数据调整）
child_fixed_location = [0]*10 + [1]*10  # 示例：前10个孩子去校区0，后10个去校区1

# 约束1：孩子只能去固定校区，禁止前往其他校区
for c in all_children:
    fixed_l = child_fixed_location[c]
    for d in all_days:
        for l in all_locations:
            if l != fixed_l:
                # 所有家长都不能带该孩子去非固定校区
                for n in all_parents:
                    model.Add(rides[(n, d, c, l)] == 0)

# 约束2：每个孩子每天必须被恰好一位家长接送（若需求为孩子必须被接送则添加）
for c in all_children:
    for d in all_days:
        fixed_l = child_fixed_location[c]
        model.Add(sum(rides[(n, d, c, fixed_l)] for n in all_parents) == 1)

6. 均衡家长工作量，实现任务公平分配 #

通过最小化家长总行程次数的差值来实现公平：

# 计算每位家长的总行程次数
parent_total_trips = []
for n in all_parents:
    total = sum(parent_trip[(n, d, l)] for d in all_days for l in all_locations)
    parent_total_trips.append(total)

# 定义最大、最小行程次数变量
max_trips = model.NewIntVar(0, num_days*2, 'max_trips')
min_trips = model.NewIntVar(0, num_days*2, 'min_trips')

model.AddMaxEquality(max_trips, parent_total_trips)
model.AddMinEquality(min_trips, parent_total_trips)

# 目标：最小化最大与最小行程次数的差值，实现工作量均衡
model.Minimize(max_trips - min_trips)

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