top of page

応用型の巡回セールスマン問題を最適化して解く！

  • 執筆者の写真: Naoaki Mochida
    Naoaki Mochida
  • 2月8日
  • 読了時間: 5分

本記事では、量子コンピュータを活用して巡回セールスマン問題（TSP）を最適化する方法を解説します。具体的には、QUBO（Quadratic Unconstrained Binary Optimization）を用いた定式化を行い、最適な訪問順序を求めます。


1. 問題設定



問題
問題

巡回セールスマン問題（TSP）とは、複数の都市を一度ずつ訪問し、最短距離で巡回する順序を求める最適化問題です。本記事では、以下のルールに基づき問題を解きます。

  • 4つの都市（A, B, C, D）を訪問する順序を最適化

  • 各都市は1回ずつ訪問

  • 移動距離の合計を最小化

  • Aを出発点とし、初めに入っている15km分のガソリンを切らさないように補充しながら、すべての都市に行く。


都市間の距離は以下のように設定します。


量子ビットの配置
量子ビットの配置

2. 定式化

QUBOを用いた定式化を行い、制約条件とコスト関数を構築します。


制約条件:


  1. Aが出発点。

  2. A, B, C, Dは1回ずつ通る。

  3. n番目に通る都市は1つ。

  4. Cは2地点以内に通る。(補充が必要なため)


コスト条件:


  1. なるべく短い距離で行きたい。

  2. なるべくガソリンを使わない。


  1. 問題の考え方


制約条件

(1) Aを出発点とする。

Hconst = 0
Hconst += (q[0][0] - 1)**2

(2) 各都市は1回ずつ訪れる。

Hconst += (q[0][1] + q[1][1] + q[2][1] + q[3][1] - 1)**2
Hconst += (q[0][2] + q[1][2] + q[2][2] + q[3][2] - 1)**2
Hconst += (q[0][3] + q[1][3] + q[2][3] + q[3][3] - 1)**2

(3) 各訪問順序において1都市のみ訪れる。

Hconst += (q[0][0] + q[0][1] + q[0][2] + q[0][3] - 1)**2
Hconst += (q[1][0] + q[1][1] + q[1][2] + q[1][3] - 1)**2
Hconst += (q[2][0] + q[2][1] + q[2][2] + q[2][3] - 1)**2
Hconst += (q[3][0] + q[3][1] + q[3][2] + q[3][3] - 1)**2

(4) Cは2地点以内に訪れる(補充が必要なため)。

Hconst += (q[1][2] + q[2][2] - 1)**2


コスト関数(なるべく少ないガソリンで達成したい)


(1) なるべく短い距離で達成したい。

Hcost = 0
Hcost += 8 * (q[0][0]*q[1][1])
Hcost += 14 * (q[0][0]*q[1][2])
Hcost += 13 * (q[0][0]*q[1][3])
...

(2) なるべく15kmを超えないように行きたい。

Hcost += (8 * q[1][1] + 8 * q[2][0] - 15)**2
Hcost += (8 * q[1][1] + 7 * q[2][2] - 15)**2
Hcost += (8 * q[1][1] + 9 * q[2][3] - 15)**2

Hcost += (14 * q[1][2] + 14 * q[2][0] - 15)**2
Hcost += (14 * q[1][2] + 7 * q[2][1] - 15)**2
Hcost += (14 * q[1][2] + 10 * q[2][3] - 15)**2

Hcost += (8 * q[2][1] + 8 * q[3][0] - 15)**2
Hcost += (8 * q[2][1] + 8 * q[3][2] - 15)**2
Hcost += (8 * q[2][1] + 9 * q[3][3] - 15)**2

Hcost += (14 * q[2][2] + 14 * q[3][0] - 15)**2
Hcost += (14 * q[2][2] + 7 * q[3][1] - 15)**2
Hcost += (14 * q[2][2] + 10 * q[3][3] - 15)**2

ハミルトニアンの構築

H = Hconst + 0.0001 * Hcost

  1. 全体のコード


from tytan import *

# 量子ビットの用意
q = symbols_list([4, 4], 'q{}_{}')

# 制約条件1(Aが出発点)
Hconst = 0
Hconst += (q[0][0] - 1)**2

# 制約条件2(A. B, C, Dは1地点ずつ通る)
Hconst += (q[0][1] + q[1][1] + q[2][1] + q[3][1] - 1)**2
Hconst += (q[0][2] + q[1][2] + q[2][2] + q[3][2] - 1)**2
Hconst += (q[0][3] + q[1][3] + q[2][3] + q[3][3] - 1)**2

#制約条件3(n番目に通る都市は1つ)
Hconst += (q[0][0] + q[0][1] + q[0][2] + q[0][3] - 1)**2
Hconst += (q[1][0] + q[1][1] + q[1][2] + q[1][3] - 1)**2
Hconst += (q[2][0] + q[2][1] + q[2][2] + q[2][3] - 1)**2
Hconst += (q[3][0] + q[3][1] + q[3][2] + q[3][3] - 1)**2

#制約条件4(Cは2地点以内に通る。A→B→CまたはA→C)
Hconst += (q[1][2] + q[2][2] - 1)**2

#コスト条件1(なるべく短い距離で行きたい)
Hcost = 0

Hcost += 0 * (q[0][0]*q[1][0])
Hcost += 8 * (q[0][0]*q[1][1])
Hcost += 14 * (q[0][0]*q[1][2])
Hcost += 13 * (q[0][0]*q[1][3])
Hcost += 8 * (q[0][1]*q[1][0])
Hcost += 0 * (q[0][1]*q[1][1])
Hcost += 7 * (q[0][1]*q[1][2])
Hcost += 9 * (q[0][1]*q[1][3])
Hcost += 14 * (q[0][2]*q[1][0])
Hcost += 7 * (q[0][2]*q[1][1])
Hcost += 0 * (q[0][2]*q[1][2])
Hcost += 10 * (q[0][2]*q[1][3])
Hcost += 13 * (q[0][3]*q[1][0])
Hcost += 9 * (q[0][3]*q[1][1])
Hcost += 10 * (q[0][3]*q[1][2])
Hcost += 0 * (q[0][3]*q[1][3])

Hcost += 0 * (q[1][0]*q[2][0])
Hcost += 8 * (q[1][0]*q[2][1])
Hcost += 14 * (q[1][0]*q[2][2])
Hcost += 13 * (q[1][0]*q[2][3])
Hcost += 8 * (q[1][1]*q[2][0])
Hcost += 0 * (q[1][1]*q[2][1])
Hcost += 7 * (q[1][1]*q[2][2])
Hcost += 9 * (q[1][1]*q[2][3])
Hcost += 14 * (q[1][2]*q[2][0])
Hcost += 7 * (q[1][2]*q[2][1])
Hcost += 0 * (q[1][2]*q[2][2])
Hcost += 10 * (q[1][2]*q[2][3])
Hcost += 13 * (q[1][3]*q[2][0])
Hcost += 9 * (q[1][3]*q[2][1])
Hcost += 10 * (q[1][3]*q[2][2])
Hcost += 0 * (q[1][3]*q[2][3])

Hcost += 0 * (q[2][0]*q[3][0])
Hcost += 8 * (q[2][0]*q[3][1])
Hcost += 14 * (q[2][0]*q[3][2])
Hcost += 13 * (q[2][0]*q[3][3])
Hcost += 8 * (q[2][1]*q[3][0])
Hcost += 0 * (q[2][1]*q[3][1])
Hcost += 7 * (q[2][1]*q[3][2])
Hcost += 9 * (q[2][1]*q[3][3])
Hcost += 14 * (q[2][2]*q[3][0])
Hcost += 7 * (q[2][2]*q[3][1])
Hcost += 0 * (q[2][2]*q[3][2])
Hcost += 10 * (q[2][2]*q[3][3])
Hcost += 13 * (q[2][3]*q[3][0])
Hcost += 9 * (q[2][3]*q[3][1])
Hcost += 10 * (q[2][3]*q[3][2])
Hcost += 0 * (q[2][3]*q[3][3])


Hcost += (8 * q[1][1] + 8 * q[2][0] - 15)**2
Hcost += (8 * q[1][1] + 7 * q[2][2] - 15)**2
Hcost += (8 * q[1][1] + 9 * q[2][3] - 15)**2

Hcost += (14 * q[1][2] + 14 * q[2][0] - 15)**2
Hcost += (14 * q[1][2] + 7 * q[2][1] - 15)**2
Hcost += (14 * q[1][2] + 10 * q[2][3] - 15)**2

Hcost += (8 * q[2][1] + 8 * q[3][0] - 15)**2
Hcost += (8 * q[2][1] + 8 * q[3][2] - 15)**2
Hcost += (8 * q[2][1] + 9 * q[3][3] - 15)**2

Hcost += (14 * q[2][2] + 14 * q[3][0] - 15)**2
Hcost += (14 * q[2][2] + 7 * q[3][1] - 15)**2
Hcost += (14 * q[2][2] + 10 * q[3][3] - 15)**2


H = Hconst + 0.0001*Hcost


# コンパイル・サンプリング
qubo, offset = Compile(H).get_qubo()     # コンパイル
print(f'offset\n{offset}')
solver = sampler.SASampler()             # サンプラー選択
result = solver.run(qubo, shots=100)     # サンプリング
# 結果表示
for r in result[:5]:
    print(f'Energy {r[1]}, Occurrence {r[2]}')

    #配列に
    arr, subs = Auto_array(r[0]).get_ndarray('q{}_{}')
    print(arr)

 5. 結果

以下のように最適な訪問順序は A → B → C → D であることが分かります。

offset
9.27
Energy -9.138, Occurrence 15
[[1 0 0 0]
 [0 0 1 0]
 [0 1 0 0]
 [0 0 0 1]]
Energy -9.133299999999998, Occurrence 33
[[1 0 0 0]
 [0 1 0 0]
 [0 0 1 0]
 [0 0 0 1]]
Energy -9.0909, Occurrence 9
[[1 0 0 0]
 [0 0 1 0]
 [0 0 0 1]
 [0 1 0 0]]
Energy -9.076799999999999, Occurrence 19
[[1 0 0 0]
 [0 0 0 1]
 [0 0 1 0]
 [0 1 0 0]]
Energy -8.1511, Occurrence 1
[[1 0 0 0]
 [0 1 1 0]
 [0 0 0 1]
 [1 0 0 0]]

 6. まとめ

本記事では、QUBOを用いた発展した巡回セールスマン問題の最適化を量子アニーリングを実施しました。QUBOの定式化によって制約条件を考慮しつつ、最適な経路を求めることが可能となります。

今後は、より多くの都市や追加の制約条件を考慮した拡張問題やHOBOで解いていきます。

お楽しみに！


 
 
 

Comments

bottom of page