池上 敦子

事業所におけるスタッフの毎日の勤務を決定する問題をスタッフスケジューリング（勤務表作成問題）という．一般に人件費は抑制されることが多いことから，スタッフスケジューリングは実行可解を求めることすら難しいことが多く，長い時間を費やす作業である．さらに訪問介護事業所においては，サービスの利用者が必要とする介護サービスに対して，適切なヘルパーを割り当て，ヘルパーの勤務可能性と移動時間も考慮する必要があるため，さらに難しい問題となる．訪問介護事業所でのITによる支援は事務手続きに関するものが主体であり，実用的な自動スケジューリング機能は提供されていないと言っていいだろう．他の最適化問題を含め，最適化手法を用いた支援システムの研究は多くあるが，実際に計画を作成する際に必要となる労力やコスト，つまり勤務表作成にかかる労力がどの程度削減できるのか，作業のボトルネックはどの部分になるのか，という点を明らかにしようと試みた研究はほとんど行われていない．我々は「勤務表作成者の負荷の軽減」を目標とし，最適化技術を用いたスケジューリング機能に重きを置いた勤務表作成支援システムの構築に関する研究を行ってきた．本論文では，このシステムを用いて実際に行われた勤務表作成の作業を観察することで，最適化システムの導入でどのような作業効率化が図れるか，システムが持ちうる問題点はどこにあるのか，といった点を明らかにし，良いシステムをデザインする上での指針を得ることを目的とする．

鉄道運賃は,基本的に乗車距離が長くなればなるほど高くなるように設定されているが,同じ距離でも,会社によって,さらには同じ会社内でも地域や路線によって異なる料金が設定されている.さらに,乗車区間によっては割引ルールや特定の運賃が設定されていることなどから,最短経路の運賃が最安になるわけではない.運賃計算では,利用者の乗車経路が明確でない場合,乗車可能経路の中から最も安い運賃となる経路を利用したとみなし,その運賃を採用するルールが設定されている.そのため,与えられた2駅間の正しい運賃を計算するためには,その2駅間の乗車可能経路の運賃を全て,もしくはその1部を列挙して判断する必要があると考えられてきた.これに対し,我々は2008年,複数の鉄道会社を含む鉄道ネットワークにおける最安運賃経路探索用ネットワークFarenetと探索アルゴリズムを提案し,これを利用した自動改札機用運賃計算エンジンの実用にいたった.本論文では,Farenet構築の基盤となった1会社内の運賃計算,具体的には,首都圏エリアで利用可能であるICカード乗車券Suica/PASMOの適用範囲に含まれるJR東日本510駅の全2駅間(129,795組)に対して行った運賃計算について報告する.4つの対キロ運賃表と複数の運賃計算ルールが存在するこの運賃計算において,異なる地域・路線を考慮した部分ネットワークとダイクストラ法を利用することにより,多くの経路を列挙する従来の運賃計算方法において数時間要していた計算を,約1秒で処理することに成功した.論文の最後では,アルゴリズムの効率を示すとともに,対象ネットワークが持つ運賃計算上の特徴についても報告する.

本論文では,改札を通らずして複数の鉄道会社をまたいで乗車した場合の鉄道運賃計算を扱う.一般的に,鉄道運賃は多数存在する到着可能経路の中で最も安い経路を利用したとみなし,その運賃を採用することになっている.また,鉄道会社ごとの運賃体系の違いや乗継割引等によって,距離最短の経路と運賃最安の経路が一致するとは限らない.筆者らの先行研究では,従来の「可能経路列挙とその運賃比較」による最安運賃経路探索に対して,ダイクストラ法を利用できるネットワークと探索アルゴリズムを提案し,正確かつ高速な計算を可能にした.この運賃計算方法は基本的な運賃計算制度及び乗継割引制度に基づく最安運賃経路を導くが,自動改札機における運賃計算のためには,更に利用する鉄道会社の数に関する制約を考慮する必要がある.本論文では,ネットワークを階層的に扱うことで,この問題を解決する自動改札機のための運賃計算方法を提案する.提案方法は,膨大な量の運賃計算を高速に行うことを可能にしたため,実際の自動改札機や自動精算機などの運賃計算にかかわるシステムに適用された.

In machining of products in which a large number of cutting tools and machining processes are required, the sequence in which a workpiece is machined has an effect not only on factors relating to productivity such as machining time, machining cost, and power consumption, but also on the machining error and quality of the machined surface. However, the number of combinations of processing sequences for machining of such products is extremely large, and it is therefore difficult to design an optimal machining process within a short time. In this study, an algorithm for solving the shortest path problem is used to develop a process planning support system that takes into account the various above-mentioned factors in machining using a machining center. The system incorporates various functions such as prevention of interference between the tool and the workpiece resulting from the machining sequence, prevention of processes in which previous machining is invalidated, and integration of processes performed using a same tool. Machining times based on NC data are calculated, and the shortest machining time for a product requiring 15 processes (using 9 tools) is analyzed. A comparison of results obtained using the proposed system with machining times required for processes designed by operators confirmed that the analytical results are valid.

本研究では,運賃設定の異なる複数の鉄道会社を含む鉄道ネットワーク上の運賃計算を正確かつ高速に行えるネットワーク表現とアルゴリズムについて報告する.鉄道運賃は,利用者の乗車経路が明らかであるとき,多くの場合,その経路に含まれる各鉄道会社が定めた運賃を足し合わせることによって得られる.一方,利用者の乗車経路が明確でない場合,利用可能経路の中で最も安い経路を利用したとみなし,その運賃を採用することが一般的である.しかし,鉄道運賃は,基本的には「距離が長くなればなるほど高く」なるように設定されているものの,同じ距離でも,会社によって異なる料金が設定されていることや,乗車区間によって割引ルールや特別運賃が設定されていることなどから,物理的距離に基づくショーテストパスが最も安い経路になるわけではない.よって,与えられた2駅間の正しい運賃を計算するためには,その2駅間の可能経路の運賃をすべて,もしくは,その1部を列挙して比較判断する必要があることがこれまでにも報告されてきた.本研究では,物理的構造に基づくネットワーク上での経路探索を行う代わりに,ダイクストラ法が利用可能な運賃計算用ネットワークを構築し,ダイクストラ法と,少ないケースではあるがK-shortest paths問題用のアルゴリズムを利用することにより,複数社を含む鉄道ネットワーク運賃計算の大幅な高速化に成功した.

この研究では, CFSI回答データの効率的な入力方式が検討された. このデータは, 1枚あたり81個の〇×(はい, いいえ) 記号で構成され, 通常, 〇の数は×の数よりはるかに少ない. 以下の三つの入力方式が評価された: A) 被験者は〇×の代わりにそれぞれ1と2をテンキーから入力する; B) 被験者は〇とマークされた問題番号をテンキーから入力する; C) 被験者は〇とマークされた問題番号の隣のボックスをマウスでクリックする. 20歳代前半の43名の被験者は, タッチタイプができる18名 (男14, 女4) とできない25名 (男22, 女3) に分けられた. 各被験者は三つの方式で, それぞれ15枚分の回答データの入力を求められた. 結果は以下のように要約された.<br>1) キーボートとマウスでは, 被験者のキーボード操作技量にかかわらず, キーボードのほうが有利であった.<br>2) グループとも〇の数の増加によって, 最も効率的な入力方法が方法Bから方法Aに変わった. その分岐点は, タッチタイピスト群で17, 非タッチタイピスト群で15であった.

SNAP is a computerized notation analysis system for soccer player and team performance. It has the capacity for measuring players' movements off the ball, although many other analysis systems do not. In this study we planned to implement a subsystem which evaluates the performance of a defensive system in SNAP. Then we defined some defensive tactics in two popular formations (four backs and three backs), and examined whether defenders ware able to carry out these tactics during attacks from the opposing team.

We believe that movements off the ball are important factors to create shooting chances during a match. To measure movements off the ball, a game analysis system SNAP was developed in 2002. SNAP is capable of computing defined positive movements off the ball from input data, such as the ball and players' positions on the pitch. The aim of this study is to demonstrate the importance of movements off the ball in order to create shooting chances by evaluating quantitative data obtained from SNAP. The data that we analyzed from three J-league games showed that there was a higher frequency of positive movements off the ball by the attacking side before shooting.

Scheduling nurses to staff shifts is a major problem in hospitals. The necessity of maintaining a certain level of service and skill in the makeup of every shift, while balancing the workload among the nurses involved, is incredibly difficult. It is often impossible to develop a schedule which satisfies all the requirements despite the time and resources spent in the effort. This paper summarizes all our published research on nurse scheduling to date. The difficulties realized by our two investigations in Japan are shown first, together with a resulting scheduling problem. The nurse scheduling model based on the results is then described. In this model, all constraints are divided into two essentially different types; that which maintains a certain level of skill for each shift (&#039;shift constraints&#039;) and that which concerns the workload for each nurse (&#039;nurse constraints&#039;). By classifying the constraints in this manner, we can determine what is affected by a specific constraint when the constraint is not satisfied. We developed efficient algorithms while taking advantage of the structure of this model. Finally, it is shown that our algorithm can solve this problem for a 2-shift system efficiently.

この論文では2交替制ナース・スケジューリング問題に対して提案されているアルゴリズムの改善を試みる. 1998年に提案された池上・丹羽のアルゴリズムは, 看護婦の1ヶ月分の実行可能勤務パターンから最適なパターンを選び出すという部分問題を看護婦毎に設定し, これらを繰り返し解くことにより全体として実行可能な勤務表を作成していくものである. しかし部分問題を解くアルゴリズム自体は考えられておらず, 実際には実行可能勤務パターンをすべて列挙し, その都度全勤務パターンの評価計算をして比較するというものであった. よって, 効率よく実行可能解を見つけ出すと言われるものの実行可能解を与えるまでの時間に問題を抱えていた. この論文では, 部分問題を効率よく解くヒューリスティック解法を構築するために, 提案されているアルゴリズムの振る舞いを観察し, 解の改善過程において採用される勤務パターンの特徴を明らかにした. そして, 比較計算する実行勤務パターンを有効な範囲に絞り込むことによりスピードアップを図った. 改善されたアルゴリズムは提案されているアルゴリズムと同じ実行可能解を数倍から数10倍の速さで与えることができた.