日時：12月6日（月） 15:00〜17:30 場所：京都大学 本部構内 工学部総合校舎 総合213講義室 講演題目と講演者： ・ 宮本 俊幸（大阪大学大学院 工学研究科） 「Pickup and Delivery問題に対する分散アプローチ」講演要旨 ・ 中山慎一（徳島大学 総合科学部 自然システム学科 数理科学） 「最小節点ランキング全域木問題について」講演要旨
Pickup and Delivery問題に対する分散アプローチ
宮本 俊幸（大阪大学大学院 工学研究科）
Pickup and Delivery問題は、複数の客を複数の車両で出発点から 目的地まで運ぶときに、客の時間枠要求等を考慮しつつ配送ルート の効率化を目指す問題です。デマンドバスや工場内のAGVの運転計 画問題など、さまざまな応用があります。本講演ではPickup and Delivery問題に対するエージェントを用いた分散アプローチについ て述べます。
最小節点ランキング全域木問題について
中山慎一（徳島大学 総合科学部 自然システム学科 数理科学）
製造工程における組み立て段階のスケジューリング問題やVLSIレイ アウトなどへの応用が動機付けとなり節点ランキング問題というの が提案された．節点ランキング問題というのは以下のような問題で ある．
グラフの各節点に整数を割り当てるが，同じ値が割り当てられた節 点間のいかなるパスにも必ず自分の値より大きな値の節点が存在し なければならない．そうした節点への整数割り当ての中で，割り当 てた最大値が最も小さくなるような割り当てをグラフGの最小節点 ランキングという．最小節点ランキング問題とは，与えられたグラ フGの最小節点ランキングを求める問題である． この問題から派生した問題として最小節点ランキング全域木問題と いうのが存在する．最小節点ランキング全域木問題とは，グラフG において，節点ランキングが最小となる全域木Tを求める問題であ る．
本発表では，最小節点ランキング全域木問題がNP困難であることを 述べ，また，いくつかの部分クラスについては，多項式時間アルゴ リズムが存在することを述べる． （本研究結果は，豊橋技術科学大学 増山繁先生，宮田敬三君との 共同研究によるものである．）