Seemingly long optimisation times

Hi!

I am solving a TSP for pickup and delivery and delivery only. However, for my intended implementation the solving speed is too slow, is there anything I can do to increase the solving speed?

This is my code:

# --- Model
m = gurobi.Model("SPDP")
if agent.model.time != 67:
    m.setParam("OutputFlag", 0)
# m.setParam('TimeLimit', 1)
m.setParam("MIPFocus", 1)
m.setParam("Heuristics", 0.5)

# --- Decision Variables

# xij: 1 if node i and j are connected , i!=n+n+1, j!=0
X = [
    [
        m.addVar(vtype=gurobi.GRB.BINARY, name="X_" + str(i) + "_" + str(j))
        for j in range(1, n + n + k + 2)
        if j != i and (i, j) != (0, 2 * n + k + 1)
    ]
    for i in range(n + n + k + 1)
]
X_names = [
    [(i, j) for j in range(1, n + n + k + 2) if j != i and (i, j) != (0, 2 * n + k + 1)]
    for i in range(n + n + k + 1)
]
# Qi: load on the truck after each node
Q = [
    m.addVar(vtype=gurobi.GRB.CONTINUOUS, name="Q_" + str(i))
    for i in range(n + n + k + 2)
]
# Bi: beginning time of service at node i
B = [
    m.addVar(vtype=gurobi.GRB.INTEGER, name="B_" + str(i)) for i in range(n + n + k + 2)
]

m.update()

# --- Objective Function
if bidding_rule == "makespan":
    m.setObjective((B[-1] - B[0]), gurobi.GRB.MINIMIZE)
elif bidding_rule == "travel_time":
    m.setObjective(
        sum(
            X[i][j] * information_arcs[X_names[i][j]]["time"]
            for i in range(n + n + k + 1)
            for j in range(n + n + k)
            if i != j
        ),
        gurobi.GRB.MINIMIZE,
    )
elif bidding_rule == "cost":
    m.setObjective(
        sum(
            X[i][j] * information_arcs[X_names[i][j]]["cost"]
            for i in range(n + n + k + 1)
            for j in range(n + n + k)
            if i != j
        ),
        gurobi.GRB.MINIMIZE,
    )


# --- Constraints

# Constraint (1): for each destination in the vertices (except 0), there must be an arc going towards it
for j in V:
    if j == 0:
        continue
    m.addConstr(
        sum(
            X[i][X_names[i].index((i, j))]
            for i in range(2 * n + k + 1)
            if i != j and (i, j) != (0, 2 * n + k + 1)
        )
        == 1,
        name="Visit every node",
    )

# Constraint (2): for each destination in the vertices (except n + n + 1), there must be an arc going from it
for i in V:
    if i == n + n + k + 1:
        continue
    m.addConstr(sum(X[i][j] for j in range(2 * n + k)) == 1, name="Visit every node")

# Constraint (3): updates load after each node visit
for arc in arcs:
    m.addConstr(
        Q[arc[1]]
        >= (Q[arc[0]] + information_vertices[arc[1]]["mass"])
        * X[arc[0]][X_names[arc[0]].index((arc[0], arc[1]))],
        name="mass update",
    )

# Constraint (4): ensures that vehicle capacity is not exceeded
for node in V:
    m.addConstr(max(0, information_vertices[node]["mass"]) <= Q[node], name="capacity")
    m.addConstr(
        Q[node]
        <= min(
            agent.mass_capacity,
            agent.mass_capacity - information_vertices[node]["mass"],
        ),
        name="capacity",
    )

# Constraint (5): visit pickup vertex before delivery vertex
for node in P:
    m.addConstr(B[node] <= B[node + n], name="precedence")

# Constraint (6): Make sure that next visiting time follows time rules
for arc in A:
    if information_arcs[arc]["distance"] == 0:
        # Must be at least 1 to prevent subtours
        TAT = 1
    else:
        TAT = agent.TAT / 60

    m.addConstr(
        B[arc[1]]
        >= (B[arc[0]] + information_arcs[arc]["time"] + TAT)
        * X[arc[0]][X_names[arc[0]].index((arc[0], arc[1]))],
        name="time update",
    )

# Constraint (8):
for node in V:
    m.addConstr(B[node] <= information_vertices[node]["deadline"], name="deadlines")

# Constraint (9): Vehicle should be empty after performing all requests
m.addConstr(Q[n + n + k + 1] == 0, name="empty at the end")

# Constraint (10): Bounds for B and Q
for node in V:
    m.addConstr(B[node] <= 1440, name="bounds")
    m.addConstr(Q[node] <= 3000, name="bounds")

m.update()

start = time.time()
m.optimize()
end = time.time()
opt_time = end - start
print(opt_time)

And this is a log file for an instance that is taking particularly long.

Set parameter MIPFocus to value 1
Set parameter Heuristics to value 0.5
Gurobi Optimizer version 10.0.3 build v10.0.3rc0 (win64)
CPU model: Intel(R) Core(TM) i7-6700HQ CPU @ 2.60GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 110 rows, 212 columns and 452 nonzeros
Model fingerprint: 0x2b28c196
Model has 364 quadratic constraints
Variable types: 15 continuous, 197 integer (182 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  QMatrix range    [1e+00, 1e+00]
  QLMatrix range   [1e+00, 3e+01]
  Objective range  [1e+00, 4e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+00, 3e+03]
Presolve removed 17 rows and 10 columns
Presolve time: 0.00s
Presolved: 667 rows, 489 columns, 2335 nonzeros
Variable types: 167 continuous, 322 integer (174 binary)
Root relaxation: objective 0.000000e+00, 63 iterations, 0.00 seconds (0.00 work units)
    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time
     0     0    0.00000    0   47          -    0.00000      -     -    0s
     0     0    0.00000    0   63          -    0.00000      -     -    0s
     0     0    0.00000    0   75          -    0.00000      -     -    0s
     0     0    0.00000    0   23          -    0.00000      -     -    0s
H    0     0                       9.6000000    0.00000   100%     -    0s
     0     0    0.00000    0   31    9.60000    0.00000   100%     -    0s
     0     0    0.00000    0   42    9.60000    0.00000   100%     -    0s
     0     0    0.00000    0   53    9.60000    0.00000   100%     -    0s
H    0     0                       4.4000000    0.00000   100%     -    0s
     0     0    0.00000    0   56    4.40000    0.00000   100%     -    0s
     0     0    0.00000    0   58    4.40000    0.00000   100%     -    0s
     0     0    0.00000    0   65    4.40000    0.00000   100%     -    0s
     0     2    0.00000    0   47    4.40000    0.00000   100%     -    0s
* 2566  1026              34       2.4000000    0.00000   100%   9.5    2s
Cutting planes:
  Learned: 14
  Gomory: 1
  Implied bound: 12
  Clique: 3
  MIR: 23
  StrongCG: 5
  Flow cover: 49
  Inf proof: 1
  Mod-K: 1
  RLT: 3
  Relax-and-lift: 16
Explored 3405 nodes (33383 simplex iterations) in 4.02 seconds (2.22 work units)
Thread count was 8 (of 8 available processors)
Solution count 3: 2.4 4.4 9.6 
Optimal solution found (tolerance 1.00e-04)
Best objective 2.400000000000e+00, best bound 2.400000000000e+00, gap 0.0000%

Could you help me out? Thank you in advance!

Kind regards,

Nikki Kamphuis