top of page

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

  • 執筆者の写真: Naoaki Mochida
    Naoaki Mochida
  • 2024年12月29日
  • 読了時間: 6分

今回は、都市間距離の最適化問題をHOBO形式で解き、効率的な解法を探る方法を解説します！以下のような都市間距離のマップを元に、訪問順序を最適化する問題を取り上げます。


1. 問題設定



問題：都市とそれぞれの距離
問題：都市とそれぞれの距離


4つの都市 A, B, C, D を訪問する順序を最適化する問題を考えます。この際、都市間の移動距離を最小化することが目的です。以下のルールを満たす必要があります：

  • 全ての都市を1回ずつ訪問する。

  • 訪問の順序によって発生する距離の合計を最小化する。

  • スタート地点とゴール地点は決まっていない。


2. 定式化

今回はQUBOを用いて問題を定式化しました。（HOBOの応用が必要ないため。）


制約条件

  1. 各都市には1度だけ訪れる。

  2. 各時間に訪れる都市は1つだけ。


コスト関数

  1. なるべく最短距離で全ての都市に1回ずつ行く。


3. 問題の考え方

  1. 2次元の4x4のテーブル表として考える。


コード：

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

  1. 行と列の制約

  • 1番目、2番目、3番目、4番目の都市は1つずつである。

  • A市、B市、C市、D市はそれぞれ1回ずつ通る。

コード：

#N番目に訪れる都市は1つだけ
Hconst = 0
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

#ある都市に訪れるタイミングは1つだけ
Hconst += (q[0][0] + q[1][0] + q[2][0] + q[3][0] - 1)**2
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

  1. 距離のペナルティー

  • 同じ都市に行く場合のペナルティーは0。

  • 違う都市に行く場合のペナルティーは距離分。

コード：

#1番目から2番目への移動
Hcost = 0
Hcost += 0 * (q[0][0] * q[1][0])
Hcost += 8 * (q[0][1] * q[1][0])
Hcost += 3 * (q[0][2] * q[1][0])
Hcost += 10 * (q[0][3] * q[1][0])

Hcost += 8 * (q[0][0] * q[1][1])
Hcost += 0 * (q[0][1] * q[1][1])
Hcost += 6 * (q[0][2] * q[1][1])
Hcost += 3 * (q[0][3] * q[1][1])

Hcost += 3 * (q[0][0] * q[1][2])
Hcost += 6 * (q[0][1] * q[1][2])
Hcost += 0 * (q[0][2] * q[1][2])
Hcost += 7 * (q[0][3] * q[1][2])

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

#2番目から3番目への移動
Hcost += 0 * (q[1][0] * q[2][0])
Hcost += 8 * (q[1][1] * q[2][0])
Hcost += 3 * (q[1][2] * q[2][0])
Hcost += 10 * (q[1][3] * q[2][0])

Hcost += 8 * (q[1][0] * q[2][1])
Hcost += 0 * (q[1][1] * q[2][1])
Hcost += 6 * (q[1][2] * q[2][1])
Hcost += 3 * (q[1][3] * q[2][1])

Hcost += 3 * (q[1][0] * q[2][2])
Hcost += 6 * (q[1][1] * q[2][2])
Hcost += 0 * (q[1][2] * q[2][2])
Hcost += 7 * (q[1][3] * q[2][2])

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

#3番目から4番目への移動
Hcost += 0 * (q[2][0] * q[3][0])
Hcost += 8 * (q[2][1] * q[3][0])
Hcost += 3 * (q[2][2] * q[3][0])
Hcost += 10 * (q[2][3] * q[3][0])

Hcost += 8 * (q[2][0] * q[3][1])
Hcost += 0 * (q[2][1] * q[3][1])
Hcost += 6 * (q[2][2] * q[3][1])
Hcost += 3 * (q[2][3] * q[3][1])

Hcost += 3 * (q[2][0] * q[3][2])
Hcost += 6 * (q[2][1] * q[3][2])
Hcost += 0 * (q[2][2] * q[3][2])
Hcost += 7 * (q[2][3] * q[3][2])

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

4. 全体のコード

以下は本問題をHOBO形式で解いたPythonコードの一部です。

import numpy as np
from tytan import *

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

#N番目に訪れる都市は1つだけ
Hconst = 0
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

#ある都市に訪れるタイミングは1つだけ
Hconst += (q[0][0] + q[1][0] + q[2][0] + q[3][0] - 1)**2
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

#都市間の距離に比例したコスト
#1番目から2番目への移動
Hcost = 0
Hcost += 0 * (q[0][0] * q[1][0])
Hcost += 8 * (q[0][1] * q[1][0])
Hcost += 3 * (q[0][2] * q[1][0])
Hcost += 10 * (q[0][3] * q[1][0])

Hcost += 8 * (q[0][0] * q[1][1])
Hcost += 0 * (q[0][1] * q[1][1])
Hcost += 6 * (q[0][2] * q[1][1])
Hcost += 3 * (q[0][3] * q[1][1])

Hcost += 3 * (q[0][0] * q[1][2])
Hcost += 6 * (q[0][1] * q[1][2])
Hcost += 0 * (q[0][2] * q[1][2])
Hcost += 7 * (q[0][3] * q[1][2])

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

#2番目から3番目への移動
Hcost += 0 * (q[1][0] * q[2][0])
Hcost += 8 * (q[1][1] * q[2][0])
Hcost += 3 * (q[1][2] * q[2][0])
Hcost += 10 * (q[1][3] * q[2][0])

Hcost += 8 * (q[1][0] * q[2][1])
Hcost += 0 * (q[1][1] * q[2][1])
Hcost += 6 * (q[1][2] * q[2][1])
Hcost += 3 * (q[1][3] * q[2][1])

Hcost += 3 * (q[1][0] * q[2][2])
Hcost += 6 * (q[1][1] * q[2][2])
Hcost += 0 * (q[1][2] * q[2][2])
Hcost += 7 * (q[1][3] * q[2][2])

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

#3番目から4番目への移動
Hcost += 0 * (q[2][0] * q[3][0])
Hcost += 8 * (q[2][1] * q[3][0])
Hcost += 3 * (q[2][2] * q[3][0])
Hcost += 10 * (q[2][3] * q[3][0])

Hcost += 8 * (q[2][0] * q[3][1])
Hcost += 0 * (q[2][1] * q[3][1])
Hcost += 6 * (q[2][2] * q[3][1])
Hcost += 3 * (q[2][3] * q[3][1])

Hcost += 3 * (q[2][0] * q[3][2])
Hcost += 6 * (q[2][1] * q[3][2])
Hcost += 0 * (q[2][2] * q[3][2])
Hcost += 7 * (q[2][3] * q[3][2])

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

# 式の合体
H = Hconst + 0.1*Hcost

#コンパイル
qubo, offset = Compile(H).get_qubo()
print(f'offset\n{offset}')

#サンプラー選択
solver = sampler.SASampler()

#サンプリング
result = solver.run(qubo, shots=500)

#上位5件
for r in result[:3]:
    print(f'Energy {r[1]}, Occurrence {r[2]}')

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

5. 結果

実行環境：

  • CPU/GPU: CUDA対応環境

  • ライブラリ: Tytan

結果を以下に示します：

offset
8.0
Energy -6.8, Occurrence 39
[[0 0 0 1]
 [0 1 0 0]
 [0 0 1 0]
 [1 0 0 0]]
Energy -6.8, Occurrence 61
[[1 0 0 0]
 [0 0 1 0]
 [0 1 0 0]
 [0 0 0 1]]
Energy -6.7, Occurrence 19
[[1 0 0 0]
 [0 0 1 0]
 [0 0 0 1]
 [0 1 0 0]]

つまり、以下のようにA, C, B, D またはその逆の順番が最適です。




6. まとめ

本記事では、都市間の距離最小化問題をQUBOで最適化する方法を紹介しました。QUBOの活用により、問題の制約条件とコスト条件を量子ビットで表し、正確な最適化が可能であることが分かりました。次回は、さらに複雑な問題や、HOBOの応用事例について解説します！

お楽しみに！

 
 
 

Comments

bottom of page