令和元年度（第19回）電子航法研究所研究発表会

6/7/2019

空域編成に対する2つの最適化アプローチ
筑波大学

猿渡康文

神奈川大学

伊豆永洋一

防衛大学校

鵜飼孝盛

航空交通管理領域 蔭山康太

背景と目的解法のフレームワーク
管制作業量和最小化
管制作業量平準化
可視化
テストデータへの適用

我が国の航空交通
航空管制の年間取り扱い数
1998年（197万）→2017年（310万）：1.6倍以上
国際線/上空通過を中心とした需要の継続の予測

効率性/環境への意識の向上
燃料効率の高い飛行の実現の要求

航空交通システムの性能向上の必要我が国の航空路
レーダ覆域（陸域）“飛行の道路”

http://www8.cao.go.jp/koutu/taisaku/h20kou_haku/genkyo/h3/h3s2_1.html

陸域において定義される
出発・目的空港の組合せごとの推奨経路
固定の経路構成

計画経路

ウェイポイント(航空無線施設/地点)
緯度経度の定義

計画経路
RJCC
計画経路

STONE

TOBBY
HPEDAIGO
RJTT

ウェイポイント(航空無線施設/地点)
緯度経度の定義

運航者が飛行前に経路を計画ウェイポイント（WP）の列

計画経路（交通量に応じて色分け）

RJCC
計画経路

STONE

TOBBY
HPE
DAIGO
RJTT

ウェイポイント(航空無線施設/地点)
緯度経度の定義

運航者が飛行前に経路を計画
ウェイポイント（WP）の列

航空管制機関で集計
空域全体の飛行の流れ

利用者選択経路
User Preferred Route：UPR
運航者が燃料消費などを加味して計画した経路
風向・風速に応じた様々な経路構成

UPR

太平洋上で運用
陸域への拡大計画
向い風の迂回セクタ（空域の単位）
セクタ = 航空管制官の配置単位
飛行の監視、指示、情報交換（管制作業）

航空管制官

我が国のセクタの例

セクタごとに配置セクタとしての条件（主要なもの）
セクタ最小滞在時間（管制指示時間の確保）
境界線­WP間最小距離（管制指示時間の確保）
凸性（同一航空機の複数回進入の回避）
連結性（飛び地の回避）

効率的運航支援の重要性
現行の推奨経路

UPR経路の例

風向・風速の影響で変動交通流（経路構成）の交差頻度／取り扱い数の増減
管制作業量：交通流に依存セクタ間での管制作業量のばらつきの増大

効率的運航支援：経路構成に応じたセクタ境界線設定

空域編成問題（本研究での定義）
セクタA
セクタB

セクタD
セクタC

セクタA

？

セクタB

？

セクタD
セクタC

（入力）計画経路（WPの列）の集合（出力）セクタ数とセクタ境界線（条件）セクタとして満たすべき条件
各セクタでの管制作業量の平準化 → 最適化

管制作業量のモデル化
セクタ間作業②

セクタ間作業①
通信設定
飛行計画などの確認

離脱

通信設定

飛行数に依存

飛行数に依存進入

飛行距離に依存セクタ内作業
他飛行との間隔などの確認

管制作業量 =
セクタ内作業 + λ(セクタ間作業① + セクタ間作業②）

数理最適化アプローチ■最適化のターゲット：
管制作業量の平準化
航空機の飛行距離と機数の扱いがポイント■求解のアプローチ：
飛行距離機数求解

意図

管制作業量和最小化
そのまま
そのまま
ハード

管制作業量平準化
機数で近似
そのまま
比較的容易

・管制作業量の和の最小化
を、各セクタでの管制作業量の最小化で実現・セクタ間での管制作業量のばらつきを上下限を設定して抑制

そのまま

計画経路のグラフによる表現
頂点：WP

枝：隣接WP間

重み付きグラフG = (V, E)（枝への重み付けなどにより作業量の表現が可能）

G1, G2, ⋯, Gk
部分グラフへの分割
各セクタに対応
大まかな領域

背景と目的解法のフレームワーク
管制作業量和最小化
管制作業量平準化
可視化
テストデータへの適用

管制作業量和最小化問題と列生成アプローチ〜解法構築のアイデア
セクタA
セクタC

セクタB
計画経路とセクタの例
セクタ
空域編成
WP全体をグループ分けすることで実現

グループ内のWPが必ずつながっているもの

グラフの木構造を利用可能

管制作業量和最小化問題と列生成アプローチ〜集合分割問題
⇥min.

c1

c2

c316 1
66 ..
4 .

10..
.

01..
.

<latexit sha1_base64="3Q4l9sM0AMhSsSTl2tV8l9JLpsY=">AAAC4XichVE7bxQxEJ5dHjmWRy6hiUSz4pSI6jSbIBFRRdBQ5sElkbLRyutzDite78rrO3HZ3A+ACtFQpAoSQoifQcMfoEhLhyiDREPB7EMgiAhjefz583wzYzvOlMwt4onjXrh46fJU64p39dr1G9PtmdnNPB0aLno8VanZjlkulNSiZ6VVYjszgiWxElvx/sPyfGskTC5T/diOM7GbsIGWe5IzS1TUPgxjMZC6YMaw8aRQZBPfa8g4YdbIpxOPR4G/4PNosfJL5EPVT21+PuCR9kKh+7/y+GFYE3U1L2p3sIuV+WdB0IAONLaatt9CCH1IgcMQEhCgwRJWwCCnsQMBIGTE7UJBnCEkq3MBE/BIO6QoQRGM2H3yA9rtNKymfZkzr9ScqiiahpQ+zOMnfIen+BHf4xf88c9cRZWj7GVMa1xrRRZNP5/b+P5fVUKrhSe/Vef2bGEPlqteJfWeVUx5C17rRwevTjfur88XC/gav1L/x3iCH+gGevSNv1kT60dQfkDw93OfBZuL3QC7wdrdzsqD5itacAtuwx1673uwAo9gFXpU97PTcmacWZe7z9wX7ss61HUazU34w9yjn85CtSc=</latexit>

s.t.

2

⇤. . . . . . . . . . . . cn
管制作業量323 2 3... ... ... ... 0x1167 6 7... ... ... ... 1 77 6 x2 7 6 1 7.. 7 6 .. 7 = 6 .. 7... ... ... ... . 54 . 5 4 . 50 1 1 ... ... ... ... 0<latexit sha1_base64="czXmzWpUn016DsjF5UAi85xaROI=">AAAEDXicjVG/b9NAFH6x+VEOaFNYkFgsokZM0buqUhFSUQULY3+QtlIcWbZzSU+92JZ9iRqs/AMsjAxMIKEKMbMhFgb4Bxj6JyDGIrEw8Ow4gpK05Fnn++6793337p0XKZloxOOSYV64eOny3BV29dr1+YXy4o2dJOzFvqj7oQrjPc9NhJKBqGupldiLYuF2PSV2vYNH2f5uX8SJDIMnehCJZtftBLItfVcT5SyWjmwl2rrBbE90ZJC6cewOhqkqYsi4VbWygTRs1Qp1cj5Ay7bZWMBnFPFMZPfH9ASYyaTIJqfx0bMej8wWQau4O7Nj2dnXTVZlU1vjD9mhkxd86Cz/VXdOBFOd1s504qNunXLhUz2ccgVrmIc1CXgBKlDERlg+AhtaEIIPPeiCgAA0YQUuJPQ1gANCRFwTUuJiQjLfFzAERtoeZQnKcIk9oH+HVo2CDWideSa52qdTFI2YlBYs4Vd8iyf4Bd/hN/x1pleae2S1DGj2RloROQvPbm3//K+qS7OG/T+qc2vW0IZ7ea2Sao9yJruFP9L3n7442b6/tZRW8TV+p/pf4TF+ohsE/R/+m02x9RKyB+D/tnsS7CzXONb45kpl/WHxFHNwG+7AXer3KqzDY9iAOvjGvLFirBkPzOfme/OD+XGUapQKzU04Febn30w9ElM=</latexit>

セクタ

xn

セクタを全列挙
困難
列生成法の利用
効率的に列挙1

意思決定変数：選ぶ(1)／選ばない(0)
管制作業量
[

352

3

142

53

2

62

12
2

WPと計画経路

26636
64665465710110010001010 · · · · · · · · · · · ]·010011セクタ

37777· · · · · · · · · · · ·775

管制作業量和最小化問題と列生成アプローチ〜アルゴリズム
列生成アルゴリズム（限定フェーズ）

1. （すでに生成した）一部の列だけに限定した部分問題を解き、暫定解を得る（列生成フェーズ）2. 必要に応じて列（セクタの候補）を逐次生成する■追加すべき列が存在しないならば終了する■有用な列が存在するならば、部分問題に追加し、1へ戻る

一部の列生成された列暫定解の双対情報
セクタ生成問題
列すべての列

管制作業量和最小化問題と列生成アプローチ〜列生成セクタ（根付き有向木）生成問題
根min.

(1sub. toX✓)

X

wij (1yi )yj + ✓(i,j)2EX

wij dij zij(i,j)2Ez0j = 1,j2 (0)Xzji = yij2⇢(i)

Xj2 (i)for i 2 V ,zij  |V | ⇥ yili X+ 1  lj +X|V |(1zij =yi(i,j)2E

根for i 2 V ,zij )1,for (i, j) 2 E,i2V

yi 2 {0, 1} for i 2 V ,zij 2 {0, 1} for (i, j) 2 Ē,li 2 R for i 2 V .

<latexit sha1_base64="VBqOLNX618ZUdbmZsa/fQLoUgCM=">AAAGAHicpZPPTxNBFMcHaRXXH4BeTLxMhGIr0Mxy0ZCQEA2JR6BSSBhsdrfTdsrsbt2dVssyF4/+AyZ60sSo8WC8evXiP+CBP8F4xMSLB99Oh4A0VKPbdPbt2/f9vO/My7otwWNJyN7QqeFM9vSZkbPWufMXLo6OjV8qx2E78tiaF4ow2nCdmAkesDXJpWAbrYg5vivYurt9J32/3mFRzMPgnuy22Jbv1ANe454jIVUZH35GN60cppI9kklpWeVpRyZUAKDqqEqSp74jG54jkpIqqPvJDVWYT8sFq8ldi7qszoPEiSKnqxIhlNXj+DwoKjyFaZXHLeF0Y9kVDOftWSobTDoFTOO2D3A+04SYB3hJ4YeVhDcV1HQhUAVYmwpP457iZEFVrzt6xbOmjuuassJmIykx9a7RmFJjM267RSzDfqc9SlNTaJUJ6eRJQWHoQppqwZ5JEbm/EPHCgTNaZ1qetn/QdqrmwGthhCeN20mluQOxUSM00CaQFrDZ0H8Q+4xCwW55F2jcZ/G/NRBaNG1rmEgHOQ1IGG2vR6Gfd2SwwDzR89H5G78Lx0auDc/axpexn240wWQGHA3cjNYcHMRg0aEV6jpRsqQO5OKwZfrpuG6yOqhn0aIsqJpPyMrRiNcbEpJblmVVxiZIkegL9we2CSaQuZbDsdeIoioKkYfayEcMBUhCLJCDYvhtIhsR1ILcFkogF0HE9XuGFLJA24YqBhUOZLdhrcPTpskG8JwyY632oIuAfwRKjHLkC3lL9sln8o58JT9PZCWakXrpwt3taVmrMvrkSunHH1U+3CVqHKoGepaohm5prxy8t3Qm3YXX03d2nu6X5ldzyRR5Sb6B/xdkj3yCHQSd796rFbb6HKUDsI8fd39QnivapGivzE0s3jajGEFX0TWUh/O+iRbRXbSM1pCXGcpcz5CMnX2cfZN9n/3QKz01ZDSX0W9X9uMvNVfLKw==</latexit>yi =(1 waypoint i in the tree
0 otherwise<latexit sha1_base64="0k7M5KVG6Rtd17TXzFdDeJKEgXU=">AAACwHichVHLahRBFD1pH4ntI6NuBDeFkwRXw+0gRAQhxI3LPJwkMB2G7s7NTJGe6ra7ZuKkmR/wB1y4UhARv0Lc+AMu8gUibpQIblx4p6dRNKi3qKpTp+65daoqTGOdW6KjKefU6TNnp2fOuecvXLw0W7t8ZTNP+lnEzSiJk2w7DHKOteGm1Tbm7TTjoBfGvBXu3xvvbw04y3ViHthhyju9oGP0no4CK1S71hq2tbqr/JA72hSRVMpHrqcWlG/5kS0OgmGaaGPVnJ5T2ijbZWUz5pHyfZd+piXCZwc655Hrs9mt6rRrdWpQGeok8CpQRxWrSe0lfOwiQYQ+emAYWMExAuTSWvBASIXbQSFcJkiX+4wRXNH2JYslIxB2X8aOrFoVa2Q9rpmX6khOiaVnolSYp/f0io7pHb2mj/T9r7WKssbYy1DmcKLltD37+NrGt/+qejJbdH+p/unZYg+3S69avKclM75FNNEPDp8cb9xZny8W6Dl9Ev/P6Ijeyg3M4Gv0Yo3Xn8KVD/D+fO6TYHOx4VHDW7tVX16pvmIG13EDN+W9l7CM+1hFU859gw/4jC/OitN1EufhJNWZqjRX8Vs4hz8ABxGsmQ==</latexit>

根付き有向木zij =<latexit sha1_base64="a80uHdTX+hZXCpOInxBX21v+wt4=">AAACx3ichVFNSxxBEC3HxJhJoqteArk0WRUFWWqCoAiC6CW5+bUqOLLMjOXaOtMzTPeuH8McvPoHcsgpgRBCfkYu/oEc/AlByMWAOeSQ2tkhIZEk1XT369f1ql93+0kotUG87LF679ztu9d/337w8NHAYGVoeEPHrTSgehCHcbrle5pCqahupAlpK0nJi/yQNv3Dpc7+ZptSLWO1bk4S2om8ppJ7MvAMU42Kf9rI5EEu5oXrU1OqLOBiOrcdMS5cQ8cm09SkiJQRoxNy6mByVEglzD4JkxLlwnVt/JkaM58eSU257ZLaLWs1KlWsYRHiNnBKUIUyluPKO3BhF2IIoAURECgwjEPwQHPbBgcQEuZ2IGMuZSSLfYIcbNa2OIs4w2P2kMcmr7ZLVvG6U1MX6oBPCbmnrBQwhp/wPV7jBX7Az/j9r7WyokbHywnPfldLSWPw/PHazX9VEc8G9n+p/unZwB7MFl4le08KpnOLoKtvn768XptbHcvG8Q1esf/XeIkf+Qaq/TV4u0Krr8DmD3D+fO7bYONZzcGaszJdXVgsv6IfnsBTmOD3noEFeA7LUOdzL+AL3MA364UVW23ruJtq9ZSaEfgtrLMfRaivBg==</latexit>(1 segement (i, j) in the tree
0 otherwise

Xi2V

⇤i yi

背景と目的解法のフレームワーク
管制作業量和最小化
管制作業量平準化
可視化
テストデータへの適用

管制作業量の定式化①
セクタ間の作業量
Vs
5
2
3

3
2

2
1

Vs

2

cut(Vs, Vs) = (2 + 3) + (3 + 2) = 10

Vs に関するカット枝の重み和

数字は通過機数を表す

管制作業量の定式化②セクタ内の作業量
Vs

数字は通過機数を表す
52

Vs

3

3222
1vol(Vs) = (2 + 3 + 5) + (5 + 3 + 2) = 20
Vs に含まれる頂点の重みつき次数Normalized-cutの定義
Vs に関するカット枝の重み和kcut(Vs, Vs)∑ vol(Vs) V に含まれる頂点の重み付き次数の和ss=1(k = 2) Vs

Vs(2+3+5)+(5+3+2)=2055Vs2233222Vs

3

1(2+3+5)+(2+2)+(5+3+2)=24(2+3+1)+(1+3+2)+(2+2)=16(2+2)+(2+3)+(1+3+2)+(2+2)=19cut(Vs, Vs) 10 10=+= 1.02
∑ vol(Vs)20 19s=12221k3kcut(Vs, Vs) 10 10=+= 1.12
∑ vol(Vs)
24 16
s=1

算出の手順評価関数Normalized-cutの最小化k
セクタ間作業量を小さく（分子）cut(Vs, Vs)
セクタ内作業量を平準化（分母） ∑ vol(Vs)s=1
スペクトル法の適用
Algorithm 3 εϖΫτϧ๏
1: ϥϓϥγΞϯ L ʹؔ͢ΔҰൠԽ‫ݻ‬༗஋໰୊ Lu = λDu Λղ͖ɼখ͍͞ํ͔Β k ‫ݸ‬ͷ‫ݻ‬༗஋jλj ͱରԠ͢Δ‫ݻ‬༗ϕΫτϧ u Λ‫ٻ‬ΊΔɽLB ←2: for i ∈ V do
3:!kj=1 λj .

z i ← (u1i , u2i , . . . , uki ) ∈ Rk

4: σʔλ {z 1 , z 2 , . . . , z n } ʹରͯ͠ k-means ΫϥελϦϯάΛ࣮ߦ͠ɼ෼ׂ {V1 , V2 , . . . , Vk } ΛಘΔ.

5: UB ← Ncut(V1 , V2 , . . . , Vk ) ͱͯ͠ LB ͱ UB Λग़ྗ͢Δɽ

(ShiJ.,MalikJ.
2000)
͜͜·ͰͰಘΒΕΔ΋ͷ͸ɼม਑఺΍ۭߓɼߤ࿏ಉ࢜ͷަࠩ఺ͱ͍ͬͨ఺ΛͲͷηΫλʔʹೖΕ背景と目的解法のフレームワーク
管制作業量和最小化
管制作業量平準化
可視化
テストデータへの適用

セクタ境界線の決定
アルゴリズムの適用結果＝WP全体のグループ分け
各セクタ境界線の形状は未決定
境界線決定アルゴリズムの開発（2段階）
初期分割（制約付き三角形分補正（競合学習法）

凹凸の低減
凸に近い

背景と目的解法のフレームワーク
管制作業量和最小化
管制作業量平準化
可視化
テストデータへの適用

テストデータの作成
便数が多い路線の選択
発着空港が適度に分散

部分的な空域モデル

WP数 : 84
枝数 : 99

仙 台

金 沢
伊 丹
福 岡
高 松

羽 田

管制作業量和最小化の結果（実装）Python3.6.3, Gurobi Optimizer 8.0.1（最適化）（色分け：セクタ）

セクタ番号

WP数

作業量#151.91#232.05#331.00

#45

1.76

#515

1.40

#640

4.15

#713

2.41

作業量：最大作業量との比

作業量のばらつき：最大で4倍程度

管制作業量平準化の結果（実装）Python3.6.3, SciPy（線形計算）+ scikit-learn（k-means）（色分け：セクタ）

セクタ番号

WP数

作業量

#119

1.38

#219

2.00

#3

12

1.00

#412

1.63

#56

2.13

#68

1.63

#78

1.63

作業量：最大作業量との比

作業量のばらつき：最大で2倍程度

おわりに空域編成に対する2つの最適化アプローチ
モデル化と解法の提案
解法の実装
テストデータへの適用

今後の課題
我が国全体の空域モデルへの適用