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
# model.Add(y[0,p] == 1)
# 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]
model.Add(start_time[i,p] >= lb).OnlyEnforceIf(y[i,p])
model.Add(start_time[i,p] <= ub)
# 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)
```
