Quando eu comento a restrição
#Restricoes #modelo.Add(expr_distancia <= distancia_heuristica)
o retorno dá correto, quando não comento ele so retorna o mesmo valor... 45,8. Não sei se dessa forma o modelo tá salvo com o valor da heuristica com outros enderecos. E por o valor ser sempre menor que o modelo encontra, ele so diz que é 45.8.
def modelo_matematico_com_heuristica(origem, destino, endereco):
# Definindo o grafo
G = criar_grafo(origem, destino, endereco)
n = G.number_of_nodes()
# Solução inicial com a heurística
rota_heuristica, distancia_heuristica = vizinho_mais_proximo(origem, destino, endereco)
# Chamando o solver
modelo = pywraplp.Solver.CreateSolver("SCIP")
# Definindo o limite de tempo (1 minuto)
modelo.SetTimeLimit(60 * 1000)
# Variáveis de decisão
x = {}
for i, j in G.edges():
x[(i, j)] = modelo.BoolVar(name=f"x[{i,j}]")
u = {}
for i in G.nodes():
u[i] = modelo.NumVar(lb=1.0, ub=n, name=f"u[{i}]")
# Função objetivo
expr_distancia = sum(G.get_edge_data(i, j)['weight'] * x[i, j] for i, j in G.edges())
modelo.Minimize(expr_distancia)
# Definindo o limite inicial da distância com a solução heurística
modelo.Add(expr_distancia <= distancia_heuristica)
# Restrições
for i in G.nodes():
if i != 'destino':
modelo.Add(sum(x[i, j] for j in G.successors(i)) == 1)
if i != 'origem':
modelo.Add(sum(x[j, i] for j in G.predecessors(i)) == 1)
for i, j in G.edges():
modelo.Add(u[i] - u[j] + n * x[i, j] <= n - 1)
# Resolução
status = modelo.Solve()
# Formatação dos resultados
melhor_rota = rota_heuristica
distancia_percorrida = distancia_heuristica
status_descricao = {
pywraplp.Solver.OPTIMAL: 'Ótima',
pywraplp.Solver.FEASIBLE: 'Viável',
}
if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
print("Solução ", status_descricao[status])
distancia_percorrida = modelo.Objective().Value()
melhor_rota = [0] * n
for i in G.nodes():
indice = round(u[i].solution_value()) - 1
melhor_rota[indice] = G.nodes[i]["local"]
return melhor_rota, distancia_percorrida
origem = (0, 0)
destino = (4, 4)
import random
endereco = [(random.randint(0,100), random.randint(0,100)) for i in range(30)]
print(endereco)
menor_rota, distancia_percorrida = modelo_matematico_com_heuristica(origem, destino, endereco)
print(distancia_percorrida)