Google OR tools - train scheduling problem revisited

Question

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()

Answer 1

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