EXCELによる最長片道ルート探索:東京メトロ編

3.ソルバーの制約式

(2)最低運賃区間の判定

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

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



「東京メトロ大回り乗車」の最長ルートを計算するに当たっては起点駅iの選択は任意であるので、起点駅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万個以上となってしまう。これに手入力で数値を1つずつ入れていくのは大変である。しかし、この行列は、実はかなり簡単な作成方法がある。4章でそれを説明することにしたい。



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


Copyright(c) 2005 KONDO Hideaki All rights reserved.
初版: 2005年2月12日