「巡回セールスマン問題」で中央区の公園56ヶ所を効率的に巡る

デイリーポータルZ

数学の世界には、セールスマンがいい感じにすべての場所を経由して一周する最短経路を求める問題があり、「巡回セールスマン問題」と呼ばれています。

実際、宅配便の配達ルート設計などに使われていると聞きますが、計算したルートをたどるとどうなるのか、ずっと気になっていました。

自分の足を使って試したら、理論と現実のギャップに打ちのめされました。

巡回セールスマン問題とは

数学の世界には巡回セールスマン問題という、最適化問題(いい感じの計算方法でいい感じの答えを導こうぜ!)というものがあります。

001_巡回セールスマンの例_1.png
たとえば、5か所の都市があるとします

セールスマンが複数の都市を最短経路で経由して元の場所に戻りたいとします。

002_巡回セールスマンの例_2.png
このようなルートが最短距離っぽいですよね。

図のようなルートが答えとなります。

上記のように経由する都市が5ヶ所であれば簡単ですが経由する都市数が増えれば増えるほど最短距離のルートを探すことが難しくなります。

そのため、最短経路の答えになるべく近く計算時間も短いものを見つけるというものが巡回セールスマン問題と呼ばれるもので、プログラムは宅配便の配達ルートの設定などに使われているそうです。

今回は実際に歩いてみて「最短経路だ!巡回セールスマン問題の研究ってすごいなあ」と体感したいと思います。

中央区の全公園、56か所の最短経路を描きます

巡回するのは中央区の全公園(56か所)に決めました。セールスマンはビジネス街の公園にいるイメージがあるからです。

中央区にある全公園56か所は以下の位置にあります(児童遊園を含めるとプラス33か所で流石にクタクタになるだろうという不安があり、今回は除外しました)。

こちらの地図含め、本記事の公園の位置情報は「中央区オープンデータ」より取得しました。

約10平方キロメートルの中央区の範囲を東西南北様々な場所に公園があります。

この56か所をなんのプログラムも使わず一筆書きで最短距離で一周するルートを見つけ出すのは、悔しいですが難しそうです。

そこで、使うのが巡回セールスマン問題の計算プログラムというわけです。

56か所の公園同士の移動時間と距離を調べて、そのデータをもとにプログラムが最短経路を導出してくれます。

算出された最短経路がこちらです。

ちょうど何にも例えずらいフォルムの最短経路ができました。全体的には近そうな公園をうまく経由してるなというくらいの感想です。

ただ、日本橋駅付近から、築地市場まで南西に走る1本の道沿いを見ると、あえて途中で銀座方面の公園を経由し築地市場から北上しなおしており、人間には簡単には思いつかないルート構築なのが分かります。

マイマップの該当箇所を拡大表示

まさにこの辺りは頭の柔軟さとは違う合理性の極致といった印象です。

道のりは合計で21km、ハーフマラソン相当です。めちゃくちゃ長い。いや、巡回セールスマン問題のおかげでたった21kmですんだと思うことにしましょう。

この最短経路の道順を、グーグルマップで調べなおして、各地点の到着予想時間をグラフにまとめてみました

003_理論上の移動分数のグラフ.png
約272分、4時間32分で一周できそうです。

この経路と時間を信じて実際に歩いきます。272分の旅の始まりです。

004_セールスマンの恰好をした男.JPG
スタート地点へ向かう私。巡回セールスマン問題にちなみ、セールスマンの恰好をしてまいります。眼鏡が曇ってるのが気になりますね。

京橋1丁目からスタート

スタート地点の楓川久安橋公園に向かいます。

005_楓川久安橋公園_スタート地点.JPG
スタート地点かつゴール地点の楓川久安橋公園。

9時開始のつもりが、着いた時刻は13時21分。3度寝はしない方が良いそうです。

なお全公園を巡り終える終了予定時刻は272分後、17時53分です。このとおりの時間に戻ってこられるかどうか、検証したいと思います。

おおきなリンゴとミカン 2か所目~11か所目

それでは56箇所の公園を巡っていきたいと思います。見どころをダイジェストでお送りします。 

006_楓川宝橋公園.JPG
2か所目。楓川宝橋公園。おおきなリンゴとミカンがあります。オフィス街にしては全力でメルヘン。キュートさに動揺してしましました。

5か所目、水谷橋公園では予想外の疲労を味わうことに。

007_水谷橋公園入口.JPG
5か所目、水谷橋公園は
008_水谷橋公園の案内図.JPG
80段の階段の先の屋上にありました。

階段を使って後悔です。エレベーターをお勧めします。経験者からのアドバイスです。

009_水谷橋公園の景色.JPG
公園が屋上にあると都会を感じますね。
010_数寄屋橋公園.JPG
6か所目。数寄屋橋公園。不思議なモニュメントもあります。岡本太郎作「若い時計台」らしいです。爆発!

10か所目は、築地川銀座公園。この公園は個人的な盛り上がりスポットでした。

011_築地川銀座公園入口.JPG
10か所目。築地川銀座公園。首都高の上に建てられています。
012_築地川銀座公園_アガベ.JPG
なんと、アガベが咲いているのです!!

実は私、この2年間で観葉植物主趣味にはまりにはまってしまい、一時期は週一で観葉植物のお店に行き都内の主要なお店はあらかた行ってしまったほどです。

そんな私の目の前にアガベが咲いているのです。アガベの花はめったに見られないもので、1世紀に一度咲く花と言われます。

ここ数年日本では一斉にこのタイプのアガベが開花しているのですが、私はそれらを見るタイミングを逃しており、初めて生で目撃することが出来ました! 嬉しい!アガベはまだ自分は所有していないのですが、手にしたいという情熱が溢れていきます。

「興奮してないで、巡回セールスマン問題の件はどうなったの?」私の理性が指摘してきたので、ここまでの時間を確認しましょう。

013_比較グラフ_10か所目まで.png
青が理論上の移動時間、赤が実際に移動時間です

順調に遅れています。本来3.5キロを47分で歩かなければならないところを、66分かけてしまっているのです。

遅さの心当たりは2つあります。1つ目は足の遅さです。私はハチャメチャに足が遅く普段から街中でご老人に抜かれることすら頻繁にあります。

そして、どの公園も特色があり、気になるポイントを撮影したらすぐ時間が経過してしまうのです。困ったものです。

いったん広告です

11か所目~22か所目

15か所目、桜川屋上公園。再び屋上タイプの公園です。今回ここで2つ目です。

のちにわかることですが屋上タイプの公園は中央区に5か所あり、そのたびに私の足に疲労をあたえてくださいました。

014_桜川屋上公園の階段.JPG
15か所目。桜川屋上公園。公園へつながる階段です。
015_桜川屋上公園_景色.JPG
屋上にある公園とは思えないくらい緑が多いです。
016_あかつき公園.JPG
20か所目。あかつき公園。遊具が豊富で子供たちがいっぱい!眼鏡もまだまだ曇っています。
017_築地川公園.JPG
21か所目。築地川公園。20か所目のあかつき公園と隣接し遊具も豊富!
018_はとば公園.JPG
22か所目。はとば公園。球体が公園の真ん中に鎮座。クール。

ここで月島に突入です。再度、経過時間を確認しましょう。私は遅れをリカバーできたのかな?

019_比較グラフ_22か所目まで.png
青が理論値、赤が実際の時間です。

理論では88分のところを127分で40分の遅延です。客先に40分遅刻と考えると大失態です。しっかりしてください!

先ほどまでは足の遅さ、公園の特色に目移りすることが遅れの理由でしたが、広すぎる公園、階段を登らないといけない川沿いの公園や屋上にある公園があり、足への疲労が蓄積した結果、遅れに繋がっていると感じております。

しかも、雨粒がかすかに降り始め文字通り雲行きが不安です。

020_勝鬨橋.JPG
勝鬨橋。空は曇天。不安も満点。

23か所目~37か所目

021_月島第二児童公園.JPG
23か所目。月島第二児童公園。平日の15時頃。子供たちのはしゃぎ盛りです。

26か所目(豊海児童公園)から27か所目(朝潮運河親水公園)の途中で問題発生。工事で道が封鎖されており、予定の進路に戻るのに手間取りまくり。

022_工事.JPG
工事の一角。通行不可であたりをぐるぐるしました。

16時20分ごろにはだいぶ暗くなりました。日没が早すぎる。

023_夜のとばり.JPG
夜のとばりが、降ります。

月島には3か所連続で屋上に公園がありました。その3か所だけ他の公園には無かった、区が公式で制定している別名があるのがみどころです。

024_晴海第三公園.JPG
30か所目。晴海第三公園。別名サウストリトンパーク。オリンピック関連の平和モニュメントがあります
025_晴海第二公園.JPG
31か所目。晴海第二公園。別名なかよしひろば。サウストリトンパークに比べて落ちつたネーミング。
026_晴海第一公園.JPG
32か所目。晴海第一公園。別名ふれあいの森。屋上とは思えないほど木々が生い茂っています。さっきも似たようなこと言ったかも。
027_佃三丁目公園.JPG
35か所目。佃三丁目公園。THE・夜。

暗いし、雨がふってきました。私の心にも雨がふります。

028_石川島公園.JPG
37か所目。石川島公園。かなり暗い。

月島エリアを巡り終え、残り19か所です。がんばれ私!現時点の進捗を振り返りましょう。

029_比較グラフ_37か所目まで.png
素晴らしい遅れです。もうリカバーはきついです。私!ファイト!
いったん広告です

38か所目~56か所目

030_越前堀児童公園.JPG
38か所目。越前堀児童公園。もう人が誰もいません。
031_箱崎川第一公園.JPG
41か所目。箱崎川第一公園。高架下タイプの公園です。

疲労がピークに達し、ベンチに座ったらびちょびちょでした。悲しくて立ち上がれません。

032_濡れベンチ.JPG
私の尻を濡らした、悲しみの濡れベンチ。
033_あやめ第一公園.JPG
44か所目。あやめ第一公園。雨がしのげる高架下の公園を愛し始めています。
034_浜町公園.JPG
47か所目。浜町公園。公園にスポーツセンターが。
035_千代田公園.JPG
48か所目。千代田公園。中学校の校庭と一体型という珍しいタイプ。
036_堀留児童公園.JPG
50か所目。堀留児童公園。雨がザーザー。

もはや雨を無視できません。我慢できずに傘を買いました。傘に文明を感じます。

037_本石町公園.JPG
54か所目。本石町公園。オフィス街のせいか喫煙所のみ。大人は公園では遊ばないみたいです。
038_楓川新場橋公園.JPG
56か所目の公園。楓川新場橋公園です。

なぜか最後の公園、楓川新場橋公園は見つけ出すのに苦労しました。公園ぽっさが今日一で無いのです。

あたりをグルグル回っり地図とにらめっこし、「いま立っている場所が楓川新場橋公園か!!」と判明、さながら幸せの青い鳥のような結末でした。

というわけで無理やり無事に、ゴール地点に到着です。時刻は20時16分。

039_ゴール.JPG
光り輝く、楓川久安橋公園の看板。

雨、寒さ、暗さ、疲労。あらゆる問題が私を阻み、私もめげずに頑張りました。結果は以下の通りです。

040_比較グラフ_全区間.png
巡回セールスマン問題が導き出した移動時間は約272分。実際の移動時間は415分です。約1.5倍の時間。

ゴールの到着時刻は20時16分。予定より約140分遅れです。仕事ではやっちゃいけない数字。

この膨大な遅れの理由は元からの足の遅さ、公園の魅力のおかげ生じた写真撮影の手間、思ったより多い階段、長距離の疲労、冬の時期がもたらす寒さと日の入りの速さの合わせ技、降りしきる雨、と上げればきりがないというありさまです。

私の向こう見ずな所を踏まえてたとしてもこんなにも苦難が多いのは完全なる想定外でした。

巡回セールスマン問題の解にしたがって歩いていると、「無駄なルートを歩いていない」と意識で気持ちが楽でした。

しかし、雨風寒さ疲労を考慮できておらず想像以上に遅れました。今後街中の特定の施設(コインパーキングや区役所、公衆トイレ、国内の世界遺産などなど)を全部回る企画をするときには、疲労の概念を忘れずにスケジュールを組むことを心がけようと思います。

041_オチ.JPG
セールスマンらしさを演出するための鞄とびしょ濡れになった後に購入した傘のおかげでカメラを持つのに苦労すること苦労すること。

 

Source

タイトルとURLをコピーしました