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

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

https://luckypierrot.jp/

https://qiita.com/riicon72/items/c696cfc29f2d8be5a94f#_reference-6392c7e61dd18dde38a7

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/986141/48a5c03a-2340-5cff-26c5-bc41974c3552.png)

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

結果はこの通り。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/986141/e392ca09-3a3e-4041-8f29-e9291fb9ec3b.png)


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

## 全店舗回るための準備

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

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

必要なパッケージをインストールしておきます。
```python
pip install folium osmnx networkx
```

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

https://osmnx.readthedocs.io/en/stable/index.html

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

https://networkx.org/

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/986141/b1e0bb0d-eb52-4e77-9299-e27e38509e4e.png)


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

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

https://luckypierrot.jp/shop/

```python
# 函館駅の座標
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で座標をノードに変換
```python
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()`メソッドで得られた結果は次の通りです。
```python
ox.plot_graph_folium(G)
```
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/986141/3bde4ce4-0349-3254-e659-d94927d31afc.png)


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

## NetworkXでノードから最短経路を探索する
得られたノードを使って最短経路を探ります。

```python
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)
```

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

```python
# 経路を取得する関数
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`で描画します。プラグインを使うことで経路に矢印をつけてどのような順番で進むのかを分かるようにしています。

![無題の動画.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/986141/d392fa1c-412d-627c-9cc8-732f676e8f99.gif)


```python
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
```

## まとめ

<details><summary>最終的なコードはこちら</summary>

```python
!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
```

</details>

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

https://luckypierrot.jp/menu/chineasechicken/

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/986141/8a128899-0895-ca19-c3fb-06fc62ae52e2.png)

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