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

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

準備

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

グラフ

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

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

整数計画問題

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

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

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

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

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

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

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

片道乗車券の発売条件

グラフの三重化

片道乗車券の発売条件をグラフにおける制約の形で素直に書き下そうとすると、以下のようになります。

• 頂点 v を最長路が通らない場合、最長路に含まれる枝は頂点 v に接する枝のうち丁度0本
• 頂点 v が最長路の途中に位置する場合、最長路に含まれる枝は頂点 v に接する枝のうち丁度2本
• 頂点 v が最長路の端点に位置する場合、最長路に含まれる枝は頂点 v に接する枝のうち丁度1本、但し以下の 例外を除く
  • 頂点 v が「Pの字型」の経路の末端の頂点の場合は丁度3本
  • 頂点 v が「Oの字型」の経路の端点（起点かつ終点）の頂点の場合は丁度2本
• 最長路の端点に位置する頂点は丁度2個、但し「Oの字型」の経路の場合は丁度1個

上述の SWA さんの手法では、場合分けをしつつこれらの条件を「Iの字型」の経路に帰着させていらっしゃいます。
ですが、これはやや面倒なので本稿では別のアプローチを取ります。

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

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

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

三重化したグラフにおいては、元々存在した頂点（上図白丸）を「最長路の途中の点専用」、新たに導入した頂点（上図黒丸）を「最長路の端点専用」と役割を分離します。
このようにすると、元のグラフにおける下図Aの最長路は、三重化したグラフでは下図Bのように表現できます。

こうすることで、上述の片道乗車券の発売条件を以下のような簡単な形に書き換えることができます。
これは最長路が「Iの字型」「Oの字型」「Pの字型」のいずれの場合であっても同じです。
（「Bの字型」の経路も許容してしまっていますが、これは敢えてそうしています）

• 白丸の各頂点 v について、最長路に含まれる枝は頂点 v に接する枝のうち丁度0本または2本
• 破線の枝のうち最長路に含まれる枝は丁度2本
• 元のグラフにおいて同じ枝だった複製3本を重複して使うことは無い

これらの条件は、以下の通り1次不等式・等式で表現することができます。

• 白丸の各頂点 v について、 かつ、頂点 v に接する各枝 j について
• 
• 各枝 i とその複製 i', i'' について x_i + x_i' + x_i'' ≤ 1

孤立ループの除去

以上の不等式・等式で片道乗車券の発売条件は概ね表現できているのですが、実のところまだ足りない条件があります。
以上の不等式・等式だけでは、下図のような「本筋とは独立したループ」（B～C～D～B）を含む経路を排除できていません。

こればかりは仕方が無いので、ソルバの出した解にこのようなループが含まれていた場合、その都度アドホックにループを取り除く制約式（上図の場合 x_BC + x_CD + x_DB ≤ 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 は十分大きな定数）[注3]

新在別線派B・C

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

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

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

実乗可能粁程の表現

券面粁程と実乗粁程

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

分岐駅周辺の粁程の補正 その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 は十分大きな定数）[注3]

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

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

脚注

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