Sub local_search_shift(ByRef M() As Long, ByRef v_sol() As Integer, ByRef z As Long)
 
    ' Local search usando o operador de vizinhança
    ' shift (reinsere um ponto em outro local (fazendo o shift de todos os outros)
    
    Dim melhora As Boolean
    melhora = True
    
    Do While melhora = True
       ' GERAR OS VIZINHOS
       melhora = gera_vizinhos_shift(M, v_sol, z)
    Loop
  
End Sub
 
Function gera_vizinhos_shift(ByRef M() As Long, ByRef v_sol() As Integer, ByRef z As Long) As Boolean
    
    ' Gerar os vizinhos pelo shift, ate o
    ' momento em que um vizinho tenha valor de z
    ' melhor do que o z do argumento
    
    Dim i As Integer
    Dim j As Integer
    Dim custo_shift As Long
    Dim melhorou As Boolean
    
    For i = 2 To UBound(v_sol) ' elemento a ser reinserido
        For j = 0 To i - 2     ' posição da reinserção
            custo_shift = shift(M, v_sol, i, j)
            If custo_shift < z Then
            
                ' Faz o shift no vetor e retorna o resultado
                z = custo_shift
                Dim aux As Integer
                aux = v_sol(i)
                Dim index As Integer
                
                For index = i To j + 1 Step -1
                    v_sol(index) = v_sol(index - 1)
                Next index
                v_sol(j) = aux
                
                melhorou = True
                gera_vizinhos_shift = melhorou
                Exit Function
            End If
        Next j
    Next i
 
    melhorou = False
    gera_vizinhos_shift = melhorou
 
End Function
 
Function shift(ByRef M() As Long, ByRef v_sol() As Integer, index_antigo As Integer, index_novo As Integer) As Long
 
    ' faz a inserção do elemento de index_antigo na posicao index_novo,
    ' realocando os outros elementos para direita.
    ' Sempre index_antigo > index_novo
    
    Dim v_copia() As Integer
    v_copia = v_sol
    
    Dim i As Integer
    Dim aux As Integer
    
    aux = v_copia(index_antigo)
    
    ' Aloca os elementos para a direita
    For i = index_antigo To index_novo + 1 Step -1
        v_copia(i) = v_copia(i - 1)
    Next i
    
    ' Reinsere o elemento na nova posição
    v_copia(index_novo) = aux
    
    shift = calcula_custo(v_copia, M)
 
End Function