Solucionado (ver solução)
Solucionado
(ver solução)
1
resposta

Meu modelo não está retornando nenhuma mudança, mesmo gerando novas rotas.

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)
1 resposta
solução!

Consegui corrigir, o erro estava na minha funcao vizinho_mais_proximo.