在这种情况下,如果我们不关心重叠,我们如何允许将路线分配给1列以上的列车
例如,理论上一条路线可以由1列以上的列车执行,但列车仍然遵守剩余的里程和其他约束
更具体地说,如果我们有火车,我会接受根据12小时连续时段分配的每日路线,如下所示: 列车1:07:00-19:00 列车2:12:00-24:00
我所说的连续小时是指满足07:00-11:00+14:00-15:00+17:00-24:00形式的12小时列车轮班解决方案的解决方案不应被接受。我试图修改代码,但仍然无法获得最佳结果
from itertools import combinations
from ortools.sat.python import cp_model
import numpy as np
def main():
model = cp_model.CpModel()
solver = cp_model.CpSolver()
# data
route_km = {
"0": 30,
"1": 30,
"2": 30,
"3": 30,
"5": 30,
"4": 30,
"6": 30,
"7": 30,
"8": 30,
"9": 30,
"10": 30,
"11": 30,
"12": 30,
"13": 30,
"14": 30,
"15": 30,
"16": 30,
"17": 30,
"18": 30,
"19": 30,
"20": 30,
"21": 30,
"22": 30,
"23": 30,
"24": 30,
"25": 30,
"26": 30,
"27": 30,
"28": 30,
"29": 30,
"30": 30,
"31": 30,
"32": 30,
"33": 30}
train_cum_km = {
'T1': 0,
'T2': 0}
route_times = {
"0", ('07:00', '07:30'),
"1", ('07:30', '08:00'),
"2", ('08:00', '08:30'),
"3", ('08:30', '09:00'),
"5", ('09:30', '10:00'),
"4", ('09:00', '09:30'),
"6", ('10:00', '10:30'),
"7", ('10:30', '11:00'),
"8", ('11:00', '11:30'),
"9", ('11:30', '12:00'),
"10", ('12:00', '12:30'),
"11", ('12:30', '13:00'),
"12", ('13:00', '13:30'),
"13", ('13:30', '14:00'),
"14", ('14:00', '14:30'),
"15", ('14:30', '15:00'),
"16", ('15:00', '15:30'),
"17", ('15:30', '16:00'),
"18", ('16:00', '16:30'),
"19", ('16:30', '17:00'),
"20", ('17:00', '17:30'),
"21", ('17:30', '18:00'),
"22", ('18:00', '18:30'),
"23", ('18:30', '19:00'),
"24", ('19:00', '19:30'),
"25", ('19:30', '20:00'),
"26", ('20:00', '20:30'),
"27", ('20:30', '21:00'),
"28", ('21:00', '21:30'),
"29", ('21:30', '22:00'),
"30", ('22:00', '22:30'),
"31", ('22:30', '23:00'),
"32", ('23:00', '23:30'),
"33", ('23:30', '24:00')}
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 route must be assigned
for r in routes:
model.Add(sum(assignments[(t, r)] for t in trains) > =1)
# constraint 2: each driver must do at least one route and max 24 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) <= 24)
# constraint 3: ensure the end of day cum km is less than 720
# create a new variable which must be in the range (0,720)
day_end_km = {
t: model.NewIntVar(720, 720, 'train_%s_day_end_km' % t)
for t in trains
}
for r1 in routes:
for r2 in routes[routes.index(r1):]:
for t in trains:
if abs(sum(list(route_km.values())[:routes.index(r1)])- sum(list(
route_km.values())[:routes.index(r2)])) > 30:
model.Add(assignments[t, r1] == 0)
for t in trains:
# this will be constrained because day_end_km[t] is in domain [0, 720]
tmp = sum(assignments[t, r]*route_km[r] for r in routes) + train_cum_km[t]
model.Add(day_end_km[t] == tmp)
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'Driver {t} does route {t_routes} '
f'with end of day cumulative work of '
f'{solver.Value(day_end_km[t])}')
if __name__ == '__main__':
main()
我使用以下函数解决了连续插槽的问题:
更多信息请参见here
相关问题 更多 >
编程相关推荐