ラッキーピエロ全店を最短でめぐりたい

Last updated at 2024-07-11Posted at 2024-07-11

函館にしかないハンバーガー屋

ラッキーピエロというハンバーガー屋さんをご存じでしょうか？なんでも北海道の函館周辺にあるテーマパークのようなハンバーガー屋さんらしいです。愛唱は「ラッピ」。

店舗ごとに雰囲気も違い、ハンバーガーの種類も豊富ということで、ハンバーガー好きなら函館に行って全店舗を回りたい！
ということで、最短で全店舗回れるルートマップを解析しました！

結果はこの通り。

では、実装方法を説明します。

全店舗回るための準備

方針は以下の通りです。なお、スタート地点は函館駅とします。

全店舗の座標を調べる
OSMnxで座標をノードに変換
NetworkXでノードから最短経路を探索する
経路を解析したノードを座標に戻す
Foliumで進行方向がわかるように地図を描く

必要なパッケージをインストールしておきます。

pip install folium osmnx networkx

OSMnx はOpenStreetMapから道路やその他の地理の特徴を簡単にダウンロード、分析することができるパッケージです。ちなみに、OpenStreetMapはオープンデータの地理情報をつくるプロジェクトです。

NetworkX は複雑なネットワーク構造を解析するためのパッケージです。

このようなノードを条件に合わせてどのようにつなげばよいかを解析できます。

したがってOSMnxで地理データを取得してノードにしてNetworkXに渡せばOKということです！

全店舗の座標を調べる

ラッキーピエロのホームページから店舗情報を調べて、緯度と経度を辞書をつくります。

# 函館駅の座標
hakodate_station = (41.773783785595, 140.72629663847)

# ラッキーピエロ全店舗の座標
lucky_pierrot_locations = {
    'tougeshita':(41.924028,140.661811),
    'marinasuehiro':(41.76715,140.716208),
    'tokura':(41.784386,140.807722),
    'syowa':(41.810118,140.73601),
    'morimachiakaigawa':(42.002671,140.634149),
    'esashiiriguchimae':(41.922607 ,140.151815),
    'hondori':(41.799166,140.775791),
    'hokutoinari':(41.820609,140.645271),
    'hakodateekimae':(41.771809,140.725811),
    'mihara':(41.814805,140.755051),
    'minatohokudaimae':(41.808902,140.716329),
    'goryokakukoenmae':(41.794327,140.75315),
    'matsukage':(41.791185,140.762141),
    'hitomi':(41.781089,140.760869),
    'honmachi':(41.788153,140.751117),
    'jujigaiginza':(41.763651,140.719228 ),
    'bayerea':(41.765751,140.714941)
}

「北斗飯生」は「ほくといなり」など読み方で苦戦しました。森町赤井川店は遠いので計算時間が長くなります。

OSMnxで座標をノードに変換

import osmnx as ox

# 道路の地理データを取得
G = ox.graph_from_place('Hakodate-shi, hokkaido, japan', network_type='drive')

# 座標をノードに変換
hakodate_station_node = ox.distance.nearest_nodes(G, hakodate_station[1], hakodate_station[0])
lucky_pierrot_nodes = {loc: ox.distance.nearest_nodes(G, coord[1], coord[0]) for loc, coord in lucky_pierrot_locations.items()}

なお、osmnx.graph_from_place()メソッドで得られた結果は次の通りです。

ox.plot_graph_folium(G)

nearest_nodes()メソッドで座標の最も近いノードが選ばれます。

NetworkXでノードから最短経路を探索する

得られたノードを使って最短経路を探ります。

import networkx as nx
from itertools import permutations

# 最短距離ルートを探索する関数
def find_shortest_route(graph, start_node, lucky_pierrot_nodes):
    shortest_distance = float('inf')
    shortest_route = None

    nodes = list(lucky_pierrot_nodes.values())
    for perm in permutations(nodes):
        current_distance = 0
        current_node = start_node
        route = [start_node]

        for node in perm:
            current_distance += nx.shortest_path_length(graph, current_node, node, weight='length')
            current_node = node
            route.append(node)

        current_distance += nx.shortest_path_length(graph, current_node, start_node, weight='length')  # Return to the start
        route.append(start_node)

        if current_distance < shortest_distance:
            shortest_distance = current_distance
            shortest_route = route

    return shortest_route, shortest_distance

# 最短ルートと距離を取得
shortest_route_nodes, shortest_distance = find_shortest_route(G, hakodate_station_node, lucky_pierrot_nodes)

経路を解析したノードを座標に戻す

初めに取得した函館の地理データから選ばれたノードを抜き出して、座標に戻します。

# 経路を取得する関数
def get_route(graph, orig, dest):
    return nx.shortest_path(graph, orig, dest, weight='length')

# ノードを座標に変換
shortest_route_coords = []
for i in range(len(shortest_route_nodes) - 1):
    segment = get_route(G, shortest_route_nodes[i], shortest_route_nodes[i + 1])
    shortest_route_coords.extend([(G.nodes[node]['y'], G.nodes[node]['x']) for node in segment])

Foliumで進行方向がわかるように地図を描く

最後はFoliumで描画します。プラグインを使うことで経路に矢印をつけてどのような順番で進むのかを分かるようにしています。

import folium

# マップの作成
map_nyc = folium.Map(location=hakodate_station, zoom_start=12)

# マーカーを追加
folium.Marker(hakodate_station, popup="hakodate_station", icon=folium.Icon(color='red')).add_to(map_nyc)
for name, loc in lucky_pierrot_locations.items():
    folium.Marker(loc, popup=name).add_to(map_nyc)

# 最短ルートを描画
folium.PolyLine(shortest_route_coords, color="blue", weight=2.5, opacity=1).add_to(map_nyc)

# ルートに矢印を追加
folium.plugins.AntPath(locations=shortest_route_coords, color="blue", weight=2.5).add_to(map_nyc)

print(f"The shortest route distance is: {shortest_distance / 1000} km")
map_nyc

まとめ

最終的なコードはこちら

!pip install folium osmnx networkx

import folium
import osmnx as ox
import networkx as nx
from itertools import permutations

# 函館駅の座標
hakodate_station = (41.773783785595, 140.72629663847)

# ラッキーピエロ全店舗の座標
lucky_pierrot_locations = {
    'tougeshita':(41.924028,140.661811),
    'marinasuehiro':(41.76715,140.716208),
    'tokura':(41.784386,140.807722),
    'syowa':(41.810118,140.73601),
    'morimachiakaigawa':(42.002671,140.634149),
    'esashiiriguchimae':(41.922607 ,140.151815),
    'hondori':(41.799166,140.775791),
    'hokutoinari':(41.820609,140.645271),
    'hakodateekimae':(41.771809,140.725811),
    'mihara':(41.814805,140.755051),
    'minatohokudaimae':(41.808902,140.716329),
    'goryokakukoenmae':(41.794327,140.75315),
    'matsukage':(41.791185,140.762141),
    'hitomi':(41.781089,140.760869),
    'honmachi':(41.788153,140.751117),
    'jujigaiginza':(41.763651,140.719228 ),
    'bayerea':(41.765751,140.714941)
}

# 道路の地理データを取得
G = ox.graph_from_place('Hakodate-shi, hokkaido, japan', network_type='drive')

# 座標をノードに変換
hakodate_station_node = ox.distance.nearest_nodes(G, hakodate_station[1], hakodate_station[0])
lucky_pierrot_nodes = {loc: ox.distance.nearest_nodes(G, coord[1], coord[0]) for loc, coord in lucky_pierrot_locations.items()}

# 最短距離ルートを探索する関数
def find_shortest_route(graph, start_node, lucky_pierrot_nodes):
    shortest_distance = float('inf')
    shortest_route = None

    nodes = list(lucky_pierrot_nodes.values())
    for perm in permutations(nodes):
        current_distance = 0
        current_node = start_node
        route = [start_node]

        for node in perm:
            current_distance += nx.shortest_path_length(graph, current_node, node, weight='length')
            current_node = node
            route.append(node)

        current_distance += nx.shortest_path_length(graph, current_node, start_node, weight='length')  # Return to the start
        route.append(start_node)

        if current_distance < shortest_distance:
            shortest_distance = current_distance
            shortest_route = route

    return shortest_route, shortest_distance

# 最短ルートと距離を取得
shortest_route_nodes, shortest_distance = find_shortest_route(G, hakodate_station_node, lucky_pierrot_nodes)

# 経路を取得する関数
def get_route(graph, orig, dest):
    return nx.shortest_path(graph, orig, dest, weight='length')

# ノードを座標に変換
shortest_route_coords = []
for i in range(len(shortest_route_nodes) - 1):
    segment = get_route(G, shortest_route_nodes[i], shortest_route_nodes[i + 1])
    shortest_route_coords.extend([(G.nodes[node]['y'], G.nodes[node]['x']) for node in segment])

# マップの作成
map_nyc = folium.Map(location=hakodate_station, zoom_start=12)

# マーカーを追加
folium.Marker(hakodate_station, popup="hakodate_station", icon=folium.Icon(color='red')).add_to(map_nyc)
for name, loc in lucky_pierrot_locations.items():
    folium.Marker(loc, popup=name).add_to(map_nyc)

# 最短ルートを描画
folium.PolyLine(shortest_route_coords, color="blue", weight=2.5, opacity=1).add_to(map_nyc)

# ルートに矢印を追加
folium.plugins.AntPath(locations=shortest_route_coords, color="blue", weight=2.5).add_to(map_nyc)

print(f"The shortest route distance is: {shortest_distance / 1000} km")
map_nyc

ちなみに、以前東京でハンバーガー屋さんを探すのが好きだった私は、テレビでラッキーピエロの存在を知り、函館を訪れました。
この記事のように全部回ってやると意気込んでいましたが、個々のハンバーガーは値段の割にサイズがかなりずっしりで、4店舗で限界でした。おいしかったです。

バンズを斜めにした時の高さ？？

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up