日本ソフトウェア科学会第 37 回大会 (2020 年度) 講演論文集

互いに独立した複数の巡回路を構築する
アントコロニー最適化手法
岩崎 悠

長谷部 浩二巡回セールスマン問題 (Traveling Salesman Problem: TSP) は，与えられた N 頂点からなる重み付き完全グラフ
に対し，1 人のセールスマンがすべての頂点を 1 度ずつ通るようなパスの最小コストを求める組合せ最適化問題である．本研究ではこの TSP を拡張し，互いに辺を共有しない K 本の巡回路のコストの和ならびに平均を最小化する
2 つの問題を提案する．この拡張した問題は，元の TSP と比較して計算量の観点から求解がより困難である．そこで本研究では，アントコロニー最適化 (Ant Colony Optimization: ACO) を応用した KI-Average-ACO という近似解法を提案する．具体的には，K 体のアリを複数同時に移動させ貪欲にコストの平均化を行い，2-opt 法を応用
してパスの構築成功確率を増加させる．以上で述べた KI-Average-ACO による近似解と二分探索を用いた二次計画法による近似解を比較した結果，bays29 というグラフで K = 6 個の巡回路を構築する場合 KI-Average-ACO は二次計画法で求められたコストの約半分に留まる巡回路を求めることができた．

1 はじめに巡回セールスマン問題 (Traveling Salesman Prob-

lem: TSP) は代表的な組合せ最適化問題の 1 つである [4]．この問題は，N 個の都市と都市間を結ぶ重み付き辺からなる完全グラフにおいて，すべての都市を

1 つずつ訪問するような最短の巡回路を求める問題で図1ある．TSP はグラフ理論における NP 困難な組合せ

K = 2 個の互いに独立した巡回路．

N = 8 の完全グラフにおける最適化問題として有名であり，さまざまな多項式近似
アルゴリズムやヒューリスティックアルゴリズムが提問題にも応用されている [4]．

案されている．TSP は多くのアルゴリズムのベンチ

TSP の巡回路を求めるアルゴリズムは物流や旅客マークとしても有用な問題であるほか，ジョブショッ

輸送の計画などに幅広く応用されている．こうした従プスケジューリングや車両配送問題などの他の最適化

来の TSP のアルゴリズムは経路を 1 つ求めるためにAnt colony optimization for ﬁnding multiple mutuallyindependent circuits.
This is an unrefereed paper. Copyrights belong to
the Author(s).
Yu Iwasaki, 筑波大学大学院理工情報生命学術院 シス テ ム 情 報 工 学 研 究 群 情 報 理 工 学 位 プ ロ グ ラ ム,
Graduate School of Science and Technology Degree
Programs in Systems and Information Engineering
Master’s Program in Computer Science, Universityof Tsukuba.
Koji Hasebe, 筑波大学システム情報系, Faculty of Engineering, Information and Systems.

用いられる．しかしながら，実世界における配送計画
やネットワーク経路の最適化などへの応用を考えた際には，複数の独立した巡回路を同時に求められると便利な場合がある．例えば，配送システムを構築する際にあらかじめ配送経路を複数個求めて冗長化することにより，自然災害や交通状態への耐障害性の向上が期待される．
そこで，本研究では完全グラフにおける K 個の互
いに独立したコストの合計が最小となるような巡回

路の組を求める問題である K-Independent Traveling

性が高くなり，独立した巡回路の構築失敗率が増加

Salesman Problem (KI-TSP) を提案する．互いに独してしまう．そこで，構築の失敗率を抑えるために 2立した巡回路とは，図 1 のように，K 個の TSP によ

つのヒューリスティックを用いる．1 つ目は余裕残余る経路が 1 本も辺を共有することないような巡回路度であり，移動先の頂点候補が少ない危険な頂点にの組を意味する．KI-TSP の解を求めることで，コス優先してアリが移動するための指標である．2 つ目はトの合計ができるだけ小さい K 個の巡回路を用意す

2-best-opt であり，2-opt と呼ばれるアルゴリズムをることができる．しかし，K 本のパスの形状につい応用した手法である．K 個の巡回路のうち，重複して KI-TSP は考慮していないため，形状やコストがて利用されている辺を巡回路内でうまく交換するこ

互いに大きく異なる巡回路が構成されやすい．

とによって，重複のない K 個の巡回路に作り変える．

このことから，本研究では KI-TSP の目的関数を変更した K-Independent Average Traveling Salesman

これらのヒューリスティックによって，構築失敗率や目的関数の値である重み付け和を小さくできる．

Problem (KI-Average-TSP) を併せて提案する．こ

本研究では，提案手法を評価するために 3 つの実の KI-Average-TSP は，K 個の互いに独立した巡回験を行った．1 つ目の実験では，KI-Average-ACO で路のコストの合計と分散の重み付け和を最小化する問提案した 2 つのヒューリスティックの組み合わせによ題である．KI-Average-TSP では合計に加えて分散る性能の違いと特徴を検証した．2 つ目の実験ではもコストとして指標に加えることで，K 本の巡回路

KI-TSP，3 つ目の実験では KI-Average-TSP を解くのコストを平均化し似た形状の巡回路を構築できる．

アルゴリズムの比較実験を行った．実験の結果，KI-

提案する KI-TSP ならびに KI-Average-TSP を解Average-ACO における 2-best-opt はなにもヒューリ

くために，本研究ではアントコロニー最適化 (Antスティックを用いない場合と比べて最大で 4 倍近くコ

Colony Optimization: ACO) の基本モデルである

ストを改善することができた．一方，余裕残余度は

Ant System を応用した手法を提案する [1]．ACO は，コストの改善は小さく実行時間は長くなってしまう

現実のアリの群れが餌を探すときに最短経路を発見

が，大きいグラフにおいて構築失敗率を減らすことする過程にヒントを得たメタヒューリスティクスによができる有用性が示された．KI-TSP では KI-ACO

る探索アルゴリズム手法である．ACO は，巡回セー

が，KI-Average-TSP では KI-Average-ACO がより

ルスマン問題などの多くの離散的な組合せ最適化問

コストを小さくすることができ，構築する巡回路が題に応用されている．

多い場合は数理最適化を用いた近似解よりも 2 倍

KI-TSP を解くための KI-ACO では，Ant System

近くコストの小さい巡回路を構築できた．これらのを K 回だけ同じグラフに対して実行する．k 回目のことから，KI-ACO は KI-TSP の近似解を求めるア

Ant System によって求められた 1 個のパスに含まれルゴリズムとして有用であると考えられる．また，るグラフの辺のフェロモンを 0 とし辺のコストを無

KI-Average-ACO は 2 つのヒューリスティックを用限大とする．これによって，k + 1 個目のパスの構築いることで構築失敗率を減らしながらコストを小さでは k 個目のパスまでに使用した辺を可能な限り避くでき，グラフや構築する本数が大きくなるほど，二けることができる．なお，辺のコストを無限大にする

分探索を用いた数理最適化と比べて小さいコストをアプローチは先行研究において提案されている [3]．

現実的な時間で求めることができる．

KI-Average-TSP を解く KI-Average-ACO では，本論文の構成は以下の通りである．第 2 節では，本1 体ずつアリに巡回路を構築させる Ant System と異研究の関連研究を説明する．第 3 節では，KI-TSP 並

なり，K 体のアリを 1 辺ずつ同時に移動させる．こびに KI-Average-TSP の定義を説明する．第 4 節でれによって，K 体のアリが平等に好ましい辺を貪欲は，KI-TSP ならびに KI-Average-TSP を解く KI-に利用して分散を小さくすることができる．しかし，

ACO, KI-Average-ACO について説明する．第 5 節アリが移動するにつれて同じ辺を 2 回使用する可能では，提案するアルゴリズムの実験ならびに評価を行う．最後に，結論とこれからの課題について述べる．

定義 1. KI-TSP は G = (V, E, d) において以下の目
的関数の解を求める問題である．

2 関連研究アントコロニー最適化は，現実のアリの群れが餌

min.

る [1]．アリは餌を発見すると巣に戻るときにフェロモンと呼ばれる成分を分泌する．このフェロモンによって，アリの群れは巣から餌までの最短経路を発見∑

dij · xijki∈V j∈V k∈Kまでの最短経路を発見する過程にヒントを得たメタ
ヒューリスティクスによる探索アルゴリズム手法であ

∑∑ ∑

s.t.

∑

xijk ≤ 1(∀i, j)xijk = 1(∀i, k)xjik = 1(∀i, k)

k∈K

∑

j∈V

j∈V

することができる．ACO はこれらの群れの性質を更

uik + 1 − (N − 1)(1 − xijk ) ≤ ujk

新式として定式化することでグラフネットワークに関

xijk ∈ {0, 1}する問題の近似解を求めることができる．このうち，

0 ≤ uik ≤ N − 1(∀i, j, k)

TSP は ACO に関するベンチマークとして利用されている．

変数 xijk はアリ k による頂点 i から頂点 j へ向か

これらのアントコロニー最適化は，トラックなどのう辺の使用の有無を表す．変数 uik は巡回セールス

配送車でデポ (車の発着地点) から顧客の家まで資源マン問題のパスを効率よく探索するための MTZ 制を届ける Vehicle Routing Problem にも適用されて約である．また，これ以降 K 個の巡回路のコストのいる [6]．また，複数のセールスマンがデポから互い

合計 (すなわち，KI-TSP における目的関数の値) をに分担して都市を訪問するような部分巡回路を構築

costsum と表記する．

する Multiple Traveling Salesman Problem でも良い結果を示している [2]．

3. 2 KI-Average-TSP

一方で，完全グラフにおいて互いに複数の独立した

KI-Average-TSP は，グラフ G = (V, E, d) におけ

巡回経路を求める研究は少ない．Teng の研究 [7] でる K 本の互いに辺を共有しない独立した巡回路の組

は，グラフネットワークにおいて複数のハミルトンパ

み合わせのうち，K 本の巡回路のコストの平均と，分スの成立条件などの補題の証明を数学的に行ってい散の重み付け和を最小化する問題である．その形式的る．しかし，実際に互いに独立した巡回路を構築するな定義は以下の通りである．

アルゴリズムに関する研究は，著者らの知る限り未だなされていない．

定義 2. KI-Average-TSP は G = (V, E, d) において
以下の目的関数の解を求める問題である．

3 問題定義本 論 文 で 扱 う グ ラ フ は G = (V, E, d) （|V | =N, |E| = N (N − 1)/2）と表される重み付き無向min.

costavg + γ · costθvar

(1)

ただし，

完全グラフであり，辺 (i, j) の重みは dij で表される．

3. 1 KI-TSP
本論文で提案する KI-TSP は，グラフ G = (V, E, d)における K 本の互いに辺を共有しない独立した巡回
路の組み合わせのうち，K 本の巡回路のコストの合計を最小化する問題である．その形式的な定義は以下の通りである．

costavg=

costvar=1
costsum ,K
1 ∑ ∑∑((
dij · xijk −Kk∈K i∈V j∈V
1 ∑∑ ∑(
dij · xijk′ ))2 ).
K i∈V j∈V ′k ∈K

ここで，γ, θ は平均と分散の重み付けを行うための4. 2 KI-Average-ACO
4. 2. 1 概要
KI-Average-ACO は K 個の巡回路のコストを平均化するために，通常の ACO と異なり K 体のアリをそれぞれ 1 辺ずつ同時に移動させることでコストの
図2

KI-ACO における巡回路の構築方法．
1 個ずつ巡回路を構築する．

平均化を図る．しかし，K 体のアリを同時に移動させると構築失敗率が増加してしまうため 2 つのヒュー
リスティクスを併用する．1 つ目は余裕残余度であり，パラメータであり，制約は KI-TSP の制約と等しい．

ある頂点から移動できる頂点数が少ない頂点に優先

つまり，目的関数の定義のみが異なる．これ以降 K

的にアリを移動させるための指標である．これによっ

本の巡回路のコストの平均と標準偏差の重み付け和て，多くの移動できる将来性のある頂点を後回しにす(1) を costavva = costavg + γ · costθvar と表す．

ることで構築失敗率を減らすことができる．2 つ目は以上の定義から，KI-Average-TSP は KI-TSP を

2-best-opt であり，K 個の巡回路のうち失敗した巡一般化した問題となっている．KI-Average-TSP にお回路を 2-opt で再構築することで，無駄のない探索をけるパラメータ γ, θ を 0 とすることで K 本の巡回路行うことを目指す．これらのアルゴリズムによって，のコストの平均の最小化の問題となる．KI-TSP では

通常の ACO を K 回繰り返すよりも K 個の巡回路の合計の最小化としているが，平均の最小化と合計の最移動コストを平均化させながら，構築失敗率を小さく小化の結果は等しくなる．

することが可能である．KI-Average-ACO のアルゴ
リズムは，以下のアルゴリズム 1 で示す通りである．

4 アルゴリズム

4. 2. 2 アリの同時移動

4. 1 KI-ACO

KI-Average-ACO では，K 体のアリを 1 辺ずつ同

KI-ACO は構築したい独立した巡回路の個数であ時に移動させることですべてのアリができる限り貪

る K の数だけ Ant System を実行する． k 回目の欲に好ましい辺を使用できるようにする．このとき毎Ant System では，アリとフェロモンを用いて新たに回の移動後にこれまでの合計移動コストの降順にア

1 個の巡回路を構築する．巡回路を構築した後はそのリを並べて，その順番で次のアリの移動を行うよう巡回路に含まれるグラフの辺のフェロモンを 0, コスにする．これによって，移動コストが大きくなってしトを無限大とする．これによって，k + 1 回目以降のまったアリほどより小さいコストやフェロモンの多い

Ant System ではすでに使用された辺に可能な限りア辺を優先的に移動できるため，コストの平均化を貪欲リが移動しなくなり互いに独立したパスを構築できに行うことができる．ただし，KI-ACO のアルゴリ

る．ただし，グラフネットワークのフェロモンはすべズムと同様，アリが移動に使用した辺はコストを無てのサイクルで共有のものとする．例えば，図 2 で限大，フェロモンを逐次に 0 とし可能な限り使われ示すように最初の Ant System で青色の巡回路が構ないようにする．この同時移動による構築方法の例

築され，次の Ant System でオレンジ色の巡回路がを図 3 で示す．ここでは，K = 2 の場合における青構築される．

とオレンジのアリが巡回路を構築する様子を表して

この KI-ACO の方法では，はじめは自由に使用でいる．青とオレンジのアリは 1 辺ずつ同時に移動し，きるコストの小さい辺が多く残っているため，構築さ可能な限り自分または他のアリが使用した辺を再びれる巡回路のコストも小さい．しかし，k のサイクル

使用しないように次の頂点を決定する．また，対応すが進むにつれて使用できる辺の数が減ってコストの大るコードはアルゴリズム 1 の 15 行目である．

きい辺のみが残り，構築される巡回路のコストも大きくなる．

アルゴリズム 1: KI-Average-ACO
1function ki aco(G, N , K)

2

aco(G)

3

ants = [ ]4for i ← 1 to K do

5ants.append(Ant())

6

end

7

for t ← 1 to KT do

図3

KI-Average-ACO における巡回路の構築方法．

4. 2. 3 移動残余度
KI-TSP の K 体のアリを同時に移動させるという

8

make tsps(G, N , K, ants)

性質から，アリの移動にしたがい，他のアリに既に使

9

2 best opt(G, K, ants)

用された辺を使用せざるを得ない状況が多く発生しpheromone update(G, ants)

構築失敗率が増加してしまう．そのため，K 体のア

10
11
12
13
14

end

リが巡回路を重複なく構築する成功回数を増やすた

function make tsps(G, N , K, ants)
for i ← 1 to N dofor j ← 1 to K doants[j].move one edge(G)15

めに余裕残余度と呼ばれるヒューリスティクスを導入
して確率移動式を定義する．

K 体のアリがそれぞれ N 回の移動のうち既に t 回移動していたとし，アリ h が既に訪問した頂点集合を Uh

16

end

とする．このとき，アリ h が頂点 x から矛盾なく移動

17

ants.rsort(key=ant.costsum )できる頂点集合を返す関数を Rht (x) ⊂ V と定義する．

18
19
20
21

end

/ Uk を満たし，矛盾がないとは頂点 y ∈ Rht (x) が，y ∈function 2 best opt(G, N , K, ants)
for i ← 1 to K do
if ants[i].path has duplicated edgethen(x, y) の辺が他のアリ 1, 2, . . . , h − 1, h + 1, . . . , K にまだ使用されていないことである．
このとき，アリ h が頂点 i から次の頂点 j を選ぶ移h
動確率 Pij
を式 (2) のように定義する．ただし，τij

22

ant = ants[i]は辺 (i, j) のフェロモン量，ηij はヒューリスティク

23

alts = [ ]24for j ← 1 to N do

ス値である．また，Nht (i) は t 回目の移動においてアfor k ← 1 to N do

25
26

27

|Rht (j)| で移動確率を割っている．この演算によって，

ant.path[k])移動できる頂点が少ない余裕のない頂点に優先的に

if at.path has no貪欲に移動し，移動できる頂点が多い頂点を後回しに

contradiction then

することができる．これによって，構築失敗率を減ら

alts.append(at)すことができる．時間計算量は乗算で O(N ) だけ追

end
end

30
31

end

32

alts.sort(key=ant.costsum )33

ants[i] = alts[0]

34
35

end
end

では，次の頂点 j からさらに移動できる頂点の個数

at = ant.2 opt(ant.path[j],2829

リ h が頂点 i から移動できる頂点集合である．式 (2)加でかかるが，その分構築失敗率が減少し，より効率的に近似解を探索することが可能である．

Pijh = ∑[τij ]α [ηij ]β1× tα [η ]β[τ]|Rt (i) iu
iu
h (j)|
u∈Nh
1
ηij =
dij

(2)
(3)

!

!

K
∑
τij (t + 1) = ρ · τij (t) +∆hij ,h=1 1((i, j) ∈ lh )costavva∆hij =
0(otherwise)

"

(4)

(5)

#

ρ はフェロモンの残留率，Ch はアリ h の構築した巡回路のコスト，lh はアリ h のパス, costavva は K
個の巡回路のコストの平均と分散の重み付き和であ
図42-best-opt の例

る．ただし，K 個のパスが互いに独立でない場合は，グラフに対するフェロモンの更新式を実行しない．こ4. 2. 4 2-best-opt
K 個の巡回路の構築の成功確率をさらに増やし
costavva を最小化するために巡回路の構築後に 2best-opt というヒューリスティクスを利用してパスを改善する．2-best-opt はアルゴリズム 1 の 19 行目
である．
構築後の K 個のパスにおいて，ある辺 e = (a, b) が複数のアリ F (> 1) 体のパスに重複して利用されているとする．このとき，F 体のアリのパス l1 , l2 , . . . , lF
に対してそれぞれに 2-best-opt を行う．2-best-opt の操作は以下の通りである．図 4 で示す通り，あるパス

l の他のパスにも重複して使用されている辺 e = (a, b)と，l の他の N − 1 本の辺 e′ = (c, d) を 2-opt の操作で交換した場合を考える．このとき，もし交換後に新しくできる２本の辺 e1 = (a, c), e2 = (b, d) がまだどの K 個のパスにも使用されていないならば辺の利用回数を矛盾なく下げることができるため，辺 e′ を辺の交換候補 S に加える．そして，これらの辺の交換候補のうち，辺 e と交換することで最もパス l の移動コストが小さくなるような 1 つの辺 e′ ∈ S を選択して e と 2-opt で交換する．
この 2-best-opt によって，K 個の巡回路の構築の失敗の要因となっている重複辺を貪欲に修正でき，構築失敗率ならびに costavva を小さくすることができる．

4. 2. 5 フェロモン更新
2-best-opt の実行後，K 個のパスが互いに独立した正しい巡回路である場合は，フェロモン更新式 (4)を実行する．フェロモン更新はアルゴリズム 1 の 10行目である．

れは，正しく構築できたときのみ更新を行うことによって探索の集中化を図るためである．

5 実験による評価
5. 1 概要
本節では，4 節で提案した KI-ACO と KI-Average-

ACO のアルゴリズムを評価するために行った 3 つの実験ならびに結果について説明する．

1 つ目の実験は，KI-Average-ACO で提案した 2
つのヒューリスティックの性能検証を行う実験である．この実験によって，KI-Average-ACO におけるヒューリスティックの特徴を明らかとし，以降の実験で使用するヒューリスティックの組み合わせを定める．

2 つ目の実験は，KI-TSP の問題を解くアルゴリ
ズムの比較を行う実験である．比較対象は KI-ACO，

KI-Average-ACO, 数理最適化の 3 つである．
3 つ目の実験は，KI-Average-TSP の問題を解くア
ルゴリズムの比較を行う実験である．比較対象は同様に KI-ACO，KI-Average-ACO, 数理最適化の 3 つである．
これら 3 つの実験における共通のパラメータは表 1
で示す通りである．AT は KI-ACO における k 本目のパスを構築するときに実行する Ant System のサイ
クル数を表す．一方 KT は KI-Average-ACO は K
本のパスを構築するために実行するサイクル数を表す．LT は，アントコロニー最適化が確率的なシミュ
レーションであることから，より確からしい結果を得るために行う実験の試行回数である．

表1

表2

共通パラメータ

parametervalue

フェロモン係数 α1

ヒューリスティック係数 β3フェロモン残留率 ρ

0.97

KI-Average-ACO におけるヒューリスティックの性能比較

instance

name

cost

time

fail

NONE

inf

12

1.00

RES

inf

72

1.00

2BO

1.57 · 105

14

0.88

RES+2BO

1.63 · 105

73

0.90

NONE

7.00 · 104

30

0.99

RES

2.63 · 104

173

0.96

2BO

1.32 · 104

32

0.73

RES+2BO

1.17 · 104

178

0.65

5. 2 ヒューリスティックの性能比較

NONE

1.40 · 106

67

0.98

KI-Average-ACO のアルゴリズムに含まれる余裕

RES

6.56 · 105

702

0.91

2BO

3.49 · 105

70

0.58

RES+2BO

3.92 · 105

696

0.51

Ant-System のアリの数

N

Ant-System のサイクル数 AT

200

KI-Average-ACO のサイクル数 KT

1000

試行回数 LT

10

残余度ならびに 2-best-opt の性能や特徴を計測す

ulysses22

bays29att48

るための実験を行った．本実験では，余裕残余度と2-best-opt の利用の有無 4 通りの組み合わせで比較した．ただし，フェロモン更新は必ず行うものとする．

とで，bays29 のようにグラフによっては最もコスト

TSPLIB [5] と呼ばれる TSP に用いるグラフデータを小さくすることができるほか，bays29 や att48 のセットから頂点数の異なる ulysses22, bays29, att48

ように頂点数の大きいグラフでは構築失敗率を最もの 3 つのグラフを用いて組み合わせを比較する．比小さくすることができる．よって，実行時間に余裕が較の指標は重み付きコスト costavva ，実行時間，そしあり大きなグラフで多くの巡回路を構築する場合はて構築失敗率の 3 つである．ここで，1 本でも同じ辺余裕残余度と 2-best-opt を併用するのが良いと考えを使用してしまった場合は構築失敗とみなす．また，られる．

LT = 1000 回だけ K 本の巡回路を構築しようとする

KI-TSP ならびに KI-Average-TSP の実験では，ため，例えば構築失敗率が 0.48 の場合は 1000 回のより実行時間が短い 2-best-opt のみを用いた KI-

うち 480 回どれか 1 本以上の辺を重複して使用してAverage-ACO を使用することとする．

しまったことを表す．実験の結果は表 2 で示す通りであり，RES は余裕残余度のみを使用する場合，2BO

5. 3 KI-TSP を解くアルゴリズムの比較

は 2-best-opt のみを使用する場合，RES+2BO はど

KI-TSP の問題を解く 3 つのアルゴリズムの性能

ちらも使用する場合，NONE はどちらも使用しないに関する比較実験を行った．比較するアルゴリズム

場合を表す．

は KI-ACO と KI-Average-ACO と数理最適化によ

表 2 から，3 つのグラフそれぞれで 2-best-opt が大る求解である．このうち，KI-Average-ACO では合

きくコストを削減していることが分かる．特に att48計を最小化すればよいため γ = 0, θ = 0 として探索では 1.40 · 106 から 3.49 · 105 に大きくコストを改善を行った．また，数理最適化は 3 節で定義した数式できている．一方，余裕残余度は 2-best-opt よりもコを，Gurobipy と呼ばれる Python のライブラリ上でストを小さくすることはできず，実行時間が長くなっ実装し最適解を求めた．KI-TSP は 0-1 整数計画問題てしまう．これは，余裕残余度は構築の失敗率を防ぐに相当する．

ためにコストを大きくするような辺も使用し，追加計実験で使用するグラフは 29 頂点の bays29 という算量が O(N ) だけかかるためである．特徴すべき点

グラフであり，KI-ACO ならびに KI-Average-ACO

として，余裕残余度は 2-best-opt と合わせて使うこは表 1 のパラメータを用いた．実験結果は図 5 が示

0.– $&2.– $YHUDJH $&202$YHUDJH &RVWV:HLJKWHG &RVWV

0

0

0

.

.

図5

KI-TSP におけるコストの比較．

.– $&2.– $YHUDJH $&202

図6

KI-Average-TSP におけるコストの比較．

すグラフの通りである．MO は数理最適化による求分散の重み付け和を最小化することを目的とする．

解を表し，縦軸は K 本の巡回路のコストの平均，横KI-Average-TSP の最悪時間計算量が O(N !K ) か

軸は構築する巡回路の本数を表す．K = 10 以降におつ二次計画問題に相当するため，一般的に数理最適化

いて MO のグラフが表示されていないが，これは構などにより厳密解を求めることは非常に難しい．実際

築する巡回路の個数に比例して制約式と変数が増加に著者らの実験環境で厳密解を求めた際には，N = 8

するため計算量が大きくなり，今回の実験環境では厳などの比較的小さいグラフや K = 3 などの少ない巡密解を求めることができなかったことを表す．

回路の個数の場合しか解を得ることができなかった．

KI-ACO は，KI-Average-ACO と比較してより厳そのため，本実験で使用する gr17 という N = 17 頂密解に近い巡回路を構築できた．これは 1 個の巡回点のグラフでも同様に厳密解を求めることはできな路を構築するごとにグラフのフェロモンをアリの群かった．そこで本研究では，比較対象として数理最適

れが変化させたことが原因であると考えられる．ま化と二分探索を用いて近似解を求めるアルゴリズム

た，KI-Average-ACO は K 体のアリによる 1000 回を採用した．これは，分散が K 個の巡回路から計算のみのサイクルであるが，KI-ACO では N 体のアリされることに着目し，最も大きい巡回路のコストとが AT = 200 のサイクルを K 回繰り返すため探索最も小さい巡回路のコストの差 d がどこまで小さく

回数自体が大きいことも寄与していると考えられる．

できるかという制約式を加えて予め定めた猶予時間

K = 14 個の巡回路を構築できなかった KI-ACO に内で計算できるかを二分探索する．これによって，猶対して，KI-Average-ACO は K = 14 個の構築に成予時内で探索できる最も小さいコストの差 d を計算

功しており独立した多くの巡回路を構築することにでき，そのときの解は K 個の巡回路のコストの分散適しているのではないかと考えられる．

が近似解ではあるが小さくなっている．本実験では，二分探索における 1 回の数理最適化の巡回路の構築

5. 4 KI-Average-TSP を解く
アルゴリズムの比較における猶予時間を 300 秒とした．
実験結果は図 6 ならびに図 7 の示すグラフの通り

KI-Average-TSP の問題を解く 3 つのアルゴリズである．図 6 が示すように，KI-ACO のアルゴリズ

ムの性能に関する比較実験を行った．比較するアルムを KI-Average-TSP に用いると分散が非常に大きゴリズムは KI-ACO と KI-Average-ACO と数理最くなる．これは，KI-ACO が現時点で構築できる最適化による求解である．このとき，KI-Average-TSP

小の巡回路を構築し，K 個の巡回路のコストが互いの重み付きパラメータは γ = 1, θ = 1 とし，平均とに大きく異なるためである．図 7 で K = 7 の MO の実験では，KI-Average-ACO における 2-best-opt
N:HLJKWHG &RVWV

Nと余裕残余度の性能，KI-ACO，KI-Average-ACO の.– $YHUDJH $&202

アルゴリズムの性能の検証を行った．ヒューリスティッ

N

クの性能を調べる実験では 2-best-opt はコストの削N減に大きく寄与し，余裕残余度は構築失敗率を減らす

N

ことでより大きなグラフでの求解を可能とした．また，N

KI-ACO は合計の最小化に優れ，KI-Average-ACO

N

は KI-Average-TSP の問題で二分探索を用いた数理
最適化の解よりも構築する巡回路が大きいときにコ.

図7

KI − ACO を除いた

KI-Average-TSP におけるコストの比較．

ストを小さくできた．
本 研 究 の 今 後 の 課 題 は ，KI-TSP な ら び に KI-

Average-ACO をより現実的な問題に展開させることである．すべての辺を 1 度しか使えないという状況

グラフが途切れていることは，K = 7 において MOは運送やスケジューリングでも少なく，時間をずらす

が猶予時間 300 秒で 7 個の巡回路の組を 1 通りも発ことで 2 度以上同じ辺を使用できる．そのため，い見することができなかったことを表す．巡回路の構築

くらかの辺は複数の巡回路で使用してよいなど，現実の本数が 1 本から 4 本の間では MO の二分探索によの運送やネットワークのトポロジの問題に適用しやする数理最適化がより重み付き和を小さくすることにいモデルに変更したアントコロニー最適化のアルゴ

成功している．構築する本数の多い K = 5, 6, 7 におリズムの開発を行いたいと考えている．

いては KI-Average-ACO がよりコストを小さくできている．この結果から，KI-Average-ACO はグラフ

参 考 文 献が大きくなっても許容できる現実的な時間で近似解[1] Dorigo, M. and Stützle, T.: Ant colony optimization: overview and recent advances, Handbook of
metaheuristics, Springer, 2019, pp. 311–351.
[2] Junjie, P. and Wang, D.: An Ant Colony Optimization Algorithm for Multiple Travelling Salesman Problem., 01 2006, pp. 210–213.
[3] Little, J. D., Murty, K. G., Sweeney, D. W., andKarel, C.: An algorithm for the traveling salesman
problem, Operations research, Vol. 11, No. 6(1963),
pp. 972–989.
[4] Matai, R., Singh, S. P., and Mittal, M. L.: Traveling salesman problem: an overview of applications, formulations, and solution approaches, Traveling salesman problem, theory and applications,Vol. 1(2010).
[5] Skorobohatyj, G.:
MP-TESTDATA - The
TSPLIB Symmetric Traveling Salesman Problem
Instances, http://elib.zib.de/pub/mp-testdata/
tsp/tsplib/tsp/.
[6] Tan, W. F., Lee, L. S., Majid, Z. A., and Seow,
H. V.: Ant Colony Optimization for Capacitated
Vehicle Routing Problem, Journal of Computer Science, Vol. 8, No. 6(2012), pp. 846–852.
[7] Teng, Y.-H., Tan, J. J., Ho, T.-Y., and Hsu, L.H.: On mutually independent hamiltonian paths,
Applied Mathematics Letters, Vol. 19, No. 4(2006),
pp. 345 – 350.

を探索できるアルゴリズムであると考えられる．しかし，K が大きくなるにつれて KI-Average-ACO の
コストの標準偏差が大きくなってしまっている．これは，KI-Average-ACO が貪欲に探索し局所解に陥っているのが原因である．

6 まとめと今後の課題
本研究では，巡回セールスマン問題を拡張した

KI-TSP ならびに KI-Average-TSP と呼ばれる 2 つの問題を提案した．また，これら 2 つの問題を解く手法としてアントコロニー最適化を応用した KI-ACOと KI-Average-ACO を提案した．KI-ACO は Ant

System を K 回繰り返すことで K 本の巡回路のコストの合計の近似解を求めた．KI-Average-ACO は K
体のアリを同時に移動させることによって分散を小さくし，2-best-opt ならびに余裕残余度と呼ばれるヒューリスティックを用いることで構築失敗率を減らすことを目指した．