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

3.ソルバーの制約式

(1)起点駅・終点駅にダミー変数を導入

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

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

  1. 全てのiに対し、
    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)

  2. Σ全てのi Xi=1、Σ全てのi Yi=1

例えば、i=九段下の場合、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(九段下,竹橋)

となる。



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


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