Traveling salesman variant

Question

I'm trying to build a model using the traveling salesman as a starting point. Instead of being just one traveling salesman I need it to be multiple salesmans that have to reach the same end node and then come back to the origin node. The logic is the same, trying to minimize distance traveled by all salesmans and that between all of them, they cover every node (city). I implemented the model using excel's solver, but it has problems with subtours, so I decided to use gurobi since it had pre made constraint to fix that in the traveling salesman example.

The basic optimization model is this:

Plus the subtour constraints.

The model I'm doing is more complicated because it needs times of arrivals, volume restrictions and others, so if I can't make this work, I surely cannot proceed.

Before typing the code my inputs are:

nodes = ['Node 1', 'Node 2', ... , 'Node9'] 
dist = {(Node1,Node2): 0.03, ..., (Node9, Node8): 0.5} #--> Distances between nodes for different nodes
salesmans = ['salesman1', 'salesman2']

The code I used in gurobi/python is:

import math
import json
from itertools import combinations,product

def subtourelim(model, where):
    if where == GRB.Callback.MIPSOL:
        # make a list of edges selected in the solution
        vals = model.cbGetSolution(model._vars)
        selected = gp.tuplelist((i, j, k) for i, j, k in model._vars.keys()
                         if vals[i, j, k] > 0.5)
        # find the shortest cycle in the selected edge list
        tour = subtour(selected)
        if len(tour) < len(nodes):
            # add subtour elimination constr. for every pair of cities in subtour
            model.cbLazy(gp.quicksum(model._vars[i, j, k] for i, j, k in combinations(tour, 2))
                     <= len(tour)-1)
def subtour(edges):
    unvisited = nodes[:]
    cycle = nodes[:] # Dummy - guaranteed to be replaced
    while unvisited:  # true if list is non-empty
        thiscycle = []
        neighbors = unvisited
        while neighbors:
            current = neighbors[0]
            thiscycle.append(current)
            unvisited.remove(current)
            neighbors = [j for i, j, k in edges.select(current, '*')
                     if j in unvisited]
        if len(thiscycle) <= len(cycle):
            cycle = thiscycle # New shortest subtour
    return cycle

import gurobipy as gp
from gurobipy import GRB

m = gp.Model()

# Variables: is city 'i' adjacent to city 'j' on the tour?
vars = m.addVars(dist.keys(), salesmans, obj=dist, vtype=GRB.BINARY, name='asignacion')


# Constraints: A node can't be visited by itself o leave to visit itself
for i, j, k in vars.keys():
    if i==j:
        m.addConstr(vars[i, j, k] == 0)

# From each node you have to visit one other node
m.addConstrs((vars.sum(i,'*','*') == 1 for i in nodes))
# Each node has to be visited once
m.addConstrs((vars.sum('*',j,'*') == 1 for j in nodes))


# Optimize the model
m._vars = vars
m.Params.lazyConstraints = 1
m.optimize(subtourelim)

When I just try to add those few constraints, the model has errors on the subtour functions that I don't understand

ValueError                                Traceback (most recent call last)
callback.pxi in gurobipy.CallbackClass.callback()

<ipython-input-2-a1cb8952ed8c> in subtourelim(model, where)
     13         if len(tour) < len(nodes):
     14             # add subtour elimination constr. for every pair of cities in subtour
---> 15             model.cbLazy(gp.quicksum(model._vars[i, j, k] for i, j, k in combinations(tour, 2))
     16                          <= len(tour)-1)

gurobi.pxi in gurobipy.quicksum()

<ipython-input-2-a1cb8952ed8c> in <genexpr>(.0)
     13         if len(tour) < len(nodes):
     14             # add subtour elimination constr. for every pair of cities in subtour
---> 15             model.cbLazy(gp.quicksum(model._vars[i, j, k] for i, j, k in combinations(tour, 2))
     16                          <= len(tour)-1)

ValueError: not enough values to unpack (expected 3, got 2)

If anyone can help me I would be very very grateful :)

Answer 1

Thanks to @orlp that hinted me my mistake, I had to fix the "subtour_elim" function like this:

def subtourelim(model, where):
    if where == GRB.Callback.MIPSOL:
        # make a list of edges selected in the solution
        vals = model.cbGetSolution(model._vars)
        selected = gp.tuplelist((i, j, k) for i, j, k in model._vars.keys()
                             if vals[i, j, k] > 0.01)
        # find the shortest cycle in the selected edge list
        tour = subtour(selected)
        if len(tour) < len(nodes):
            # add subtour elimination constr. for every pair of cities in subtour
            for k in salesmans:
                model.cbLazy(gp.quicksum(model._vars[i, j, k] for i, j in combinations(tour, 2)) <= len(tour)-1)