最長片道切符問題の定式化

本ページは最長片道切符の流儀とバリエーションのサブページです。

GitHub にて最長片道切符問題ソルバのソースコードを公開しています。

準備

最長片道切符問題を整数計画問題として解く手法は、偉大なる先駆者である SWA さんらによって確立されています。
本稿でも概ね同氏の手法を踏襲していますので、共通する部分については概略の説明に留めます。
詳細な解説は同氏の「最長片道きっぷの経路を求める」をご参照ください。

グラフ

下図のように、幾つかの点（頂点と呼びます）の間を幾つかの線（枝と呼びます）で結んだ構造をグラフと呼びます。
この例の場合、頂点は A から J まで10個、枝は a から n まで14本あります。
各枝には重みと呼ばれる実数値が振られています。例えば枝 a の重みは 4.0、枝 b の重みは 5.0、といった具合です。

最長片道切符問題においては、駅（路線の起終点駅及び分岐駅）を頂点、線路を枝、駅間の粁程を重みと見做すことで、路線網をその侭グラフとして扱います。

整数計画問題

以下の形で表される問題を線形計画問題と呼びます。
特に変数 x₁, x₂, ..., x_n の変域を整数に限った問題を整数計画問題、更に変域を 0 か 1 に限った問題を二値整数計画問題と呼びます。

一般の整数計画問題を効率的に解くアルゴリズムは存在しないと言われていますが[注1]、高性能なソルバが幾つか公開されており、実用上は多くの問題を合理的な時間内に解くことができます。
最長片道切符問題の求解に当たっては、最長片道切符問題を二値整数計画問題に帰着させてソルバで解きます。

最長片道切符問題と整数計画問題

最長片道切符問題は、「路線網（グラフ）の枝のうち、どの枝が最長路（最長片道切符の経路）に含まれるか？」を求める問題であると言えます。

各枝 i について以下の変数を導入します。

すると、最長片道切符問題は以下の形で表現することができます。

あとは、「片道乗車券の発売条件を満たす」という制約条件さえ連立1次不等式（または等式）の形で表現できれば OK です。

片道乗車券の発売条件

片道乗車券の経路の分類

「片道乗車券の発売条件を満たす」というのは、単に「一筆書きできる経路である」という意味ではありません。
片道乗車券の発売条件を満たすためには、以下の条件を満たす必要があります。

• 経路が環状線1周を超えてはならない
• 経路に折り返し（復乗）となる部分があってはならない

これらを満たす経路は、下図の3つの形に分類できます。

タイプL

同じ駅を二度通らない“一本道”のタイプ

タイプO

起点駅と終点駅とが同一である環状タイプ

タイプP

一度通過した駅に戻ってくるタイプ

「タイプL」「タイプO」「タイプP」という名称は、最長片道切符問題 (Longest Oneway-ticket Problem) の頭文字に掛けて、SWA さんの共同研究者である宮代隆平さんによって命名されたものです。

なお、下図のような「タイプB」の経路は片道乗車券の発売条件を満たしませんが、このような経路もある種の「タイプP」の経路を探索する上で有用なので、求解の過程では排除せずに考慮に含めることにします。（詳細は SWA さんの解説を参照）

グラフの三重化

片道乗車券の発売条件（または「タイプB」）をグラフにおける制約の形で素直に書き下そうとすると、以下のようになります。

• 最長路上に無い頂点 v に対し、頂点 v に接する枝のうち最長路に含まれる枝は丁度0本
• 最長路の途中に位置する頂点 v に対し、頂点 v に接する枝のうち最長路に含まれる枝は丁度2本
• 最長路の端点に位置する頂点 v に対し、頂点 v に接する枝のうち最長路に含まれる枝の本数は以下の通り:
  • 頂点 v が「タイプL」の起点または終点の場合: 丁度1本
  • 頂点 v が「タイプO」の起終点の場合: 丁度2本
  • 頂点 v が「タイプP」の起点の場合: 丁度1本
  • 頂点 v が「タイプP」の終点の場合: 丁度3本
  • 頂点 v が「タイプB」の起点または終点の場合: 丁度3本（但し起終点が一致する場合は丁度4本）
• 最長路の端点に位置する頂点は丁度2個、但し「タイプO」の場合は丁度1個

上述の SWA さんの手法では、タイプ別に場合分けをしてそれぞれの最長路（の上界）を求めていらっしゃいます。
ですが、これはやや面倒なので本稿では別のアプローチを取ります。

本稿では、場合分けをする代わりに、以下の通りグラフを変形します。

1. 各頂点 v を“複製”し、頂点 v′ を追加する（下図黒丸）
2. 各枝 u–v（頂点 u, v 間を結ぶ枝）と同じ重みを持つ枝を“複製”し、枝 u′–v と枝 u–v′ を追加する（下図破線）

1本の枝を3本に“複製”するので、この変形をグラフの三重化と呼んでいます。

例えば、図1のグラフを三重化すると下図のようになります。

元のグラフにおける有効な経路は、

• 黒丸の頂点と破線の枝は経路の両端専用
• 白丸の頂点と実線の枝は経路の途中専用

と役割を分離することで、三重化したグラフにおいては

• 黒丸の頂点から始めて、途中は白丸の頂点のみを通り、最後は黒丸の頂点で終わる
• 同じ頂点は2度通らない（但し起終点が一致するのは可）
• 元のグラフにおいて同じ枝だった“複製”3本は重複して使わない

という条件を満たす経路として表現できます。

図2のグラフにおいて、これらの条件を満たす経路のうち最長のものを探すと、下図太線の経路が得られます。

その上で、頂点や枝の“複製”を元に戻すと、これは元のグラフ（図1）における最長路になっています。（下図太線）

斯くして最長路のタイプによって場合分けをすること無く最長路を求めることができました。

あとは三重化したグラフにおける制約条件

• 黒丸の頂点から始めて、途中は白丸の頂点のみを通り、最後は黒丸の頂点で終わる
• 同じ頂点は2度通らない（但し起終点が一致するのは可）
• 元のグラフにおいて同じ枝だった“複製”3本は重複して使わない

を連立1次不等式（または等式）の形で表現してやれば OK です。これは以下の通り実現できます。

• 各白丸の頂点 v について以下を満たす:
  • 
  • （但し j は頂点 v に接する各枝）
• 
• 各枝 i とその複製 i′, i″ について x_i + x_i′ + x_i″ ≤ 1

このうち一番下の条件にある x_i + x_i′ + x_i″ を以降単に x̄_i と書くことにします。

※本稿の定式化では「最長路が唯1本の枝のみからなる」というケースは無視しています。JRの路線網ではそのようなケースが最長路となることが無いのは明らかですが、より単純なグラフで最長路を考える場合はご注意ください。

孤立ループの除去

前節で片道乗車券の発売条件（または「タイプB」）を連立1次不等式（または等式）の形に落とし込みましたが、実のところまだ足りない条件が1つあります。

前節の不等式・等式だけでは、下図のような「本筋から独立したループ」（H～I～J～H）を含む経路を排除できていません。

こればかりは仕方が無いので、ソルバの出した解にこのようなループが含まれていた場合、その都度アドホックにループを取り除く制約式（上図の場合 x_HI + x_IJ + x_JH ≤ 2）を追加して再度ソルバを回します。
（これは上述の SWA さんの手法でも同じです）

特例に拠る経路の制約

経路特定区間

最長片道切符の経路には、前節の片道条件の他にも、個別の特例による制約条件が幾つかあります。
その一つが経路特定区間（旅客営業規則第69条）です。

下図で、赤羽～大宮間を通過する経路は、「赤羽～武蔵浦和～大宮」（太線）という経路を採る場合であっても、「赤羽～南浦和～大宮」（二重線）という経路で運賃計算を行うことになっています。
但し、経路が太線と二重線との両方に跨がる場合はこの限りではありません。

この条件は、以下のように1次不等式で表現することができます。

x̄₁ + x̄₂ + (1 − x̄₃) + (1 − x̄₄) ≥ 1

経路特定区間は他にもありますが、基本的に同様の条件を加えて対応しています。
但し、函館線（砂原線）大沼～森間と呉線三原～海田市間については、途中で分岐する枝が存在しないので、単に計算に使わない枝をグラフから省くことで表現しています。

また、新幹線と並行在来線とを別線として扱う区間についても、結果の正規化のために同様の不等式制約を加えています。

通過連絡運輸

最長片道切符の経路には、以下に挙げた私鉄線の区間を組み込むことができます。

但し、1枚の乗車券で複数回の通過連絡運輸を適用することはできません。最長片道切符に組み込める私鉄線は高々1社までです。
この条件は、以下のように1次不等式で表現することができます。

x̄_IGR + x̄_えちご1 + x̄_えちご2 + x̄_伊勢 + x̄_丹後1 + x̄_丹後2 + x̄_丹後3 + x̄_智頭1 + x̄_智頭2 + x̄_智頭3 + x̄_土佐 ≤ 1

山陽新幹線（新下関～博多間）の扱い

本稿では、山陽新幹線（新下関～博多間）の扱いに関して4通りの流儀を扱います。
それそれの詳細は相違点4. 山陽新幹線（新下関～博多間）の扱いは？をご参照ください。

• • 並行在来線（山陽線・鹿児島線）と同一視する〔新在同一派〕
  • 並行在来線（山陽線・鹿児島線）とは別線として扱う〔新在別線派〕
    • 山陽新幹線～篠栗線の乗継に関する区間外乗車の特例を認めない〔新在別線派A〕
    • 山陽新幹線～篠栗線の乗継に関する区間外乗車の特例を認める
      • 特例適用時に博多駅の再通過を認めない〔新在別線派B〕
      • 特例適用時に博多駅の再通過を認める〔新在別線派C〕

新在別線派A

新在同一派の経路計算においては新幹線を丸ごと無視してしまえば問題ありませんが、新在別線派の場合は新幹線を考慮に入れる必要があります。
とは言え、下図太線のように単純に新幹線の枝を追加しただけでは制約条件が足りません。[注2]

小倉～博多間で新幹線を使用する場合、小倉～西小倉や博多～吉塚の在来線に折り返す経路は認められていません。
これは「枝6を経路に採用する場合は、枝1及び枝5は使用してはならない」という制約として、次の1次不等式で表現することができます。

x̄₁ + x̄₅ + Mx̄₆ ≤ M （但し M は十分大きな定数）

新在別線派B・C

新在別線派B・Cの場合は吉塚駅での篠栗線との乗継を考慮する必要があるのでもう少し複雑です。
これは、小倉～博多間の枝（下図枝6）の他に小倉～吉塚間の枝（下図枝7）を加えることで表現します。

枝6と枝7は同時に使用できず、かつこれらを使用する場合は枝1及び枝5は使用できず、かつ枝7を使用する場合は枝4も使用できません。
この制約条件は次の連立1次不等式で表現することができます。

x̄₁ + x̄₅ + Mx̄₆ + Mx̄₇ ≤ M かつ x̄₄ + Mx̄₇ ≤ M （但し M は十分大きな定数）

実乗可能粁程の表現

券面粁程と実乗粁程

前節までで述べた制約条件はあくまで「券面経路として実現可能な経路」の制約条件です。
本稿では券面経路自体の経路長（営業キロ・運賃計算キロ）のみではなく実際に乗車できる経路長（実乗可能粁程）の最長化についても扱うので、券面経路に対する実乗可能粁程を上手くグラフと不等式の形で表現する必要があります。
本節では、実乗可能粁程を表現する手法について述べます。

分岐駅周辺の粁程の補正 その1

券面粁程と実乗粁程との間に差異が生じる代表的なケースに、特定分岐区間や分岐駅通過の特例に拠る区間外乗車があります。

例えば、新旭川～旭川間（左下図太線）は、新旭川駅を通過する列車に乗車する場合に限り、区間外乗車が認められています。
つまり、「稚内～新旭川～網走」の乗車券 (489.7 km) があれば、実際には「稚内～新旭川～旭川～新旭川～網走」 (497.1 km) という経路での乗車が可能であるということです。

これを表現するために、計算上の各区間の粁程を右下図のように補正します。
こうすることで「稚内～新旭川～網走」の経路長が 497.1 km となり、実乗可能な粁程を表現することができます。
区間外乗車のできない「稚内～新旭川～旭川」や「網走～新旭川～旭川」という経路の場合は本来の営業キロと同じ値となります。

実乗可能粁程の計算に当たり同様の補正を行った区間は下表の通りです。

分岐駅周辺の粁程の補正 その2

「分岐駅周辺の粁程の補正 その1」の方法では実乗可能粁程を表現しきれないのが以下のケースです。

宇多津駅周辺には、宇多津～坂出間（特定分岐区間）と宇多津～丸亀間（分岐駅通過）の2つの区間外乗車の特例があります。
これは右下図のように、宇多津～坂出間の粁程を 9.8 km、宇多津～丸亀間の粁程を 11.8 km とすることで表現しています。
こうすることで「茶屋町～宇多津～坂出」の経路長が 40.8 km、「茶屋町～宇多津～丸亀」の経路長が 42.8 km となり、実乗可能な粁程を表現することができます。

なお、「丸亀～宇多津～坂出」という経路を採ると粁程がおかしな値となってしまいますが、そのような経路は最長片道切符の経路たり得ないので問題ありません。

枝の追加による区間外乗車の表現

粁程の補正だけでは実乗可能粁程を表現しきれないケースもあります。

「東京～品川～武蔵小杉」を通る乗車券 (16.8 km) を持っている場合、品川～大崎間 (2.0 km) の区間外乗車が認められています（左下図太線）。
これは粁程の補正だけでは表現できないので、「東京～武蔵小杉間 20.8 km」という枝を追加することで表現します（右下図太線）。

しかし、このようにすると品川駅における片道乗車券の制約が崩れてしまいます。
そこで、「追加した枝を経路に採用する場合は、品川駅を通る枝1～5は使用してはならない」という制約を追加します。
この条件は、以下のように1次不等式で表現することができます。

x̄₁ + x̄₂ + x̄₃ + x̄₄ + x̄₅ + Mx̄_追加枝 ≤ M （但し M は十分大きな定数）

実乗可能粁程の計算に当たり同様の枝の追加を行った区間は下表の通りです。

また、尾久問題否定派の経路の計算の際には、「尾久経由の経路を採用する場合は、日暮里～田端間及び日暮里～新松戸間の枝は使用してはならない」という形で同様の不等式制約を追加しています。

脚注

• ^ 1. 整数計画問題は NP-困難問題と呼ばれる問題の一つであり、求解に要する時間計算量を問題の大きさに対して多項式で押さえることはできないと言われています。（P≠NP予想）
• ^ 2. 新下関～小倉間は最長片道切符の経路を考える上では問題とならないので、小倉～博多間のみを考慮します。