1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
| import numpy as np
import matplotlib.pyplot as plt
from docplex.mp.model import Model
rnd=np.random
rnd.seed(0)
#Number of client
n=5
#Pickup locations
P=[i for i in range(1,n+1)]
#Delivery locations
D=[i for i in range(n+1,2*n+1)]
#N the set of all nodes 0 and 2n+1 are the start and end terminal.
N=[0]+P+D
#Set of vehicule
K=[1]
#Maximum Capacity of the vehicle
Q=15
#A set of edges
A = [(i,j) for i in N for j in N]
#Amount loaded onto vehicle at node i, qi = qi+n (q pickup = q delivery for the same node i)
q ={i:rnd.randint(1,10)for i in P}
q1={i:-q[i-n] for i in D}
q.update(q1)
# Generating random numbers between (0 and 2n+1) * 200.
loc_x = rnd.rand(len(N))*200
# Generating random numbers between (0 and 2n+1) * 100.
loc_y = rnd.rand(len(N))*100
plt.scatter(loc_x[1:n+1],loc_y[1:n+1],c='b')
plt.scatter(loc_x[n+1:],loc_y[n+1:],c='g')
#Pickup and Delivery points
for i in P:
plt.annotate('$q_%d=%d$'%(i,q[i]),(loc_x[i],loc_y[i]))
for i in D:
plt.annotate('$q_%d=%d$'%(i-n,q[i]),(loc_x[i],loc_y[i]))
#Depot point
plt.plot(loc_x[0],loc_y[0],c='r' ,marker='s')
plt.show()
#cost of each arc
c= {(i,j):np.hypot(loc_x[i]-loc_x[j],loc_y[i]-loc_y[j]) for i,j in A}
#CPLEX Model
mdl = Model('DARP')
#Initializing our binary variable x_i,j
x=mdl.binary_var_dict (A,name='x')
#Initializing our cumulative demand u
u=mdl.continuous_var_dict (N,ub=Q ,name = 'u')
#Initializing the objectif function
mdl.minimize(mdl.sum(c[i,j]*x[i,j]for i in N for j in N))
#Initialzing constraint every request is served exactly once
mdl.add_constraints(mdl.sum(x[i,j]for j in N)==1 for i in P)
#Initialzing constraint same vehicle services pickup and delivery
mdl.add_constraints(((mdl.sum(x[i,j]for j in N))-(mdl.sum(x[n+i,j] for j in N)))==0 for i in P)
#Initialzing constraint the same vehicle that enters a node leaves the node
mdl.add_constraints(((mdl.sum(x[j,i]for j in N))-(mdl.sum(x[i,j] for j in N)))==0 for i in (P+D))
###LES CONTRAINTES QUI NE FONCTIONNENT PAS###
#Initialzing constraint every vehicle enters the end terminal
#mdl.add_constraints(mdl.sum(x[i,0] for i in N)==1)
#mdl.add_constraints(mdl.sum(x[0,j] for j in N)==1)
#Initialzing constraints setting and checking vehicle load
mdl.add_indicator_constraints_(mdl.indicator_constraint(x[i,j],u[i]+q[j]==u[j])for i in N[1:] for j in N[1:])
mdl.add_constraints(u[i]>=q[i] for i in N[1:])
mdl.add_constraints(u[i]<=min(Q,Q+q[i]) for i in N[1:])
#Getting the solution
solution =mdl.solve(log_output=True)
#Printing the solution
print(solution)
#Identifing the active arcs.
active_arcs =[ a for a in A if x[a].solution_value> 0.9]
#Pickup and Delivery points
plt.scatter(loc_x[1:n+1],loc_y[1:n+1],c='b')
plt.scatter(loc_x[n+1:],loc_y[n+1:],c='g')
for i in P:
plt.annotate('$q_%d=%d$'%(i,q[i]),(loc_x[i],loc_y[i]))
for i in D:
plt.annotate('$q_%d=%d$'%(i-n,q[i]),(loc_x[i],loc_y[i]))
for i,j in active_arcs :
#Coloring the active arcs
plt.plot([loc_x[i],loc_x[j]],[loc_y[i],loc_y[j]],c='g',alpha=0.3)
#Depot point
plt.plot(loc_x[0],loc_y[0],c='r' ,marker='s')
plt.show() |
