多目的進化型人工神経回路網を用いた複数 TSP の解法――パレートフロントにおける端点と選好解の特徴――

片田喜章 † , 渡邉真也 †† 大倉和博 ‡ ,摂南大学 † , 室蘭工業大学大学院 †† 広島大学 ‡はじめに

1

巡回セールスマン問題 (TSP) は複数都市の地理情報が与えられ，セールスマンが全都市を訪問し重複なく一巡して出発した都市に戻る経路を求める問題である 1) ．TSP は数理最適化の典型的な問題であり，厳密解法 2, 3) ・メタヒューリス
ティックスを用いた解法 4, 5) など多くの研究がある．典型的な TSP は 1 人のセールスマンの経路問題であるのに対し，複数人のセールスマンが担当する都市を決めて訪問する経路を求める問題
は複数巡回セールスマン問題 (Multiple Traveling
Salesman Problem: MTSP) とよば れ る ．
MTSP では従来，都市を割り当てる場合に訪問都市群が 1 つの塊を形成するような割り当てを実施することが多い 6, 7) ．そして，割り当てられた都市群に対しそれぞれで TSP を解くという手法が用いられる 8) ．しかし，出発都市を全セールスマンで共通にする場合など，割り当てられる都市群が 1 つの塊を形成していることが総巡回路長の削減や TSP に分類される応用事例で独自に設定された評価指標の改善に寄与するとは限らない．
そこで，我々は訪問都市群の割当てを複数評価指標にもとづいて決定するために，多目的進化計算を用いて設計する人工神経回路網 (ANN) を使用し，割り当てられた都市群の巡回路を TSP
で 広 く 採 用 さ れ て い る 近 似 解 法 を 用 い て 解 く，二段階探索法 8) を提案している 9) ．文献 9) では，3 人のセールスマンに訪問都市群を割り当てる場合の実験を行い，提案手法は k-means 法よりも良い 目的間数値が得られることを確認した．
本稿では，TSP に関するテスト問題を用いて，3,4,5 人のセールスマンに訪問都市群を割り当てる場合の計算機実験を行って提案手法の有効性を検証する．また，得られたパレートフロントの 端点と選好解の特徴を調べる．

2

都市クラスタリング手法

地理情報に基づいて訪問都市を割り当てる (分類する) 手法を以降，都市クラスタリング手法とよぶ．本研究では完全結合型フィードフォワード
ANN を用いる (図 1)．ここで， 入力は正規化した都市座標の値 x, y ∈ {0.0, 1.0}, 各ニューロンの活性化関数はシグモイド関数，出力の値はセールスマン k の選択確率とし，ソフトマックス関数により k を決定する．本設定を用いることにより，都市座標平面を非線形に分割することが可能になる．さらに多目的進化計算を用いて ANN を設計することで，複数評価指標にもとづく適応的な 訪問都市割当てが期待できる．
ANN の入力ノード数を Ni ，中間ノード数を Nh ，出力ノード数を No とすると，各ニューロンにバイアスを設定するため，ニューロン間の結合荷重の合計数はN = (Ni + 1)Nh + (Nh + 1)No になる．図
1 は (Ni , Nh , No ) = (2, 4, 3) の場合を示している．

Multi-Objective Evolutionary Artiﬁcial Neural Networks Approach to Multiple TSP†††‡

Yoshiaki Katada(katada @ setsunan.ac.jp)
Shinya Watanabe(sin @ csse.muroran-it.ac.jp)
Kazuhiro Ohkura(kohkura @ hiroshima-u.ac.jp)

Department of Electrical and Electronic Engineering, Setsunan University (†)
College of Information and Systems, Muroran Institute ofTechnology (††)
Graduate School of Advanced Science and Engineering, Hiroshima University (‡)

Input Neuron

Hidden Neuron

Output Neuron

Fig. 1 フィードフォワード型人工神経回 路網

3

MTSP の目的関数10.9minimize
f1 =F (x) = (f1 (x), f2 (x))
1K′K∑

Lk(2)

k=1,Lk ̸=0max Lk −f2 =(1)1≤k≤K

min1≤k≤K,Lk ̸=0max LkLk(3)

1≤k≤K

4

進化型多目的最適化

2 章 で 述 べ た ANN の 重 み の 設 計 に 実 数 値 型 の多目的進化計算である MOEA/D-DE11) を適用す
る．MOEA/D-DE は多目的最適化問題を複数の単目的最適化問題に分割し原問題のパレートフ
ロ ン ト を 近 似 す る MOEA/D12) と ，実 数 値 型 の最適化問題を扱う差分進化 (DE) のオペレータとpolynomial mutation で 構 成 さ れ て い る ．複 数 の単目的最適化問題を集約する関数として，文献12) では 3 種類が提案されているが，本研究ではTchebycheﬀ 関 数 (式 (4)) を用い る ．
g(x|λ, z∗ ) = max {λi |fi (x) − zi∗ |}
1≤i≤m

0.8
0.7
0.6
λ2

Lk を k 番 目 の セ ー ル ス マ ン (k ∈ {1, 2, · · · , K})が担当する都市の巡回路長，K は巡回可能なセー
ル ス マ ン 数 と す る ．MTSP で は セ ー ル ス マ ン 全員分の巡回路長を評価する．本研究では式 (2) により，巡回路長の合計を都市の割当てがあったサ
ラリーマン数 K ′ で除して平均巡回路長として算出している．これは巡回可能なサラリーマンをできるだけ多く参加させたいという動機による．
さらに，各セールスマンの巡回路長をなるべく均等化したい．このために Lk に関する最大値や平均値 10) ，分散，標準偏差 7) が評価されることが多い．本研究では，均等化係数 6) とよばれる式 (3) を採用する．したがって，2 目的最小化問題(m = 2) を解く こ と になる ．

0.5
0.4
0.3
0.2
0.1
000.1

0.2

0.3

0.4

0.5
λ1

0.6

0.7

0.8

0.9

1

Fig. 2 2 目的空間における重みベクト ル値を使用する 13) ．各目的関数の最小値については初期世代から現在 (tc ) まで，最大値については1 世代前 (tc − 1) と現在 (tc ) の値を用いる．

5

計算機実験

5.1

問題設定

本 稿 で は ，TSP の ベ ン チ マ ー ク 14) の 中 か ら ，fnl4461(以下，4461 都市問題) を対象とする (図 3)．
本問題の 1 人のセールスマンによる最短巡回路長は 182, 566 であることが報告されている．
さらに出発都市に関して下記の設定を 行う．

out: 出発都市は，出発都市以外の全都市配置がつくる凸包の外側に設置する．すべてのセールスマンはこの都市を共通の出発都市とする．上記 4461 都市問題では (5500, 5500) の位
置に出発都 市を設置する．
inc: 出発都市以外の全都市配置の中心に出発都市を設置する．すべてのセールスマンはこの都市を共 通の出発都市とする．
11000

10000

(4)
9000

こ こ で ，m は 目 的 関 数 の 数 ，z∗ は 参 照 点 ，λは 重 み ベ ク ト ル を 表 す．参 照 点 は 探 索 中 に 得ら れ た 各 目 的 関 数 fi の 最 小 値 が 用 い ら れ る 場合 が 多 い ．重 み ベ ク ト ル の 要 素 は 文 献 12) に倣って {0/H, 1/H, · · · , H/H} の い ず れ か を と り，
∑m1 λi = 1 を満たすものとする．m = 2 のときの重 み ベ ク トル を図 2 に 示す．
なお，3 章で述べた目的関数間でスケールが大きく異なるため，式 (4) における fi は正規化した

8000

7000

6000
6000

7000

8000

9000

10000

Fig. 3 4461 都市問題

11000

each: 割り当てられた都市群毎に出発都市を設置する．したがって，各セールスマンは共通の出 発 都市 を も たな い ．
したがって，out, inc の都市設定では都市数は 4462，each では 4461 と な る ．
計算 機 実 験 設定

5.2

2 章で述べた ANNs の結合荷重値 w ∈ {−4.0, 4.0}を 3 章で述べた 2 目的最小化問題の設計変数とする．本問題設定では ANN の出力ノード数 No は巡回可能なセールスマン数 K と等しくなる．本稿では (Ni , Nh , No ) = (2, 4, K)，K ∈ {3, 4, 5} と し て ，各設定に関して MOEA/D-DE を 10 試行実行した．
MOEA/D-DE に 関 す る 設 定 パ ラ メ ー タ を 表 1 に示 す．
ANN によって割り当てられた都市群の巡回路を TSP 近似解法 (LKH-2.0.9)15, 16) を用いて解く．
MOEA/D-DE の 1 個 体 の 評 価 に 関 し て ，LKH の実 行 時 間 を 1s と し ，5-opt, no-patching(C = 0) とする．
ま た ，MOEA/D-DE に よって 得 ら れ る 解 を 考察するために，4461 都市問題の出発都市に関する各設定に対しセールスマン数をK = 1とし，LKH を上記と同じ設定で実行する計算を行った．
5.3

計算 機 実 験 結果

5.3.1

K = 1の場合

セールスマン数を K = 1 とし，各出発都市の設定に LKH を適用して得られた最短巡回路長 (fb1 とする) を表 2 に示す．each の結果は純粋な TSP の問題と等価であり，報告されている最短巡回路長に近い値が獲得されている．なお，表中には後述する考察のために，fb1 をK で除した値も示している．

5.3.2

MTSP に関 する結 果 (K = 3, 4, 5)

各出発都市の設定に関して，K = 3, 4, 5 の場合に MOEA/D-DE を 10 試行実行した中で任意の試行において得られたパレートフロントを図 4-12に示す．1 試行の間に獲得された全非劣解をアーカイブとして保存し描画している．4 章で述べた

Table 1 MOEA/D-DE の設 定 パ ラ メ ー タN
100
T10δ
0.9nr2F0.5CR1.0
重 み ベ ク ト ル 数 100 評 価 回 数 20000

ように，本問題設定は実数値を設計変数とする
最 適 化 問 題 で あ る が ，MTSP は 基 本 的 に 組 合 せ最適化問題のために目的関数値は離散値をとる．
そのため，得られたパレートフロントも離散的である．各軸に対し，十分に収束していることがわかる．K = 3 の場合，非劣解の数はそれほど多く獲得されなかった．K = 4, 5 の場合，都市群ごとに出発都市をもつ場合を除いて多くの非劣解を獲得している．また，各図に f1・f2 軸に沿った端点と著者が選出した解 (選好解) を示した．得られた非劣解集合を代表する点として，これらを以下で考察する．
出発都市が外側に位置する場合に得られた各巡回路長と目的関数値を表 3,4,5 に示す．表中，− はそのセールスマンに出発都市以外の都市の割当てがなかったことを表す．ここで，inv1 は図 4,5,6において，f2 軸に沿った端点を示した解，inv2 は選好解，inv3 は f1 軸に沿った端点を示した解を表す．まず，inv1 は f1 の値が非常に小さく，f2 の値が大きい値を示している．inv1 は 1 人または 2 人のサラリーマンに少数の都市を割り当て K ′ = K を満たし，残りのサラリーマンに大部分の都市を割り当てていると解釈できる．そのため，f1 は最小値をとるが，f2 に見られるように最小巡回路長は最大巡回路長の 1 ∼ 2%となっている．また，inv1 が示す f1 の値は fb1 /K を基準として，それよりも少し大きい値と考えられる (表 2)．inv2 は選好解であり，f1 の値は inv1 に次いで fb1 /K に近く，セールスマン間の巡回路長差は最大巡回路長の 2%以下となっている．inv3 は f1 の値が大きく，f2 の値が極めて小さい．これは 2 人だけに都市を割当てており，割り当たられた 2 人の巡回路長の差が最大巡回路長の 0.1% 以下となっているためである．また，inv3 が示す f1 の値は fb1 /2 を基準としてそれよりも少し大きい値と考えられる (表 2)．

Table 2 各 出 発 都 市 に 対 す る K = 1 の 場 合 に 得られた最短巡回路長
outinceachbf1
183946.2 182884.6 182908.0
fb1 /291973.1
91442.3
91454.0
fb1 /361315.4
60961.5
60969.3
fb1 /445986.5
45721.245727.0
fb1 /536789.2
36576.936581.6

11

Preto front
Extreme sol

0.8

Preto front
Extreme sol

0.8

f2

0.6

f2

0.6
0.4

0.4

0.2

0.2

0070000

80000
f1

90000

90000

Fig. 7 出発都市が中心に位置する場合のパレー
トフロント (K = 3)

1

Preto front
Extreme sol

0.8

80000
f1

Fig. 4 出発都市が外側に位置する場合のパレー
ト フロ ン ト (K = 3)

1

70000

Preto front
Extreme sol

0.8

f2

0.6

f2

0.6
0.4

0.4

0.2

0.2

0050000

60000

70000
f1

80000

90000

Fig. 5 出発都市が外側に位置する場合のパレー
ト フロ ン ト (K = 4)

10.8

50000

60000

70000
f1

80000

90000

Fig. 8 出発都市が中心に位置する場合のパレー
トフロント (K = 4)

1

Preto front
Extreme sol

0.8

f2

0.6

f2

0.6

Preto front
Extreme sol

0.4

0.4

0.2

0.2

00
40000 50000 60000 70000 80000 90000
f1

Fig. 6 出発都市が外側に位置する場合のパレー
ト フロ ン ト (K = 5)40000 50000 60000 70000 80000 90000
f1

Fig. 9 出発都市が中心に位置する場合のパレー
トフロント (K = 5)

1

Table 3 出発都市が外側に位置する場合に得られ た巡回路長と目的関数値 (K = 3)
inv 1
inv 2
inv 3
L1
1392.062790.9
L292014.2
62761.995727.9
L393782.9
62799.3
95703.6

Preto front
Extreme sol

0.8
0.6
f2

f1
f2

0.4

62396.4
0.985157

62784.0
0.000595

95715.70.000255

0.2
070000

80000

90000

f1

Fig. 10 割り当て 都市群 ごとに出発都 市をもつ場 合の パ レ ー ト フロ ン ト (K = 3)

1

f1
f2

Preto front
Extreme sol

0.8

Table 4 出発都市が外側に位置する場合に得られた巡回路長と目的関数値 (K = 4)
inv 1
inv 2
inv 3
L1
61923.1
49031.593194.7
L2 122882.0
48851.093144.6
L32843.548875.0
L41365.748475.447253.6
0.988886

48808.2
0.011342

93169.70.000537

f2

0.6
0.4
0.2
050000

60000

70000
f1

80000

90000

Fig. 11 割り当て 都市群 ごとに出発都 市をもつ場 合の パ レ ー ト フロ ン ト (K = 4)

10.8

Table 5 出発都市が外側に位置する場合に得られた巡回路長と目的関数値 (K = 5)
inv 1
inv 2
inv 3
L1
2503.340546.093213.5
L219016.4 341074.6
L322660.1
41162.2
L44173.240935.8
L5 144730.0
41271.1
93279.8
f1
f2

38616.6
0.982703

40997.9
0.017570

93246.60.000711

Preto front
Extreme solf2

0.6
0.4
0.2
040000 50000 60000 70000 80000 90000
f1

Fig. 12 割り当て 都市群 ごとに出発都 市をもつ場 合の パ レ ー ト フロ ン ト (K = 5)

出発都市が中心に位置する場合，割当て都市群ごとに出発都市をもつ場合に得られた各巡回路長と目的関数値を表 6-11 に示す．表中，− は出
発都市が中心に位置する場合には出発都市以外の 都 市 の 割 当 て が な かった こ と を ，割 当 て 都 市
群ごとに出発都市をもつ場合には割当て都市数が 0 も し く は 1 で あった こ と を 表 す．出 発 都 市 の位置の違いによる巡回路長の合計値に違いがあるが，出発都市が外側に位置する場合と同様の傾向が見られる．出発都市が中心に位置する場
合 の K = 3 に 関 し て ，inv1 が f2 = 0.41，つ ま り，
最 小 巡 回 路 長 は 最 大 巡 回 路 長 の 約 半 分 と な り，割り当て都市数・巡回路長が小さくなく，唯一傾Table 6 出発都市が中心に位置する場合に得られ た巡 回 路 長 と 目的 関 数値 (K = 3)
inv 1
inv 2
inv 3
L1
46421.6
61771.1
91894.2
L279271.0
61831.991890.7
L358387.3
61791.2
f1
f2

61359.9
0.414394

61798.1
0.000983

91892.40.000039

Table 7 出発都市が中心に位置する場合に得られ た巡 回 路 長 と 目的 関 数値 (K = 4)
inv 1
inv 2
inv 3
L1
58772.1
47046.6
91931.3
L260117.3
47118.691927.3
L365684.5
47036.9
L4509.8
47134.1
f1
f246270.9
0.992238

47084.0
0.002063

37237.3
0.959712

38253.4
0.002371

K = 5 に 関 する巡 回 路

K = 5 に 関 し て ，各 出 発 都 市 の 設 定 に お け る
inv1,2,3 のそれぞれの巡回路を図 13,14,15 に示す．
ここで，1 つの色が 1 人のサラリーマンの巡回路
を 表 す．帯 状 の 塊 が 現 れ る こ と は ，提 案 手 法 で得られる ANN で都市の割当てを行う場合の特徴の 1 つ で あ る 9) ．ま た ，前 節 で 述 べ た inv1,2,3 の割当て戦略が各巡回路にも表れている．つまり，
inv1 は図中でかろうじて確認できるほどの少ない都市割当てを 1 人または 2 人のサラリーマンに行い，残りのサラリーマンで大部分の巡回路を形 成 し て い る ．inv2 は 巡 回 路 を 均 等 に 構 成 し て

61040.1
0.983151

61472.3
0.008348

91858.20.000117

Table 10 割り当て都市群ごとに出発都市をもつ
場合に得られた巡回路長と目的関数値 (K = 4)
inv 1
inv 2
inv 3
L1 139702.2
46318.991776.2
L22417.1
46275.9
L338257.1
46324.746189.7
L43268.746280.8
f1
f2

45911.3
0.982698

46300.1
0.001053

91766.70.000208

Table 11 割り当て都市群ごとに出発都市をもつ
場合に得られた巡回路長と目的関数値 (K = 5)
inv 1
inv 2
inv 3
L1 116810.2
37033.091803.9
L216840.7
37038.2
L32964.337053.8
91732.2
L410266.8
37052.9
L537491.8
37019.2-91908.1
0.000001

向 の異 な る 点 で ある ．

5.3.3

f1
f2

91929.3
0.000044

Table 8 出発都市が中心に位置する場合に得られ た巡 回 路 長 と 目的 関 数値 (K = 5)
inv 1
inv 2
inv 3
L132418.7
38219.2
91908.1
L249515.6 338222.7
L352583.7
38276.1
L449550.0
38239.091908.1L52118.538310.0
f1
f2

Table 9 割り当て都市群ごとに出発都市をもつ場 合に得られた巡回路長と目的関数値 (K = 3)
inv 1
inv 2
inv 3
L16051.061165.7
91852.9
L22934.061680.6
L3 174135.1
61570.7
91863.6

f1
f236874.8
0.974623

37039.40.000932

91768.0
0.000781

おり，望ましい巡回路となっている．inv3 は 2 人で都市を分割しており，巡回路長がほぼ 等 し くなっている様子がわかる．
K = 3, 4 の巡回路に関しても同じような結果が得られた．

6

おわりに

本研究では複数巡回セールスマン問題に対し，多目的進化計算を用いて設計する人工神経回路網を用いて訪問都市群の割当てを行い，割り当てられた都市群の巡回路を近似解法を用いて解く手法を提案し，TSP に関するテスト問題を用いて計算機実験を行って提案手法の有効性を検

11

10.9

0.9

0.9

0.8

0.8

0.8

0.7

0.7

0.7

0.6

0.6

0.6

0.5

0.5

0.5

0.4

0.4

0.4

0.3

0.3

0.3

0.2

0.2

0.2

0.1

0.1

0.1

0000.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

000.1

0.2

(a) INV 1

0.3

0.4

0.5

0.6

0.7

0.8

0.9

100.1

0.2

(b) INV 2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0.7

0.8

0.9

1

0.7

0.8

0.9

1(c) INV 3Fig. 13 出発都 市 が 外 側に位置する場合に得られた巡回路 (K = 5)

1

11

0.9

0.9

0.9

0.8

0.8

0.8

0.7

0.7

0.7

0.6

0.6

0.6

0.5

0.5

0.5

0.4

0.4

0.4

0.3

0.3

0.3

0.2

0.2

0.2

0.1

0.1

0.1

000

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

000.1

0.2(a) INV 1

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0

0.1

0.2(b) INV 2

0.3

0.4

0.50.6(c) INV 3Fig. 14 出発都 市 が 中 心に位置する場合に得られた巡回路 (K = 5)

11

1

0.9

0.9

0.9

0.8

0.8

0.8

0.7

0.7

0.7

0.6

0.6

0.6

0.5

0.5

0.5

0.4

0.4

0.4

0.3

0.3

0.3

0.2

0.2

0.2

0.1

0.1

0.1

0000.1

0.2

0.3

0.4

0.5

0.6

(a) INV 1

0.7

0.8

0.9

1

000.1

0.2

0.3

0.4

0.5

0.6(b) INV 2

0.7

0.8

0.9

1

0

0.1

0.2

0.3

0.4

0.5

0.6(c) INV 3

Fig. 15 割当 て 都市 群 ご と に出発都市をもつ場合に得られた巡回路 (K = 5)

証した．さらに，得られたパレートフロントの端点と選好解の特徴を調べた．得られた結果を以 下に ま と め る ．

• f1 が極端に良い解では，1 人または 2 人がその他の数%の経路を巡回し，残りの人で多くの都市を巡回する (出発都市が中心に位置する 場 合 の K = 3 を 除 く)．こ の 場 合 の f1 の 値
は (1 人 TSP の最短巡回路長/巡回可能なサラ
リ ー マ ン 数) に近 い ．
• 選 好 解 で は 各 目 的 関 数 の最 小 値 に 近 い．f1の値は (1 人 TSP の最短巡回路長/巡回可能なサラリーマン数) に近く，f2 の値はセールス
マ ン 間 の 巡 回路長 差 で 1.7%以下 を 示 した．
• f2 が極端に良い解は 2 人で都市群を巡回し，f1 の値は (1 人 TSP の最短巡回路長/2) に近く，巡 回 路 長 差は 0.1%以下 を 示し た ．
従って，提案手法によって得られた選好解は出発都市の位置に適応して，各セールスマンで平均 化 さ れ た短 い 巡 回路 を 形成 し て い る ．
今後，各セールスマンの巡回路長に制約を設ける問題に取り組みたい．また，ANN を用いて都市群の割当てを行なっていることの有用性を検証する目的で，巡回路計画後に訪問都市群が追加されることを想定した実験を行う予定である．
これらの結果をもとに，複数ドローンの飛行経路計画問題に取り組む．出発都市を離着陸を行う地点，巡回する都市を通過点 (ウェイポイント) に 対 応 さ せ て 考 え る と MTSP と 捉 え ら れ る ．
現在，本稿で扱った問題設定に加えて，衝突回避を 目 的 関 数に 含め た 実験を 行って い る ．

謝辞5) M. Dorigo, K. Socha, An Introduction to Ant
Colony Optimization, Approximation Algorithms
and Metaheuristics, CRC Press, 20076) 渡邊，小野，松永，金川，高橋，ファジィc-means法を用いた複数巡回セールスマン問題の一解法，日本ファジィ学会誌, Vol.13, No.1, pp.119–126, 2001
7) 坂本，延寛，鈴木，山本，古川，渡辺：局所クラス タ リ ン グ 組 織 化 法 に よ る n-TSP に 解 法 ，2008
年度精密工学会北海道支部学術講演会講演論文
集 ，pp.35–36, 2008
8) X. Xu, H. Yuan, M. Liptrott, M. Trovati: Two
Phase Heuristic Algorithm for The Multipletravelling Salesman Problem, Soft Computing, 22,pp.6567–6581, 20189) 片田，渡邉，多目的進化型人工神経回路網を用いた複数 TSP の解法, 第 15 回進化計算シンポジウ
ム 2021 講 演 論 文 集, pp.170-175, 2021
10) I. Vandermeulen, R. Groß, A. Kolling: Balanced
Task Allocation by Partitioning the Multiple Traveling Salesperson Problem, In Proc. of the 18th
International Conference on Autonomous Agentsand Multiagent Systems (AAMAS 2019), pp.1479–1487, 201911) H. Li, Q. Zhang, Multiobjective Optimization Problems With Complicated Pareto Sets,
MOEA/D and NSGA-II, IEEE Transactions on
Evolutionary Computation, Vol. 13, No. 2, pp.284–302, 200912) Q. Zhang, H. Li, MOEA/D: A Multiobjective
Evolutionary Algorithm Based on Decomposition,IEEE Transactions on Evolutionary Computation,
Vol. 11, No. 6, pp.712–731, 200713) L. He, H. Ishibuchi, A. Trivedi, H. Wang, Y.
Nan and D. Srinivasan, A Survey of Normalization Methods in Multiobjective Evolutionary Algorithms, IEEE Transactions on Evolutionary Computation, Vol. 25, No. 6, pp. 1028–1048, 2021

本研 究 は科 研 費 (21K12081) の 助成 を 受けたものである．

14) TSPLIB,
http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/

参考文献
1) 山 本 ，久 保 「 巡 回 セ ー ル ス マ ン 問 題 へ の 招 待 」
朝 倉 書 店 ， 1997

15) K. Helsgaun, General k-opt submoves for the LinKernighan TSP heuristic, Mathematical Programming Computation, 1:119-163, 20092) ウィリアム・J・クック，「驚きの数学 巡回セール
ス マ ン 問 題 」青 土 社 ，201316) LKH-2.0.9
http://webhotel4.ruc.dk/~keld/
research/LKH/

3) Concorde
TSPsolver,
http://www.math.uwaterloo.ca/tsp/concorde/4) 永田，小林，巡回セールスマン問題に対する交叉：枝 組 み 立 て 交 叉 の 提 案 と 評 価 ，人 工 知 能 学
会 誌 ，Vol.14, No.5, pp.848–859, 1999