我要解决的问题有点像员工在这里安排:
https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py
但是，有些事情我仍然坚持，不知道如何将其合并到代码中。我将在下面解释问题。
问题
我有47列火车的车队，我想每天分配给49条路线。应该为火车分配以下约束:
我想拥有一个进一步的约束，但这并不是很珍贵(这是一个软约束):
我有一个火车的数据框，看起来像这样。我可以随机选择一个日期，并查看47列火车中每列火车直到前一天(即2018年9月18日)结束时的累积里程:
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公里的路线被定义为长路线，低于此路线则为短路线。在这49条 route ，只有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。)
非常感谢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)
如果一天中将火车分配给两条路线，则两条路线的时间不得重叠
创建一个函数，如果两个路由重叠，则返回
TrueEfficient 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()])
关于python - Google OR工具-火车调度问题，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/57062032/