蟻コロニー最適化を用いた渋滞時の巡回経路探索
2003MT095 関原 啓太

2005MT041 伊藤 祐基
指導教員

1 はじめに
現在のカーナビには，VICS(Vehicle Information andCommunication System) などの普及により，渋滞や交通規制などの道路交通情報をリアルタイムに受信し，動的環境下で新たな推奨経路を生成するカーナビも市販されている．しかし，複数の目的地を設定し，最後に出発地点に戻るような経路を案内する機能を持ったカーナビはない．このような巡回路を求めることを巡回セールス
マン問題 (TSP) という [4]．
そこで本研究では，TSP を解くための代表的な解法(最近傍法，貪欲法，最遠挿入法，2-opt 法，山登り法，焼きなまし法，蟻コロニー最適化) を比較し，より最適解に近づくことができるアルゴリズムを選択する．そして，道路交通情報をリアルタイムに計算し，動的に TSPを解く機能を提案する．まず，現在のカーナビに TSP を解く機能が用いられていないことを示し，各アルゴリズ
ムの中から，最近傍法，2-opt 法，蟻コロニー最適化を挙げ，性能評価を行う．そして，ACO は，フェロモンというパラメータを用いて経路探索を行っているため，前回の解で用いたフェロモン量を利用することで，より効率の良い経路を探索すると思われる．よって我々は ACOに着目し，CA 法によるシミュレーションを行った．そして，動的環境下で効率の良い巡回経路を求めることができているかを確かめるために，渋滞状況を考慮しない場合との比較を行った．その結果，動的環境下では経路を迂回することで距離は長くなるが，コストはより小さくなることが分かった．次に我々が採用した ACO について，ACO が本研究に適しているかを確かめるために，精度と計算時間について 2-opt 法と比較する．

きなまし法，タブー探索法，遺伝的アルゴリズムがある．
本研究では，代表的な最近傍法，2-opt 法，蟻コロニー最適化を挙げる．

1.

最近傍法
貪欲的に次々と近い点を訪れる方法．最近傍法のアルゴリズムを図 1 に示す．

¶³

任意に一点を選び，出発点とする；while(すべての点を選ぶまで){選んだ点以外から，選んだ点に最も近い点を選ぶ；
選んだ点を新たな出発点とする；}
最後に選んだ点と最初に選んだ点を結び，巡回路を作る；µ図1

異なることが多い• 求まった巡回路との間にどのくらいの差があるのかを評価する効果的な方法がない

2.

2-opt 法解の一部について改善を行い，これを繰り返して全体の改善を行う方法．2-opt 法のアルゴリズムを図 2 に示す．
¶³

巡回路を 1 つ作る；
while( となる枝がなくなるまで) {枝 (a，d) と枝 (b，c) を枝 (a，b）と枝 (c，d) でカーナビの機能
現在市販されているカーナビの主な機能として，つなぎ直す；µ}´
図2可能が挙げられる．現在のカーナビには，TSP に似た機能として何ヵ所か経由地点を設定することができるが，この場合各地点を回る順番は利用者自身があらかじめ決定するため，その経路が最短ではない．

TSP の解法
構築法の中には，ランダムサーチ，最近傍法，貪欲法，最遠挿入法があり，改善法の中には，2-opt 法，山登り法，焼最近傍法のアルゴリズム• プログラミングが容易である• 出発地点の取り方によって，構成される巡回路が

2.1

2.2

´

(特徴)

2 TSP に関する研究

1. 静的環境における渋滞データバンク探索
2. 動的環境におけるスイテルート案内
3. 目的地に着くまでの経由地を最大 5 ヵ所まで設定

2005MT123 和久田 崇

河野 浩之

2-opt 法のアルゴリズム(特徴)• 近傍を大きくすれば，得られる解の精度は向上す
るが，近傍の探索に要する時間が長くなり，計算効率が下がる

3.

蟻コロニー最適化 (ACO)ACO は，都市間の距離の短さと都市間のフェロモン量の多さから次に訪れる都市を確率的に選択する手法である [1]．まず，蟻はえさを探すためにランダムに動き回るが，えさを見つけて巣に戻るときはフェロモンを出す．フェロモンは限りがあり，経路が長くなるほどフェロモンが薄くなってしまうので，濃い経路を他の蟻も辿ることで，最適経路となる．

START

TSPの入力フェロモンの初期化 1(特徴)

全てのエージェントが同一の短い経路を選択するまで• グラフが動的に変化する場合に遺伝的アルゴリズ

No

ムより有効
• 継続的に実行されるので，リアルタイムでの変化に適応することができる• 大域探索に弱い
動的環境における TSP の解法
環境の変化があった場合，その新しい環境が前回の環境に近い場合，新しい解も前回の環境の解に近いことが予想できる．よって，新しい解は前回の解の近傍にあることになり，前回の解をもとにして探索を行うことで，効率の良い探索ができると考えられる．動的環境用プログラムでは前回の解を改善することで新しい解を求める．そのため，解法は改善法しか利用することができない．代表的な解法では，2-opt 法，タブー探索法，焼きなまし法が改善法であるが，最近傍法，貪欲法，最遠挿入法は構築法であるため，利用できない．
環境の変化が小さい場合は局所改善型である 2-opt 法
は動的環境用において探索時間が短縮する．ACO は，フェロモンというパラメータを用いて経路探索を行っているため，前回の解で用いたフェロモン量を利用することで，より効率の良い経路を探索すると思われる．よって本研究では ACO に着目する．

全エージェントが巡回路を生成するまでNo
Yes

カーナビの新機能の提案
現在のカーナビには，動的環境における最短経路を探索する機能は備えているが，TSP のように複数の目的地について最適経路を計算する機能を備えていない．この場合，どの順番で目的地を巡回するかは利用者の直感によって判断されるため，遠回りをしてしまう場合や，混んでいる場所に先に向かってしまう場合などが考えられる．
本研究では，道路交通情報をリアルタイムに計算し，動的に TSP を解く機能を提案する．
カーナビに TSP を解く機能を導入することができれば，車で自社を出発し，営業で各支店を回る場合や時間指定のない荷物の配送で各地点を回る場合に，最適経路を導くことができ，時間やガソリンなどのコストを削減することが可能である．

3.1

3.2 蟻コロニー最適化 (ACO) のフローチャート
ACO のフローチャートを図 3 に示す．ACO，2-opt
法，最近傍法によって求められた距離と計算時間を表 1に示す．ここでの都市は，x 座標，y 座標共に 0 から 10エージェントの巡回路の生成 2

最良解の更新2.33 動的環境における TSP の導入

Yes

フェロモンの更新 3TSPの解を出力END

図 3 ACO のフローチャートまでランダムに出力した値であり，時間の単位は秒である．

表1

ACO (距離)(時間)
2-opt (距離)(時間)
最近傍法 (距離)(時間)

各アルゴリズムの実行結果

5 都市

10 都市

30 都市

50 都市

22.1
0.05
22.1
0.00
22.1
0.00

26.9
0.21
26.9
0.01
36.6
0.00

53.7
1.88
56.3
0.00
69.2
0.00

57.1
5.32
60.50.0068.10.00

表 1 より，解の精度は ACO，2-opt 法，最近傍法の順に悪くなり，計算時間は圧倒的に ACO が長い．我々は，解の精度を重要視し，また動的環境に適している ACO を用いてシミュレーションを行っていく．

4 セルオートマトン (CA) 法による TSP の実装
CA 法を用いた交通流シミュレーション
動的環境下で TSP を適応させるために，交通流を再現する必要がある．本研究では，CA 法と NS モデルを用いたシミュレーションを行う．ＣＡ法とは道路を多数のセルをつないだ帯として表し，道路の状態を各セルに車が存在するか否かで表現するものである．最も基本的なモデルとして，先のセルが空いていれば車を移動させ，空いていなければそのセルに留まるという，ウルフラムのルール 184 がある. 図 4 にルール 184 の車の進行の様子を示す．
4.1

¶tt+2t+3

図4

ルール 184 の車の進行の様子

本研究ではそれに車の加減速を取り入れた NS モデルを使用する.NS モデルに対する各セルの更新は以下の4 つの規則によって行われる．ただし車の速度は 0 からvmax の整数とする．なお本研究では，vmax を 5 とする．
加速 : もし車両の速度 v が最大速度 vmax より小さかった場合，かつ今の速度 v で進む距離に 1 セル分を加えた距離に他の車両がいなかったら，速度を (v + 1) とする
減速 : 車両がセル i にいてその前の車両がセル (i + j)にいる場合，もし j ≤ v ならセル i にいる車両の速度を (j − 1) とする
ランダムブレーキ : 確率 p で車両の速度が 0 でないとき，速度を 1 小さくする
車両の運動 : 速度 v の車は，1 ステップでその位置から進行方向に v 進める
シミュレーションの詳細
本研究では，メッシュ型の道路を用いる．そしてできるだけ実際の道路に近づけるために，東西，南北にそれぞれ主要道を設け，一方通行を 2 箇所に作り，一部の道路を削除した．また，主要道とは車の流入率を他の道路に比べて多くし，交差点での右左折の割合を減らし，直進する割合を増やす．信号も主要道が青の時間を増やす．また，各交差点間の経路に距離を表す基本コスト 1を設定し，車の渋滞状況に応じてコストを追加する．コストとは，各交差点間内の車が 5 以下の場合は 0 を，10以下の場合は 1 を，15 以下の場合は 2 を，20 以下の場合は 3 を，20 より多ければ 5 をコストとして追加する．
図 5 に設定の詳細を示す．

4.2

4.3 ACO と 2-opt 法を用いた最適経路の探索
CA 法により再現したネットワーク内に，複数の経由地点を設定する．それらから任意の 2 地点を選択し，その間の移動コストと経路をダイクストラ法により求める．全ての 2 地点の組合せについてこれを行い，データを配列に格納する．このコストの配列を用いて，TSP を解く．CA のステップが進むごとに，渋滞状況は変化し，コストが更新されるため，巡回経路は動的に求められる．効率の良い探索ができているかを確かめるために，渋滞状況を考慮しない静的環境での経路探索も同時に行い，それぞれの距離とコストを比較する．

³

各交差点間 : 24 セル車の流入率 (主) ： 1/3
車の流入率 (一) ： 1/10
右左折率
(主 → 主) ： 直進 60%, 左折 20%, 右折 20%(主 → 一) ： 直進 80%, 左折 10%, 右折 10%(一 → 主) ： 直進 20%, 左折 40%, 右折 40%(一 → 一) ： 直進 70%, 左折 15%, 右折 15%
信号制御 (主と一) ： 青信号の時間を一般道の 2 倍信号制御 (上記以外)：青信号の時間を一般道と同じ
主 : 主要道

一 : 一般道

µ´
図5

設定の詳細

5 シミュレーション評価
5.1 ACO による静的環境と動的環境の比較
3 都市から 20 都市まで，渋滞を考慮しない静的環境における場合と，渋滞を考慮する動的環境における場合ををそれぞれ ACO を用いて解き，結果を表 2 に示す．ここで集計した数値とは，セルオートマトンの開始から交通状況の安定する 300 ステップ目のものである．

表2

ACO によるシミュレーション結果

静的環境

3 都市
4 都市
5 都市
6 都市
7 都市
8 都市
9 都市
10 都市
11 都市
12 都市
13 都市
14 都市
15 都市
16 都市
17 都市
18 都市
19 都市
20 都市

動的環境

距離

コスト

距離

コスト

151517192022232325262528293132353738

1920262827323436343638
41414344464948

161717192123252627292931323334363941

161719202225263029313237393940434746

表 2 より，距離は静的環境が短いが，コストは高い．

これを動的に計算することで，渋滞を迂回するなど，より低コストの経路を導くことができる．本研究の場合，多くの経由地点を入力すると渋滞が発生しても迂回路を生成することが少なくなっていくが，それは本研究で用いたネットワークが経由地点の数に対して狭いためである．経由地点を設定する際，ある地点から次の地点へ訪れる経路として複数の候補が存在する程度に各地点の間隔を大きくとることができ，それを受容するだけの広さを持つネットワークならば，効率の良い巡回経路探索を行うことができると思われる．

ACO と 2-opt 法の比較
表 2 から 10 都市までが妥当な数値を出力すると考えら
れ，3 都市から 10 都市まで，それぞれ 10 回ずつシミュレーションを行い，どちらがより低コストな経路を導くことができるか集計を行う．その結果を表 3 に示す．表3 は，10 回のコストの平均値とコストの最大値，最小値を示し，計算時間の単位は，µ秒である．
5.2

表 3 ACO と 2-opt 法のシミュレーション結果

ACO
3 都市
4 都市
5 都市
6 都市
7 都市
8 都市
9 都市
10 都市

平均値

計算時間

最大値

最小値

12.8
13.4
16.8
20.1
22.2
23.2
25.4
28.9

11000
19000
29000
41000
56000
72000
90000
110000171620
2425
26
30
40

10
101518
19
21
23
24

平均値

計算時間

最大値

最小値

12.7
13.4
18.9
21.5
25.6
28.8
32.4
36.7

33.5
31.5
33.8
36.5
38.6
43.3
44.6
39.2

171620
24
28
34
34
43

1010
18
1724
23
28
34

2-opt 法
3 都市
4 都市
5 都市
6 都市
7 都市
8 都市
9 都市
10 都市

図 6 は，5 都市における ACO と 2-opt の比較を行った
際のシミュレーション結果を示す．
この結果より，計算時間では圧倒的に 2-opt 法が短いが，精度は 2-opt 法より ACO がより短いコストで巡回することがわかる．また，都市数を多くする程，精度の差は大きくなる．我々は，計算時間を短縮させることよりも，解の精度を向上させることで，より効率の良い経路を導き，その結果，移動時間を短縮させることができ，より大きなメリットがあると判断した．

図 6 ACO と 2-opt 法の比較

6 まとめ
本研究では，複数の経由地点を巡回し，動的環境下での最適経路を求めるため，TSP に対する様々なアルゴリズムを研究し，それらの性能や特徴について比較した．
我々は ACO に着目し，CA 法によるシミュレーションを行った．そして，動的環境下で効率の良い巡回経路を求めることができているかを確かめるために，渋滞状況を考慮しない場合との比較を行った．その結果，動的環境下では経路を迂回することで距離は長くなるが，コストはより小さくなることが分かった．次に我々が採用した ACO について，ACO が本研究に適しているかを確かめるために，精度と計算時間について 2-opt 法と比較した．その結果，2-opt 法に比べ計算時間では圧倒的に長いものの，解の精度はより良い巡回路を導くことができる．また，表 1 と表 3 から，動的環境で蟻コロニー最適化を用いることにより，より効率の良い巡回路を生成すると判断できる．
我々は，今後の課題として，地図を読み込み，地図上でTSP のシミュレーションが可能になれば，もっと身近に利用できるだろう．

参考文献[1] 亀田陽介， 局所最適解をフェロモンの初期配置に利用したアントコロニー最適化法による TSP の解法 , 修士論文, 筑波大学大学院システム情報工学研究科,2007.
[2] 狩野均，小塚英城， ＣＡ法による広域道路交通シミ
ュレータを用いた経路案内方式の評価 ， 情報処理学会，高度交通システム研究会 ITS-10-6，pp.37-43，2002.9.
[3] 加藤恭義，光成友孝，築山洋， セルオートマトン法複雑系の自己組織化と超並列処理- ，森北出版，1998.
[4] 久保幹雄， 巡回セールスマン問題への招待 ，朝倉書店，1997.