TOP

NEWS

POSTED

2013.10.24

TITLE

村上啓介助教(理工・経営システム工学科)が、「2013年度スケジューリング学会学会賞(学術賞)」を受賞

村上啓介助教(理工学部経営システム工学科)が、「2013年度スケジューリング学会学会賞(学術賞)」を受賞しました。
同賞は、毎年開催されるスケジューリング・シンポジウムを含め、スケジューリング学会が対象とするさまざまな研究課題に関する研究論文の中で、特に学術的に優秀と認められた研究論文におくられるものです。

村上助教の研究タイトルは、「被覆制約付き巡回路問題に対する発見的解法」です。
被覆制約付き巡回路問題は、いくつかの基本的な組合せ最適化問題* の性質を合わせ持ち、現実問題にも応用可能な大変興味深いものです。
応用例としては、発展途上国における医師団の訪問経路を求める問題が挙げられます。 医師団は場所を移動しながら、各所で人々を診断しなければなりません。その際、全ての人が徒歩で診断を受けに来られるように、医師団が訪問する場所をいくつか決定しなければいけません。すなわち、全ての人の徒歩圏内に少なくとも1ヶ所は訪問場所が存在しなければなりません。さらに、医師団はなるべく多くの人を診るために移動時間を短くしなければいけません。この問題は医師団が全ての人を診断できるという条件の下に移動時間を最小化する問題として扱うことができ、被覆制約付き巡回路問題になります。
村上助教は、大規模な被覆制約付き巡回路問題に対して新たな考え方に基づく解法を提案し、数値実験により提案解法が既存解法より優れていることを実証しました。

村上助教の研究は、「既存研究よりも遥かに大規模な問題に対して有効な解法を提案したこと」が高く評価され、「2013年度学会賞(学術賞)」に値すると認められました。

* 組合せ最適化問題

条件を満たす解の中で一番良いものを求める問題は最適化問題と呼ばれ、特に解が順番や割当のような組合せ的な性質を持つ問題は組合せ最適化問題と呼ばれます。