位置ゲー攻略のためにPythonとNetworkXで最短経路を探る(2)

前回

前回、駅メモというゲームのために最短経路問題に取り組みましたが、18きっぷ旅用の出力になってしまいました。
今回はこの新幹線使わない問題の改善と、エッジの重みの設定、表示の簡略化を行います。

新幹線使わない問題

前回、横浜駅から鳥取駅までの経路を検索すると、

最短経路（駅名）: 横浜 -> 戸塚 -> 大船 -> 藤沢 -> 辻堂 -> 茅ケ崎 -> 平塚 -> 大磯 ->
二宮 -> 国府津 -> 鴨宮 -> 小田原 -> 早川 -> 根府川 -> 真鶴 -> 湯河原 -> 熱海 ->
熱海 -> 函南 -> 三島 -> 沼津 -> 片浜 -> 原 -> 東田子の浦 -> 吉原 -> 富士 -> 富士川 ->
新蒲原 -> 蒲原 -> 由比 -> 興津 -> 清水 -> 草薙 -> 東静岡 -> 静岡 -> 安倍川 -> 用宗 ->
焼津 -> 西焼津 -> 藤枝 -> 六合 -> 島田 -> 金谷 -> 菊川 -> 掛川 -> 愛野 -> 袋井 ->
御厨 -> 磐田 -> 豊田町 -> 天竜川 -> 浜松 -> 浜松 -> 高塚 -> 舞阪 -> 弁天島 ->
新居町 -> 鷲津 -> 新所原 -> 二川 -> 豊橋 -> 西小坂井 -> 愛知御津 -> 三河大塚 ->
三河三谷 -> 蒲郡 -> 三河塩津 -> 三ケ根 -> 幸田 -> 相見 -> 岡崎 -> 西岡崎 -> 安城 ->
三河安城 -> 東刈谷 -> 野田新町 -> 刈谷 -> 逢妻 -> 大府 -> 共和 -> 南大高 -> 大高 ->
笠寺 -> 熱田 -> 金山 -> 尾頭橋 -> 名古屋 -> 枇杷島 -> 清洲 -> 稲沢 -> 尾張一宮 ->
木曽川 -> 岐阜 -> 岐阜 -> 西岐阜 -> 穂積 -> 大垣 -> 垂井 -> 関ケ原 -> 柏原 ->
近江長岡 -> 醒ケ井 -> 米原 -> 米原 -> 坂田 -> 田村 -> 長浜 -> 虎姫 -> 河毛 -> 高月 ->
木ノ本 -> 余呉 -> 近江塩津 -> 新疋田 -> 敦賀 -> 敦賀 -> 西敦賀 -> 粟野 -> 東美浜 ->
美浜 -> 気山 -> 三方 -> 藤井 -> 十村 -> 大鳥羽 -> 若狭有田 -> 上中 -> 新平野 ->
東小浜 -> 小浜 -> 勢浜 -> 加斗 -> 若狭本郷 -> 若狭和田 -> 若狭高浜 -> 三松 -> 青郷 ->
松尾寺 -> 東舞鶴 -> 東舞鶴 -> 西舞鶴 -> 真倉 -> 梅迫 -> 淵垣 -> 綾部 -> 綾部 ->
高津 -> 石原 -> 福知山 -> 上川口 -> 下夜久野 -> 上夜久野 -> 梁瀬 -> 和田山 -> 養父 ->
八鹿 -> 江原 -> 国府 -> 豊岡 -> 豊岡 -> 玄武洞 -> 城崎温泉 -> 竹野 -> 佐津 -> 柴山 ->
香住 -> 鎧 -> 餘部 -> 久谷 -> 浜坂 -> 諸寄 -> 居組 -> 東浜 -> 岩美 -> 大岩 -> 福部 -> 鳥取

という18きっぷ専用の結果になりました。
原因は【駅データ.jp】さんからお借りしているデータが無料版だったことで、新幹線駅が含まれていなかったことでした。

有料データと無料データの違いは何ですか？
駅マスタの新幹線駅のデータすべて

引用元：よくあるご質問

というわけで有料会員登録しました。
必要な金額を銀行振り込みして、振り込みの報告をすれば有料版のデータが使えます。
（有償版も商用、非商用問わず利用可能で非常に素晴らしいサイトです）

重みの追加

せっかく課金したので、1駅間の距離が長い駅を優先して使うように、距離の逆数を重みとして設定しました。

def haversine(lat1, lon1, lat2, lon2):
    # 緯度経度から2点間の距離を求める
    
    # 地球の半径（キロメートル）
    R = 6371.0
    lat1, lon1, lat2, lon2 = map(math.radians, [lat1, lon1, lat2, lon2])
    dlat = lat2 - lat1
    dlon = lon2 - lon1
    a = math.sin(dlat/2)**2 + math.cos(lat1) * math.cos(lat2) * math.sin(dlon/2)**2
    c = 2 * math.atan2(math.sqrt(a), math.sqrt(1 - a))
    distance = R * c
    return distance

edges['distance'] = edges.apply(lambda row: haversine(row["lat1"], row["lon1"], row["lat2"], row["lon2"]), axis=1)
# 距離の逆数(0除算対策の0.1)
edges['weight'] = edges['distance'].apply(lambda x: 1 / (x + 0.1))

表示の簡略化

移動する各駅をそのまま表示するのではなく、発駅と着駅、利用する路線名だけを表示するように工夫しました。

def simplify_path(path):
    if not path:
        return []
    simplified_path = [path[0]]
    current_line = G.nodes[path[0]]['line_cd']
    for station in path[1:]:
        next_line = G.nodes[station]['line_cd']
        if next_line != current_line:
            simplified_path.append(station)
            current_line = next_line
    if path[-1] != simplified_path[-1]:
        simplified_path.append(path[-1])
    return simplified_path

出力

最短経路（駅名）
 横浜 JR東海道本線(東京～熱海) ->
品川 東海道新幹線 ->
新大阪 山陽新幹線 ->
岡山 JR伯備線 ->
伯耆大山 JR山陰本線(豊岡～米子) ->
鳥取 JR山陰本線(豊岡～米子)

というわけで、上記のような出力になります。
前回と比べると大分現実的な出力になりましたが、横浜→新横浜→姫路→鳥取、または大阪から[スーパーはくと]が効率の良い移動方法だと思います。
設定している重みの問題か(1駅間の距離が長いJRが優先される？)
もしくは、スーパーはくとがJR山陰本線→那智急行→JR因美線と複数路線を通ることが原因か。。。
改善しなければいけないことはまだまだありそうです。

次回は本命となるコンプリートのための巡回セールスマン問題をやってみたいと思います。

コード