Problema del viajante de comercio (TSP) resuelto con Pyhton y Or-Tools. En cada archivo se encuentra un modelo diferente para abordar la eliminación de subtours.
Contiene el modelo del TSP solucionando el problema de los subtours con el uso de Ui.
u = {}
for i in range(1,nodes):
u[i] = solver.IntVar(1.0,solver.infinity(),'u[%i]' % (i))
for i in range(1,nodes):
for j in range(1,nodes):
solver.Add(u[j]>=(u[i]+x[i,j]-(nodes-2)*(1-x[i,j])))
Mejora el modelo anterior de las Uij reforzando las restricciones
for i in range(1,nodes):
for j in range(1,nodes):
solver.Add(u[j]>=(u[i]+x[i,j]-(nodes-2)*(1-x[i,j])+(nodes-3)*x[j,i]))
Contiene el modelo del TSP solucionando el problema de los subtours con el uso de Vij.
v = {}
for i in range(1, nodes):
for j in range(1, nodes):
if i != j:
v[i, j] = solver.BoolVar('v[%i, %i]' % (i, j))
for i in range(1,nodes):
for j in range(1,nodes):
if i != j:
solver.Add((v[i,j]+v[j,i]) == 1)
for i in range(1,nodes):
for j in range(1,nodes):
if i != j:
for k in range(1, nodes):
if (k != i) & (k != j):
solver.Add( v[i,j]+v[j,k] <= v[i,k]+1 )
for i in range(1,nodes):
for j in range(1,nodes):
if i != j:
solver.Add(x[i,j] <= v[i,j])
Contiene el modelo del TSP solucionando el problema de los subtours con el uso de fij.
f = {}
for i in range(nodes):
for j in range(nodes):
f[i, j] = solver.IntVar(0.0,solver.infinity(),'f[%i, %i]' % (i, j))
for i in range(1,nodes):
solver.Add((solver.Sum([f[i,j] for j in range(nodes)])-solver.Sum([f[j,i] for j in range(nodes)]))==1)
for i in range(nodes):
for j in range(nodes):
solver.Add(0<=f[i,j]<=(nodes-1)*x[i,j])
Mejora el modelo anterior de las fij reforzando las restricciones
for i in range(1,nodes):
solver.Add((solver.Sum([f[i,j] for j in range(nodes)])-solver.Sum([f[j,i] for j in range(nodes)]))==1)
for i in range(1,nodes):
for j in range(1,nodes):
solver.Add(x[i,j]<=f[i,j]<=(nodes-2)*x[i,j])
for i in range(1,nodes):
solver.Add(f[i,0]==(nodes-1)*x[i,0])
for i in range(1,nodes):
solver.Add(f[0,i]==0)
Se resuelve el TSP dado un conjunto de precedencias.
Se definen como un vector de pares (vectores de 2 elementos) que representan las precedencias.
precedencias = [[3,2],[1,2]]
Si se elige el método para eliminar los subtours el método de Vij basta con lo siquiente:
for p in precedencias:
solver.Add(v[p[0],p[1]] == 1)
NOTA: Al hacerlo aleatorio, para saber la demanda del primer nodo se está haciendo una suma de la demanda de todos los nodos y luego poniéndose la inversa de este número como la demanda del almacén. Por esto hay que controlar manualmente la Q (carga máxima del camión), pues esta ha de ser mayor que las demandas y la demanda del almacen puede ser muy alta por lo previamente explicado.
aux = 0
d = []
for i in range(1,nodes):
x = rand.randint(-10,10)
d.append(x)
aux+=x
d.append(-aux)
for i in range(nodes):
solver.Add((solver.Sum([f[j,i] for j in range(nodes)])-solver.Sum([f[i,j] for j in range(nodes)])) == d[i])
for i in range(nodes):
for j in range(nodes):
solver.Add(0<=f[i,j]<=Q*x[i,j])
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent