平成１３年度第４回KSMAP

日時：２月２０日（水）　１５：００ 〜 １８：００

京都大学 工学部7号館 4階 第3講義室

       会場への案内  

講演題目と講演者

  混載輸送ネットワーク設計
   宮本裕一郎   （東京商船大学商船学部）

  投票力指数計算の高速化
   宇野毅明     （国立情報学研究所アルゴリズム基礎分野） 

例えば，宅配便などの輸送ネットワークにおける拠点間の輸送を考える．このたぐいの
ネットワークにおいて需要は（多少の変動はあるにしろ）定常的にあるので，拠点間は定
期便が走っており，日々の変動に従って定期便に微調整を加えるのが普通である．今回は
この定期便の経路選択をネットワーク設計問題として考える．拠点は末端・中継点を含め
て全て与えられているとし，荷物は発地・着地ごとに区別されるとする．

これらを抽象化したモデルとして以下の問題を考える．
「点集合と有向枝集合により構成されるネットワークと，そのネットワーク上を流れる品
種の集合が与えられている．各品種の始点・終点は各1つであり，各品種の流量は与えら
れている．枝に流れが生じると，品種に依存しない固定費用（枝の施設費用）と品種に依
存する変動費用が生じる．各品種についてその流れがsimple path上を流れなければいけ
ないという条件の下で，総費用（＝固定費用＋変動費用）を最小にする流れを求めよ．」
この問題に対するアプローチとして，整数計画ソルバーを用いるもの，ラグランジュ緩和
と劣勾配法を用いるもの，メタ解法を紹介する．あわせて計算実験結果も紹介する．余裕
があれば問題の拡張も話す予定である．

 投票力指数とは、議会の各政党の力を指標化したものである。いくつかの
有名な投票力指数に対して、1政党の指数を計算する動的計画法アルゴリズムが
提案されている。この動的計画法は、比較的構造が単純で無駄がないので、
改良は難しいように思える。本発表では、問題を「全政党の投票力指数を
計算する」とした場合に対する、比較的簡単なアイディアを用いた
改良法を提案する。改良により、全プレイヤー分の計算量が1人分の計算量
と等しくなる。