量子アニーリング前処理・共通問題生成仕様

更新日: 2026-08-28

1. 目的

本仕様は、道路・低空・高空・汎用の巡回、割当、衝突回避、突発禁止条件を、量子アニーリング、量子最適化、または古典アニーリングへ渡す共通QUBOデータへ変換する方法を定める。

実装は EvoSpikeNet-Core/evospikenet/optimization/ に置く。アプリケーションはドメイン固有データを整形するだけとし、QUBO生成、動的制約、ソルバー入力形式を個別に再実装しない。

2. 責務分離

flowchart LR
    Source[道路網・空域・運行データ] --> Normalize[Domain adapter]
    Normalize --> Problem[OptimizationProblem]
    Restrictions[突発禁止・気象・規制] --> Dynamic[DynamicConstraint]
    Dynamic --> Build[QuboProblemBuilder]
    Problem --> Build
    Build --> Qubo[QuboProblem]
    Qubo --> Solver[D-Wave / OpenJij / Fixstars / Qiskit / SA]
    Solver --> Verify[アプリケーションの安全検証]

RoadNetworkBuilder: OSMまたはキャッシュ済みNetworkX道路グラフから、有向道路リンクと移動コストを作成する。
OptimizationProblem: 候補、競合、必須選択、動的制約を表す共通入力モデル。
QuboProblemBuilder: 共通入力を problem["qubo"] へ変換する。小規模では密行列、大規模では非ゼロ係数だけを持つ疎辞書を選択できる。
アプリケーション: 道路規制・飛行規則・衝突判定・解の適用可否を最終検証する。量子ソルバーの出力だけで実機を制御しない。

3. 共通入力仕様

OptimizationProblem の domain は以下から選ぶ。

`domain`	候補例	主な制約例
`road`	拠点間の道路リンク、配送割当	一方通行、通行止め、容量、時間窓
`low_altitude`	UAV回廊、ウェイポイント、高度層	ジオフェンス、障害物、電池、機体間分離
`high_altitude`	飛行回廊、空域予約、高度層	飛行許可、気象、航空機分離、時間枠
`generic`	任意の選択、割当、スケジューリング	ドメイン固有ルール

候補には一意な id と最小化する cost を持たせる。追加属性はドメインアダプタと動的制約の照合に使用する。

OptimizationProblem(
    name="morning-delivery-replan",
    domain="road",
    candidates=[
        {
            "id": "road:hub:depot-a",
            "cost": 1350.0,
            "source_id": "hub",
            "destination_id": "depot-a",
            "path_node_ids": (101, 302, 417),
        }
    ],
    conflict_pairs=[("route-a", "route-b")],
    required_groups=[("route-a", "route-b")],
    dynamic_constraints=[],
)

4. 道路データ生成

4.1 実装場所と任意依存

道路ネットワーク生成は evospikenet.optimization.road_network の RoadNetworkBuilder が担当する。OSMnxは必須依存にしない。実OSM取得が必要な環境だけで次を導入する。

pip install 'evospikenet[road]'

オフラインテストや再現実験では、キャッシュ済みのNetworkX有向グラフを RoadNetworkBuilder.from_graph() に渡す。

4.2 OSMからの生成手順

拠点を RoadLocation(location_id, latitude, longitude) として定義する。
対象領域を道路用途（network_type="drive"）で取得する。
各拠点を最寄りのOSM道路ノードへスナップする。
全順序対 \(i \ne j\) の最短経路を length 重みで算出する。
到達できない対はリンクを作らず、探索候補から除外する。
生成日時、バウンディングボックス、ネットワーク用途を RoadNetworkSnapshot.metadata に保存する。

自動車道路は一方通行を持つため、道路グラフを無向化してはならない。\(d(i,j)\) と \(d(j,i)\) を別々に保持する。

from evospikenet.optimization import RoadLocation, RoadNetworkBuilder

locations = [
    RoadLocation("haneda", 35.5492, 139.7898, "Haneda Hub"),
    RoadLocation("kawasaki", 35.5312, 139.7029, "Kawasaki Depot"),
]
snapshot = RoadNetworkBuilder().from_osm(
    locations,
    north=35.68,
    south=35.48,
    east=139.84,
    west=139.60,
)

from_osm() はOSMnx 1系と2系の graph_from_bbox 引数差を内部で吸収する。OSMnxの実ネットワークは MultiDiGraph なので、複数道路エッジのうち length が最小のものを最短経路計算に使用する。

4.3 添付スクリプトとの差分

添付の生成例の目的は正しいが、本実装では以下を変更する。

get_undirected() を使わず、有向グラフを保持する。
ペアは i < j ではなく全順序対 \(i \ne j\) を評価する。
9999.0 の疑似距離を出力せず、到達不能リンクは候補から除外する。
Python表示用 road_links ではなく、RoadNetworkSnapshot と OptimizationProblem を返す。
OSMnxは任意依存とし、通常テストではネットワークアクセスを使わない。

5. 巡回・競合・禁止条件のQUBO変換

候補 \(c_i\) を選ぶ二値変数 \(x_i \in \{0, 1\}\) とする。候補コストは対角項として加える。

\[ C_{base} = \sum_i cost_i x_i \]

衝突する道路区間・空間セル・時刻枠の候補ペア \((i,j)\) には、同時選択を避ける罰則を加える。

\[ P_{conflict} = \lambda_c x_i x_j \]

候補群 \(G\) から一つだけを選ぶ場合は、次を加える。

\[ P_{exactly-one} = \lambda_g \left(\sum_{i \in G} x_i - 1\right)^2 \]

QuboProblemBuilder は conflict_pairs と required_groups からこれらの項を構築する。巡回路の連結性、出発・帰着、部分巡回排除、複数車両容量、時間窓は、候補の離散化後に道路専用エンコーダで追加する。大規模道路網を交差点単位でQUBO化しない。

6. 突発的禁止条件

DynamicConstraint で、事故、工事、道路閉鎖、災害、飛行禁止空域、気象、機体故障、通信断を期限付きで表現する。

from datetime import datetime, timezone
from evospikenet.optimization import DynamicConstraint

closure = DynamicConstraint(
    constraint_id="road-closure-20260828-01",
    constraint_type="road_closure",
    severity="hard",
    candidate_ids=frozenset({"road:haneda:kawasaki"}),
    active_from=datetime(2026, 8, 28, 10, tzinfo=timezone.utc),
    active_until=datetime(2026, 8, 28, 12, tzinfo=timezone.utc),
    penalty=10000.0,
)

hard: 対象候補に大きなQUBO罰則を加える。候補生成時にも除外し、解の検証時にも拒否する。
soft: 迂回、渋滞、気象、通信品質低下などを追加コストとして加える。
candidate_ids: 特定の道路リンク、回廊、機体、割当候補を指定する。
attributes: {"airspace": "restricted"} や {"road_class": "motorway"} のように候補属性で対象を選ぶ。
active_from / active_until: 評価時刻に有効な制約だけを適用する。期限切れ制約はQUBOに影響しない。

7. ソルバー接続と適用条件

7.1 QUBO表現の選択

QuboProblemBuilder.build() は representation="dense" または representation="sparse" を受け付ける。既定値は互換性のため dense である。

dense_problem = QuboProblemBuilder().build(problem, representation="dense")
sparse_problem = QuboProblemBuilder().build(problem, representation="sparse")

dense_matrix = sparse_problem.to_dense()
sparse_coefficients = sparse_problem.to_sparse()

疎表現は次の辞書形式で、ゼロ係数を保持しない。

{(row_index, column_index): coefficient}

運用上は、QUBOを内部で疎辞書として生成し、疎辞書を受け取れるアニーラー・プラグインへそのまま渡す。Qiskitのように密行列を要求するバックエンドでは、ソルバー境界でだけ to_dense() 相当の変換を行う。全候補が一意に決まる場合は、ソルバー探索を省略して直接割当し、HPDBNと安全制約で検証する。

密行列を避けることは、QUBOの候補間競合探索を自動的に高速化することを意味しない。候補が多い場合は、同一機体、同一時間スロット、軌道が重なる候補だけを比較し、無関係な候補の全組合せ比較を避ける必要がある。

from evospikenet.optimization import QuboProblemBuilder
from evospikenet.optimizer import get_optimizer

solver_input = QuboProblemBuilder().build(road_problem, representation="sparse").as_problem_dict()
solutions = get_optimizer("dwave").solve(
    solver_input,
    options={"sampler": "QPU", "num_reads": 100},
)

同じ solver_input は dwave、openjij、fixstars_amplify、qiskit と古典フォールバックに渡せる。ただし、量子実機・量子アニーリング・クラウド最適化は緊急制御の待機点にしない。HPDBNとの外部実行契約は HPDBN外部定義最適化に従う。

8. テストと受け入れ条件

有向道路で往復コストが異なること。
到達不能なリンクが候補に含まれないこと。
MultiDiGraph の複数エッジから最短の length を選ぶこと。
道路閉鎖が有効時間内だけハード制約となること。
道路、低空、高空、汎用の全ドメインが同一QUBO出力契約を満たすこと。
ソルバーの解を道路規制、空域規制、衝突判定、安全制御で再検証すること。