Go to Qiita Advent Calendar Top
LoginSignup
21
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

Day 1

Medley（メドレー） Advent Calendar 2025

@yujittttttt(Yuji Tamai)in株式会社メドレー

チェン素麺 GA篇

Last updated at Posted at 2025-11-30

この記事は Medley（メドレー） - Qiita Advent Calendar 2025 1日目の記事です。

株式会社メドレーでSREエンジニアをしている @yujittttttt です。
私も田舎のネズミが好きです。

本日は 「全国の美味しい素麺を食べたい衝動がLLMを超えた」 話をしたいと思います。

Chain Somen

素麺、美味しいですよね。
私は自宅に徳用そうめんを常にストックしていて、季節問わずいつでも食しています。
私の目が見えなくなっても、私の噛む力で素麺だってわかるくらいに覚えています。

ただ、素麺というのを外食でほとんど食したことがありません。
自宅で簡単に作った素麺でもあんなに美味しいのですから、プロが作ったらもっと美味しいに違いありません。

全国の素麺を提供している飲食店を連鎖的にハシゴしたい

この衝動を一部界隈1で 「チェン素麺」 と言います。

本記事では、全国の素麺屋さんをハシゴするための最短経路を求める方法について論じたいと思います。

最短経路を遺伝的アルゴリズムで求める

最短経路を求める問題は、競技プログラミングの問題でもよく出てくる、いわゆる「巡回セールスマン問題」2です。
すべての拠点を最短経路で通過するにはどの順番で行くのが最適かという問題です。

定義

  • 素麺屋は、某グルメサイトから「そうめん」を店名または説明文に含んでいるものをそれと定義する
  • 株式会社メドレーの本社・六本木ヒルズをスタート地点として、全国の素麺屋をめぐり、六本木ヒルズに帰ってくるルートとする
  • 拠点間の移動は直線的に移動し、交通機関の影響を受けないものとする3
  • 移動距離は、ハバーサイン公式で求めるものとする

ハバーサイン公式は、地球を完全な球体と仮定して、緯度経度から球面上の2点間の最短距離（大円距離）を求める計算方法です。
実際の地球は南北に潰れた楕円体なので、この計算方法では実際には誤差が出ます。

d = 2r \arcsin \left( \sqrt{ \sin^2 \left( \frac{\phi_2 - \phi_1}{2} \right) + \cos \phi_1 \cos \phi_2 \sin^2 \left( \frac{\lambda_2 - \lambda_1}{2} \right) } \right)

順列の計算量の爆発力

某グルメサイトを検索したところ、素麺屋は全国に16ヶ所ありました。
一番確実に最短距離を求める方法は、考えられるすべての経路の移動距離を計算して比較することです。

japan_base.png
※日本地図素材 Frame illust

しかしながら、16ヶ所を巡る経路数は、16の階乗で計算され、20兆9227億以上になります。
これは1経路を1マイクロ秒で計算できたとしても、243日もかかる計算になります。
これが、順列の悪魔の爆弾のような計算量の爆発力です。

243日もかかってしまうと、もはや2026年のアドカレ記事になってしまうので、2025年のアドカレに間に合わせるため、遺伝的アルゴリズム（Genetic Algorithm、以下GA） を用いて解析することにしました。

GA

GAは、遺伝子の進化をモデルにしたアルゴリズムです。
簡単に言えば、何度も試行錯誤して、悪い結果だった要素は淘汰し、良い結果だった要素を組み合わせて次世代を作り出し（交叉）、時には大きな変化を加えて（突然変異）、最適解に近づけていくアプローチです。

例えば、関数f(x)が最大値をとるxを求めるとします。
最初は、xにランダムな値を与えて、最大のf(x)を求めます。
局所最適解となるxを見つけられたら、その周辺のf(x)を重点的に調べます。
しかし、それだけでは全然違うところにある本当の最適解に気づけなくなってしまうので、一定の割合で大きくxを変化させて、最適解を見落とさないようにします。

ga-graph.png

そういうアルゴリズムですので、最適解に辿り着けない可能性は大いにありえます。
その代わりに計算量を大きく減らして、短時間で最適解に近しい値を得ることができるのがGAの良いところです。

GAで解析してみた

Python3でGA解析バッチ処理を作成しました。
実際に動かしてみたところ、50世代目くらいで局所最適解に辿り着くと、そこからいくらやっても変化がなかったので、突然変異を起こしやすくするための工夫があれこれ入っています。

ソースコード
ga.py
#!/usr/bin/env python3
"""遺伝的アルゴリズムで素麺ルートの最短経路を探索する。"""

from __future__ import annotations

import json
import math
import random
import sqlite3
from datetime import datetime, timezone
from pathlib import Path
from typing import Dict, List, Sequence, Tuple
from urllib.parse import urlencode


BASE_DIR = Path(__file__).resolve().parent
DB_PATH = BASE_DIR / "chain-somen.db"
STATE_PATH = BASE_DIR / "ga_state.json"

START_ID = "DEPARTURE"
START_LAT = 35.660259
START_LNG = 139.729584
START_NAME = "出発地点 (六本木ヒルズ)"
START_ADDRESS = "六本木ヒルズ"

GENERATIONS_PER_RUN = 10000
ELITE_RATE = 0.05
MUTATION_RATE = 0.2
POPULATION_SIZE = 400
TOURNAMENT_SIZE = 3
RANDOM_PARENT_RATE = 0.1
ELITE_RESET_INTERVAL = 100
IMMIGRATION_STAGNATION_LIMIT = 1000
IMMIGRATION_RATIO = 0.2
MAX_WAYPOINTS_PER_URL = 9

RUN_TIMESTAMP = datetime.now(timezone.utc).strftime("%Y%m%d%H%M%S")
STATE_BACKUP_PATH = BASE_DIR / f"ga_state_{RUN_TIMESTAMP}.json"


def haversine(lat1: float, lng1: float, lat2: float, lng2: float) -> float:
    """地球上での直線距離(キロメートル)を返す。"""
    r = 6371.0
    phi1 = math.radians(lat1)
    phi2 = math.radians(lat2)
    d_phi = math.radians(lat2 - lat1)
    d_lambda = math.radians(lng2 - lng1)
    a = math.sin(d_phi / 2) ** 2 + math.cos(phi1) * math.cos(phi2) * math.sin(d_lambda / 2) ** 2
    c = 2 * math.atan2(math.sqrt(a), math.sqrt(1 - a))
    return r * c


def ensure_logs_table(conn: sqlite3.Connection) -> None:
    conn.execute(
        """
        CREATE TABLE IF NOT EXISTS logs (
            id INTEGER PRIMARY KEY AUTOINCREMENT,
            restaurant_ids TEXT NOT NULL,
            total_distance REAL NOT NULL,
            created_at TEXT NOT NULL
        )
        """
    )
    conn.commit()


def load_restaurants(conn: sqlite3.Connection) -> List[Dict]:
    cur = conn.execute("SELECT id, name, address, lat, lng FROM restaurants ORDER BY id")
    rows = [
        {"id": row[0], "name": row[1], "address": row[2], "lat": row[3], "lng": row[4]}
        for row in cur.fetchall()
    ]
    if not rows:
        raise RuntimeError("restaurantsテーブルが空です。setup.pyを先に実行してください。")
    return rows


def load_distance_lookup(conn: sqlite3.Connection) -> Dict[Tuple[str, str], float]:
    lookup: Dict[Tuple[str, str], float] = {}
    cur = conn.execute("SELECT from_restaurant_id, to_restaurant_id, distance FROM distances")
    for from_id, to_id, distance in cur.fetchall():
        lookup[(from_id, to_id)] = distance
    return lookup


def pair_distance(
    rest_a: str,
    rest_b: str,
    coords: Dict[str, Tuple[float, float]],
    lookup: Dict[Tuple[str, str], float],
) -> float:
    key = tuple(sorted((rest_a, rest_b)))
    distance = lookup.get(key)
    if distance is not None:
        return distance
    lat1, lng1 = coords[rest_a]
    lat2, lng2 = coords[rest_b]
    return haversine(lat1, lng1, lat2, lng2)


def route_distance(
    route: Sequence[str],
    coords: Dict[str, Tuple[float, float]],
    lookup: Dict[Tuple[str, str], float],
) -> float:
    total = 0.0
    extended = [START_ID] + list(route) + [START_ID]
    for prev_id, next_id in zip(extended, extended[1:]):
        total += pair_distance(prev_id, next_id, coords, lookup)
    return total


def rank_population(
    population: Sequence[Sequence[str]],
    coords: Dict[str, Tuple[float, float]],
    lookup: Dict[Tuple[str, str], float],
) -> List[Tuple[List[str], float]]:
    scored: List[Tuple[List[str], float]] = []
    for route in population:
        distance = route_distance(route, coords, lookup)
        scored.append((list(route), distance))
    scored.sort(key=lambda item: item[1])
    return scored


def tournament_select(ranked: Sequence[Tuple[List[str], float]], k: int = TOURNAMENT_SIZE) -> List[str]:
    contenders = random.sample(ranked, k=min(k, len(ranked)))
    contenders.sort(key=lambda item: item[1])
    return list(contenders[0][0])


def select_parent(ranked: Sequence[Tuple[List[str], float]]) -> List[str]:
    if random.random() < RANDOM_PARENT_RATE:
        return list(random.choice(ranked)[0])
    return tournament_select(ranked)


def ordered_crossover(parent_a: Sequence[str], parent_b: Sequence[str]) -> List[str]:
    if len(parent_a) < 2:
        return list(parent_a)
    start, end = sorted(random.sample(range(len(parent_a)), 2))
    child = [None] * len(parent_a)
    child[start : end + 1] = parent_a[start : end + 1]

    pointer = 0
    for gene in parent_b:
        if gene in child:
            continue
        while child[pointer] is not None:
            pointer += 1
        child[pointer] = gene
    return child  # type: ignore[return-value]


def mutate(route: List[str]) -> None:
    if len(route) < 2:
        return
    idx_a, idx_b = random.sample(range(len(route)), 2)
    route[idx_a], route[idx_b] = route[idx_b], route[idx_a]


def evolve_population(
    ranked_population: Sequence[Tuple[List[str], float]],
    current_generation: int,
) -> List[List[str]]:
    if current_generation % ELITE_RESET_INTERVAL == 0 and current_generation != 0:
        elite_count = 0
    else:
        elite_count = max(1, int(len(ranked_population) * ELITE_RATE))
    next_generation = [list(route) for route, _ in ranked_population[:elite_count]]

    while len(next_generation) < POPULATION_SIZE:
        parent_a = select_parent(ranked_population)
        parent_b = select_parent(ranked_population)
        child = ordered_crossover(parent_a, parent_b)
        if random.random() < MUTATION_RATE:
            mutate(child)
        next_generation.append(child)

    return next_generation


def initialize_population(rest_ids: Sequence[str]) -> List[List[str]]:
    population: List[List[str]] = []
    for _ in range(POPULATION_SIZE):
        population.append(random.sample(rest_ids, len(rest_ids)))
    return population


def set_random_state_from_serialized(state_obj) -> None:
    def to_tuple(obj):
        if isinstance(obj, list):
            return tuple(to_tuple(item) for item in obj)
        return obj

    random.setstate(to_tuple(state_obj))


def serialize_random_state():
    return random.getstate()


def load_state(rest_ids: Sequence[str]):
    if not STATE_PATH.exists():
        return None
    data = json.loads(STATE_PATH.read_text(encoding="utf-8"))
    saved_ids = data.get("restaurant_ids")
    if sorted(saved_ids or []) != sorted(rest_ids):
        return None
    population = data.get("population") or []
    if len(population) != POPULATION_SIZE:
        return None
    required_set = set(rest_ids)
    for route in population:
        if set(route) != required_set:
            return None
    random_state = data.get("random_state")
    if random_state:
        set_random_state_from_serialized(random_state)
    return {
        "population": [list(route) for route in population],
        "completed_generations": int(data.get("completed_generations", 0)),
        "stagnant_generations": int(data.get("stagnant_generations", 0)),
        "last_best_distance": data.get("last_best_distance"),
    }


def save_state(
    population: Sequence[Sequence[str]],
    completed_generations: int,
    rest_ids: Sequence[str],
    stagnant_generations: int,
    last_best_distance: float | None,
) -> None:
    payload = {
        "population": [list(route) for route in population],
        "restaurant_ids": list(rest_ids),
        "completed_generations": completed_generations,
        "random_state": serialize_random_state(),
        "stagnant_generations": stagnant_generations,
        "last_best_distance": last_best_distance,
    }
    serialized = json.dumps(payload, ensure_ascii=False, indent=2)
    STATE_PATH.write_text(serialized, encoding="utf-8")
    STATE_BACKUP_PATH.write_text(serialized, encoding="utf-8")


def save_log(conn: sqlite3.Connection, route: Sequence[str], total_distance: float) -> None:
    conn.execute(
        """
        INSERT INTO logs (restaurant_ids, total_distance, created_at)
        VALUES (?, ?, ?)
        """,
        (",".join(route), total_distance, datetime.now(timezone.utc).isoformat()),
    )
    conn.execute(
        """
        DELETE FROM logs
        WHERE id NOT IN (
            SELECT id FROM logs ORDER BY total_distance ASC, id ASC LIMIT ?
        )
        """,
        (GENERATIONS_PER_RUN,),
    )
    conn.commit()


def _format_coord(rest_id: str, coords: Dict[str, Tuple[float, float]]) -> str:
    lat, lng = coords[rest_id]
    return f"{lat},{lng}"


def _build_google_maps_url(nodes: Sequence[str], coords: Dict[str, Tuple[float, float]]) -> str:
    origin = _format_coord(nodes[0], coords)
    destination = _format_coord(nodes[-1], coords)
    waypoints_raw = [_format_coord(rid, coords) for rid in nodes[1:-1]]
    waypoints = "|".join(waypoints_raw)
    params = {
        "api": 1,
        "origin": origin,
        "destination": destination,
        "travelmode": "driving",
    }
    if waypoints:
        params["waypoints"] = waypoints
    return f"https://www.google.com/maps/dir/?{urlencode(params, safe='|,')}"


def build_google_maps_urls(route: Sequence[str], coords: Dict[str, Tuple[float, float]]) -> List[str]:
    urls: List[str] = []
    chunk_nodes: List[str] = [route[0]]
    for node in route[1:]:
        chunk_nodes.append(node)
        waypoint_count = max(0, len(chunk_nodes) - 2)
        if waypoint_count >= MAX_WAYPOINTS_PER_URL or node == route[-1]:
            urls.append(_build_google_maps_url(chunk_nodes, coords))
            chunk_nodes = [node]
    return urls


def main() -> None:
    with sqlite3.connect(DB_PATH) as conn:
        ensure_logs_table(conn)
        restaurants = load_restaurants(conn)
        restaurant_lookup = {row["id"]: row for row in restaurants}
        coords = {row["id"]: (row["lat"], row["lng"]) for row in restaurants}
        coords[START_ID] = (START_LAT, START_LNG)
        lookup = load_distance_lookup(conn)
        rest_ids = [row["id"] for row in restaurants]

        state = load_state(rest_ids)
        if state:
            population = state["population"]
            completed_generations = state["completed_generations"]
            stagnant_generations = state.get("stagnant_generations", 0)
            last_best_distance = state.get("last_best_distance")
            print(f"前回の状態を読み込みました。累計{completed_generations}世代。")
        else:
            population = initialize_population(rest_ids)
            completed_generations = 0
            stagnant_generations = 0
            last_best_distance = None
            print("新規に個体群を生成しました。")

        for generation_offset in range(1, GENERATIONS_PER_RUN + 1):
            ranked = rank_population(population, coords, lookup)
            best_route, best_distance = ranked[0]
            current_generation = completed_generations + generation_offset

            if last_best_distance is None or best_distance < last_best_distance - 1e-9:
                last_best_distance = best_distance
                stagnant_generations = 0
            else:
                stagnant_generations += 1

            if stagnant_generations >= IMMIGRATION_STAGNATION_LIMIT:
                print("停滞を検知したため移民を導入します。")
                working_population = [list(route) for route, _ in ranked]
                immigrants = max(1, int(POPULATION_SIZE * IMMIGRATION_RATIO))
                for idx in range(immigrants):
                    working_population[-(idx + 1)] = random.sample(rest_ids, len(rest_ids))
                population = working_population
                ranked = rank_population(population, coords, lookup)
                best_route, best_distance = ranked[0]
                last_best_distance = best_distance
                stagnant_generations = 0

            if generation_offset == 1 or generation_offset % 50 == 0:
                print(f"世代{current_generation}: 距離 {best_distance:.2f} km")
            save_log(conn, best_route, best_distance)
            population = evolve_population(ranked, current_generation)
            save_state(population, current_generation, rest_ids, stagnant_generations, last_best_distance)

        ranked_final = rank_population(population, coords, lookup)
        best_route, best_distance = ranked_final[0]
        save_log(conn, best_route, best_distance)
        save_state(
            population,
            completed_generations + GENERATIONS_PER_RUN,
            rest_ids,
            stagnant_generations,
            last_best_distance,
        )

        print("\n=== 最終結果 ===")
        print(f"総移動距離: {best_distance:.2f} km")
        print("巡回順序:")
        full_route = [START_ID] + best_route + [START_ID]
        for idx, rest_id in enumerate(full_route):
            if idx == 0:
                segment_distance = 0.0
            else:
                segment_distance = pair_distance(full_route[idx - 1], rest_id, coords, lookup)
            if rest_id == START_ID:
                name = START_NAME
                address = START_ADDRESS
            else:
                info = restaurant_lookup[rest_id]
                name = info["name"]
                address = info["address"]
            print(f"{idx:02d}. {name} ({address}) - 前地点から {segment_distance:.2f} km")
        urls = build_google_maps_urls(full_route, coords)
        if len(urls) == 1:
            print(f"\nGoogle Maps URL:\n{urls[0]}")
        else:
            print("\nGoogle Maps URLs:")
            for idx, url in enumerate(urls, start=1):
                print(f"{idx:02d}. {url}")


if __name__ == "__main__":
    main()

GAによる最適解

総移動距離: 約 3,407 km

順序 所在地 区間距離(km)
Start 出発地点 (六本木ヒルズ) -
1 東京都江東区 6.12
2 東京都墨田区 3.07
3 東京都台東区 2.48
4 埼玉県さいたま市 21.61
5 京都府京都市 364.73
6 大阪府大阪市 42.24
7 兵庫県姫路市 74.93
8 福岡県北九州市 379.93
9 沖縄県豊見城市 902.98
10 奈良県桜井市 1216.64
11 奈良県桜井市 0.25
12 静岡県浜松市 173.16
13 静岡県静岡市 68.45
14 神奈川県足柄下郡 69.63
15 東京都品川区 72.97
16 東京都世田谷区 2.94
Goal 到着地点 (六本木ヒルズ) 4.87

沖縄以降の経路を青にしています。
近いところから順番に回っていくかと思いましたが、北寄りの拠点を取りつつ西に向かい、沖縄からは南寄りの拠点を取りながら戻ってくるという、輪を作るような経路になりました。
東京の店から始まり東京での店で終わらせてるのは、何かしらの思いを感じさせます。

japan_ga.png

Gemini3でも試してみた

Gemini3に同じ命題を与えて解析してみました。計算時間は30秒程度でした。

総移動距離: 約 3,439 km

順序 所在地 区間距離(km)
Start 出発地点 (六本木ヒルズ) -
1 東京都江東区 6.1
2 東京都墨田区 3.1
3 東京都台東区 2.5
4 埼玉県さいたま市 21.6
5 東京都世田谷区 24.6
6 東京都品川区 2.9
7 神奈川県足柄下郡 71.4
8 静岡県静岡市 69.8
9 静岡県浜松市 68.7
10 京都府京都市 182.5
11 奈良県桜井市 53.9
12 奈良県桜井市 0.2
13 大阪府大阪市 37.0
14 兵庫県姫路市 75.1
15 福岡県北九州市 377.2
16 沖縄県豊見城市 888.9
Goal 到着地点 (六本木ヒルズ) 1,553.9

こちらは西に向かいながら近くにある拠点をどんどん取っていって、沖縄を最後に帰ってくる経路になりました。
人間が経路を考えたらこうなるだろうなという印象でした。

japan_gemini.png

解析方法を聞いたら以下のように解説してくれました。素晴らしい分析からのアプローチだと思いました。

Geminiの解説

経路探索アルゴリズム：ハイブリッド手法

日本の地理的特性を活かしたヒューリスティック（発見的）手法を組み合わせて解いています。

A. 地理的クラスタリング（グループ化）

まず、位置情報を基に大きく3つのエリアに分類しました。

  1. 首都圏（密集エリア）： 東京、埼玉、神奈川
  2. 本州・九州（線形エリア）： 静岡、京都、奈良、大阪、兵庫、福岡
  3. 遠隔地： 沖縄

B. 最近傍法 (Nearest Neighbor) ＋ 2-opt法

次に、以下のロジックで順序を決定しました。

  1. 首都圏の最適化（局所探索）
    六本木ヒルズを起点に、最も近い未訪問の点を次々に選ぶ「最近傍法」をベースにしつつ、経路が交差しないように修正しました。
    ◦ 六本木から見て東側（江東区・墨田区）を先に回収。
    ◦ 北上して埼玉を回収。
    ◦ 南西（世田谷・品川）へ抜けて神奈川へ接続。
    ◦ これにより、都内での行ったり来たり（ジグザグ移動）を排除しました。
  2. 一筆書きの適用（大域探索）
    首都圏を出た後は、日本の地形が「弓なりの線形」であることを利用し、経度順（東から西へ）に並べ替えるのが最も効率的です。
    ◦ 神奈川 → 静岡 → 関西 → 九州 と、一方向に進むことで距離ロスを最小化します。
  3. 終端処理（沖縄と帰還）
    沖縄は他の点から極端に離れているため、ルートの途中（例えば関西と九州の間）に挟むと、「本州→沖縄→本州」という巨大な往復移動が発生し、距離が跳ね上がります。
    そのため、 「全ての拠点を回った最後に沖縄に行き、そこから一気にスタート地点（東京）に戻る」 という三角形を描くルートを採用しました。

人類が作ったGA vs Gemini

[GA] 3,407 km < [Gemini] 3,439 km

32km差で人類の勝利です！🎊🎊🎊

ただ、GAは開発〜検証で工数 8時間くらいかかっているので、タイパでいうとGeminiの圧倒的勝利です🏳️。

結論

今回はGAにより巡回セールスマン問題を解決しましたが、他にも解決方法はあると思います。
私も十本に一本くらいしか面白い解決方法には出会えませんが、でもその一本に人生を変えられた事があります。

タイパよくLLMを使うのも良いですが、時には自分でアプローチから考えてみるのも面白いです。

We're hiring!

株式会社メドレーでは様々な職種で人材を募集しています4。
お気軽にお問合せください。

採用情報 | 株式会社メドレー

明日も見ると言いなさい

明日12月2日は @1plus4 による記事です！明日もお楽しみに！

  1. 筆者の心の中にだけ存在している界隈です ↩

  2. 筆者はよく「巡回サラリーマン問題」と言い間違えます ↩

  3. 筆者は天使の悪魔と契約しているので、空を飛べます ↩

  4. デビルハンターは募集していません ↩

21
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
21
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?