Google OR 工具 - 火车调度问题
Google OR tools - train scheduling problem
我要解决的问题有点像这里的员工安排：
https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py
但是，有几件事我卡住了，不知道如何将其合并到代码中。我将在下面解释这个问题。
问题
我有一个由 47 列火车组成的车队，我想每天分配给 49 条路线。应为列车分配以下约束：
一天中每列火车必须至少使用一次（没有火车必须整天闲置）
每列火车必须至少分配一条路线（最多两条路线）并且必须覆盖每条路线
列车最终里程一旦分配到某条线路，不得超过24800（即前一天累计里程+分配线路里程<=24800）。这可能是通过查看下面第 3 table 中的 total_km_day_end 列得到最好的理解
如果一天内有两条线路，两条线路的时间不能重叠
另一个我想要但并不重要的约束是这个（假设它是一个软约束）：
- 前一天里程数高的列车应分配到短线，前一天里程数低的列车应分配到长线
我有一个 火车 的数据框，看起来像这样。我可以随机选择一个日期，并查看 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
路由 的数据框如下所示。请注意，超过 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
EDIT/UPDATE (2/8/19):
（注意：下面的代码显示了将 6 列火车分配给 8 条路线的问题的简化版本。我还在代码中包含了约束 5。）
非常感谢 Stradivari 和 Laurent 在这方面的帮助。
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)
列车最终里程，一旦分配到一条路线，不得超过24,800
用每条路线的里程创建一个字典：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)
如果一天内有两条线路，两条线路的时间不能重叠
创建一个函数，如果两条路线重叠returns True
Efficient date range overlap calculation in python?
然后：
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()])
您可以计算将一条路线分配给一列火车的分数。 （比如 mileage_of_day_before + 路线长度）
然后将每个布尔赋值变量的加权和最小化。
运行 上面的代码，我没有得到相同的输出。 （可能是由于平台差异，其中使用了多个 model.Minimize objective 之一...）
尽管如此，上述输出中最小和最大 EOD 公里之间的范围是 23520。
最小化范围不是更好的得分吗objective？
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)
使用上面的方法 objective 找到范围为 23510 的最优解。
（更好的得分 objective 是最小化范围之和 和 每列火车的 EOD km 与平均 EOD 之间的增量总和公里。虽然对于这个数据集，解决方案与简单最小化范围时的解决方案相同。）
我要解决的问题有点像这里的员工安排：
https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py
但是，有几件事我卡住了，不知道如何将其合并到代码中。我将在下面解释这个问题。
问题
我有一个由 47 列火车组成的车队，我想每天分配给 49 条路线。应为列车分配以下约束：
一天中每列火车必须至少使用一次（没有火车必须整天闲置）
每列火车必须至少分配一条路线（最多两条路线）并且必须覆盖每条路线
列车最终里程一旦分配到某条线路，不得超过24800（即前一天累计里程+分配线路里程<=24800）。这可能是通过查看下面第 3 table 中的 total_km_day_end 列得到最好的理解
如果一天内有两条线路，两条线路的时间不能重叠
另一个我想要但并不重要的约束是这个（假设它是一个软约束）：
- 前一天里程数高的列车应分配到短线，前一天里程数低的列车应分配到长线
我有一个 火车 的数据框，看起来像这样。我可以随机选择一个日期，并查看 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
路由 的数据框如下所示。请注意，超过 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
EDIT/UPDATE (2/8/19):
（注意：下面的代码显示了将 6 列火车分配给 8 条路线的问题的简化版本。我还在代码中包含了约束 5。）
非常感谢 Stradivari 和 Laurent 在这方面的帮助。
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)
列车最终里程，一旦分配到一条路线，不得超过24,800
用每条路线的里程创建一个字典：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)
如果一天内有两条线路，两条线路的时间不能重叠
创建一个函数，如果两条路线重叠returns True
Efficient date range overlap calculation in python?
然后：
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()])
您可以计算将一条路线分配给一列火车的分数。 （比如 mileage_of_day_before + 路线长度）
然后将每个布尔赋值变量的加权和最小化。
运行 上面的代码，我没有得到相同的输出。 （可能是由于平台差异，其中使用了多个 model.Minimize objective 之一...）
尽管如此，上述输出中最小和最大 EOD 公里之间的范围是 23520。
最小化范围不是更好的得分吗objective？
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)
使用上面的方法 objective 找到范围为 23510 的最优解。
（更好的得分 objective 是最小化范围之和 和 每列火车的 EOD km 与平均 EOD 之间的增量总和公里。虽然对于这个数据集，解决方案与简单最小化范围时的解决方案相同。）