• Gurobi Staff

Hi Roos,

Your linearization of the max and min terms looks ok. I guess "qi" can get negative, otherwise the max and min terms would not make sense.

What exactly does not work? Could you show the relevant Gurobi log output or error messages?

Best regards,
Mario

Yes qi can be negative because by delivery the demand is negative and for pick up it is positive

Can share my full code with you

n= 3
n2 = 3

P = [i for i in range (1, n+1)]
D = [i for i in range (n+1,n+n2+1)]
Ck = {1:6, 2:6}
K = [i for i in range (1, len(Ck)+1)]
N = P + D
qi = {0:0, 1:6, 2:3, 3:6, 4:-6, 5:-3, 6:-6, 7:0}
di = {0:0, 1:6, 2:3, 3:6, 4:6, 5:3, 6:6, 7:0}

req ={1:(1,4), 2:(2,5), 3:(3,6)}

L= 1+n + n2

cijk = {(0,0,1):0, (0,1,1):2.236, (0,2,1):4.123, (0,3,1):2.236, (0,4,1):5.830, (0,5,1):2.236, (0,6,1):3.605, (0,7,1):0,
(1,0,1):2.236, (1,1,1):0, (1,2,1):5.099, (1,3,1):3.162, (1,4,1):7.280, (1,5,1):3.162, (1,6,1):4, (1,7,1):2.236,
(2,0,1):4.123, (2,1,1):5.099, (2,2,1):0, (2,3,1):6.325, (2,4,1):9.219, (2,5,1):2,(2,6,1):1.414, (2,7,1):4.123,
(3,0,1):2.236, (3,1,1):3.162, (3,2,1):6.325, (3,3,1):0, (3,4,1):4.123, (3,5,1):4.472,(3,6,1):5.830, (3,7,1):2.236,
(4,0,1):5.830, (4,1,1):7.280, (4,2,1):9.219, (4,3,1):4.123, (4,4,1):0, (4,5,1):7.810,(4,6,1):9.219, (4,7,1):5.830,
(5,0,1):2.236, (5,1,1):3.162, (5,2,1):2, (5,3,1):4.472, (5,4,1):7.810, (5,5,1):0, (5,6,1):1.414, (5,7,1):2.236,
(6,0,1):3.605, (6,1,1):4, (6,2,1):1.414, (6,3,1):5.830, (6,4,1):9.219, (6,5,1):1.414,(6,6,1):0, (6,7,1):3.605,
(7,0,1):0, (7,1,1):2.236, (7,2,1):4.123, (7,3,1):2.236, (7,4,1):5.830, (7,5,1):2.236, (7,6,1):3.605, (7,7,1):0,
(0,0,2):0, (0,1,2):2.236, (0,2,2):4.123, (0,3,2):2.236, (0,4,2):5.830, (0,5,2):2.236, (0,6,2):3.605, (0,7,2):0,
(1,0,2):2.236, (1,1,2):0, (1,2,2):5.099, (1,3,2):3.162, (1,4,2):7.280, (1,5,2):3.162, (1,6,2):4, (1,7,2):2.236,
(2,0,2):4.123, (2,1,2):5.099, (2,2,2):0, (2,3,2):6.325, (2,4,2):9.219, (2,5,2):2,(2,6,2):1.414, (2,7,2):4.123,
(3,0,2):2.236, (3,1,2):3.162, (3,2,2):6.325, (3,3,2):0, (3,4,2):4.123, (3,5,2):4.472,(3,6,2):5.830, (3,7,2):2.236,
(4,0,2):5.830, (4,1,2):7.280, (4,2,2):9.219, (4,3,2):4.123, (4,4,2):0, (4,5,2):7.810,(4,6,2):9.219, (4,7,2):5.830,
(5,0,2):2.236, (5,1,2):3.162, (5,2,2):2, (5,3,2):4.472, (5,4,2):7.810, (5,5,2):0, (5,6,2):1.414, (5,7,2):2.236,
(6,0,2):3.605, (6,1,2):4, (6,2,2):1.414, (6,3,2):5.830, (6,4,2):9.219, (6,5,2):1.414,(6,6,2):0, (6,7,2):3.605,
(7,0,2):0, (7,1,2):2.236, (7,2,2):4.123, (7,3,2):2.236, (7,4,2):5.830, (7,5,2):2.236, (7,6,2):3.605, (7,7,2):0}

tijk ={(0,0,1):0, (0,1,1):2.236, (0,2,1):4.123, (0,3,1):2.236, (0,4,1):5.830, (0,5,1):2.236, (0,6,1):3.605, (0,7,1):0,
(1,0,1):2.236, (1,1,1):0, (1,2,1):5.099, (1,3,1):3.162, (1,4,1):7.280, (1,5,1):3.162, (1,6,1):4, (1,7,1):2.236,
(2,0,1):4.123, (2,1,1):5.099, (2,2,1):0, (2,3,1):6.325, (2,4,1):9.219, (2,5,1):2,(2,6,1):1.414, (2,7,1):4.123,
(3,0,1):2.236, (3,1,1):3.162, (3,2,1):6.325, (3,3,1):0, (3,4,1):4.123, (3,5,1):4.472,(3,6,1):5.830, (3,7,1):2.236,
(4,0,1):5.830, (4,1,1):7.280, (4,2,1):9.219, (4,3,1):4.123, (4,4,1):0, (4,5,1):7.810,(4,6,1):9.219, (4,7,1):5.830,
(5,0,1):2.236, (5,1,1):3.162, (5,2,1):2, (5,3,1):4.472, (5,4,1):7.810, (5,5,1):0, (5,6,1):1.414, (5,7,1):2.236,
(6,0,1):3.605, (6,1,1):4, (6,2,1):1.414, (6,3,1):5.830, (6,4,1):9.219, (6,5,1):1.414,(6,6,1):0, (6,7,1):3.605,
(7,0,1):0, (7,1,1):2.236, (7,2,1):4.123, (7,3,1):2.236, (7,4,1):5.830, (7,5,1):2.236, (7,6,1):3.605, (7,7,1):0,
(0,0,2):0, (0,1,2):2.236, (0,2,2):4.123, (0,3,2):2.236, (0,4,2):5.830, (0,5,2):2.236, (0,6,2):3.605, (0,7,2):0,
(1,0,2):2.236, (1,1,2):0, (1,2,2):5.099, (1,3,2):3.162, (1,4,2):7.280, (1,5,2):3.162, (1,6,2):4, (1,7,2):2.236,
(2,0,2):4.123, (2,1,2):5.099, (2,2,2):0, (2,3,2):6.325, (2,4,2):9.219, (2,5,2):2,(2,6,2):1.414, (2,7,2):4.123,
(3,0,2):2.236, (3,1,2):3.162, (3,2,2):6.325, (3,3,2):0, (3,4,2):4.123, (3,5,2):4.472,(3,6,2):5.830, (3,7,2):2.236,
(4,0,2):5.830, (4,1,2):7.280, (4,2,2):9.219, (4,3,2):4.123, (4,4,2):0, (4,5,2):7.810,(4,6,2):9.219, (4,7,2):5.830,
(5,0,2):2.236, (5,1,2):3.162, (5,2,2):2, (5,3,2):4.472, (5,4,2):7.810, (5,5,2):0, (5,6,2):1.414, (5,7,2):2.236,
(6,0,2):3.605, (6,1,2):4, (6,2,2):1.414, (6,3,2):5.830, (6,4,2):9.219, (6,5,2):1.414,(6,6,2):0, (6,7,2):3.605,
(7,0,2):0, (7,1,2):2.236, (7,2,2):4.123, (7,3,2):2.236, (7,4,2):5.830, (7,5,2):2.236, (7,6,2):3.605, (7,7,2):0}

V = [0] + P + D +[n+n2+1]
A = [(i,j) for i in V for j in V]

m = grb.Model("PDPTW")

x = m.addVars(A,K, vtype=grb.GRB.BINARY, name="xijk") #BINARY variable, shows if Arc is used =1 or not =0
Q = m.addVars(V,K, vtype=grb.GRB.CONTINUOUS, name="Qik") #Continous variable, cumulative demand, with upper bound Q
B = m.addVars(V,K, vtype=grb.GRB.CONTINUOUS, name="Bik")

m.setObjective(grb.quicksum(grb.quicksum(cijk[(i,j,k)] * x[(i,j,k)] for i,j in A if i!=j if i!=L if j!=0) for k in K), sense=grb.GRB.MINIMIZE) #Objective function, minimizing the distance

#Every vertex need to be served exactly once
m.addConstrs(grb.quicksum(grb.quicksum(x[(i,j,k)] for j in V if j!=i if i!=L if j!=0) for k in K)== 1 for i in N)

#Every vehicle starts and end at the depot
m.addConstrs(grb.quicksum(x[(i,j,k)] for i,j in A if i==0 and i!=j)==1 for k in K)
m.addConstrs(grb.quicksum(x[(i,j,k)] for i,j in A if j==L and i!=j)==1 for k in K)

#Flow conservation Every node has a incoming and outcoming arc
m.addConstrs((grb.quicksum(x[(i,j,k)] for i in V if i!=j if i!=L) - grb.quicksum(x[(j,i,k)] for i in V if i!=j if i!=0))==0 for j in N for k in K)

#Subtour elimination
m.addConstrs(B[(j,k)] + 1000 * (1- x[(i,j,k)]) >= B[(i,k)] + di[i]+ tijk[(i,j,k)] for i,j in A for k in K if j!=i if j!=0 if i!=L)

#Capacity constraints
m.addConstrs(Q[(j,k)] + 1000 *(1-x[(i,j,k)]) >= (Q[(i,k)] + qi[j]) for i,j in A for k in K if i!=j if i!=L if j!=0)
m.addConstrs(Q[(i,k)] >= 0 for i in V for k in K if i!=L)
m.addConstrs(Q[(i,k)] >= qi[i] for i in V for k in K if i!=L)
m.addConstrs(Q[(i,k)] <= Ck[k] for i in V for k in K if i!=L)
m.addConstrs(Q[(i,k)] <= (Ck[k] + qi[i]) for i in V for k in K if i!=L)

#Every pick up and delivery point are associated
m.addConstrs((grb.quicksum(x[(i,j,k)] for j in V if i!=j if j!=0) - grb.quicksum(x[(i,j,k)] for j in V if i!=j if j!=0))==0 for i in P for k in K)

#Delivery can only occur after pickup
m.addConstrs(B[(i,k)]<= B[(n+i, k)] for i in P for k in K)

Output is as follows:

Solved in 0.028 secs.

OPTIMAL
Objective value: 24.075000000000003
Used edges:
0 1 1
0 4 2
1 6 1
2 5 1
3 7 2
4 3 2
5 7 1
6 2 1

Now delivery takes place before picking up

• Gurobi Staff

Hi Roos,

Ok, so you want to solve a pickup-and-delivery problem with 3 commodities, each with a dedicated source and target node. You have two vehicles, each with capacity 6. The model is called PDPTW but I could not detect any time windows here. Anyway, if you have time windows, you just need to bound the B(i,k) variables.

Your solution shows that pickup and delivery, e.g., of the first commodity from 1 to 4, is done by different vehicles. If you output the values for the visiting time variables B(i,k), you will see that your last set of constraints is satisfied but still not enough to ensure that one commodity is completely handled by one vehicle. Usually, one uses binary assignment variables y(i,k) to assign the visit of node i to vehicle k. Then, you can state that $$y_{i,k} = y_{i+n,k}$$. You also need to use variables y(i,k) in the flow conservation constraints, and you could use them to better bound capacity variables Q and visiting time variables B.

Note that you should always use the smallest possible BigM value instead of 1000. Here, you could use vehicle capacities and time window bounds (if available).

Best regards,
Mario