We've studied TSP and now we're tasked to extend it for multiple salespersons. Below code using PULP with my added logic which unfortunately does not work. Can someone help me solve this problem?
# create encoding variables
bin_vars = [ # add a binary variable x_{ij} if i not = j else simply add None
[ LpVariable(f'x_{i}_{j}', cat='Binary') if i != j else None for j in range(n)]
for i in range(n) ]
time_stamps = [LpVariable(f't_{j}', lowBound=0, upBound=n, cat='Continuous') for j in range(1, n)]
# create add the objective function
objective_function = lpSum( [ lpSum([xij*cj if xij != None else 0 for (xij, cj) in zip(brow, crow) ])
for (brow, crow) in zip(bin_vars, cost_matrix)] )
prob += objective_function
# add constraints
for i in range(n):
# Exactly one leaving variable
prob += lpSum([xj for xj in bin_vars[i] if xj != None]) == 1
# Exactly one entering
prob += lpSum([bin_vars[j][i] for j in range(n) if j != i]) == 1
# add timestamp constraints
for i in range(1,n):
for j in range(1, n):
if i == j:
continue
xij = bin_vars[i][j]
ti = time_stamps[i-1]
tj = time_stamps[j -1]
prob += tj >= ti + xij - (1-xij)*(n+1)
# Binary variables to ensure each node is visited by a salesperson
visit_vars = [LpVariable(f'u_{i}', cat='Binary') for i in range(1, n)]
# Salespersons constraints
prob += lpSum([bin_vars[0][j] for j in range(1, n)]) == k
prob += lpSum([bin_vars[i][0] for i in range(1, n)]) == k
for i in range(1, n):
prob += lpSum([bin_vars[i][j] for j in range(n) if j != i]) == visit_vars[i - 1]
prob += lpSum([bin_vars[j][i] for j in range(n) if j != i]) == visit_vars[i - 1]
# Done: solve the problem
status = prob.solve(PULP_CBC_CMD(msg=False))
from How to extend TSP to MTSP using Pulp
No comments:
Post a Comment