研究者総覧「情報知」
計算機数理科学専攻
- 氏 名
- 橋本 英樹（はしもと ひでき）
- 講座等
- 計算論講座
- 職 名
- 助教
- 学 位
- 博士（情報学）
- 研究分野
- 組合せ最適化 / アルゴリズム / スケジューリング / オペレーションズリサーチ
研究内容
組合せ最適化問題に対する効率的なアルゴリズムの研究
組合せ最適化問題は，問題の解が定義される空間や制約などが離散的である問題で，制約を満たす解の中で与えられた指標を最小にするものを求めることが目的です．その適用範囲は非常に広く，社会で現れる様々な問題は組合せ最適化問題として表現できます．しかし，それらは多くの場合，NP困難な問題で，現実的な計算時間で最適解を得ることは非常に困難です．その一方で，現実の問題では厳密な最適解が必要とされることはまれで，適度な精度の近似解を現実的な計算時間で求める解法で十分に実用的だと考えられています．このような状況では，効率よく近似最適解を求める解法が有用となります．近年，そのような近似解法として良い成果をあげているものとして，局所探索法やメタ戦略があり，これまでに多くのアルゴリズムの提案が行われてきました． 私の研究では，組合せ最適化問題に対して，効率よく近似最適解を求めるアルゴリズムの開発を目指しています．具体的には，対象とする問題が持つ良い内部構造を見いだしそれをうまく利用した数理的な手法や，またアルゴリズム中で必要な操作を高速に実現するためのデータ構造の開発を行い，高性能なアルゴリズムの設計をしています．
現在の主な研究テーマとして，
- 配送計画問題
- スケジューリング問題
- グラフ分割問題に対する近似解法
- リアルタイムシステムの設計
などがあります．
ここでは，配送計画問題について少し紹介します．この問題は，現実の問題とも密接な関わりを持つ問題で，工学的な見地からも盛んに研究されており，オペレーションズリサーチの分野で現実社会の問題に適用して成功を収めた例のひとつです．配送計画問題は，様々な制約条件の下で，複数の車両を用いて全ての客をちょうど1回ずつ訪問するような経路の中で，コストが最小のものを求める問題です．制約条件としては，例えば各車両の容量制約や時間枠制約があります．容量制約とは，客の要求量の総和が車両の容量を越えてはならないというもので，時間枠制約とは，客が指定する時間枠内にサービスを開始しなければならないというものです．これまでに局所探索法に基づく効率的な解法を提案したのですが，現在は，これに数理的なアプローチを組込むことでより高性能な解法の開発を行っています．
現実社会に現れる問題は複雑で開発したアルゴリズムを単純に適用できない場合もありますが，より良い解決を実現ための基盤となる研究を行いたいと考えています．
経歴
- 2008年 京都大学大学院情報学研究科数理工学専攻修了 情報学博士
- 2008年 名古屋大学大学院情報科学研究科 附属組込みシステム研究センター 研究員
- 2009年 中央大学理工学部経営システム工学科 助教
- 2011年 名古屋大学大学院情報科学研究科計算機数理科学専攻 助教
所属学会
- 日本オペレーションズ・リサーチ学会
- 電子情報通信学会
- スケジューリング学会
主要論文・著書
- A GRASP Based Approach for Technicians and Interventions Scheduling for Telecommunications, Annals of Operations Research, 183 (2011) 143--161
- An LP-Based Algorithm for Scheduling Preemptive and/or Non-preemptive Real-time Tasks, Journal of Advanced Mechanical Design, Systems, and Manufacturing, 4 (2010) 578-587
- A Set Covering Approach for the Pickup and Delivery Problem with General Constraints on Each Route, Pacific Journal of Optimization, 5 (2009) 185-202
- An Iterated Local Search Algorithm for the Time-Dependent Vehicle Routing Problem with Time Windows, Discrete Optimization, 5 (2008) 434-456
- The Vehicle Routing Problem with Flexible Time Windows and Traveling Times, Discrete Applied Mathematics, 154 (2006) 2271-2290
