分散制約充足問題／分散制約最適化問題は，マルチエージェント環境における分散問題解法として注目を集めている．しかし提案されている解法は，最適解を保証するために非常に長い処理時間を要するか，あるいは確率的解法により短い時間で荒い近似解を得るのが限界であった．現実世界の複雑な問題に適用しようとした場合，多くの変数を扱うために，完全アルゴリズムでは処理時間が，近似解法では解の品質が課題になっていた．先に我々は，分散制約充足問題のためにTabu Searchをマルチエージェント環境で用いる方法を提案した．この手法をもとに今回，Simulated Annealingの要素を加えることで，分散制約最適化問題でも高い品質の近似解を短い時間で得る解法を開発した．本論文では，提案するアルゴリズムの原理，既存アルゴリズムとの比較評価，および10000変数の大規模問題への適用結果を報告する．