我试图解决的问题有点像这里的员工调度问题：
https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py
但是，有一些事情我被困住了，不知道如何合并到代码中。下面我会解释这个问题。
问题
我有一个由 47 趟列车组成的车队，我想每天将它们分配给 49 条路线。列车应分配以下约束：
每趟列车白天必须至少使用一次（任何列车不得全天闲置）
每趟列车必须分配至少一条路线（最多两条路线）并且必须覆盖每条路线
列车分配路线后最终里程不得超过24,800（即前一天累计里程+分配路线里程<= 24,800). This is probably best understood by looking at the total_km_day_end column in the 3rd table below
如果一趟列车一天分配两条路线，这些路线的时间不得重叠
我想要的另一个约束，但我并不珍惜这个（假设这是一个软约束）：
我有一个火车的数据框，如下所示。我可以随机选择一个日期，查看 47 趟列车中每趟列车截至前一天（即 18/9/2018）的累计里程：
Date | Day | Train | Cum_mileage_prev_day
----------| --------- | --------- |----------------------
19/9/18 | WED | T32 | 24,300
19/9/18 | WED | T11 | 24,200
19/9/18 | WED | T38 | 24,200
. . . .
. . . .
19/9/18 | WED | T28 | 600
19/9/18 | WED | T15 | 200
19/9/18 | WED | T24 | 100
以及routes的数据框，如下所示。请注意，100 公里以上的路线被定义为长路线，低于 100 公里的路线被定义为短路线。在 49 条路线中，只有 6 条路线较短（10 公里） - 请注意，下面仅显示了 5 条较短路线：
Route | Start | End | Total_km | route_type
------ | --------- | ---------|-------------|-------------
R11 | 5:00 | 00:00 | 700 | Long
R32 | 6:00 | 00:50 | 600 | Long
R16 | 5:20 | 23:40 | 600 | Long
. . . . .
. . . . .
R41 | 11:15 | 12:30 | 10 | Short
R42 | 11:45 | 13:00 | 10 | Short
R43 | 12:15 | 13:30 | 10 | Short
R44 | 12:45 | 14:00 | 10 | Short
R45 | 13:20 | 14:35 | 10 | Short
我想要的结果是这样的，火车被分配了 1 或 2 条路线，并且显示当天结束时的总里程（假设分配的路线由火车完成）：
Date | Day | Train| Cum_mil_prev_day | first_assign | second_assign | total_km_day_end
-------| ------| -------|-------------------|--------------|---------------|----------------
19/9/18| WED | T32 | 24,300 | R41 | R44 | 24,320
19/9/18| WED | T11 | 24,200 | R42 | R45 | 24,220
19/9/18| WED | T38 | 24,200 | R43 | | 24,210
. . . . . .
. . . . . .
19/9/18| WED | T28 | 600 | R11 | | 1300
19/9/18| WED | T15 | 200 | R32 | | 800
19/9/18| WED | T24 | 100 | R16 | | 700
编辑/更新（2/8/19）：
（注意：下面的代码显示了该问题的简化版本，其中 6 趟列车分配给 8 条路线。我还在代码中包含了约束 5。）
非常感谢斯特拉迪瓦里和洛朗在这方面的帮助。
from itertools import combinations
from ortools.sat.python import cp_model
def test_overlap(t1_st, t1_end, t2_st, t2_end):
def convert_to_minutes(t_str):
hours, minutes = t_str.split(':')
return 60*int(hours)+int(minutes)
t1_st = convert_to_minutes(t1_st)
t1_end = convert_to_minutes(t1_end)
t2_st = convert_to_minutes(t2_st)
t2_end = convert_to_minutes(t2_end)
# Check for wrapping time differences
if t1_end < t1_st:
if t2_end < t2_st:
# Both wrap, therefore they overlap at midnight
return True
# t2 doesn't wrap. Therefore t1 has to start after t2 and end before
return t1_st < t2_end or t2_st < t1_end
if t2_end < t2_st:
# only t2 wraps. Same as before, just reversed
return t2_st < t1_end or t1_st < t2_end
# They don't wrap and the start of one comes after the end of the other,
# therefore they don't overlap
if t1_st >= t2_end or t2_st >= t1_end:
return False
# In all other cases, they have to overlap
return True
def main():
model = cp_model.CpModel()
solver = cp_model.CpSolver()
# data
route_km = {
'R11': 700,
'R32': 600,
'R16': 600,
'R41': 10,
'R42': 10,
'R43': 10,
'R44': 10,
'R45': 10}
train_cum_km = {
'T32': 24_300,
'T11': 24_200,
'T38': 24_200,
'T28': 600,
'T15': 200,
'T24': 100}
route_times = {
'R11': ('05:00', '00:00'),
'R32': ('06:00', '00:50'),
'R16': ('05:20', '23:40'),
'R41': ('11:15', '12:30'),
'R42': ('11:45', '13:00'),
'R43': ('12:15', '13:30'),
'R44': ('12:45', '14:00'),
'R45': ('13:20', '14:35')}
trains = list(train_cum_km.keys())
routes = list(route_km.keys())
num_trains = len(trains)
num_routes = len(routes)
assignments = {(t, r): model.NewBoolVar('assignment_%s%s' % (t, r))
for t in trains for r in routes}
# constraint 1: each train must be used
for r in routes:
model.Add(sum(assignments[(t, r)] for t in trains) == 1)
# constraint 2: each train must do at least one (max two) routes
for t in trains:
model.Add(sum(assignments[(t, r)] for r in routes) >= 1)
model.Add(sum(assignments[(t, r)] for r in routes) <= 2)
# constraint 3: ensure the end of day cum km is less than 24_800
# create a new variable which must be in the range (0,24_800)
day_end_km = {
t: model.NewIntVar(0, 24_800, 'train_%s_day_end_km' % t)
for t in trains
}
for t in trains:
# this will be constrained because day_end_km[t] is in domain [0, 24_800]
tmp = sum(assignments[t, r]*route_km[r] for r in routes) + train_cum_km[t]
model.Add(day_end_km[t] == tmp)
# constraint 4: where 2 routes are assigned to a train, these must not overlap
for (r1, r2) in combinations(routes, 2):
if test_overlap(route_times[r1][0], route_times[r1][1], route_times[r2][0], route_times[r2][1]):
for train in trains:
model.AddBoolOr([assignments[train, r1].Not(), assignments[train, r2].Not()])
# constraint 5: trains with high cum km should be assigned short routes
# and trains with low mileage to long routes
score = {
(t,r): route_km[r] + train_cum_km[t]
for t in trains for r in routes
}
for r in routes:
model.Minimize(sum(assignments[t,r]*score[t,r] for t in trains))
status = solver.Solve(model)
assert status in [cp_model.FEASIBLE, cp_model.OPTIMAL]
for t in trains:
t_routes = [r for r in routes if solver.Value(assignments[t, r])]
print(f'Train {t} does route {t_routes} '
f'with end of day cumulative kilometreage of '
f'{solver.Value(day_end_km[t])}')
if __name__ == '__main__':
main()
输出：
Train T32 does route ['R42', 'R45'] with end of day cumulative kilometreage of 24320
Train T11 does route ['R41', 'R44'] with end of day cumulative kilometreage of 24220
Train T38 does route ['R43'] with end of day cumulative kilometreage of 24210
Train T28 does route ['R16'] with end of day cumulative kilometreage of 1200
Train T15 does route ['R32'] with end of day cumulative kilometreage of 800
Train T24 does route ['R11'] with end of day cumulative kilometreage of 800
我的头顶上，不确定这是否是最好的方法：
assignments = {
(route, train): model.NewBoolVar('')
for route in routes
for train in all_trains
}
for train in all_trains:
model.Add(sum(assignments[route, train] for route in routes) >= 1)
model.Add(sum(assignments[route, train] for route in routes) <= 2)
创建一个字典，其中包含每条路线的里程：
route_km = {'R11': 700, 'R16': 600}cum_mileage = {0: 24_320, 3: 24_220}for train in all_trains:
model.Add(cum_mileage[train]+sum(
assignments[route, train]*route_km[route]
for route in routes
) <= 24_800)
创建一个函数，如果两条路线重叠，则返回
True
from itertools import combinations
for (r1, r2) in combinations(routes, 2):
if not conflicts(r1, r2):
continue
for train in all_trains:
model.AddBoolOr([assignments[r1, train].Not(), assignments[r2, train].Not()])
然后最小化每个布尔赋值变量的加权和。
尽管如此，上述输出中最小和最大 EOD 公里数之间的范围是 23520。
最小化范围不是更好的得分目标吗？
max_day_end_km = model.NewIntVar(0, 28_400, "max day_end_km")
model.AddMaxEquality(max_day_end_km, [day_end_km[t] for t in day_end_km])
min_day_end_km = model.NewIntVar(0, 28_400, "min day_end_km")
model.AddMinEquality(min_day_end_km, [day_end_km[t] for t in day_end_km])
km_range = model.NewIntVar(0, 28_400, "km_range")
model.Add(km_range == max_day_end_km - min_day_end_km)
model.Minimize(km_range)
使用上述目标，找到范围为 23510 的最优解。（更好的评分目标是最小化每列列车的 EOD 公里与平均 EOD 公里之间的范围
和 的总和。尽管对于此数据集，解决方案与解决方案相同当简单地最小化范围时。）