In [ ]:

    

from ortools.sat.python import cp_model


def SolveRosteringWithTravel():
  model = cp_model.CpModel()

  # [duration, start, end, location]
  jobs = [[3, 0, 6, 1], [5, 0, 6, 0], [1, 3, 7, 1], [1, 3, 5, 0], [3, 0, 3, 0],
          [3, 0, 8, 0]]

  max_length = 20

  num_machines = 3
  all_machines = range(num_machines)

  horizon = 20
  travel_time = 1
  num_jobs = len(jobs)
  all_jobs = range(num_jobs)

  intervals = []
  optional_intervals = []
  performed = []
  starts = []
  ends = []
  travels = []

  for m in all_machines:
    optional_intervals.append([])

  for i in all_jobs:
    # Create main interval.
    start = model.NewIntVar(jobs[i][1], horizon, 'start_%i' % i)
    duration = jobs[i][0]
    end = model.NewIntVar(0, jobs[i][2], 'end_%i' % i)
    interval = model.NewIntervalVar(start, duration, end, 'interval_%i' % i)
    starts.append(start)
    intervals.append(interval)
    ends.append(end)

    job_performed = []
    job_travels = []
    for m in all_machines:
      performed_on_m = model.NewBoolVar('perform_%i_on_m%i' % (i, m))
      job_performed.append(performed_on_m)

      # Create an optional copy of interval to be executed on a machine
      location0 = model.NewIntVar(jobs[i][3], jobs[i][3],
                                  'location_%i_on_m%i' % (i, m))
      start0 = model.NewIntVar(jobs[i][1], horizon, 'start_%i_on_m%i' % (i, m))
      end0 = model.NewIntVar(0, jobs[i][2], 'end_%i_on_m%i' % (i, m))
      interval0 = model.NewOptionalIntervalVar(
          start0, duration, end0, performed_on_m, 'interval_%i_on_m%i' % (i, m))
      optional_intervals[m].append(interval0)

      # We only propagate the constraint if the tasks is performed on the machine.
      model.Add(start0 == start).OnlyEnforceIf(performed_on_m)
      # Adding travel constraint
      travel = model.NewBoolVar('is_travel_%i_on_m%i' % (i, m))
      startT = model.NewIntVar(0, horizon, 'start_%i_on_m%i' % (i, m))
      endT = model.NewIntVar(0, horizon, 'end_%i_on_m%i' % (i, m))
      intervalT = model.NewOptionalIntervalVar(
          startT, travel_time, endT, travel,
          'travel_interval_%i_on_m%i' % (i, m))
      optional_intervals[m].append(intervalT)
      job_travels.append(travel)

      model.Add(end0 == startT).OnlyEnforceIf(travel)

    performed.append(job_performed)
    travels.append(job_travels)

    model.Add(sum(job_performed) == 1)

  for m in all_machines:
    if m == 1:
      for i in all_jobs:
        if i == 2:
          for c in all_jobs:
            if (i != c) and (jobs[i][3] != jobs[c][3]):
              is_job_earlier = model.NewBoolVar('is_j%i_earlier_j%i' % (i, c))
              model.Add(starts[i] < starts[c]).OnlyEnforceIf(is_job_earlier)
              model.Add(starts[i] >= starts[c]).OnlyEnforceIf(
                  is_job_earlier.Not())

  # Max Length constraint (modeled as a cumulative)
  # model.AddCumulative(intervals, demands, max_length)

  # Choose which machine to perform the jobs on.
  for m in all_machines:
    model.AddNoOverlap(optional_intervals[m])

  # Objective variable.
  total_cost = model.NewIntVar(0, 1000, 'cost')
  model.Add(total_cost == sum(
      performed[j][m] * (10 * (m + 1)) for j in all_jobs for m in all_machines))
  model.Minimize(total_cost)

  # Solve model.
  solver = cp_model.CpSolver()
  result = solver.Solve(model)

  print()
  print(result)
  print('Statistics')
  print('  - conflicts       : %i' % solver.NumConflicts())
  print('  - branches        : %i' % solver.NumBranches())
  print('  - wall time       : %f ms' % solver.WallTime())


SolveRosteringWithTravel()