繁野研究室

過去の卒業論文

過去の修士論文

過去の博士論文

戻る

パンケーキソート

大きさがまちまちのパンケーキが山になっているときに，途中にヘラを入れて，その上にあるパンケーキの山を反転する，という操作を繰り返してパンケーキを大きさ順に並べ替えるソートの一種 上へ

Kirkmanの女学生問題

15人の女学生を3人ずつ5組に分けて散歩に行くときに，一緒に行った学生とは同じ班にならないように7日間の組み分け方法を求めるのがKirkmanの女学生問題です． 実際の教育現場や企業研修でも同じ人となるべく重ならないような組み分けを求める場面が多く，いろいろなケースを想定して，複数の定式化で組み分けを求めました． 上へ

制約付きシグマゲーム

グラフの各ノードがON/OFFのいずれかの状態にあり，あるノードを選択すると，そのノードに隣接するノードのON/OFF状態が反転する．このとき，ある状態から始めてなるべくONの状態を減らすようにノードを選ぶのがシグマゲーム．ここでは，ONのノードしか選択できず，かつ，各ノードを高々1回しか選択できない場合についてその性質を調べました． 上へ

調理手順スケジューリング

ファミリーレストランとの共同研究で，複数オーダを受けた時に，どのような順序で調理を行うかをスケジュールする問題．すべてのオーダが仮にわかっている時の最適スケジュールを求め，共同研究者のオンラインアルゴリズムの性能を評価しました． 上へ

コリドール

コリドールは自分のコマを相手側のゴールに早く到達できたプレイヤーが勝ちとなるボードゲーム．各プレイヤーは自分の手番には，コマをすすめるか，フェンスをおいて経路を遮断するかのどちらかを選択する．このコリドールに対する対戦ソフトの元となる評価関数の性能向上をしました． 上へ

健康診断におけるスケジュール作成

大学の学生健康診断は，検診時間は短いのに待ち時間が長いです．これは，各々がすいていそうなところから検診を受けることにより，ある検診項目で行列ができてしまうからかもしれません．この問題点を解消するために，学生に健診の指定したらどのくらい待ち時間が削減されるかを検証しました． 上へ

スマートフォンアプリケーションの分類

住田研究室との共同プロジェクトの一部です．アプリケーション所持データからアプリケーションを分類し，それぞれのクラスが今後どのように変化しているかを予測しました． 上へ

社会的伝播ルール

ネットワーク上に情報が拡散する様子を表現している２つのモデルを対象としました．すべてのノードに情報が拡散するための初期伝達ノード数最小化の指標を，ネットワークの種類を変えて考察し，さらに，情報が拡散しやすいように条件を緩めた上で初期伝達ノード数を求めました． 上へ

自動販売機補充ルート

自動販売機に飲料を補充するルート作成問題．特に，移動距離，移動時間などの指標による最適ルートの違いに注目． 上へ

検索連動型広告のアドランク

インターネット検索でブラウザに表示される検索連動型広告のオークションの理論にアドランクを加え，その影響を理論面と数値実験から検証．アドランクの与え方によって，利得が変化することを明らかにしました． 上へ

光パス通信における最大流問題と波長変換回数最小化問題

光パス通信の特徴を考慮して，多品種流問題とビンパッキング問題を併せ持った問題に対する最大流問題や要求を収容するときの波長変換回数を最小化する最適化問題に対する解法の提案と計算機実験による検証．とくに，最大化問題においては，どの程度までリソースが活用できるかの使用率の指針を与えることができました． 上へ

タクシー料金配分

災害時などに目的地がことなる人がタクシーに相乗りできたとしたら，どのように費用分担すればよいかを，コア，仁などのゲームの解と比較して考察しました． 上へ

座席指定問題

ジェットコースターで到着順に希望の席に着くときと，みんなの希望をきいてから座席を決める場合とではどのくらい満足度が向上するかをシミュレーションで調査．待ち時間に希望を申請して，乗り場に行くと，席が割り当てられるというサービスができたら満足度はぐっと上がるはず． 上へ

離散ボロノイゲーム・情報拡散ゲーム

無向グラフとN人のプレイヤーがおり，各プレイヤーがノードを１つずつ選択して情報をおくる．時間の経過とともに，情報をもったノードに隣接するノードへ情報が拡散する．各プレイヤーが自分の情報をなるべく多くのノードに拡散させたいときに，最初にどのノードを選択すればよいか，という問題．離散ボロノイと情報拡散では同時に２つの情報を受け取ったときの挙動が異なる．この２つのゲームの中間として，多数決で挙動をきめる場合を扱った．また，離散ボロノイに対しては，簡単なグラフ上でのナッシュ均衡の存在性をきっちりと示した． 上へ

スタッフスケジューリング支援システム

筑波山にある温泉旅館のスタッフのスケジューリングを作成するヒューリスティックアルゴリズムを作成し，Excel上で動く支援システムを実現． 上へ

消費電力モデル

スマート・グリッドを導入したときに需要型の電力マネジメントがどこまで可能かを大学の電力データを用いて検証． 上へ

非適応型故障診断

ネットワーク上で故障しているリンクを探すための非適応型グループテスト．ネットワークが小さいときの最小テスト回数を提示． 上へ

Popular Matching

例えば，各サークル団体に活動する部屋を割り当てる問題は，サークルと部屋を1対1に対応させるマッチング問題となります．このとき，各サークルはどの部屋を使いたいかの希望があります．どのサークルも第一希望の部屋を割り当てられればみんな幸せですが，なかなかそうはいきません．いろんな割り当て方に対して，どちらの割り当てがよいかを多数決で決定できるような割り当てをpopular matchingといいます．サークルの部屋割りにpopular matchingを適用すると結構良い結果が得られました． 上へ

オンラインオークション

供給物が次々と到着する中で，入札者に供給物を割り当てるかどうかを決定するオークションです．あらかじめすべての情報が分かっていない中で意思決定しなければならないのですが，なるべく後悔の度合いを少なくするためにはどのような決定方法を用いればよいかを考えます．対象とするオンラインオークションは，インターネットの広告オークションなどの単純なモデルでしたが，理論的に良いとされる決定方法は数値実験でも良い傾向が見て取れました． 上へ

タクシー会社における効率的資産運用モデル

タクシー会社の協力のもと，タクシーの乗車記録を用いて，最適な待機場所の決定と各待機場所への車両配車数を求める問題をモデル化しました． p-メディアン問題，議員定数配分問題といったORでの代表的な手法の有効性を検証できました． 上へ

ペンシルパズルにおける単一ブロック消去法戦略

数独(ナンプレ)を解くときの代表的な消去法についての既存研究を基に，消去法の実際の有効性，カックロへの拡張と有効性の検証を行いました．さらに， 消去法が活用できるような串刺し数独といった新しいパズルも提案しました． 上へ

飲食店の勤務スケジューリング

サービス業における勤務スケジューリングの実用化に向けて，まず，各店舗でどのように勤務スケジュールが作られているのかを学生のアルバイト先についてアンケートを行い，その傾向を調査しました．その上で，飲食店での勤務スケジュールを特徴付けて汎用的なスケジューラを目指してモデル構築してExcelを用いて簡単なスケジューラを実装しました． 上へ

手術室割当問題

病院で，多くの患者が手術を待っている中，どの患者をいつどの手術室で執刀するかを決定することはとても重要になっています．診療科，手術室の種類などその制約はとても複雑ですが，ここでは，いくつかのシナリオを基に，実際の手術データを用いて，何曜日にどの手術室で手術を行うかを決定する問題を解き，シナリオごとに比較検討しました． 上へ

手術室スケジューリング

病院で，多くの患者が手術を待っている中，どの患者をいつどの手術室で執刀するかを決定することはとても重要になっています．診療科，手術室の種類などその制約はとても複雑ですが，ここでは，特に，機材の制約について整理をしました．機材制約を現場で把握しやすくする工夫を考えたり，実際に手術スケジュールに機材制約を組み込んだときの結果を示しました． 上へ

コミュニティバススケジューリング

共同研究の一環として，コミュニティバスの指定されたダイヤに対して，バスと運転手の割当てをおこなう問題．最適化問題として，定式化して解くことで，ダイヤを改正したときに，最低何台のバスが必要かがすぐに分かるようになりました． 上へ

人数の下限制約が重視される勤務スケジュール作成

保育所などの勤務スケジュールでは，利用者数によって配置の下限人数を必ず満たさなければならず，さらに，利用者の急な変更もたびたびある．そこで，下限を必ず満たし，変更時に修正しやすい勤務スケジュールの作成を目指しました． 上へ

ネットワーク上の競争的情報拡散

無向グラフとN人のプレイヤーがおり，各プレイヤーがノードを１つずつ選択して情報をおくる．時間の経過とともに，情報をもったノードに隣接するノードへ情報が拡散する．ただし，同時に２つの情報を受け取ると，そのノードにはなにも情報がなくなる．各プレイヤーが自分の情報をなるべく多くのノードに拡散させたいときに，最初にどのノードを選択すればよいか，について研究しました． 上へ

従属条件付きマッチング問題

無向グラフにおいて，端点を共有しない辺集合をマッチングといいます．マッチングにカバーされている頂点に対して，従属条件が与えられている問題が多項式時間で解けるかどうかを考えました．ここでの従属条件とは，例えば，人と仕事の割当がマッチングを表しているときに，新人に仕事が割当られるときには，トレーナーにも仕事が割り振られて同時に仕事をしなくてはいけない，というような制約です． 上へ

タクシー乗務員の評価

タクシー会社様にご協力いただき，タクシー乗務員の１ヶ月間の勤務日のタコグラフのデータをいただき，そのデータから，効率性を指標とするDEAによって，各乗務員の評価を与えてみました． 上へ

ブロードキャストセンター

コミュニケーションネットワークにおいて，情報発信ノードからすべてのノードへ情報を伝えるプロセスをブロードキャストといいます．ノードごとに単位時間できる送信数がきまっているときに，最短時間でブロードキャストを達成できる情報発信ノードをブロードキャストセンターといいます．木グラフ上だと，このブロードキャストセンターをすべてみつけることが効率的にできるので，その変形について研究しました． 上へ

同時到着した複数のジョブに対して到着時に順序関係が与えられるケース

レストランでの調理作業の効率化をしたい．オーダがきたら，前菜，メイン，デザートと決まった順に料理を提供しなければならない．オーダが来た時点で調理作業のデータがすべてそろい，すぐに作業に入らなければならない．．．こんなモチベーションから始まった研究です． 上へ

送迎バス運転手シフト作成とダイヤ割当

総合バス事業者様の協力を得て，運転手のシフト作成と仕事の割当を同時におこなうモデルをつくり，最適化ソフトで妥当なスケジュール作成ができることを確かめました． 上へ

故障耐性のあるネットワーク設計

コミュニケーションネットワークにおいて，情報発信ノードからすべてのノードへ情報を伝えるプロセスをブロードキャストといいます．これは，情報を受け取ったら，自分から送信できるノードへと情報を送れば達成できますが，ネットワークが大規模になると，故障も考慮しなくてはいけません．ノードの故障の中でも，もっともたちの悪い，故意に誤った情報を送信する「ビザンチン故障」を想定し，ビザンチン故障が起きても，単純なアルゴリズムでブロードキャストが達成できるネットワークの指標を示しました． 上へ

グラフ可視化アルゴリズム

鉄道網や道路網，情報網などはグラフとしてモデル化できます．グラフを見やすく表示するのがグラフの可視化です．なるべく見やすいグラフを表示するためのアルゴリズムは古くから研究されており，いくつかの枠組みがあります．この中で，ばねモデルは直感的でわかりやすいです．また，焼き鈍し法などの方法もあります．卒論ではこれらのアルゴリズムを実装して長所短所をまとめました．入力したグラフの描画がアルゴリズムの繰り返しごとに変わっていく様子は見ているだけで楽しいです． 上へ

家庭訪問スケジューリング問題

小学校の家庭訪問のスケジュール作成は担任の先生の手作業によるもので，とても大変だそうです．各家庭の都合のよい日時に訪問しなくてはならず，かつ，できるだけ同じ地域を同じ日に回りたいので，「時間制約付き配送計画問題」とみなせます．ただし，各家庭の都合の良い日時は絶対に守らなくてはいけなかったり，決まった時間枠に納めなくてはいけないなど，家庭訪問ならではの条件もあります．「時間制約付き配送計画問題」の解法を適用し，短時間でスケジュール作成に成功しました． 上へ

倉庫における勤務表作成問題

倉庫で働く従業員の仕事の割り振りに関する問題を解きました．倉庫でのヒアリングを繰り返し，問題を整理し，モデル化して要求を満たすようなスケジュール作成を試みました．卒論後，実際に使えるシステムを作成し，試用してもらいました． 上へ

生産スケジューリング

工場で製品を生産するときなどにどの設備でどの仕事をするかの順番を決定する問題が生産スケジューリング問題 です．設備の個数，種類，仕事の種類などにより様々な問題があり，古くからオペレーションズリサーチで注目されてきている問題です．卒論では，複数の製品を１台の機械を交代で使って生産するとき，在庫費用と切り替え費用を最小にするような問題を，ラグランジュ緩和法を用いて解く方法を計算機実験で比較しました．上へ

組合せ計量方式

野菜など個々の重量が異なる商品を組合せ，その合計重量を一定の範囲におさめる方法を組合せ計量といいます．野菜などの自動計量包装機で実際に用いられています．既存の研究では，探索範囲を減らす工夫やどのようなときに目標重量の組合せが得られないのかの分析が行われていました．目標重量の組合せが得られると，その組合せが取り除かれその個数分だけ新しいアイテムが入りますので，組合せの取り方がその後の組合せの探索にも影響します．単純そうですが奥深い問題です．卒論では，探索回数を減らし，かつ目標重量の組合せが得られない回数も減らすような探索方法をいくつか提案し，シミュレーションでその有効性を示しました．上へ

通貨交換問題

通貨レートや株価は入力が順次届き，その時点で行動を決定しないといけません． このように現在の情報のみで行動を順次決定する問題をオンライン問題といいます．通貨交換問題はオンライン問題の代表的な問題で，２つの通貨の交換をレートに従っていつ，どれだけ交換するかのルールを決定する問題です．卒論では，ドルから円への通貨レートが単調増加とみなし，すべての情報をもっているときのもっともよい通貨交換方法に比べて 損する割合を一定値でおさえるための交換方法を決定する問題をあつかい，既存の方法を勉強し，実際のレートを用いた計算例などで変数の動きをわかりやすく示しました． 上へ

組合せオークション

最近，ネットオークションなどでオークションにも気軽に参加できるようになってきています．さて，おそろいの 靴とバッグを落札したいとき，どのように入札したらいいでしょうか？靴だけ，バックだけはあまり欲しくないときには， 靴とバッグのセットで入札できた方が好ましいでしょう．このように複数の財の中からある組み合わせを入札するようなオークションを 組合せオークションといいます．このようなオークションは周波数のオークションなどで重要になってきています．卒論では，入札者の行動や均衡状態に対する証明を勉強し，拡張を試みました．　上へ

時間枠制約付き配送計画問題

宅配便は時間指定された顧客を順に訪問します．どのように訪問したら効率よく配達できるでしょうか？コンビニエンスストアへ商品を届けるトラックの配送順はどのように決められているのでしょうか？このように，トラックなどが配送センターから複数の決められた顧客を訪問してセンターにもどってくるとき，トラックの必要台数と各トラックの顧客の訪問順を定める問題を配送計画問題といいます．トラックの積載容量などから，複数台のトラックが必要となることもあります．さらに，顧客の訪問してほしい時間指定を守ってトラックの配送計画を考える問題が時間枠制約付き配送計画問題です．卒論では，既存のパッケージOR-objectを元にして，ユーザが経路を見ながら時間枠制約に対するペナルティーと走行距離のトレードオフを考慮しながら改善の指示を与えるシステムを作成しました．上へ

時間制約つき最短路問題

出発点と目的地が与えられたとき，複数のルートのなかから時間や費用が最小となるルートをみつける問題が最短路問題です．カーナビゲーションや電車の経路探索ソフトなどで馴染みになっている問題です．電車の経路探索などでは単に費用最小のルートをみつけると，特急などを使わずにとても時間がかかってしまうルートとなることがあります．そこで，きめられた　時間内で到着するルートのなかで費用最小のルートをみつける問題が時間制約付き最短路問題です．卒論では，この問題に対するいくつかの既存のアルゴリズムをプログラミングし，さらに，データ構造による違いも 考慮して計算機実験により，アルゴリズム（＋データ構造）の比較をしました．　上へ

Majority Problem

赤，あるいは青にぬられたボールが袋のなかに入っています．どちらの色のボールが多いかを判断したいのですが，全部取り出して数を数えることはできません．できるのは，２つのボールを取り出して，同じ色か異なる色か判断することだけです．このテストを何回行えば，どちらの色のボールが多いかを判断できるでしょうか．ボールが2色に塗り分けられているときは，効率よいテストの仕方が知られていますが，３色になると難しくなります．卒論では，３色の場合に対して，一回のテストでわかる情報をいろいろと変えて考察しました．上へ

勤務表作成問題

ある飲食店での問題です．店長は従業員の勤務希望をききながらシフトを作成しなくてはいけません．従業員は，各々の能力により出来る仕事が異なりますし，時間帯によってお店の混み具合が代わりますので勤務人数も変わります．ナーススケジューリングやクルースケジューリングに代表される問題です．卒論では，ある飲食店特有の条件を考慮して，店長の負担を少しでも減らせるようにシステムを作成しました．　上へ