鉄道の世界では、最長片道切符 という概念が存在します。鉄道路線に置いて、途中で同じ駅を2度通ることがないような出発駅から到着駅までの距離がもっとも長い経路を持つ片道乗車券のことを指します。これについては、様々な研究があり、また実際にその経路の切符を発券し、旅行している人もいます。

ここでは、JRの鉄道における最長片道切符ではなく、航空機を使った最長片道航空券 について考えてみたいと思います。

最長片道切符とは

一般に最長片道切符と呼ばれるものは、JRグループの旅客営業規則のルールに基づいて購入できる片道切符で最長となるものを指します。

細かなルールは色々ありますが、

  • 一度通った駅は2度と通らない
  • 一度通った経路は2度と通らない(一筆書き)
  • 距離(運賃計算キロ)がもっとも長いもの

を満たしている経路で購入した切符、となります。

今回考える航空機版の片道最長切符

鉄道における片道最長切符はすでに様々な研究がされています。一方で、同じルールを適用した航空券についてはあまり話題になることはありません。というのも、鉄道であれば、長距離の切符を発券すること(1枚の片道切符で発券すること)で、1キロあたりの単価を下げることができるのに対して、航空券の場合はそのようなことはなく、普通に購入するのとほとんど変わらないからかと思います。また、鉄道であれば学割などを使えば片道最長切符の運賃は100,000円以下に収まる のに対して、航空機の場合は途轍もない金額になるのもその要因と言えます。

とはいえ、実際に乗車するわけではないので、航空機版の片道最長切符を考えてみるのも良いと思います。

ルールは、鉄道における片道最長切符と同様に考え、

  • 一度通った空港は2度と通らない(経由含め)
  • 一度通った航空路は2度と通らない(一筆書き)
  • 利用した区間の区間基本マイルの合計がもっとも多いもの
  • マルチエアポートとして設定されている空港は同一空港とみなす

となるかと思います。鉄道における最長片道切符と基本的にほぼ同じルールですが、最後の「マルチエアポートとして設定されている空港は同一空港とみなす」のみが特殊なルールになります(厳密にはJRにおいて、異なる駅だが購入するきっぷによっては、計算上同一駅とみなす駅が存在するので、ここでは同一空港とみなすことにしています)。また、運賃計算キロに該当するものは、航空機では区間基本マイルになります。

ANA国内線を使った片道最長航空券を計算してみる

日本にある鉄道には国際路線はないので、鉄道における片道最長切符では自然と日本国内に限られてしまいますが、航空機では海外もスコープに入ってしまいます。ただ、そうなると簡単に計算できるものではないので、ここでは手計算でも算出できるような規模を想定して「日本国内線限定」「ANA便限定(提携会社含む)」「定期就航路線限定」「2019/03/31〜2019/06/30の時刻表」で見ていきたいと思います。

亜種として、「JAL便限定」や「LCC限定」の他に海外も対象に入れて「スターアライアンス限定」「ワンワールド限定」などの片道最長航空券も定義できそうです。その場合は、「スターアライアンス・世界一周切符」のルールに従った最長経路を求めた方が実用的でしょう。

ANA国内線の基本情報

  • ANAが就航している国内線の空港: 53空港
  • ANAが就航している国内線の全路線: 約180路線

ANA国内線におけるマルチエアポート

ANAが就航している路線で、マルチエアポートとして設定されている空港は、

  • 東京(成田国際空港・東京国際空港)
  • 大阪(関西国際空港・大阪国際空港・神戸空港)
  • 福岡(福岡空港・北九州空港・佐賀空港)
  • 広島(広島空港・岩国空港)

となります。マルチエアポートは、IATA公認のものの他に、日本独自のマルチエアポートも存在しますが、ここではその区別は行わずに、上記4エリアをマルチエアポートとして計算します。

片道最長航空券の計算ロジック

53空港・約180路線における片道最長航空券を計算していきます。鉄道における片道最長切符の計算では、まずは全国を北海道・本州・四国・九州に分けた上で(これらのエリア間を行き来することができる路線が1種類ずつのみのため)、それぞれのエリア内での片道最長切符を求めた上でそれらを結合していく形になります。また、それぞれのエリア内での片道最長切符を求めるには、さらに細かなエリアに分割していった上で、整数計画法によって求めます。詳細は、最長片道きっぷの経路を求めるなどを参照してください。

今回のANA国内線・航空路における片道最長航空券の場合、鉄道と比較すると、空港数・路線数は少ないので、プログラムを使って総当たり式で求めていくのが良さそうです。

愚直なアルゴリズムとしては、

  1. N=2とする。
  2. 対象となる全空港からN個を取り出して順番に並べる順列を全てリストアップする(これがフライトの候補)。
  3. 2でリストアップした順列(=フライト候補)全てに対して、就航路線情報とルールに適合するフライトのみに絞り込む
  4. 3で絞り込んだフライトが1件以上存在する場合、Nを1増やした上で手順2に戻る。3で絞り込んだ結果フライトが存在しない場合は手順5に進む。
  5. 手順3でリストアップした順列(=フライト)のうち、もっともマイル数の多いものを探索する

という形になります。おそらく就航路線図をみる限りだと、就航空港は札幌・東京・名古屋・大阪・福岡・那覇あたりに偏っていることもあり、片道最長航空券とはいえ、おそらく6〜10空港程度を経由する路線が限界とみています。このくらいの路線数であれば、クラウドサーバーのハイスペックマシンを利用すれば計算できそうな気がします。

ということで、Pythonを使ったマルチスレッドで実装したプログラムをGoogle CloudのCompute Engine(スペック: vCPU 24個、メモリ: 32GB) を使って計算してみました。

片道最長航空券の計算結果

vCPU: 24個、メモリ: 32GBのクラウドマシンを使って、計算させたところ、N=7の時点で30分経っても全体の数%程度しか計算が完了しない状態に陥ってしまいました。この時に出てきた経路の中でもっとも区間基本マイルの合計が大きいものが、

沖縄 → 長崎 → 大阪 → 宮古島 → 東京 → 石垣島 → 名古屋

という経路でした。が、この経路の始点と終点が就航路線の多い空港になっているので、まだまだ付け足すことはできそうです。ANAの国内線フライト時刻表をみるだけで、沖縄の手前に「広島 → 仙台 → 福岡 → 札幌 → 沖縄」を、名古屋の後ろに「名古屋 → 女満別」を付け足すことができそうで、当然こちらの方が区間基本マイルが大きくなります。おそらく他にももっと長い距離の航空券が出てくる気がします。

つまりは、1〜2時間の付け焼き刃で実装したプログラムでは片道最長航空券を計算するのは難しいようでした。

とはいえ、少なくとも

広島 → 仙台 → 福岡 → 札幌 → 沖縄 → 長崎 → 大阪 → 宮古島 → 東京 → 石垣島 → 名古屋 → 女満別

の経路の区間基本マイル以上になるのは明らかです。この区間基本マイルを合計すると、9,341マイルとなりました。

真の片道最長航空券を目指して

中途半端な経路ではなく、真の片道最長航空券を計算するための方法を考える必要があります。まず、先述したアルゴリズムを採用する場合は少なくともN=12以上になります。N=7の時点で計算しきれなかったので、アルゴリズム自体を変更する必要があります。

変更先のアルゴリズムとしては、鉄道における片道最長切符と同様に整数計画法を行うのが無難ですが、規模は大きくないので、データの保持方法をきちんと検討した上で、適切なアルゴリズムを選択すれば、別の方法でも計算可能な気はします。

これについては、今後検討を行ってみたいと思います。

まとめ

今回は、鉄道における片道最長切符の例を元に、その航空経路版について考えてみました。ANA国内線に限定することで、空港数・就航路線数を少ない状態で計算しようとしましたが、数時間で作成したプログラムで簡単に解ける問題ではないようでした。

今後、プログラム・アルゴリズムのブラッシュアップを行って、片道最長航空路について計算してみたいと思います。また、ユナイテッド航空の特典航空券を使えば3〜4万マイルほどで発券できそうな気もするので、誰か実際に挑戦してみても面白いかと思います。