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

There is no constraint that forbids two trains to be assigned to one route. But, the minimize function prevents to do it in most cases. What do you want to do exactly? — TUI lover, Mar 30 '21 at 10:07
I think that without the first constraint we will not force all the slots to be covered — azal, Mar 30 '21 at 10:37
So if I understand correctly your question, you want trains to work during at least 12h consecutively, or not be assigned at all? — TUI lover, Mar 30 '21 at 10:46
Only the first one: work during at least 12h consecutively and all of them to be assigned so as the full range of hours is covered (do not mind overlaps of course). — azal, Mar 30 '21 at 10:54

score 1 · Accepted Answer · answered Mar 31 '21 at 09:40

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

Google OR tools - train scheduling problem revisited

1 Answers1