# TSP problem: traveller does not visit all nodes - Google OR-tools

Context:

I am dealing with a kind of scheduling problem, in which I have a set of tasks and machines. All tasks must be assigned to machines (not necessary all of them). In addition to that, I must calculate the cost of transferring the product between two machines.

For starting, I based my problem in the nurses assignment: https://developers.google.com/optimization/scheduling/employee_scheduling

However, I do not know how to obtain the cost of changing machine, it means, take the material from one machine to another.

To consider the task assignment with the process sequence I established the binary variable X[w, o, j], where w is the machine, o is the operation and j is the position on the process plan.

For calculating the cost of changing machine I also established another binary variable T[w1, w2, j-1, j], that states if there is a material transition from one machine to another in two followed positions on the process plan.

Some code:

# Create the decision variabl
X = {}
for w in range(num_machines):
for p in range(num_operations):
for j in range(num_operations):
X[w, p, j] = model.NewBoolVar('X_{}_{}_{}'.format(w + 1, p + 1, j + 1))
T = {}
for w1 in range(num_machines):
for w2 in range(num_machines):
for j in range(1, num_operations):
#if w1 != w2:
# T[w1, w2] = model.NewBoolVar(f'T_{w1}_{w2}') # using f-string notation
T[w1, w2, j-1, j] = model.NewBoolVar('T_{}_{}_{}_{}'.format(w1 + 1, w2 + 1, j, j + 1))

B = model.NewBoolVar('B')     # declaring an intermediate variable


I've tried to implement some constraints:

1) The number of transitions must be equal the number of operations -1
number_transitions = sum(
T[(w1, w2, j-1, j)]
for w1 in range(num_machines)
for w2 in range(num_machines)
for j in range(1, num_operations)

)


So to establish the relation between X and T I tried 2 different ways, but any of them worked.

1st way:

# Implementing B == [X1 + X2]
for w1 in all_machines:
for w2 in all_machines:
for p1 in all_operations:
for p2 in all_operations:
for j in range(1, num_operations):
model.Add(X[w1, p1, j-1] + X[w2, p2, j] == 2).OnlyEnforceIf(B)
model.Add(X[w1, p1, j-1] + X[w2, p2, j] != 2).OnlyEnforceIf(B.Not())

# Reinforcing the value of T
for w1 in all_machines:
for w2 in all_machines:
for j in range(1, num_operations):
model.Add(T[w1, w2, j-1, j] == 1).OnlyEnforceIf(B)
model.Add(T[w1, w2, j-1, j] == 0).OnlyEnforceIf(B.Not())


2nd way:

 for p in all_operations:
for w1 in all_machines:
for w2 in all_machines:
for j in range(1, num_operations):
model.Add((X[w1, p, j-1] + X[w2, p, j]) == T[w1, w2, j-1, j] + 1)


In both of ways, when I run the code, it returns as result just solutions that do not do transitions between two machines, meaning that these constraints are not being read correctly.

I would like to know if there is a better way to solve this problem by establishing the relation between variables X and T.

I guess that it could be possible to solve like a TSP, but in my case, not all nodes are visited, but just nodes(machines) required to do a task.

Someone know how could I solve this problem? Or maybe do you have an example to send me?