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

3.ソルバーの制約式

（１）起点駅・終点駅にダミー変数を導入

起点駅と終点駅は枝が1本になるため、ＪＲのケースで用いた｢各駅においてルートに含まれる枝は0本または2本」の制約は、そのままでは成立しない。
そこで、全ての駅に、0または1をとる「起点駅ダミー変数」と「終点駅ダミー変数」を設定し、「各駅においてルートに含まれる枝数＋起点駅ダミー変数＋終点ダミー変数の合計は、0または2」、「全ての起点ダミー変数の合計＝1、全ての終点ダミー変数の合計＝1」という制約に変更する。
これにより、起点駅と終点駅では枝数がちょうど1となり、中間駅では起点駅ダミー変数も終点ダミー変数も0となることが分かる。

この制約は数式にすると次のように表わせる。
起点駅ダミー変数をXi、終点駅ダミー変数をYiとし（ｉは駅を表わす）、また、ＪＲのケースと同様、駅間の枝ごとに設定する0,1変数をH(i,j)とする（ｊはｉの隣接駅）とすると、

全てのｉに対し、
0＜＝Xi＜＝1　Xiは整数
0＜＝Yi＜＝1　Yiは整数
Σ_全てのj H(i,j)＋Xi＋Yi＜＝2
全てのjに対し、(Σ_全てのj H(i,j)＋Xi＋Yi)/2＞＝H(i,j)
Σ_全てのi Xi＝1、Σ_全てのi Yi＝1

例えば、ｉ＝九段下の場合、1.の制約式は、

　　0＜＝X_九段下＜＝1　 X_九段下は整数
　　0＜＝Y_九段下＜＝1　 Y_九段下は整数

　　ΣH＝H(九段下,飯田橋)＋H(九段下,永田町)＋H(九段下,神保町)＋H(九段下,竹橋)と定義して、

　　ΣH＋X_九段下＋Y_九段下＜＝2

　　(ΣH＋X_九段下＋Y_九段下)/2＞＝H(九段下,飯田橋)
　　(ΣH＋X_九段下＋Y_九段下)/2＞＝H(九段下,永田町)
　　(ΣH＋X_九段下＋Y_九段下)/2＞＝H(九段下,神保町)
　　(ΣH＋X_九段下＋Y_九段下)/2＞＝H(九段下,竹橋)

となる。

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