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

3.ソルバーの制約式

（２）最低運賃区間の判定

起点駅を１つ固定すると、終点駅は、起点駅から最低運賃区間内、即ち、最短距離で６㎞以内になければならない。これを制約式にするためには、起点駅iごとに、駅ｊが、最短距離で６km以内にある駅なら1、そうでないなら0とする判別定数Zijを事前に確定しておき、終点駅ダミー変数Yjと比べ、
Yj＜＝Zij
という制約式とすれば、最短距離で６km以上の駅の終点駅ダミー変数を必ず0とすることができる。

ここで、全てのｊについて、Yjを縦一列に並べたものを行列Y(107行1列)、Zijを縦一列に並べたものを行列Zi(107行1列)とすれば、この制約式は、纏めて、
Y＜＝Zi
と表わされる。

「東京メトロ大回り乗車」の最長ルートを計算するに当たっては起点駅ｉの選択は任意であるので、起点駅iの変動に合わせ、対応するZiがYの比較対象とならなければならない。
そこで、全てのiについて、Ziを横に並べたものを行列Z(107行107列)、Xiを縦一列に並べたものを行列X(107行1列)とすると、Xi＝1、即ち、起点駅をiに選んだ場合は、
Zi＝Z・X
となるので、結局、終点駅が起点駅から最低運賃区間内であるための制約は、

Y＜＝Z・X

とすることができる。

ここで、行列Zを改めて見ると、これは、横に起点駅、縦に終点駅を並べ、終点駅が起点駅から最低運賃区間内であれば交点に1、そうでなければ0を入力した行列になっていることが分かる。

この行列は、107行107列となるので、要素が1万個以上となってしまう。これに手入力で数値を１つずつ入れていくのは大変である。しかし、この行列は、実はかなり簡単な作成方法がある。4章でそれを説明することにしたい。

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