Рассматривается задача упаковки в контейнеры. Предлагается поиск решения задачи в окрестности решений, имеющей экспоненциальную мощность. Представлены различные алгоритмы построения такой окрестности решений. Сложность поиска во всех алгоритмах является полиномиальной, так как процесс поиска сводится к решению задачи о назначениях. Приведены результаты численного эксперимента, демонстрирующие преимущество предложенных алгоритмов по сравнению с классическими алгоритмами поиска в окрестностях полиномиальной сложности.