第3回研究会
2015年度第3回研究会を以下の通り開催いたしました．
- 日時：2015年 10月 24日 (土) 13:30〜18:00
- 会場：東京理科大学 神楽坂キャンパス 3号館 5階 第1演習室
- 講演者１：今堀 慎治 氏 (中央大学理工学部情報工学科)
- 題目：グラフアルゴリズムを用いたスケジューリング
- 概要：スケジューリング問題は，古くから研究されてきた最適化問題であり，実社会の様々な場面で現れることから，実用的なアルゴリズムの開発が強く求められている．本発表では，生産スケジューリングとスポーツスケジューリング分野で生じた2つの最適化問題を取り扱う．基本的なグラフアルゴリズム（オイラー路，ハミルトン閉路，マッチング，グラフの分割など）を取り入れた近似アルゴリズムを紹介し，アルゴリズムの改良や今後の発展について議論する．
- 講演者２：林 俊介 氏 (東北大学大学院情報科学研究科)
- 題目：複数のボトルネックをもつ通勤時刻選択均衡問題：無限次元相補性問題への定式化
- 概要：通勤ラッシュにおける渋滞は世界中で依然深刻な問題であり，その本質的な原因を解明すべく様々な数理モデルが提案されている．その端緒となるのが，Vickreyの提唱した出発時刻選択均衡問題であり，単一のボトルネックのみを考慮したモデルに関してはこれまで多くの研究がなされてきた．一方，複数のボトルネックを考慮したモデルに関しては，渋滞による旅行時間の伸縮が複雑に絡み合うため，これまでモデル化および解析が困難とされてきた．
本研究では，複数のボトルネックを考慮したコリドー型（直列型）道路網に対して，到着時刻をベースとした時刻座標系を新たに導入することにより，出発時刻選択均衡問題の均衡解を無限次元の相補性問題として定式化する．さらに，時刻を離散化し，相補性問題を有限近似することにより，均衡解の有する性質を解析的および実験的に調べる．
戻る
