第 4 回研究会

  • 日時: 2018 年 9 月 8 日 (土) 13:30--18:00 (開場は 13:00 頃)
  • 会場: 南山大学 名古屋キャンパス S 棟 6 階 S67 教室 (交通アクセス, キャンパスマップ)
  • 講演 1
    • 講演者: 橋本英樹氏 (東京海洋大学 流通情報工学部門)
    • 講演題目: 配送計画問題に対する局所探索フレームワーク
    • 講演概要: 配送計画問題は, 様々な制約条件の下で複数の車両を用いて顧客を訪問する経路の中で, コストが最小のものを求める問題である. 非常に実用性のある問題で, 郵便・新聞配達, 廃棄物収集, 石油運搬や機械スケジューリングなどの応用を持つ. 一般に, 配送計画問題を含む NP 困難な問題では, 与えられる問題例に対して厳密な最適解を求めることは現実的に極めて困難であると考えられている. そのような問題に対する基本的でかつ有効な近似解法の一つに局所探索法がある. 本発表では, 配送計画問題に対する基本的な解法を紹介したのち, 様々なタイプの配送計画問題に適用可能な局所探索フレームワークを説明する.
  • 講演 2
    • 講演者: 小市俊悟氏 (南山大学 理工学部 システム数理学科)
    • 講演題目: NMR スペクトルからの化合物の立体構造推定 ---離散最適化手法の応用として---
    • 講演概要: 新規化合物の立体構造を決定するための分析方法として, 核磁気共鳴分光法 (NMR) と呼ばれる方法が広く利用されている. この分析方法では, NMR スペクトルと呼ばれる化合物の立体構造に依存する特性値を観測し, それに基づいて構造決定が行われる. しかし, 実際には, その分析も分析者の経験に頼る部分が多く, 間違った立体構造が報告されることさえある. そのため, このような分析方法を, 計算機を用いて自動化しようという試みは長年続けられているが, 化合物の構造として考えられる構造が莫大な数になることもあり, 依然として改善が必要である. この研究では, このような課題に対して, 様々な離散最適化手法を適用することで, その解決を目指してきた. 具体的には, 二部マッチング問題, 最大重みクリーク問題 (クリーク列挙), デタッチメント問題などに対するアルゴリズムを応用している. 本発表では, それらの離散最適化手法が実際の問題を解くためにどのように利用されているかを中心に紹介する.
  • 参加者数: 19 名