進化計算シンポジウム2021（2021/12/25-26）

多目的進化型人工神経回路網を用いた複数 TSP の解法
片田喜章 † , 渡邉真也 ††摂南大学 † , 室蘭工業大学大学院 ††はじめに

1

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

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

Output Neuron

Fig. 1 フィードフォワード型人工神経回 路網進化型多目的最適化

2 章で述べた ANNs の重みの設計に実数値型の多目的進化計算である MOEA/D-DE9) を適用す
る．MOEA/D-DE は多目的最適化問題を複数の単目的最適化問題に分割し原問題のパレートフ
ロ ン ト を 近 似 す る MOEA/D10) と ，実 数 値 型 の最適化問題を扱う差分進化 (DE) のオペレータとPolynomial Mutation で構成されている．複数の単目的最適化問題を集約する関数として，文献
10) では 3 種類が提案されているが，本研究では地理情報に基づいて訪問都市を割り当てる (分類する) 手法を以降，都市クラスタリング手法と††Input Neuron

3

都市クラスタリング手法

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

Yoshiaki Katada(katada @ setsunan.ac.jp)
Shinya Watanabe(sin @ csse.muroran-it.ac.jp)

Department of Electrical and Electronic Engineering, Setsunan University (†)
College of Information and Systems, Muroran Institute ofTechnology (††)

170

進化計算シンポジウム2021（2021/12/25-26）

Tchebycheﬀ 関 数 (式 (1)) を用い る ．

11000

g(x|λ, z∗ ) = max {λi |fi (x) − zi∗ |}1≤i≤m(1)10000

こ こ で ，m は 目 的 関 数 の 数 ，z∗ は 参 照 点 ，λは 重 み ベ ク ト ル を 表 す．参 照 点 は 探 索 中 に 得ら れ た 各 目 的 関 数 fi の 最 小 値 が 用 い ら れ る 場
合 が 多 い ．重 み ベ ク ト ル の 要 素 は 文 献 10) に倣って {0/H, 1/H, · · · , H/H} の い ず れ か を と り，
∑m1 λi = 1 を満たすものとする．m = 2 のときの重 み ベ ク トル を図 2 に 示す．

9000

8000

7000

6000
6000

7000

8000

9000

10000

11000

10.9
0.8

Fig. 3 4461 都市問題

0.7

λ20.60.5

さらに出発都市に関して下記の設定を 行 う．

0.4
0.3

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

0.20.1000.1

0.20.30.40.5
λ10.60.7

0.80.9

1Fig. 2 2 目的空 間 におけ る 重 み ベ ク ト ル

4

2. 出発都市以外の全都市配置の中心に出発都市を設置する．すべてのセールスマンはこの都市を共 通の出発都市とする．

MTSP の目的関数

Lk を k 番 目 の セ ー ル ス マ ン (k ∈ {1, 2, · · · , K})が担当する都市の巡回路長，K はセールスマン
数 と す る ．MTSP で は セ ー ル ス マ ン 全 員 分 の 巡回路長を評価する．本研究では平均巡回路長 (式(3)) を評価する．さらに，各セールスマンの巡回路長をなるべく均等化したい．このために Lk に関する最大値や平均値 11) ，分散，標準偏差 7) が評価されることが多い．本研究では，均等化係数 6) とよばれる (式 (4)) を採用する．したがって，
2 目的 最小 化問 題 (m = 2) を解 く こ と に な る．
minimize
f1 =F (x) = (f1 (x), f2 (x))
1KK
∑

Lk(2)
(3)

3. 割り当てられた都市群毎に出発都市を設置する．したがって，各セールスマンは共通の出発都市を もたない．
5.2

計算機実験設定

2 章で述べた ANNs の結合荷重値 w ∈ {−4.0, 4.0}を 4 章で述べた 2 目的最小化問題の設計変数とする ．本 問 題 設 定 で は ANNs の 出 力 ノ ー ド 数 No はセールスマン数 K と等しくなる．本稿では K = 3,
(Ni , Nh , No ) = (2, 4, 3) と し て ，各 設 定 に 関 し て
MOEA/D-DE を 10 試行実行した．MOEA/D-DEに関する設定パラメータを表 1 に示す．
都市クラスタリングによって割り当てられた都市 群 の 巡 回 路 を TSP 近 似 解 法 (LKH-2.0.9)13, 14)k=1max Lk − min Lk

f2 =1≤k≤K

1≤k≤Kmax Lk

(4)

1≤k≤K

5計算機実験

5.1

問題 設 定本 稿 で は ，TSP の ベ ン チ マ ー ク 12) の 中 か ら ，fnl4461(以下，4461都市問題)を対象とする(図3)．
171

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

進化計算シンポジウム2021（2021/12/25-26）

を 用 い て 解 く．MOEA/D-DE の 1 個 体 の 評 価に 関 し て ，LKH の 実 行 時 間 を 1s と し ，5-opt,no-patching(C = 0) と設 定 する ．
また，提案する多目的進化型 ANNs(以下，必要に応じて eann と記す) と比較するために，都市クラスタリング手法として k-means 法を採用し，上記 LKH を適用した実験を行った．共通の出発都市をもつ場合，出発都市をクラスタリングに含める
k-means 法 (kmeans w/ depo) と 含 め な い k-means法 (kmenas w/o depo) を計算する．MOEA/D-DEの 個 体 数 を考 慮し ，100 試行実 行 し た ．

0.8

f2

0.6
0.4
0.2062000

計算 機 実 験 結 果
パレ ート フ ロ ント

図 4-6 に多目的進化型 ANNs に関して典型的な試行の結果および k-means 法の結果を示す．出発都市をクラスタリングに含める k-means 法と含めない k-means 法は同じような値を示したため，結果 が 重 なって 表 示 さ れ て い る ．い ず れ の 場 合 も多目的進化型 ANNs の解が k-means 法の解を優越している．
出発都市の位置により f1 の値は当然異なるが，共通の出発都市をもつ場合 (図 4,5)，多目的進化型 ANNs で得られた非劣解集合の中に f1 がより小さく，かつ，f2 がより小さい解があり，k-means法と比較して提案手法の有効性が確認できる．
これは，多目的進化型 ANNs が f1 と f2 を改善するアプローチであるのに対し，k-means 法は都市間距離の近さだけで都市群を各セールスマンに割り当てるので，f2 を改善する要因をもたないためである．
一 方 ，共 通 の 出 発 都 市 を も た な い 場 合 (図 6)，
多目的進化型 ANNs で得られた非劣解集合の中にf2 がより小さい解があるものの，非劣解のいずれもが f1 に関して k-means 法と比較してそれほど良 い 結 果 が得 ら れ てい な い．

5.3.2

63000

64000
f165000

66000

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

1

eann clustering
kmeans w/ depo
kmeans w/o depo

0.8
0.6
f2

5.3.1

eann clustering
kmeans w/ depo
kmeans w/o depo

0.4
0.2
061300

61400

61500
f161600

61700

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

10.8

eann clustering
kmeans

0.6
f2

5.3

10.4

選好解

多目的進化型 ANNs で得られた非劣解集合から，f2 が 0 に近くなくても f1 が小さい解が良いという観点から筆者が主観で選んだ選好解の各目的関数値および割り当て都市群の巡回路長を表 2-4 に示す．f1 を主として選んだ解であっても，f2 に関し て 多 目 的 進 化 型 ANNs で 得 ら れ た 解 は kmeans
よって得られた解の約 30〜40%であり，各セールスマンの巡回路長が平均化されていることがわ
かる．以降では，これら選好解について述べる．

172

0.2
061200 61300 61400 61500 61600 61700
f1Fig. 6 割り当て都市群ごとに出発都市をもつ場
合のパレートフロント

進化計算シンポジウム2021（2021/12/25-26）

Table 2 出発都市が外側に位置する場合に得られ た巡 回 路 長 と 目的 関 数値
ANN
kmeanskmeansw/ depo w/o depo
L1 60143.659636.3
59221.2
L2 62874.8
59167.559556.1
L3 64658.7
76038
76038
f1
f2

62559.0
0.069829

64947.3
0.221869

Table 4 割り当て都市群ごとに出発都市をもつ場 合に得られた巡回路長と目的関数値
ANN
kmeansw/ depoL1
58799.7
54661.9
L261998.3
58539.9
L362840.0
70607.7

64938.4
0.221164

f1
f2

6

Table 3 出発都市が中心に位置する場合に得られ た巡 回 路 長 と 目的 関 数値
ANN
kmeanskmeansw/ depo w/o depo
L158532.1
54669.2
54669.2
L264557.0
58952
58952
L361097.5
71087.871087.8
f1
f261395.5
0.0933272

61569.70.230963

61569.70.230963

図 7(a), 8(a), 9(a) は 0.01 刻みで 100 × 100 の格子状 に 分 布 し た 10000 個 の 点 の 位 置 座 標 を ANN に入力したときの出力 k ∈ {1, 2, 3} を色で示し，都市の位置には黒点が記してある．これらは ANNsが 入 力 空 間 (都 市 座 標 平 面) を ど の よ う に 分 割 して い る か を示 して い る．
こ れ に 基 づ い て eann に よって 得 ら れ た 巡 回 路
を図 7(b), 8(b), 9(b) に示す．割当てられた都市群が縦に長い，カーブしている，扇状に広がっているなどの特徴がある．また，出発都市が都市群の外側に位置する場合，都市群の中心に出発都市を設置する場合や共通出発都市を持たない場合と比較して，都市の割り当て方が大きく異なることがわかる．kmeans によって割り当てられた 都 市 群 の 巡 回 路 を 図 7(c), 7(d), 8(c), 8(d), 9(c)に示す．黄色でプロットしたクラスタ中心のまわり に 都 市が 割当 て ら れてお り，出発 都 市の位置
は あ ま り影 響を 与 え ていな い よ う に 思 われる．
以 上 よ り，提 案 手 法 で は 出 発 都 市 の 位 置 に 適
応して，各セールスマンで平均化された短い巡回 路 を 獲得 でき て い ること が わ か る ．

173

61211.1
0.0642263

61269.80.225837

おわりに本研究では複数巡回セールスマン問題に対し，多目的進化計算を用いて設計する人工神経回路網を用いて訪問都市群の割り当てを行い，割り当てられた都市群の巡回路を近似解法を用いて解 く 手 法 を 提 案 し た ．4461 都 市 問 題 に 適 用 し ，k-means 法よりも提案手法は良い目的関数値を示した．また，提案手法は出発都市の位置に適応して，各セールスマンで平均化された短い巡回路を獲得できていることがわかった．
今後，セールスマン数を増やした実験を行う．
これらの結果をもとに，複数ドローンの飛行経路計画問題に取り組む予定である． 出発都市を離着陸を行う地点，巡回する都市を通過点 (ウェイポイント) に対応させて考えると MTSP と捉えら れ る ．ま た ，一 般 的 な MTSP で は セ ー ル ス マン同士の経路が交錯していても問題にしないが，複数ドローンの飛行経路計画では交錯は衝突につながるため，衝突回避を目的関数に含めた実験を行っていきたい．

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

進化計算シンポジウム2021（2021/12/25-26）

参考文献
11) 山 本 ，久 保 「 巡 回 セ ー ル ス マ ン 問 題 へ の 招 待 」
朝 倉 書 店 ， 19970.82) ウィリアム・J・クック，「驚きの数学 巡回セール
ス マ ン 問 題 」青 土 社 ，2013
y0.63) Concorde
TSPsolver,
http://www.math.uwaterloo.ca/tsp/concorde/

0.40.24) 永田，小林，巡回セールスマン問題に対する交叉：枝 組 み 立 て 交 叉 の 提 案 と 評 価 ，人 工 知 能 学
会 誌 ，Vol.14, No.5, pp.848–859, 1999

000.2

0.40.60.81x5) M. Dorigo, K. Socha, An Introduction to AntColony Optimization, Approximation Algorithms
and Metaheuristics, CRC Press, 2007(a) eann に よ る 割 当 て16) 渡邊，小野，松永，金川，高橋，ファジィc-means法を用いた複数巡回セールスマン問題の一解法，日本ファジィ学会誌, Vol.13, No.1, pp.119–126, 2001

0.90.80.70.67) 坂本，延寛，鈴木，山本，古川，渡辺：局所クラス タ リ ン グ 組 織 化 法 に よ る n-TSP に 解 法 ，2008
年度精密工学会北海道支部学術講演会講演論文集 ，pp.35–36, 2008

0.50.40.30.20.18) X. Xu, H. Yuan, M. Liptrott, M. Trovati: Two
Phase Heuristic Algorithm for The Multipletravelling Salesman Problem, Soft Computing, 22,pp.6567–6581, 2018

000.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

10.9

1(b) eann に よ る 巡 回 路
19) 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, 2009

0.90.80.7
0.60.50.410) 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, 2007

0.3
0.20.1000.1

0.2

0.3

0.4

0.50.60.70.8(c) 出 発 都 市 を kmenas に 含 め な い 場 合 の 巡 回 路11) 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, 201910.90.80.70.612) TSPLIB,
http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/

0.5
0.4
0.30.213) K. Helsgaun, General k-opt submoves for the LinKernighan TSP heuristic, Mathematical Programming Computation, 1:119-163, 2009

0.1
000.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1(d) 出 発 都 市 を kmenas に 含 め る 場 合 の 巡 回 路

14) LKH-2.0.9
http://webhotel4.ruc.dk/~keld/
research/LKH/

Fig. 7 出発都市が外側に位置する場合に得られた巡回路

174

進化計算シンポジウム2021（2021/12/25-26）

10.8

y0.6
0.4

1

0.2

0.8

00.2

0.4

0.6

0.8

0.6

1
y0x

0.4

(a) eann に よ る 割 当 て

0.2

10.9

00.8

00.2

0.4

0.6

0.8

10.7

x

0.6

(a) eann に よ る 割 当 て

0.5
0.4
1
0.3
0.9
0.2
0.8
0.1
0.7
00

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0.6

(b) eann に よ る 巡 回 路

0.5
0.4

1
0.3
0.9
0.2
0.8
0.1
0.7
00

0.6

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0.9

1

(b) eann に よ る 巡 回 路

0.5
0.4
1
0.3
0.9
0.2
0.8
0.1
0.7
00

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0.6

(c) 出 発 都 市 を kmenas に 含 め な い 場 合 の 巡 回 路

0.5
0.4

1
0.3
0.9
0.2
0.8
0.1
0.7
000.6

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

(c) kmenas に よ る 巡 回 路

0.5
0.4

Fig. 9 割り当て都市群ごとに出発都市をもつ場
合 の巡回路

0.3
0.2
0.1
00

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1(d) 出 発 都 市 を kmenas に 含 め る 場 合 の 巡 回 路

Fig. 8 出発都市が中心に位置する場合に得られた巡回路

175