　今回は，スマートフォン等を用いて「巡回セールスマン問題」（Traveling Salesman Problem， TSP）を一瞬にして解き，その経路を地図上に表示してくれる「Concorde TSP」（http://www. math.uwaterloo.ca/tsp/index.html）を紹介する。TSPとは，対象となる都市の全ての２地点間の移動コスト（距離，時間，運賃など）が与えられている時，全ての都市を一度ずつ訪れる巡回路に対して，移動コストが最小となる経路を求める問題であり，組み合わせ最適化問題の中でも最も古典的な問題として知られている。例えば，旅行の計画を立てる際，お目当ての観光地をできるだけ効率的に回るためには，どのような経路を選べばよいのか考えてみる。一見単純な問題のように見えるが，n個の観光地を巡るのに，取り得る全ての経路の数は（n-１） !個存在することから，観光地の数が大きくなるほど組み合わせ爆発を起こすことが分かる。そのため，これまでに大規模な問題に対して，数理計画法を用いて最適解を厳密に求める取り組みやヒューリスティックスを用いて近似解を高速に求めるためのアルゴリズムの開発が進められてきた。今回紹介する「Concorde TSP」は，カナダ・ウォータールー大学のWilliam Cook教授により提供されており，スマートフォン等（2015年５月公開のバージョン1.5では，Apple社iOS 8.3以降と互換性あり）を用いて1,000点以上の都市に対して最適解を求めることが可能である。Cook 教授らの研究グループは，2004年に世界記録である24,978都市の最適解を厳密に解くことに成巡回セールスマン問題 140 功しており，まさに世界最高水準のプログラムであると言える。最も実用的な機能として，地図上で訪問したい都市をクリックし，その最短経路を地図上に表示することができる「Map Router」が挙げられる。移動コストについて，直線距離の他に，画面右下の「ｉ」ボタンを押すことで選択が可能である。そして，10都市までの小規模な問題に限られるが，Apple社 Map Kit Frameworkを利用して，世界各地での道路ネットワークでの移動距離や移動時間を用いた計算を行い，その経路を道なりに表示することも可能である。また，教育的な効果も非常に高く，ランダムな点やベンチマーク問題の他に，座標を入力することで自分の解きたい問題にも対応している上，これまでに提案されてきた様々なヒューリスティックスの解法による近似解を表示することも可能である。更に，取り込んだ写真から点を抽出してTSPを解く「TSP Art」のような遊び心のある機能もあり，TSPをとことん愛するCook 教授ならではのユーモアがあふれるアプリである。（東京海洋大学　渡部大輔）地図上での最適な巡回路の表示 THE JOURNAL OF SURVEY 測量 2015.8 19