# Team Orienteering Problem with Time Windows infeasible using CP-SAT solver in Google OR-Tool

I am developing a TOPTW where there are a set of N nodes. Each node i is associated with a visit time, which is also the score Si. The starting point and the end point of each tour is fixed, which is node 0. Travel time matrix is given. Not all nodes can be visited because of time budget max_time.

I worked on the following but it gave me infeasible after adjusting various parameters such as num_paths. I wonder if any of my codes go wrong?

num_vertices = 15 # num of visits
num_paths = 1 # num of walk paths
startshift = 420
endshift = 840
max_time = endshift - startshift # max shift time
scores = [0, 60, 30, 45, 45, 45, 30, 45, 45, 60, 60, 30, 30, 45, 45] # visit duration
travel_times = [
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 5, 12, 17, 25, 13, 37, 10, 12, 13, 13, 12, 27, 19, 26],
[0, 12, 5, 8, 21, 7, 32, 12, 7, 19, 7, 5, 21, 12, 23],
[0, 17, 9, 5, 17, 8, 28, 16, 11, 25, 8, 9, 18, 7, 20],
[0, 25, 19, 17, 5, 17, 18, 24, 24, 34, 17, 19, 6, 13, 8],
[0, 14, 5, 8, 17, 5, 28, 12, 11, 22, 5, 5, 18, 9, 20],
[0, 37, 30, 28, 18, 28, 5, 35, 33, 43, 28, 30, 14, 23, 20],
[0, 10, 11, 16, 23, 12, 35, 5, 14, 18, 12, 11, 25, 17, 24],
[0, 12, 7, 12, 25, 11, 33, 14, 5, 18, 11, 7, 25, 15, 27],
[0, 13, 19, 25, 34, 22, 43, 18, 18, 5, 22, 19, 35, 27, 35],
[0, 14, 5, 8, 17, 5, 28, 12, 11, 22, 5, 5, 18, 9, 20],
[0, 12, 5, 8, 21, 7, 32, 12, 7, 19, 7, 5, 21, 12, 23],
[0, 27, 20, 18, 6, 18, 14, 25, 25, 35, 18, 20, 5, 13, 8],
[0, 19, 11, 7, 13, 9, 23, 18, 15, 28, 9, 11, 13, 5, 16],
[0, 27, 22, 20, 8, 20, 20, 25, 27, 35, 20, 22, 8, 16, 5]
]
time_windows = [(420, 840), (405, 435), (405, 435), (465, 495), (480, 510), (495, 525), (495, 525), (525, 555), (525, 555), (555, 585), (555, 585), (555, 585), (585, 615), (585, 615), (585, 615)]

# Model
model = cp_model.CpModel()

# Variables
x = {}
for i in range(num_vertices):
for j in range(num_vertices):
for p in range(num_paths):
x[i,j,p] = model.NewBoolVar(f'x_{i}_{j}_{p}')

y = {}
for i in range(num_vertices):
for p in range(num_paths):
y[i,p] = model.NewBoolVar(f'y_{i}_{p}')

start_time = {}
for i in range(num_vertices):
for p in range(num_paths):
start_time[i,p] = model.NewIntVar(startshift, endshift, f'start_{i}_{p}')

wait_time = {}
for i in range(num_vertices): # wait after node i
for p in range(num_paths):
wait_time[i,p] = model.NewIntVar(0, max_time, f'wait_{i}_{p}')

# Constraints
# Start and end vertex (C1)
for p in range(num_paths):
model.Add(sum(x[0,j,p] for j in range(1, num_vertices)) == 1) # start from 0
model.Add(sum(x[i,0,p] for i in range(1, num_vertices)) == 1) # end at 0

# Connectivity of paths (C2)
for p in range(num_paths):
for k in range(num_vertices):
model.Add(sum(x[i,k,p] for i in range(num_vertices) if i != k) == y[k,p])
model.Add(sum(x[k,j,p] for j in range(num_vertices) if k != j) == y[k,p])

# Time between visits (C3) to account for service, travel and wait time
for i in range(num_vertices):
for j in range(num_vertices):
if i != j:  # exclude loops
for p in range(num_paths):
model.Add(start_time[j,p] == start_time[i,p] + int(travel_times[i][j]) + scores[i] + wait_time[i,p]).OnlyEnforceIf(x[i,j,p])

# Each vertex visited at most once (C4)
for i in range(1, num_vertices):
model.Add(sum(y[i,p] for p in range(num_paths)) <= 1)

# Restrict path duration (C5)
for p in range(num_paths):
model.Add(sum(int(travel_times[i][j])*x[i,j,p] for i in range(num_vertices) for j in range(num_vertices)) +
sum(scores[i]*y[i,p] for i in range(num_vertices)) +
sum(wait_time[i,p] for i in range(num_vertices)) <= max_time)

# Restrict the start of the service within time windows (C6 C7)
for i in range(num_vertices):
for p in range(num_paths):
lb, ub = time_windows[i]

# Objective to maximise the total collected score
objective = []
for i in range(1, num_vertices):
for p in range(num_paths):
objective.append(scores[i] * y[i,p])
model.Maximize(sum(objective))

# Solution
solver = cp_model.CpSolver()
status = solver.Solve(model)
$$$$

• You should use the circuit constraint. Commented Jul 17, 2023 at 14:05
• we cannot run your code. Please submit a minimal reproducible problem. Commented Jul 17, 2023 at 14:08
• i have updated the code with parameters. thanks Commented Jul 17, 2023 at 14:33
• startshift, endshift not defined Commented Jul 17, 2023 at 15:06
• sorry. startshift = 420, endshift = 840 Commented Jul 17, 2023 at 15:21

I enabled logging:

solver.parameters.log_search_progress = True


Unfortunately, nothing jumps out. The model is proven infeasible during presolve.

You should look at the prized collecting vrp problem written with CP-SAT. I believe this is the same problem.

• model.Add(start_time[i,p] >= lb).OnlyEnforceIf(y[i,p]) I think this and the next line should be replaced with AddLinearConstraint` (think that's the intent). Doing that, the model is still infeasible though but not in presolve. Commented Jul 17, 2023 at 18:17