Локальный поиск основан на старейшем методе оптимизации - методе проб и ошибок. Рассмотрим задачу
(4.3.1)
где 
- целевая функция, 
- допустимое множество. Обозначим 
- окрестность точки 
. Понятие окрестности в задачах ЦП тесно связано с понятием “естественного” возмущения допустимого решения. Выбор возмущения основывается на специфике решаемой задачи. На рис.1. изображен путь в задаче коммивояжера и возмущение, внесенное заменой двух дуг этого пути.
Рис.1. Смена двух дуг пути в ЗК.
Окрестность в ЗК можно определить как набор путей, получаемых из имеющегося пути 
заменой двух его произвольных дуг. В ЗК имеется возможность организовать замену 
, 
и т.д. дуг, что определяет размер окрестности.
Рассмотрим схему алгоритма локального поиска для задачи (4.3.1).