巡回セールスマン問題

巡回セールスマン問題(Traveling salesman problem)とは、セールスマンがいくつかの都市を1度ずつすべての都市を訪問して出発点に戻ってくるときに、移動コストが最小になる経路を求める問題です。

都市数  に対して、経路は  通りの候補があり、総当たりで計算すると莫大な計算時間がかかり現実的ではありません。

巡回セールスマン問題をQUBO形式で定式化するために、まず二値変数  を定義します。 は  番目に都市  を訪問する場合に 、それ以外の場合に  を取るように設定します。

巡回セールスマン問題の目的は移動コストを最小化することです。一般的に移動コストは距離で考えられることが多いため、ここでも移動距離を最小化することを考えます。  を都市   間の距離とすると、 番目に訪問する都市から  番目に訪問する都市への移動距離は以下の式で表されます。すべての訪問についてこの総和をとった以下の式が経路の総移動距離となります。ただし、巡回セールスマン問題で求める経路は出発点に戻ってくる巡回路であるため、  であるものとします。

QUBO形式による定式化では、「一つの都市を複数回訪問するもの」や「同時に複数の都市を訪問するもの」など、経路として成立しないものも解の候補に含まれます。 このような解が最適解となるのを防ぐために、「各行に1はただ1つのみ存在する」「各列に1はただ1つのみ存在する」という以下の制約を設けます。この制約に違反するときにペナルティとしてエネルギー関数が増加するように設定すべきであるため、以下の式を制約項としてエネルギー関数に加えます。

上記の目的関数と制約項を用いて、エネルギー関数は以下の式のように表されます。

実際に巡回セールスマン問題をアニーリングで解くシミュレーションをしてみます。 このとき、制約項の係数が重要な役割を果たします。適切な制約の強さは目的関数に依存し、十分大きな値にする必要があります。

ここでは、距離行列の最大値を基準値として、に設定し、を変化させてその影響を確認します。右下のグラフにと移動コストの関係をプロットします。feasibleは制約条件を満たす解、unfeasibleは制約条件に違反する解となります。