粘菌ネットワークを用いた時間枠制約付き巡回セールスマン問題の解法
True Slime Mold Network for Traveling Salesman Problem with Time Windows
加藤 由人
KATO, Yuto

概要：近年，粘菌と呼ばれる森の土の中などに存在する単細胞生物が注目されている．粘菌が採餌行動の際に自身の体で構築するネットワークは，しばしば複数の餌場の最短経路を示すことが知られている．粘菌の採餌行動を基に中垣らにより提案された粘菌数理モデルは，さまざまな問題への適用が期待されており，巡回セールスマン問題への適用手法が榎原らにより提案された．本研究では，粘菌数理モデルのさらなる適用可能性を示すことを目的として，粘菌数理モデルを巡回セールスマン問題の中でもより制約の厳しい時間枠制約付きの問題に対応させる．適用事例として北海道のすべての道の駅を営業時間内に最短日数で訪問する場合を取り上げる．
Summary: Recently, true slime mold, a monad that lives in woods, has attracted a great deal of public attention. The slime’s bodyin its gulping behavior shows the shortest route between the 2 food places. From this activity, a mathematical model was proposed byNakagaki et al. it is expected for applying various problems. Ebara et al. proposed a solving method for Traveling Salesman Problem(TSP) using this model. This study’s purpose is to show more this model’s possibility, I propose a solving method for Traveling
Salesman Problem with Time Windows (TSP-TW) using the model. This study’s data is “Collecting series of stamps at Michi-noEki (roadside rest area) in Hokkaido”.
キーワード: 粘菌・ネットワーク・時間枠制約付き巡回セールスマン問題
Keywords: True Slime Mold, Network, Traveling Salesman Problem with Time Windows
１．はじめに近年，粘菌と呼ばれる森の土の中などに生存する単細胞生物の行動原理が注目されている．粘菌は採餌行動の際に自身の体で栄養を運ぶ管のネットワークを構築する．
ネットワークはしばしば複数の餌場の最短経路を示すことが知られている．粘菌の採餌行動を元に中垣らにより提案された粘菌数理モデル[1]は，さまざまな問題への適用が期待されており，巡回セールスマン問題(TravelingSalesman Problem; TSP)への適用手法が榎原らにより提案された[2]．TSP を実際の応用事例に適用する際には，さまざまな制約条件を考慮する必要がある．中でも，物流事業などの業務特性を考慮する場合，時間的要素は必要不可欠である．本研究では，粘菌数理モデルのさらなる適用可能性を示すことを目的として，粘菌数理モデルをTSP の中でもより制約の厳しい時間枠制約付き巡回セール ス マ ン 問 題 (Traveling Salesman Problem with TimeWindows; TSP-TW)に対応させる手法を提案する．提案手法では，榎原らの適用手法に加えて，時間枠の重みを粘菌数理モデルに反映させることにより，TSP-TW に対応可能なネットワークを構築させ，巡回路を求める．北海
道の「道の駅」スタンプラリー企画を対象問題として取り上げ，評価実験により提案手法の有用性を検証する．

２．巡回セールスマン問題
TSP とは，N 個の都市を一度ずつ訪問して出発地に戻る巡回路の中で，総移動コストが最小となるようなものを求める組み合わせ最適化問題である[3]．N 個の都市の集合を𝑉 = {1, … , 𝑁}，都市𝑖と都市𝑗の間の移動コストを𝐶𝑖𝑗 とすると，目的関数は式(2.1)で表される．ただし，𝑥(𝑘)は𝑘番目に訪問する都市を表す．
𝑁−1min⁡(∑ 𝐶𝑥(𝑘)𝑥(𝑘+1) + 𝐶𝑥(𝑁)𝑥(1) )𝑘=1

N 個の都市を巡回する TSP の解候補数は(𝑁 − 1)!で表される．都市数の増加に伴い，解候補数が指数関数的に増大するため，全探索により最適解を有限時間内に求めることは極めて困難である．そのため，長時間の探索により最適解を求めるよりも，最適解に充分近い準最適解を短時間で求めるほうが実用的であると考えられており，短時間で準最適解を求めるメタヒューリスティクスと呼ばれる手法が注目されている．
２―１．時間枠制約付き巡回セールスマン問題
TSP-TW は，各都市に対して訪問可能な時間帯が設定されている TSP である．各都市にはそれぞれ異なる時間枠制約が設定されており，時間枠外の訪問はできないと

本研究内容は，情報処理学会第 77 回全国大会において発表する予定である．

1383106 加藤

(2.1)

由人

1／4

いう制約条件が加わっている．
２―２．北海道「道の駅」スタンプラリー
道の駅とは，国土交通省に登録された一般道路上の休憩施設である．2015 年 1 月現在，北海道には 114 ヶ所の道の駅が登録されており，各道の駅に設置されたスタンプを押印し，スタンプの数に応じて賞品などが与えられるスタンプラリー企画が開催されている．北海道は都市が広域に分散している広域分散型の地域社会を形成しており，都市間距離が全国の 1.5～2.0 倍であることから，すべての道の駅を訪問することを考える場合，総移動コストが訪問順に大きく依存する．
３．粘菌ネットワーク
３―１．粘菌の迷路解き
粘菌とは，森の土の中などに生存する単細胞生物である．粘菌の体には栄養が流れる複雑な管のネットワークが構築されている．2000 年，粘菌が迷路の最短経路を表すことが実験で示された．粘菌を迷路全体に置き，餌を2 ヶ所に設置すると，粘菌は体の形を変化させながら餌場に向かって移動し始める．迷路の行き止まりの経路に伸びていた体を縮め，縮めた分の体で餌場に伸びていき，2 ヶ所の餌場をつなぐ各経路に太い管を形成する．各経路のうち，遠回りの経路の管は次第にやせ細り，消滅する．最後に残る経路は，しばしば迷路の最短経路であることが確認された．空腹を満たすという欲求と一つの個体として分裂したくないという欲求の 2 つを満たそうとした結果，最短経路に管を残したと考えられている．
３－２．粘菌数理モデル
中垣らは，３－１節で述べた粘菌の挙動を数理モデルとして再現した[1]．数理モデルでは，粘菌の体をグラフで表現する．グラフのエッジは粘菌の管，ノードは管のつなぎ目である．餌場所であるノードを𝑁1 , 𝑁2 として，その他のノードを𝑁3 , 𝑁4 , 𝑁5 , …と表し，𝑁𝑖 と𝑁𝑗 を結ぶエッジを𝑀𝑖𝑗 と表す．𝑁𝑖 と𝑁𝑗 の圧力をそれぞれ𝑝𝑖 , 𝑝𝑗 であるとすると，長さが𝐿𝑖𝑗 ，半径が𝑟𝑖𝑗 であるエッジ𝑀𝑖𝑗 の単位時間あたりの餌の流量𝑄𝑖𝑗 は式(3.1)で表される．
𝜋𝑟 4 (𝑝𝑖 − 𝑝𝑗 )𝐷𝑖𝑗(3.1)
𝑄𝑖𝑗 ==⁡(𝑝 − 𝑝𝑗 )
8𝜂𝐿𝑖𝑗
𝐿𝑖𝑗 𝑖
⁡𝐷𝑖𝑗 はコンダクティビティ，すなわち流れやすさであり，式(3.2)で表される．𝜂は流体の粘性率である．
𝜋𝑟 4(3.2)
𝐷𝑖𝑗 = ⁡
8𝜂
ネットワーク全体の餌の流量は一定であることから，各ノード𝑁において式(3.3)が成り立つ．ただし，𝑄0 はネッ
トワークにおける餌の全流量を表す．
+𝑄0 ⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡(𝑖 = 1)
(3.3)
∑ 𝑄𝑖𝑗 = {−𝑄⁡0 ⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡(𝑖 = 2)0⁡⁡⁡⁡⁡⁡⁡⁡⁡(𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒)𝑗
流量に依存したコンダクティビティの変化量をコンダクティビティ・ダイナミクスと呼び，式(3.4)で表す．

1383106 加藤

𝑑𝐷𝑖𝑗= 𝑓(|𝑄𝑖𝑗 |) − 𝐷𝑖𝑗
𝑑𝑡|𝑄𝑖𝑗 |𝛾𝑓(𝑄𝑖𝑗 ) =1 + |𝑄𝑖𝑗 |𝛾(3.4)(3.5)

３－３．ＴＳＰへの適用手法
粘菌ネットワークを TSP へ適用する手法が榎原らにより提案された[3]．適用手法の概略を以下に示す．
Step1.
Step2.
Step3.
Step4.
Step5.
Step6.

メッシュの作成
コンダクティビティの初期化
ネットワークの構築
巡回路の作成Step2～Step4 の反復
局所探索法による解の改善

まず，粘菌の初期状態として三角形分割を用いてメッシュを作成する．三角形分割の手法には，ドロネー三角形分割を用いる．次に，粘菌ネットワークを構築するために各エッジのコンダクティビティ𝐷𝑖𝑗 の初期値を次のように設定する．
奇数回目
1 回目は，すべてのエッジに対してコンダクティビティを 1 と与える．以降はその時点での最良解と前回の探索で求めた解に共通するエッジ𝑀𝑖𝑗 に通常よりも大きな値𝑑(𝑑 > 1)を与える．
偶数回目
前回の探索で求めた解に含まれるエッジ𝑀𝑖𝑗 に通常よりも大きな値𝑑(𝑑 > 1)を与える．
初期化後，三角形分割を行ったグラフ G および，初期化で決定された各エッジの𝐷𝑖𝑗 を元に，粘菌ネットワークを次のように構築する．
奇数回目
ノード間距離が一定以上であり直接接続されていないノードをランダムに 4 点選択して，流入点および流出点としてそれぞれ 2 点ランダムに割り振る．
偶数回目
前回の探索により求めた解に含まれるエッジから，グラフ𝐺に含まれないエッジを取り除いたグラフ𝐺′を作成する．グラフ𝐺′において，接続エッジ数が 1以下のノード集合𝑉′を求める．𝑉′に含まれるノードにのみ餌を設置してネットワークを構築する．
構築されたネットワーク N における各エッジの𝐷𝑖𝑗 を元に次の要領で巡回路を作成する．
Step1. 𝐷𝑖𝑗 の小さなエッジを除去
ネットワーク N で使用されているエッジ𝑀𝑖𝑗 を𝐷𝑖𝑗 の昇順に並べた集合𝐸1 を求め，𝐸1 を𝐷𝑖𝑗 の小さいものから順にエッジ𝑀𝑖𝑗 を除去する．
各ノードにおける接続エッジ数が 1 以下にならないようにする．𝐸1 に除去対象のエッジがなくなれば処理を終了する．
Step2. 𝐷𝑖𝑗 の大きなエッジを接続
エッジ𝑀𝑖𝑗 を𝐷𝑖𝑗 の降順に並べた集合𝐸2 を求める．𝐸2
由人

2／4

を𝐷𝑖𝑗 の大きなものから順にエッジ𝑀𝑖𝑗 を接続する．
エッジ𝑀𝑖𝑗 を接続することにより閉路ができる場合，接続しない．
Step3. 残りのノードを接続
接続エッジ数が 1 以下のノード間をつなぐエッジを距離の昇順に並べた集合𝐸3 を求め，𝐸3 に含まれるエッジ𝑀𝑖𝑗 を距離の短い順に閉路をつくらないように接続する．最後に経路の両端をつなぎ巡回路を得る．
巡回路作成の際，残りのノード同士を強制的に接続したことにより，他のエッジと交差した非常に長いエッジが発生し解品質が悪化したため，一定回数 2-opt 法による局所探索を行い，解を改善する．
４．時間枠制約付き問題への適用提案手法では，榎原らにより提案された TSP への適用手法[3]に変更を加え，ネットワークを構築する際に時間枠制約の重みをエッジのコンダクティビティに付与することにより，時間枠制約付きの問題に対応させる．
４－１．提案手法の概略
提案手法の概略を以下に示す．
Step1. メッシュの作成
Step2. ノード選定
Step3. 時間枠制約の重みを付与したコンダクティビティの初期化
Step4. ネットワークの構築
Step5. 巡回路の作成
Step6. Step2.～Step5.を未訪問地点集合𝑊がL𝑊 = 𝜙となるまで繰り返す
まず，ネットワークを構築する前処理として，１回分のネットワーク構築範囲出発地から当日中に訪問可能なノードのみを選定して，ネットワークの構築範囲を決定する．
図 4.1 のように未訪問地点集合𝑊から，式(4.1)を満たすノード集合𝑊′を
図 4.1 ノード選定求める．ただし，𝐶𝑑𝑎 は出発地𝑑と目的地𝑎間の移動コスト，𝑙𝑎 は目的地𝑎の時間枠終了時刻，𝑡は出発時刻である．
(4.1)
𝑡 + 𝐶𝑑𝑎 ≤ 𝑙𝑎
次に，ネットワーク構築のために各エッジのコンダクティビティ𝐷𝑖𝑗 を設定する．図 4.2 のように優先的に訪問すべきノード同士が強固に接続されるように，…優先度の高い訪問地点 集合𝑊′のノード𝑁𝑖 を時間枠終了時刻𝑙𝑖 の早い順に並図 4.2 時間枠の重み付与 べた集合𝑊′′を求め，𝑊′′を結ぶエッジ𝑀𝑖𝑗 に𝑙𝑖 の早い
1383106 加藤

順に通常より大きなコンダクティビティ値𝑑(𝑑 > 1)を与える．初期化後，３－４節で述べた手法と同様に，粘菌数理モデルによりネットワークを構築する．餌の流入点と流出点はランダムにノードを選択してそれぞれ 2 点ずつ，計 4 点決定する．最後に，構築したネットワークにおける各エッジの𝐷𝑖𝑗 から巡回路を作成する．巡回路の作成方法には３－４節で述べた手法を用いる．
４－２．北海道「道の駅」スタンプラリー問題への適用
北海道「道の駅」スタンプラリー企画を対象問題とする場合，北海道道路情報総合案内 Web サイト[4]より取得した地点間移動コストデータを元にメッシュを作成して，粘菌ネットワークの初期状態とする．道の駅𝑖と道の駅𝑗を結ぶ実際の経路をエッジ𝑀𝑖𝑗 と定義する．ただし，道の駅𝑖と道の駅𝑗を結ぶ実際の経路上に道の駅𝑖，道の駅𝑗以外の道の駅が 1 つ以上存在する場合，𝑀𝑖𝑗 を定義しない．
５．評価実験
提案手法の有用性を検証するため，評価実験を行った．
５－１．実験方法
北海道の「道の駅」スタンプラリー企画を取り上げ，総移動コストが最小となるような訪問順を求める．提案
手法および遺伝的アルゴリズム(Genetic Algorithm; GA)を用いた手法による探索をそれぞれ 10 回ずつ行い，結果を比較する．GA とは，生物の進化の過程を模倣した探索アルゴリズムであり，代表的なメタヒューリスティクス手法の一つとして知られている．
本実験において，移動コストは所要時間(分），各道の駅における滞在時間は 30 分，出発地および到着地は道の駅「三笠」とする．なお，地点間移動コストおよび時間枠制約データは北海道道路情報総合案内 Web サイト[4]より取得した．また，本実験に使用した計算機のスペックは表 5.2 の通りである．
表 5.1 GA を用いた手法の各条件
条件値

条件値

染色体表現

パス表現

世代交代数3,000

選択方法

ランキング選択 集団の個体数

2,000

交叉方法

部分写像交叉0.01

突然変異

転座

突然変異確率

表 5.2 評価実験に用いた計算機のスペック
OS

プロセッサ

メモリ

Windows 7
ProfessionalIntel(R) Core(TM) i5-3320M
CPU4.00 GB５－２．実験結果
表 5.4 に実験結果を示す．提案手法と GA を用いた手法のそれぞれの結果を比較すると，最良解は 4,595(分)，平均で 6,892(分)提案手法が劣る結果となった．一方，処理時間は提案手法では約 2 秒，GA を用いた手法では約28 秒であり，提案手法の方が平均で約 26 秒速く解を導出できた．
由人

3／4

表 5.4 実験結果
最良解(分)

平均値(分)

標準偏差

処理時間(秒)提案手法

26,911

22,316

2,296

2.365

GA

30,227

23,3351,038

28.422

図 5.1 は，提案手法により求めた解が示すルートの一部を地図上に表したものである．地図上の番号は地点番
号，四角枠内の時間はそれぞれの地点の時間枠制約を表している．図 5.1 が図 5.1 提案手法により示す経路は以下の求めたルートの一部
経路 A で表される．
( )内はそれぞれの経路の総移動コストである．
・経路 A 76 → 77 → 78 → 79 → 80 (124)・経路 B 76 → 78 → 79 → 77 → 80 (112)地点 76 から次の地点に移動するとき，地点 77 に移動する経路 A より地点 78 に移動する経路 B の方が総移動コストは低いが，提案手法により導出された解は経路 A を示している．営業終了時刻が早く，優先的に訪問すべき地点 77 を先に訪問することを表しており，時間枠制約の重みを管のコンダクティビティに反映した手法が有効であることを確認できる．しかし，優先的に訪問すべきノード同士を強固に接続したことにより，残りのノードを接続した際に非効率的な巡回路が生成される場合が確認された．
５－３．現実問題への活用方法の検討
評価実験の結果，解品質は GA を用いた手法と比べ提案手法が劣る結果となった．しかし，提案手法では GAを用いた手法と比べ処理時間が大幅に短く，高速に解を導出できることを確認した．提案手法での解導出にかかる時間は約 2.3 秒であり，当該時間は GA を用いた手法による解探索において，おおよそ 300 世代目にあたる．
当該時間におけるそれぞれの解の評価値を比較すると，提案手法が GA を用いた手法より評価値が良いことが確認でき，早期に解を導出できていることがわかる．以上の特徴から，提案手法における高速な解導出と GA を用いた手法における高品質な解導出を活かした現実問題への活用手法を検討する．GA を用いた手法では通常，初期集団はランダムに生成して探索を開始する．通常生成する GA の初期集団の中の個体の一部を，提案手法による導出解に置き換えて，GA により解を探索する．
本手法の有用性を評価するため，５－１節における評
価実験と同問題である北海道の「道の駅」スタンプラリー企画を取り上げ，現実問題への活用手法による探索を
1383106 加藤10 回行う．GA の初期集団で置き換える個体の数は 3 とする．なお，実験条件は５－１節における評価実験と同条件である．
実験結果を表 5.5 に示す．GA のみを用いた手法に比べ，現実問題への活用手法では最良解で 908(分)，平均して 88(分)解品質が向上しており，GA の初期集団の一部を提案手法での導出解に置き換える手法が有効であったと考えられる．
表 5.5 現実問題への活用手法の評価実験結果

提案手法
＋GA

最良解(分)

平均値
(分)

標準偏差

処理時間(秒)

21,40823,246998

35.519６．おわりに
本研究では，粘菌ネットワークの TSP への適用手法に加え，時間枠制約の重みをエッジのコンダクティビティに反映させることにより，TSP-TW に対応させる手法を提案した．評価実験の結果，提案手法により得られたルートにおいて，時間枠制約が厳しく優先的に訪問すべき地点に先に訪問する箇所があり，時間枠制約の重み付け手法が部分的に有効であることを確認した．しかし，優先的に訪問すべきノード同士を強固に接続したことにより，残りのノードを接続したときに非効率的な巡回路が生成され，解品質が悪化した．解品質の悪化を防ぐために，時間枠制約の重み付けの表現手法の改善を検討する必要があると考える．提案手法による解品質は，最良解で 26,911(分)，平均で 30,227(分)であり，GA を用いた手法に比べて平均して 6,892(分)劣る結果となったが，GAを用いた手法と比べて大幅に高速な解導出が可能であることから，解の品質よりも処理の高速さが求められる問題に対しては適用可能性があると考える．提案手法とGA を用いた手法のそれぞれの特徴を考慮し，GA の初期集団の一部を提案手法での導出解に置き換える手法を検討した．GA のみを用いた手法よりも平均で 88(分)，最良解で 908(分)解品質が向上したことから，提案手法の高速さと GA を用いた手法の解品質の高さが有効に働き，現実問題への活用手法として有用であったと考えられる．
参考文献[1] Tero, A., Kobayashi, R. and Nakagaki, T.: Mathematicalmodel for adaptive transport network in path finding bytrue slime mold, J. Theor. Biol., Vol.244, pp. 553-564(2007)[2] 榎原博之, 田中裕也, 石川琢士: 粘菌ネットワークを用いた巡回セールスパーソン問題の解法, 情報処
理学会研究報告, Vol.2011-MPS-83, No.10 (2011)[3] 山本芳嗣, 久保幹雄: 巡回セールスマン問題への招待, 朝倉書店 (1997)[4] “北海道道路情報総合案内サイト北の道ナビ”,
http://northern-road.jp/navi/, (参照 2014-11-22)
由人

4／4