以下の通り，第10回研究会を開催いたしました．
日時: 2021年7月13日 (火) 13:30～15:00
場所: Zoom によるオンライン開催
参加者: 58 名
講演者: 田中 俊二 氏（京都大学 国際高等教育院/大学院工学研究科）
題目: 積み替え問題とその周辺
概要: 多数の荷物を限られたスペースに保管する場合，何層にも積み重ねるのが一般的である．しかし，下層の荷物を運び出すには，その上に積まれた荷物を別の場所に積み替えなければならない．その際，次に運び出す荷物の上に積み替えてしまうと，再びその荷物を積み替えなければならなくなる．したがって，荷物を運び出すのに必要となる積み替え作業を減らすためには，積み替え先をうまく選ぶことが重要である．このような荷物の積み替えに関する研究は，おもにコンテナターミナルにおけるコンテナを対象として，これまで数多く行われてきた．その代表例に，コンテナ（ブロック）積み替え問題，コンテナ整列問題がある．コンテナ積み替え問題は，コンテナをすべて運び出す際に必要となる積み替えの手間を最小化する問題，コンテナ整列問題は，積み替えなしに運び出せる配置へコンテナを積み直す問題であり，いずれもNP困難であることが知られている．本講演では，これら問題や類似の問題に対する研究動向を概観するとともに，効率的な解法を目指した我々の研究を紹介する．