Google OR tools - train scheduling problem
Off the top of my head, not sure if it is the best way:
assignments = {
(route, train): model.NewBoolVar('')
for route in routes
for train in all_trains
}
Every train must be assigned to at least one route (and max two routes)
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)
The trains final mileage, once assigned to a route, must not exceed 24,800
Create a dictionary with the mileage of each route: route_km = {'R11': 700, 'R16': 600}
and the cumulative mileage of each train 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)
Where a train is assigned to two routes in a day, the times of these routes must not overlap
Create a function that returns True
if two routes overlap
Efficient date range overlap calculation in python?
And then:
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()])
You can compute a score of assigning one route to one train. (like the mileage_of_day_before + route length)
Then you minimize the weighted sum of each Boolean assignment variables.