我试图解决的问题有点像这里的员工调度问题：
https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py
然而，有一些事情我被困住了，不知道如何将其合并到代码中。下面我就这个问题进行解释。
Problem
我有一个由 47 趟列车组成的车队，我希望每天将它们分配给 49 条路线。列车应受以下约束：
每趟列车在白天必须至少使用一次（任何列车不得全天闲置）
每趟列车必须分配至至少一条路线（最多两条路线）且必须覆盖每条路线
列车分配路线后的最终里程不得超过24800（即前一天累计里程+分配路线里程
列车一天内分配两条线路的，两条线路的时间不得重叠
我想要的另一个约束，但并不珍贵的是（假设这是一个软约束）：
- 前一天里程数高的列车应安排在短途路线上，前一天里程数少的列车应安排在长途路线上
我有一个数据框trains看起来像这样。我可以随机选择一个日期，查看 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
和一个数据框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()
Output:
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
