In this example, how could we allow routes to be allocated to more than 1 trains assuming we do not care about overlaps?
For instance, a route could be theoretically performed by more than 1 trains but the trains still obey to the rest of the milage and other constraints.
More specifically, If we have trains, I would accept an allocation to cover the daily routes based on 12-h consecutive slots as following: Train 1: 07:00 - 19:00 Train 2: 12:00 - 24:00
What I mean by consecutive hours is that solutions that satisfy a 12-h train shift solution in the form of 07:00-11:00 + 14:00-15:00 + 17:00-24:00 should not be acceptable. I have tried to modify the code but still I cannot get the optimal results.
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()
I solved the problem of consecutive slots using the following function:
def negated_bounded_span(works, start, length):
"""Filters an isolated sub-sequence of variables assined to True.
Extract the span of Boolean variables [start, start + length), negate them,
and if there is variables to the left/right of this span, surround the span by
them in non negated form.
Args:
works: a list of variables to extract the span from.
start: the start to the span.
length: the length of the span.
Returns:
a list of variables which conjunction will be false if the sub-list is
assigned to True, and correctly bounded by variables assigned to False,
or by the start or end of works.
"""
sequence = []
# Left border (start of works, or works[start - 1])
if start > 0:
sequence.append(works[start - 1])
for i in range(length):
sequence.append(works[start + i].Not())
# Right border (end of works or works[start + length])
if start + length < len(works):
sequence.append(works[start + length])
return sequence
More information can be found here