ＥＸＣＥＬによる最長片道ルート探索：東京メトロ編

3.ソルバーの制約式

（３）ラッチ外乗換え制約

まず、ラッチ外乗換駅が起点駅から最低運賃区間内である必要があるが、これは行列Zが活用できそうである。Zのラッチ外乗換駅iの行は、ｉが起点駅から最低運賃区間内であれば1、そうでなければ0が入っている1行107列の行列である。

従って、

Ri＝［Zのラッチ外乗換駅iの行(1行107列)］・X(107行1列)

とした時、ラッチ外乗換駅iでラッチ外乗換えするには、

Ri＝1

となっている必要がある。この場合、起点駅ダミー変数行列Xが限定を受けることになる。

例として、上野のラッチ外乗換えを考えてみる。上野でラッチ外乗換えとなるのは、日比谷線⇔銀座線の乗換えであるから、乗換パターンをH変数で表わすと、

H(上野,入谷)⇔H(上野,上野広小路)
H(上野,入谷)⇔H(上野,稲荷町)
H(上野,仲御徒町)⇔H(上野,上野広小路)
H(上野,仲御徒町)⇔H(上野, 稲荷町)

の4ケースとなる。

1.の場合、H(上野,入谷)とH(上野,上野広小路)が両方とも1となるためには、　R_上野＝1となっている必要がある。R_上野＝0の時は、H(上野,入谷)とH(上野,上野広小路)のどちらか一方しか1になれない。つまり、

H(上野,入谷)＋H(上野,上野広小路)－ R_上野＝＜1

となる必要があることが分かる。
2.～4.についても同様の制約式となるので、上野のラッチ外乗換えは4本の制約式で表現されることになる。

三越前、九段下も上野と全く同じパターンであり、4本ずつの制約式となる。

池袋はラッチ外乗換えが

H(池袋,新大塚)⇔H(池袋,要町)
H(池袋,新大塚)⇔H(池袋,小竹向原)
H(池袋,新大塚)⇔H(池袋,東池袋)

の3ケースとなるので、
制約式は、

H(池袋,新大塚)＋H(池袋,要町)－ R_池袋＝＜1

など3本になる。

飯田橋はラッチ外乗換えが

H(飯田橋,九段下)⇔H(飯田橋,江戸川橋)
H(飯田橋,九段下)⇔H(飯田橋,後楽園)
H(飯田橋,九段下)⇔H(飯田橋,市ヶ谷)
H(飯田橋,神楽坂)⇔H(飯田橋,江戸川橋)
H(飯田橋,神楽坂)⇔H(飯田橋,後楽園)
H(飯田橋,神楽坂)⇔H(飯田橋,市ヶ谷)

の6ケースとなるので、
制約式は、

H(飯田橋,九段下)＋H(飯田橋,江戸川橋)－ R_飯田橋＝＜1

など6本になる。

異名乗換駅i,jは駅間が距離0の枝で結ばれているので、Ri＝1またはRj＝1の場合のみ、この枝を通ることができる、という制約にすればよい。とりあえず、RiとRjを区別しなければ（計算結果に問題があればその時追加制約式を考える）、制約式は

H(i,j)－Ri＝＜0

となる。

例えば、有楽町・日比谷の制約式は、

H(有楽町,日比谷)－ R_有楽町＝＜0

である。

同様に、上野広小路・仲御徒町、淡路町・新御茶ノ水も制約式はそれぞれ1本ずつ必要となる。

大手町はラッチ外乗換駅であるが、ホームをコの字型に辿って遠回りをすれば、ラッチ外乗換えしなくてもすれば全ての路線が乗換可能なので、ラッチ外乗換え制約は課さなかった。

←前のページ　目次　次のページ→