Friday, 19 January 2024

How to extend TSP to MTSP using Pulp

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