Discussion :

[StabiloHB]

Bonjour à tous,

J'essaye de mettre en place un Dial A Ride Problem en utilisant la librairie CPLEX sur python.

Je me suis inspiré du modèle de Jean-François Cordeau & Gilbert Laporte. (Pour ne pas dire copier )

Dont les équations et les contraintes se trouvent en image ici :


J'ai simplifié le problème en supprimant les contraintes de temps ainsi que les véhicules que j'ai réduit au nombre de 1.
Pour finir le point de départ est le point d'arrivé donc 2n+1 devient 0.

Donc sauf erreurs de ma part le système devient donc :


Voici maintenant mon programme qui malheureusement ne tourne pas, ou mal.
Je m'explique :
- les contraintes pour forcer le départ du véhicule du point 0 et de le faire retourner au point 0 à la fin ne fonctionnent pas.
- Si on supprime ces contraintes, le programme tourne. Cependant, Il fait juste la tournée point à point sans s'occuper de l'ordre des pickup et delivery. (Pickup 1 doit être délivré a Delivery 1+n où n est le nombre de pickup)

Si vous avez des solutions, ou vous voyez des erreurs flagrantes je suis preneur.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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()

Merci d'avance et bonne journée à tous

PS : j'espère être dans la bonne partie du Forum, je ne sais pas trop si mon problème est algorithmique ou de programmation.

Stabilo.

EDIT : j'ai réussi à solutionner le problème de départ et d'arrivé, cplex n'acceptait pas que l'on mette 0 directement.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
#Initialzing constraint every vehicle enters the end terminal
mdl.add_constraints(mdl.sum(x[i,k] for i in N if i!=k)==1 for k in[0])
mdl.add_constraints(mdl.sum(x[k,j] for j in N if j!=k)==1 for k in[0])

[StabiloHB]

Bon après plusieurs jours, je pense qu'il n'est pas possible de simplifier un modèle comme cela.

Merci quand même

Stabilo.