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

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

目次

関連ページ

準備

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

グラフ

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

グラフの例

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

整数計画問題

以下の形で表される問題を線形計画問題と呼びます。
特に変数 x1, x2, ..., xn の変域を整数に限った問題を整数計画問題、更に変域を 01 に限った問題を二値整数計画問題と呼びます。

線形計画問題

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

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

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

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

最長片道切符問題の変数

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

整数計画問題としての最長片道切符問題の表現

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

片道乗車券の発売条件

グラフの三重化

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

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

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

  1. 各頂点 v を“複製”し、頂点 v' を追加する(下図黒丸)
  2. 各枝 u-v(頂点 u, v 間を結ぶ枝)と同じ重みを持つ枝を“複製”し、枝 u-v' と枝 u'-v を追加する(下図破線)
グラフの三重化

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

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

最長路の例
図A(元のグラフ)
三重化したグラフにおける最長路の例
図B(三重化したグラフ)

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

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

孤立ループの除去

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

孤立ループ

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

特例に拠る経路の制約

経路特定区間

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

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

経路特定区間

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

x1 + x2 + (1 − x3) + (1 − x4) ≥ 1

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

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

通過連絡運輸

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

#事業者区間
1IGRいわて銀河鉄道盛岡~好摩間
2えちごトキめき鉄道直江津~糸魚川間, 直江津~上越妙高間
3伊勢鉄道河原田~津間
4WILLER TRAINS(京都丹後鉄道)福知山~西舞鶴間, 西舞鶴~豊岡間, 豊岡~福知山間
5智頭急行上郡~佐用間, 佐用~智頭間, 上郡~智頭間
6土佐くろしお鉄道窪川~若井間
通過連絡運輸が可能な私鉄線とBRT線
通過連絡運輸が可能な私鉄線(太線)

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

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

山陽新幹線(新下関~博多間)の扱い

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

新在別線派A

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

山陽新幹線(小倉~博多間)

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

x1 + x5 + Mx6M (但し M は十分大きな定数)[注3]

新在別線派B・C

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

山陽新幹線(小倉~博多間)

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

x1 + x5 + Mx6 + Mx7M かつ x4 + Mx7M (但し M は十分大きな定数)[注3]

実乗可能粁程の表現

券面粁程と実乗粁程

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

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

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

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

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

分岐駅周辺の粁程の補正 その1(補正前)
実営業キロ
分岐駅周辺の粁程の補正 その1(補正後)
補正した粁程

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

#区間粁程(片道)備考
1特定分岐区間 松島~塩釜 10.0
2日暮里~上野 2.2
3東神奈川~横浜 1.8 分岐駅通過と重複
4武蔵白石~安善 0.6
5今宮~新今宮 1.2
6分岐駅通過 東釧路~釧路 2.9
7新旭川~旭川 3.7
8白石~札幌 5.8
9桑園~札幌 1.6
10沼ノ端~苫小牧 8.8
11川部~弘前 6.3
12追分~秋田 13.0
13羽前千歳~山形 4.8
14北山形~山形 1.9
15安積永盛~郡山 4.9
16余目~酒田 12.2
17宮内~長岡 3.0
18宝積寺~宇都宮 11.7
19新前橋~高崎 7.3
20倉賀野~高崎 4.4
21東神奈川~横浜 1.8 特定分岐区間と重複
22神田~東京 1.3
23代々木~新宿 0.7
24金山~名古屋 3.3
25越前花堂~福井 2.6
26近江塩津~敦賀 14.5
27山科~京都 5.5
28新大阪~大阪 3.8
29尼崎~大阪 7.7
30東岡山~岡山 7.3
31倉敷~岡山 15.9
32備中神代~新見 6.4
33伯耆大山~米子 4.8
34多度津~丸亀 4.2
35池谷~勝瑞 2.8
36佐古~徳島 1.4
37佃~阿波池田 5.1
38向井原~伊予市 2.5
39北宇和島~宇和島 1.5
40海田市~広島 6.4
41横川~広島 3.0
42幡生~下関 3.5
43西小倉~小倉 0.8
44吉塚~博多 1.8
45久保田~佐賀 6.4
46城野~小倉 6.1
47夜明~日田 8.5
48宇土~熊本 10.9
49田吉~南宮崎 2.0

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

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

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

分岐駅周辺の粁程の補正 その2(補正前)
実営業キロ
分岐駅周辺の粁程の補正 その2(補正後)
補正した粁程

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

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

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

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

枝の追加による表現(追加前)
実営業キロ
枝の追加による表現(追加後)
追加した枝

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

x1 + x2 + x3 + x4 + x5 + Mx追加枝M (但し M は十分大きな定数)[注3]

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

# 追加枝 実乗経路 粁程 事由
東京~武蔵小杉 東京~品川~大崎~品川~武蔵小杉 20.8 特定分岐区間(品川~大崎)
田端~新松戸 田端~日暮里~東京~日暮里~新松戸 33.6 特定分岐区間(日暮里~東京)
赤羽~新松戸 赤羽~尾久~日暮里~東京~日暮里~新松戸 39.9 特定分岐区間(日暮里~東京), 経路特定区間(尾久経由)
武蔵小杉~川崎 武蔵小杉~鶴見~横浜~鶴見~川崎 25.5 特定分岐区間(鶴見~横浜)
武蔵小杉~浅野 武蔵小杉~鶴見~横浜~鶴見~浅野 25.0 特定分岐区間(鶴見~横浜)
羽沢横浜国大~東神奈川 羽沢横浜国大~鶴見~武蔵小杉~鶴見~東神奈川 31.5 特定分岐区間(鶴見~横浜)
分岐駅通過(東神奈川~横浜)の補正 1.8 km を含む
羽沢横浜国大~川崎 羽沢横浜国大~鶴見~武蔵小杉~鶴見~横浜~鶴見~川崎 42.1 特定分岐区間(鶴見~横浜, 鶴見~武蔵小杉)
羽沢横浜国大~浅野 羽沢横浜国大~鶴見~武蔵小杉~鶴見~横浜~鶴見~浅野 41.6 特定分岐区間(鶴見~横浜, 鶴見~武蔵小杉)
小淵沢~塩尻 小淵沢~塩尻~松本~塩尻 75.0 分岐駅通過(塩尻~松本)
小牛田~一ノ関 小牛田~古川~くりこま高原~一ノ関 59.5 選択乗車(小牛田~くりこま高原)
鶴見~小田原 鶴見~東神奈川~新横浜~小田原 66.5 選択乗車(東神奈川~新横浜~小田原)
大阪~西明石 大阪~新大阪~新神戸~西明石 63.5 選択乗車(大阪~新神戸~西明石)
新宿~千葉 新宿~品川~東京~千葉 56.6 列車特定区間(特急「成田エクスプレス」)
尼崎~和田山 尼崎~姫路~和田山 153.6 列車特定区間(特急「はまかぜ」)
分岐駅通過(尼崎~大阪)の補正 7.7 km を含む

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

脚注