oneworld Explorer Explorer

Last updated on 12/22/2020, 4:24:42 AM, originally posted on 12/22/2020, 4:04:58 AM by nikorisoft

このエントリは、ニューノーマルぴょこりんクラスタ Advent Calendar 2020のために書かれたものです。

さて、2020年最後の記事は、やはりoneworld Explorerです。前回は、4大陸で3大陸を上回る効率を実現できることを示しました。旅行はできていませんが発券はできたので、ほぼ確実と言ってもいいでしょう。

ここまでやって経路をひたすら手で探しているのは、さすがに人間としてどうかと思われる頃合いかと思いますので、たまにはプログラムを書いて探索をしてみることにしました。本来は、最長解を探すのが理想なのですが、いろいろな課題があり、それを解決するには能力も気力も足りないので、ほどほどな結果を出すことを目標としていきましょう。

今回は、言語の練習としてRustで書いてみました。正しい使い方でないところが随所にあるかと思いますがご容赦くださいまし。

問題と定義

いちおう、少しフォーマルに問題を定義しましょう。

Aを空港の集合とします。次に定義する距離合計値 D(a0, a1, ... a15) が最大となるa0, a1, ..., a15 (∈A) を見つけるというものです。

D(a0, ..., a15) = d(a0, a1) + d(a1, a2) + ... + d(a15, a0)

ただし、d(a, b)は、2空港aとbの間の距離を返す関数、a0, a1, ..., a15 は、oneworld Explorerの規則を満たすものとします。

・・・どこがフォーマルなんですかね。まあ先に進みましょう。

距離関数 d

まずは、距離から定義しましょう。もちろん、地球上の物理的な距離がベースではあるのですが、ここで本当にほしいのは二空港間を飛んだ場合に得られるFOPです。従って、ボーナスを考慮しなければなりません。

適当な公式でまず大円距離を求めることで、空港の緯度と経度から距離の近似値を求めることができます。今回は、地球の半径として6335.439km(3958.756 mi)を使用しました。具体的には、下記のようなコードです。

    fn calc_distance(from: &City, to: &City) -> f64 {
        let lat1 = from.lat / 180.0 * PI;
        let lat2 = to.lat / 180.0 * PI;
        let lon1 = from.lon / 180.0 * PI;
        let lon2 = to.lon / 180.0 * PI;
    
        let d_lon = (lon1 - lon2).abs();
    
        let x = lat1.sin() * lat2.sin() + lat1.cos() * lat2.cos() * d_lon.cos();
        let y = ((lat2.cos() * d_lon.sin()).powi(2) + (lat1.cos() * lat2.sin() - lat1.sin() * lat2.cos() * d_lon.cos()).powi(2))
            .sqrt();
        let d_sigma = y.atan2(x);

        d_sigma * RADIUS_MILE
    }

これによって求まった物理的距離(mi)をdistance(a, b)として、

d(a, b) = distance(a, b) * area_multiplier * class_multiplier + bonus_point (a, b ∈ A)

ということにします。ただし、

area_multiplier
- 2.0 (a および b が日本の空港)
- 1.5 (a または b が日本の空港であり、a または b がアジア(JAL)あるいはオセアニアの空港である)
- 1.0 (それ以外)
class_multiplier
- 1.25 (ビジネスクラス(運賃クラスがD)を仮定する)
bonus_point
- 400 (a またはb が日本の空港)
- 0 (それ以外)

とします。地域の定義は、次に述べますが、ここで表現しようとしているのは、JALの国内線は2倍、アジア・オセアニアは1.5倍というアレです。つまり、JAL路線かどうかを、ここでは簡略化して、いずれかの空港が日本であれば、それはJAL路線としています。コードシェアを含めれば、だいたい正しいのですが、残念ながら完全ではありません。でも無視します。

以上を単純に書き下すと次のようになります。

    fn calc_point(from: &City, to: &City) -> u32 {
        let mul = if from.area == AreaCode::Japan && from.area == to.area {
            // Japan domestic
            2.0
        } else if (from.area == AreaCode::Japan && (to.area == AreaCode::Asia || to.area == AreaCode::Oceania)) ||
            (to.area == AreaCode::Japan && (from.area == AreaCode::Asia || from.area == AreaCode::Oceania)) {
            if from.country == "RU" || to.country == "RU" {
                // Russia (East of Ural) is considered to be in Europe
                1.0
            } else {
                1.5
            }
        } else {
            1.0
        };

        let extra = if from.area == AreaCode::Japan || to.area == AreaCode::Japan {
            400.0
        } else {
            0.0
        };

        (City::calc_distance(from, to) * mul * CLASS_MUL + extra).floor() as u32
    }

地域の定義

oneworld Explorerのルールに従い、世界を次の6カ所の地域(oneworld Explorerでは大陸 continent と呼んでいます)にわけます。

アジア
ヨーロッパ・中東
オセアニア (oneworld Explorerでは、南西太平洋と呼ばれる)
アフリカ
北アメリカ
南アメリカ

ただし、距離計算の都合上、上記と異なる次の2地域の定義も併用します。

アジア(JAL)
日本

アジア地域とアジア(JAL)地域の違いは、次の2点です。

日本はアジアだが、アジア(JAL)に含まない
ロシアのウラル以東はアジアだが、アジア(JAL)に含まない

最初は、FOP計算で、日本だけ2倍とするための扱いなので、自明でしょう。

2番目は、oneworld Explorer的には、ロシアは東西に長すぎるため、東西に分割して、シベリアなどの東部分はアジア扱いとして、西部分はヨーロッパとしています。これによって、例えばS7航空で、ウラジオストクとモスクワを反復横跳びすることで(本当にそんな路線があるかは確かめていません)、ヨーロッパでの距離を稼ぐことを防止しているのでしょう。他方、JALのFOP計算においては、ロシアはあくまでヨーロッパ扱いなので、最近開設された成田-ウラジオストク便は、ただでさえ距離が短いのに、非常に残念なことに1倍となります。

データ

さて、では、次に計算に必要なデータを収集しましょう。ここがある意味、今回の肝かもしれません。

空港

まずは空港のデータが必要となります。すべての世界中の空港のデータ(があるとして)を使うのが一つの方法ですが、oneworldの航空会社が就航している空港でないと意味がありませんし、膨大な量になるのでもう少し絞られたデータがほしくなります。

そこで、今回は、oneworld Explorerの見積もりサイトの地図が使用しているJSONデータを利用することにしました。(POSTで取得しているのでリンクは張れません)

運航路線のデータもとれれば良かったのですが、その情報はクライアントサイドで処理してないようなので残念です。

この空港データ（実際は都市データ）ですが、以下のような情報を持っています。

pub struct JsonCityData {
    pub cityCode: String,
    pub countryCode: String,
    pub lat: String,
    pub lon: String,
    pub timeZone: String,
    pub name: String
}

必要な緯度と経度、国情報、意外と便利なタイムゾーン情報が入っています。

国と地域の対応付け

さて、次に各空港と地域の対応付けが必要です。上で書いたように、国コードが入っていますので、国から地域へマップできれば良いことになります。このデータは、このrepositoryのデータを利用しました。

JPなら日本、地域がOceaniaならオセアニア、という形でマップしていくので楽ですね！

・・・というはずなのですが、いろいろ細かい問題があり、下記のようなアドホックな調整を必要としました。

地域がAsiaであればアジア。
- ただし、サブ地域がWestern Asiaの場合は中東なので、ヨーロッパ・中東に分類。
- また、イランはSouthern Asiaになっているので、これもヨーロッパ・中東に分類。
地域がEuropeであればヨーロッパ・中東。
- ただし、前述の通りロシアは二つに分かれるので、タイムゾーンが6から11の場合(ウラル以東)はアジアに分類。
地域がAfricaであればアフリカ。
- ただし、アルジェリアとモロッコとエジプトとリビアとスーダンはヨーロッパ・中東扱い。
地域がAmericasで
- サブ地域がNorthern Americaあるいは中地域がCaribbeanあるいはCentral Americaの場合は、北アメリカ
- それ以外は南アメリカ

としました。コードは、これをそのまま書いたもので、次のようなものです。

    fn find_area(country_code: &str, time_zone: &str, map: &HashMap<String, &json::JsonCountryCode>) -> AreaCode {
        let country = map[country_code];

        if country.code == "JP" {
            AreaCode::Japan
        } else if country.region == "Asia" {
            if country.sub_region == "Western Asia" {
                AreaCode::EuropeMiddleEast
            } else if country.code == "IR" { // Iran is in Middle-East
                AreaCode::EuropeMiddleEast
            } else {
                AreaCode::Asia
            }
        } else if country.region == "Oceania" {
            AreaCode::Oceania
        } else if country.region == "Europe" {
            if country.code == "RU" {
                match time_zone {
                    "6" | "7" | "8" | "9" | "10" | "11" => AreaCode::Asia,
                    _ => AreaCode::EuropeMiddleEast
                }
            } else {
                AreaCode::EuropeMiddleEast
            }
        } else if country.region == "Africa" {
            if country.code == "DZ" || country.code == "MA" { // Algeria and Morocco are in Europe
                AreaCode::EuropeMiddleEast
            } else if country.code == "EG" || country.code == "LY" || country.code == "SD" { // Egypt, Libya and Sudan are in Middle East
                AreaCode::EuropeMiddleEast
            } else {
                AreaCode::Africa
            }
        } else if country.region == "Americas" {
            if country.sub_region == "Northern America" {
                AreaCode::NorthAmerica
            } else {
                if country.intermediate_region == "Caribbean" || country.intermediate_region == "Central America" {
                    AreaCode::NorthAmerica
                } else {
                    AreaCode::SouthAmerica
                }
            }
        } else {
            panic!("Cannot determine region for {}", country.code);
        }
    }

空港の数

では、地域ごとの空港の数をカウントしてみます。

地域	データ中の空港数
アジア	210
ヨーロッパ・中東	278
オセアニア	85
アフリカ	49
北アメリカ	334
南アメリカ	17

南アメリカが少ないですね。まあ、LATAM航空が抜けたのでしょうがないですね。

dの実装の妥当性

さて、とりあえずこのように作ったd (プログラム上では、City::calc_point)がどれだけ妥当かどうかを確かめてみましょう。

まともな検証とは言いがたいですが、とりあえず、例として、前回のoneworld Explorerの旅程に対して計算をしてみて、比較してみましょう。

From	To	Estimated (MC)	Actual	`calc_point`
NRT	KUL	6681	6659	6584
KUL	HKG	1962	1965	1942
HKG	MAD	8175	8163	8165
MAD	HEL	2287	2290	2284
HEL	LIS	2612	2612	2606
LIS	LHR	1215	1236	1229
LHR	DOH	4062	4050	4041
DOH	LAX	10362	10368	10362
LAX	ANC	2925	2929	2932
ANC	DFW	3787	3803	3797
DFW	YVR	2187	2195	2185
YVR	JFK	3050	3030	3035
JFK	MIA	1362	1380	1375
MIA	BOS	1575	1575	1575
BOS	HKG	9937	9948	9932
HKG	NRT	3812	3818	3765
Total	-	65991	66021	65809

誤差 0.3% なので、まあいいんじゃないでしょうか。はい。

計算

さて、まずは何も考えずに計算してみましょう。まずは、地域内で最長のルートを探してみましょう。アジアを例にとってみると、

Result = 41500
MMB - GAN - MMB - GAN - MMB

となります。女満別空港(MMB)とモルディブのガン島のガン国際空港(GAN)を往復するというルートになります。当たり前なんですが、何の制約もつけなかったので、地域内の最長距離の2空港をひたすら往復するという答えがでます。

これは、2つの点で現実的ではありません。一つは、同じ方向のルートを2回以上使うことはできないというoneworld Explorerのルールに反しています。そして、もう一つは、こんなルートは実際には飛んでいません。

ということで、これをそのまま進めてもいいことはなさそうです。2回使えないルールを課しても、一番長いルートを往復したのち二番目のものを往復みたいなルートになるだけですね。

ヒューリスティクス

ほかの地域もこれで進めても意味がないので、ドメイン知識(?)を応用して、もうちょっと現実的なルートを出してみましょう。

ハブ・アンド・スポーク

まずは、現在、ほとんどの航空会社がハブ・アンド・スポーク戦略を採用しているため、現実的な航空路線は、航路の少なくとも片方がいずれかの航空会社のハブ空港になるということを利用します。

実際、上でも参照した過去のoneworld Explorerのルートで見てみると、

NRT - KUL - HKG - MAD - HEL - LIS - LHR - DOH - LAX - ANC - DFW - YVR - JFK - MIA - BOS - HKG - NRT (一回目のルート)
NRT - MEL - AKL - SYD - LHR - DOH - LIS - DOH - LAX - ANC - ORD - SJU - DFW - JFK - HKG - BLR - NRT (幻となった二回目ルート)

と太字で示したものがハブ空港になります。半分どころかほとんどがハブ空港ですね。

ということで、ハブ空港を下記の空港と定義して、ハブ空港でない空港からは、ハブ空港以外へのルートはないものとしましょう。実装上は距離を0としています。

TYO(東京) (日本航空)
NYC(ニューヨーク), CLT(シャーロット), WAS(ワシントン), MIA(マイアミ), DFW(ダラス・フォートワース), LAX(ロサンゼルス), CHI(シカゴ), PHL(フィラデルフィア), PHX(フェニックス) (アメリカン航空)
LON(ロンドン) (ブリティッシュ・エアウェイズ)
AMM(アンマン) (ロイヤル・ヨルダン航空)
SYD(シドニー), BNE(ブリスベン), MEL(メルボルン) (カンタス航空)
DOH(ドーハ) (カタール航空)
HEL(ヘルシンキ) (フィンエアー)
HKG(香港) (キャセイパシフィック航空)
CMB(コロンボ) (スリランカ航空)
KUL(クアラルンプール) (マレーシア航空)
MAD(マドリード) (イベリア航空)

今見返してみると、ロイヤル・エア・モロッコとS7航空が入っていませんね。まあ、たぶん大勢に影響なさそうなので、よしとしましょう。

実際に運航している路線

次に、実際に運航している路線にしぼりたいところです。しかしそういう都合のいいデータベースは簡単には見つからなかったため、Flightradar24の空港ページのRoutesタブ (リンクは羽田空港の例)のデータを使うことにしました。

これだと空港ごとにデータを取得しないといけないため、単純にやってしまうとデータをそろえるのが大変ですが、上記のようにハブ空港を選んだので、ハブ空港から飛んでいるルートのみを取得することとしました。

ただし、このリストは、実際に直近で飛んだ飛行機が存在する空港のリストで、貨物便も含んでいること、アライアンス外の航空会社によるものも含んでいることには要注意です。また、取得した日時で内容は変化するはずです。

これを踏まえて、ハブから接続されていない空港は、そもそも空港リストから除外することとしました。この結果、空港の数は、

地域	データ中の空港数
アジア	99
ヨーロッパ・中東	140
オセアニア	52
アフリカ	17
北アメリカ	282
南アメリカ	12

となりました。

地域間移動と地域間移動

これでもまだ全探索するには数が多いので、探索を次のように分けることにしました。

地域間経路の探索
地域内経路の探索 (地域に入る空港と地域から出る空港と空港数を固定)

地域間経路を最長とするような経路は、必ずしも全体としては最長にはなるとは限りませんが、ここまでいろいろ近似を繰り返してきたので今更気にしなくてもいいでしょう（台無し）。

oneworld Explorerルール

あとは、探索の途中でルールに適合しないルートは削ることにしましょう。といっても、ここまで地域の定義などで、少なからず使っているので、今回の探索で追加で必要になったのは次のルールくらいです。

同じ経路の同じルートは2回以上使えない (前の記事の(R5)参照)
北米において、本土とハワイを往復することはできない (前の記事の(NA14)参照)

3大陸版

では、3大陸を使った場合の最長路線を探索してみることにしましょう。対称なので、アジア→ヨーロッパ→北米→アジアという経路で考えます。

まずは、地域間の移動経路です。

アジア～ヨーロッパ・中東

最長のものから順に5つを書いていきましょう。

経路	距離
SIN (シンガポール) -> LON (ロンドン)	8397
MNL (マニラ) -> LON (ロンドン)	8329
KUL (クアラルンプール) -> BRU (ブリュッセル)	7952
TYO (東京) -> ZRH (チューリッヒ)	7829
TYO (東京) -> FRA (フランクフルト)	7653

上記で述べたように、この路線は、貨物便やoneworld以外の便も含んでいるため、現実的にあるかどうかとは別問題です。

幸いなことに、最長であるSIN-LON(LHR)は、BAが運航しているようですので、ここは、最初のSIN-LONを採用します。

ヨーロッパ・中東～北アメリカ

経路	距離
DXB (ドバイ) -> LAX (ロサンゼルス)	10404
DOH (ドーハ) -> LAX (ロサンゼルス)	10362
DOH (ドーハ) -> DFW (ダラス・フォートワース)	9898
DXB (ドバイ) -> MIA (マイアミ)	9795
TLV (テルアビブ) -> LAX (ロサンゼルス)	9432

DXB-LAXは、エミレーツ航空が運航していますが、残念ながらoneworldではありません。結局、ここはいままでも使っていたDOH-LAXということになります。

北アメリカ～アジア

経路	距離
MEX (メキシコシティ) -> HKG (香港)	10968
LAX (ロサンゼルス) -> SIN (シンガポール)	10959
GDL (グアダラハラ) -> HKG (香港)	10672
NYC (ニューヨーク) -> MNL (マニラ)	10616
NYC (ニューヨーク) -> HKG (香港)	10046

さて、意外とメキシコがでてきますね。残念ながら、香港からメキシコ直行便は(少なくとも現在は)ないようです。LAX-SINは、シンガポール航空が運航していますが、これもoneworldではありません。NYC(JFK)-MNLもフィリピン航空が運航していますが、これもoneworldではありません。

ということで、結局のところ、 NYC(JFK)-HKG ということになります。

地域内

これで16区間のうち3区間が確定しますので、あとは、その間を埋める最長経路を探索すれば、今回の答えとなります。なお、配分方法は、4-4-5、4-3-6、3-4-6の3つ(アジア-ヨーロッパ-北アメリカの順)がありますので、3パターンを調べてその最長のものを選択すればよいでしょう。

詳細は省略しますが、これによって得られる最長経路は4-3-6の場合で、以下のようになります。なお、oneworld Explorerは日本出発にすると安いのですが、アジア区間は、1.5倍のおかげでたいてい日本がどこかに絡んでくるため、そこを起点とすればこれを満たせることがわかります。なので、3番目が実際には最初の区間ということになります。(下記の表では、第1列はそのように書いています)

#	From	To	Estimated FOP	Realistic?
15	HKG (香港)	DEL (デリー)	2908	✓
16	DEL (デリー)	TYO (東京)	7204	✓
1	TYO（東京)	CMB (コロンボ)	8374	✓*
2	CMB (コロンボ)	SIN (シンガポール)	2110	✓
3	SIN (シンガポール)	LON (ロンドン)	8397	✓
4	LON (ロンドン)	MCT (マスカット)	4511
5	MCT (マスカット)	LON (ロンドン)	4511
6	LON (ロンドン)	DOH (ドーハ)	4041	✓
7	DOH (ドーハ)	LAX (ロサンゼルス)	10362	✓
8	LAX (ロサンゼルス)	PTY (パナマシティ)	3731
9	PTY (パナマシティ)	NYC (ニューヨーク)	2760
10	NYC (ニューヨーク)	ANC (アンカレッジ)	4207
11	ANC (アンカレッジ)	MIA (マイアミ)	4995
12	MIA (マイアミ)	ANC (アンカレッジ)	4995
13	ANC (アンカレッジ)	NYC (ニューヨーク)	4207
14	NYC (ニューヨーク)	HKG (香港)	10046	✓

合計 87,359 FOPということになります。税金抜きで計算すると、効率は7.51円/FOPです。

さて、ではこれがどれだけ現実的かを見ていきましょう。 oneworld Explorerのルール違反はありません。ですが、半数の路線は実際にoneworld加盟会社によって運航されているものですが(1, 2, 3, 6, 7, 14, 15, 16)、それ以外は旅客便としては存在しないか、oneworld外の路線ということになってしまいます。

中でも北米内が極めてダメです。アンカレッジと東海岸を結ぶ路線は残念ながらありません。そんなのがあるならば、大陸横断路線禁止項目(前の記事の(NA13))に入っているはずです。また、LAX-PTY, PTY-NYC路線は実在しているようですが、これもoneworldではないようです。残念ですね。

また、LHR-MCT路線も存在していますが、オマーン航空によるもので、これもoneworldではありません。

さらにいえば、*をつけたTYO-CMB路線も、スリランカ航空によるものなので、FOPは1.5倍ではなく1倍の計算となるはずです。いちおうJALとのコードシェアではあるので、JAL便名で予約することができれば、この通りなので完全な間違いというわけではないのですが・・・

まとめ

ということで、非現実的であれ、oneworld explorer(3大陸)でほぼ上限と思われる効率・FOPを算出することができました。どんなに頑張っても100,000 FOPを達成することは無理そうですね。

この探索の精度をより高めるには、存在しない路線をどうにかして削っていくロジックを加えていくしかないでしょう。しかし、若干、モグラたたき感というかシステマチックにできそうな良いアイディアがありませんので、今回はここまでとしたいと思います。特に、北アメリカは空港数が大量であり、かなりがんばらないと現実解を求めることは難しそうです。本当は4大陸とかもやりたかったのですけどね。

他方、アジア～ヨーロッパ間で、SIN-LHR路線をつかうという発想がなかったため(考えれば当たり前なのですが)、今後のルート作成に参考にしたいと思います。こういった一つのルートを対象にすれば、路線が実在するかどうかを確かめることができるので、実用性があるかもしれませんね。

いずれにしても、現在の世界情勢においてはこういったチケットを使うことはほぼ不可能ですし、さらに航空会社の財政状態が悪化したあと、このようなチケットが残っているかどうかも不透明です。これが未来に生かされるのか、ただの鎮魂歌になってしまうのか、前者であることを祈らざるを得ません。

ソース

READMEも何もなくて微妙ですが、いちおうソースを公開しておきます。