I am using Google OR-Tools to solve a problem where technicians work on tasks to fix machines. The machines are all initially broken and the objective is to fix the machines and minimize the total lost output (i.e. the cumulative downtime of the machines). There is a travel time between tasks AND a vehicle must be available to transport the technicians between tasks. There are fewer vehicles than technicians so there may be the situation where a technician must wait for a vehicle to become free before travelling to the next task. For example: three technicians, eight tasks, two vehicles.

A technician can work on any task and the task durations are known in advance.

I have made a code below (based on the job shop with travel time) which routes the technicians around the tasks with a fixed travel time of 2 units.

However, I am at a loss how to model the available transport constraint. (Currently, technicians can move immediately they are finished a task). Could anyone get me started on how to add this feature?

Thoughts I have had are:

• Is this actually a vehicle routing problem (and not a cp_sat) and the tasks a kind-of time window? Or is it part vehicle routing and part scheduling - if so, what solver would I use?
• Do I need a trans_for_tech variable which =1 when a vehicle is in use plus a constraint that trans_for_tech<=1 to avoid a vehicle being double-booked. Then this variable would =1 when an arc of the circuit was in use (i.e. it's boolean literal was true).
• Do the vehicles themselves actually do "tasks" (i.e. transporting) which need to be modelled by start/end/no-overlap conditions with a NewOptionalInterval to enable them when an arc of the circuit was in use. Would the start/end of these actually be the compliment of the task intervals? Then, conceptually, there would be two sets of tasks (technicians working and vehicles transporting) and these would be scheduled to minimize lost time.
• Since the vehicles transporting the technicians visit different task locations then these vehicles too have a travel time but my thought was to ignore that for now and just model the vehicles as a resource which was available immediately anywhere among the tasks but was constrained so it couldn't be in two places at once (i.e. the variable had a sum<=1 or a AddBoolOr or something similar).

Below is my code for the case where technicians move when they are ready (equivalent to each having their own transport).

from ortools.sat.python import cp_model
import pandas as pd
import time

# number technicians
n_techs = 2

#different scenarios for testing {machine:duration to fix}

#this set of tasks runs very quickly
durations={0:3, 1:1, 2:1, 3:2, 4:1}

#this scenario of tasks takes a couple minutes to finish
# durations={0:3, 1:1, 2:1, 3:2, 4:1, 5:2, 6:3, 7:4, 8:1}

#travel times between tasks (constant for now)
travel_time=2

model = cp_model.CpModel()
n_tasks=len(durations)
all_techs=range(n_techs)
all_tasks=range(n_tasks)

#horizon is sum of all durations and max travel time * number of tasks (conservative)
horizon=sum(durations.values())+n_tasks*travel_time


#boolean variable for each combination of technician and task.  if True then technician works on this task
tech_for_task={}
for tech in all_techs:
    for task in all_tasks:
        tech_for_task[(tech,task)]=model.NewBoolVar('tech_{0}_on_task_{1}'.format(tech,task))


#condition to that only one tech works on each task
for task in all_tasks:
    model.Add(sum([tech_for_task[(tech,task)] for tech in all_techs])==1)


#start,end and interval for each task
starts = {}
ends = {}
intervals = {}
for tech in all_techs:
    for task in all_tasks:
        
        starts[(tech,task)] = model.NewIntVar(0, horizon, 'tech_{0}_task_{1}_start'.format(tech,task))
        ends[(tech,task)] = model.NewIntVar(0, horizon, 'tech_{0}_task_{1}_end'.format(tech,task))
        
        #this optional interval is only live when a technician is working on a task (tech_for_task=True)
        intervals[(tech,task)]=model.NewOptionalIntervalVar(starts[(tech,task)], 
                                               durations[task], 
                                               ends[(tech,task)], 
                                               tech_for_task[(tech,task)], 
                                               'tech_{0}_task_{1}_opt_interval'.format(tech,task))


#the tasks for each technician should not overlap
for tech in all_techs:
    model.AddNoOverlap([intervals[(tech,task)] for task in all_tasks])
    

# Transition times and transition costs using a circuit constraint
for tech in all_techs:
    arcs = []
    
    for i in all_tasks:
        
        tti=(tech,i) 
        
        # Initial arc from the dummy node (0) to a task.
        start_lit = model.NewBoolVar('')
        arcs.append([0, i + 1, start_lit])
        
        # If this task is the first, set start to 0.
        model.Add(starts[tti] == 0).OnlyEnforceIf(start_lit)
        
        # Final arc from an arc to the dummy node.
        arcs.append([i + 1, 0, model.NewBoolVar('')])
        
        # Self arc if the task is not performed.
        arcs.append([i + 1, i + 1, tech_for_task[tti].Not()])        
      
        for j in all_tasks:
          
            if i==j:
                continue
            
            else:
        
                ttj=(tech,j)
                
                #the indexing of the arcs[i+1,j+1,lit] is one more than the nodes due to the dummy node (0)
                lit = model.NewBoolVar('{0} follows {1}'.format(j,i))
                arcs.append([i + 1, j + 1, lit])
                model.AddImplication(lit, tech_for_task[tti]) # if lit=True --> tech_for_task[tti]=True
                model.AddImplication(lit, tech_for_task[ttj]) # if lit=True --> tech_for_task[ttj]=True
                
                # add reified transition to link the literals with the times of the tasks
                model.Add(starts[ttj] == ends[tti] + travel_time).OnlyEnforceIf(lit)
        
    if arcs:
        model.AddCircuit(arcs)

        
# minimize sum of end time points of tasks.  ends=0 when tech_for_task=False so not cause problem
obj_fun=[]
for tech in all_techs:
    for task in all_tasks:
        obj_fun.append(ends[(tech,task)])
model.Minimize(sum(obj_fun))


start = time.time()
solver = cp_model.CpSolver()
status = solver.Solve(model)
end = time.time()


#if problem solved then put in dataframe to show results easily
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    
    print('solved ok')
    
    c_starts={}
    c_ends={}
    c_tech_for_task={}
    c_tech={}
    c_task={}
    for tech in all_techs:
        for task in all_tasks:
            tt=(tech,task)
            c_starts[tt]=solver.Value(starts[tt])
            c_ends[tt]=solver.Value(ends[tt])
            c_tech_for_task[tt]=solver.Value(tech_for_task[tt])
            c_tech[tt]=tech
            c_task[tt]=task

    df=pd.DataFrame()
    df['task']=c_task.values()
    df['tech']=c_tech.values()
    df['start']=c_starts.values()
    df['end']=c_ends.values()
    df['tech_for_task']=c_tech_for_task.values()

    #sort chronologically
    df=df.sort_values(by='start').reset_index(drop=True)
    df['duration']=df['task'].map(durations)
    
    #get only the tasks which were done by a tech (tech_for_task=0 are not meaningful)
    df=df[df.tech_for_task==1]
    
    for tech in all_techs:
        df1=df[df.tech==tech]
        print()
        print('Tasks for tech {0}'.format(tech))
        print(df1)
    

elif status==cp_model.MODEL_INVALID:
    print('Model invalid :-(')

print('Total time is:',end - start)