Étant donnée une tournée T , on regarde si l’échange de 2 villes dans T produit une tournée de meilleure qualité que T . Par exemple, si on échange b et d dans la tournée T = abcde on obtient une nouvelle tournée T ′ = adcbe. En pratique, on effectue des améliorations successives jusqu’à ce qu’il ne soit plus possible d’améliorer la solution courante. On peut aussi arrêter le processus quand une limite de temps fixée au préalable est dépassée.
Étant donnée une tournée T , on regarde si l’échange de 2 villes dans T produit une tournée de meilleure qualité que T . Par exemple, si on échange b et d dans la tournée T = abcde on obtient une nouvelle tournée T ′ = adcbe. En pratique, on effectue des améliorations successives jusqu’à ce qu’il ne soit plus possible d’améliorer la solution courante. On peut aussi arrêter le processus quand une limite de temps fixée au préalable est dépassée.