Como se calcula o custo incremental \( \Delta \) para inserir um vértice v entre i e j na heurística de inserção mínima e qual critério determina a posição de inserção?

\( \Delta_{(i,j)} = d(i,v)+d(v,j)-d(i,j)\); inserir onde \(\Delta\) for mínimo.

Explicação:
O valor \(\Delta_{(i,j)}\) mede o acréscimo (ou diminuição, se negativo) do comprimento total ao colocar v entre i e j.
Comparando \(\Delta\) para todos os arcos consecutivos da subtour, escolhe-se o arco com o menor \(\Delta\) para manter a otimização local.

Exemplo:
Subtour atual: A–B–C–A com distâncias
\(d(A,B)=8,\; d(B,C)=7,\; d(C,A)=9\).
Novo vértice: V com
\(d(A,V)=3,\; d(V,B)=6,\; d(B,V)=4,\; d(V,C)=5,\; d(C,V)=2,\; d(V,A)=6\).
Calcule:
\( \Delta_{(A,B)}=d(A,V)+d(V,B)-d(A,B)=3+6-8=1\)
\( \Delta_{(B,C)}=4+5-7=2\)
\( \Delta_{(C,A)}=2+6-9=-1\)
Como o menor \(\Delta\) é \(-1\) para o arco C–A, deve-se inserir V entre C e A, reduzindo a distância total em 1 unidade.