JP7166232B2 - 情報処理装置、情報処理方法及びコンピュータプログラム - Google Patents

Description

本発明の実施形態は、情報処理装置、情報処理方法及びコンピュータプログラムに関する。

鉄道会社等では、列車編成（以下、編成）等の作業計画は人手で行われることが多い。例えば、鉄道の検査計画に関する先行技術として、検査周期の上限と走行距離の上限を考慮して、編成の次の検査計画日を自動計算するものがある。この計算を、単体の編成毎に行う。

また、別の先行技術として、編成に対する運行計画と検査計画を同時に作成するものがある。この方法では、全ての編成に対して同じ計画をずらしながら実施する巡回計画をまず作成する。その後、巡回計画の修正を人が行う。

しかし、各移動体は、個々の移動体の事情に応じて異なる作業が設定される場合がある。巡回計画では、これらの個別の制約を満たすことはできない。

特許第３４０８４９８号 特許第３９２８２６８号

本実施形態は、作業対象の制約を満たしつつ、作業対象の作業計画を作成する情報処理装置、情報処理方法及びコンピュータプログラムを提供する。

本発明の実施形態としての情報処理装置は、単位期間あたりに実施可能な作業の回数に関する第１制約条件と、作業対象に対する作業間の期間の長さに関する第２制約条件とに基づき、前記作業対象の作業計画を作成する作業計画作成部を備える。

本実施形態に係る作業計画作成装置のブロック図。 計画条件の一例を示す図。 キャパシティ情報の一例を示す図。 周期情報の一例を示す図。 作業の上位作業情報の一例を示す図。 予定作業情報の一例を示す図。 検査計画の制約条件テーブルの一例を示す図。 運行情報の一例を概略的に示す図。 変数の最適解もしくは準最適解を求めた結果の一例のテーブルを示す図。 つなぎ制約の具体例を示す図。 運行情報に示される各日の運行セットを編成群に割り当てる例を示す図。 運行情報に示される各日の運行セットを編成群に割り当てる他の例を示す図。 第１の実施形態に係る作業計画作成部の動作の一例のフローチャート。 第２の実施形態のキャパシティ情報の一例を示す図。 第２の実施形態の周期情報の一例を示す図。 清掃計画の制約条件テーブルの一例を示す図。 作業計画最適化部により作成された清掃計画の一例を示す図。 本実施形態に係る作業計画作成装置のハードウェア構成を示す図。

以下、図面を参照しながら、本発明の実施形態について説明する。

図１は、本実施形態に係る作業計画作成装置１０１（以下、本装置１０１）のブロック図である。本装置１０１は、１つ又は複数の作業対象に対する作業計画を、個々の作業対象の制約を考慮しつつ作成する。本実施形態では、作業対象として移動体、特に、鉄道の車両編成（以下、編成）を扱う。また編成に対する作業計画として、編成に対する検査計画を作成する。移動体は、編成でなく、自動車、バスなどの車両でもよい。また、作業対象は移動体でなく、スマートフォン、パーソナルコンピュータ又は産業機械などの装置であってもよい。

図１の作業計画作成装置１０１は、入力部１００、作業計画作成部２００、出力部５００、及び各種データベース（ＤＢ）３００～３５０、４１０～４３０を備える。

入力部１００は、計画条件入力部１１０、キャパシティ情報入力部１２０、周期情報入力部１３０、上位作業情報入力部１４０、予定作業情報入力部１５０及び運行情報入力部１６０を備える。

作業計画作成部２００は、キャパシティ制約条件生成部２１０、周期制約条件生成部２２０、ＮＧ日制約条件生成部２３０、作業計画最適化部２４０、及び運行充当処理部２５０を備える。

［計画条件］
計画条件入力部１１０は計画条件の情報を入力する。入力された計画条件の情報は、計画条件ＤＢ３００に格納される。

図２は、計画条件の一例を示す。計画条件は、作業計画の作成対象となる期間（計画期間）、計画対象となる複数の移動体、計画対象となる作業、及び計画対象となる周期日数に関する情報を含む。

本例では、計画期間は４／１～４／１１であり、計画対象となる移動体は５本の車両編成（０１編成～０５編成）である。計画対象となる作業の種類は列車検査（以下、検査）である。また周期日数は各移動体で共通であり、５日である。

ここで周期日数は、検査の実施間隔日数の上限値である。したがって、検査の間隔を、検査間の期間の長さの上限値以下に抑える必要がある。周期日数は、各編成の周期制約条件として機能する。周期制約条件は、一例として作業間の期間の長さに関する第２制約条件に対応する。

本例では、周期日数は、各移動体で共通であるが、周期日数は、各移動体で異なってもよい。この場合は、後述する周期情報で移動体ごとの周期日数を定義する。周期日数は一例として列車検査の法定周期に対応する。例えば、法定検査などの場合は作業の実施間隔日数の上限(法定周期)がある。作業の間隔を法定周期以下にする必要がある。

［キャパシティ情報］
キャパシティ情報入力部１２０は、キャパシティ情報を入力する。入力されたキャパシティ情報は、キャパシティ情報ＤＢ３１０に格納される。

図３（Ａ）は、キャパシティ情報の一例を示す。キャパシティ情報は、計画期間内の各日について、１日あたりに計画対象作業（検査）を実施可能な編成の本数の最大値（キャパシティ値）を含む。本例では、キャパシティ値は、平日が２、土日は０である。ここでは１日当たりの最大値を定義しているが、任意の単位期間（半日、２日、１週間など）あたりの最大値を定義してもよい。

図３（Ｂ）は、キャパシティ情報の他の例を示す。検査を行うことが可能な場所が複数ある場合に、場所ごとに、各日のキャパシティ値を含む。本例では、検査可能な場所として、Ａ車両基地と、Ｂ車両基地とがある。検査の種類が複数ある場合は、検査の種類ごとにキャパシティ値を定義してもよい。また、場所と種類の組み合わせごとにキャパシティ値を定義してもよい。

［周期情報］
周期情報入力部１３０は、各移動体（編成）の検査の周期情報を入力する。入力された周期情報は、周期情報ＤＢ３２０に格納される。

図４は、周期情報の一例を示す。周期情報は、各編成について、検査の周期日数を含む。また、周期情報は、各編成について、検査の最終実施日の情報を含む。

各移動体で周期日数が共通の場合、周期日数を計画条件で定めることもできるが、各移動体で周期日数が共通であるか否かに拘わらず、周期情報で周期日数を定めることができる。図４の例では周期情報で各移動体の周期日数を定めた場合を示している。周期日数は、全編成で同じ５日である。

最終実施日は、計画期間の初日より前に実施された最後の検査またはその上位検査の実施日である。上位検査は、本実施形態で計画の対象とする検査とは別の作業である。予め上位検査を行う予定日が定められている。上位検査は、計画対象の検査を包含する検査である。上位検査を行うと、計画対象の検査も行われたと見なすことができる。

最終実施日は日付でもよいし、計画期間の初日から遡った日数（相対日数）でもよい。図の例では、両方の場合の例が示されている。

なお、計画対象作業は２日以上にわたり実施される場合がある。この場合、周期制約条件を、前回の作業期間との間隔と、今回の作業期間の最終日との間隔により判断してもよい。また、周期制約条件の成否を、次回の作業期間との間隔と、今回の作業期間の開始日との間隔により判定してもよい。

例えば、今回の作業を４／１１に開始し４／１３に終了する場合で、周期日数が５日の場合を考える。前回実施日又は前回実施の最終日が４／８以降ならば、前回実施日の翌日からカウントして４／１３までの日数が５日以内であるため、周期制約条件を満たす。しかしながら、前回実施日又は前回実施の最終日が４／７以前の場合は、その翌日からカウントして４／１３までの日数が６日以上となるため、周期制約条件を満たさない。

また次回実施日が４／１６以前ならば、４／１１の翌日からカウントして次回実施日までの日数が５日以内のため、周期制約条件を満たす。しかしながら、４／１７以降の場合は、４／１１の翌日からカウントして次回実施日までの日数が６日以上のため、周期制約条件を満たさない。さらに、次回作業も複数日にわたり実施する場合、例えば、４／１５～４／１６で実施する場合は、４／１１の翌日からカウントして次回実施の最終日である４／１６までの日数が５日以内のため、周期制約条件を満たす。しかしながら、４／１５～４／１７で実施する場合は４／１１の翌日からカウントして次回実施の最終日である４／１７までの日数が６日以上となるため、周期制約条件を満たさない。

［上位作業情報］
上位作業情報入力部１４０は、計画対象作業の上位作業の情報を入力する。計画対象作業が検査の場合、上位作業は上位検査である。入力された情報を上位作業情報と呼ぶ。入力された上位作業情報は、上位作業情報ＤＢ３３０に格納される。

図５は、上位作業情報の一例を示す。上位作業情報は、上位検査を識別する情報を含む。本例では、「月検査は列車検査の上位検査」及び「重要部検査は列車検査の上位検査」といった情報が示される。前述したように、上位検査がある日に設定されている場合（つまり上位検査に予定日が設定されている場合）、その日は計画対象の検査が実施されたとみなして、周期制約条件の成否を判定する。つまり上位検査から次の検査までの間隔が周期日数以下であれば、周期制約条件を満たす。

［予定作業情報］
予定作業情報入力部１５０は、予め各種作業を行う日を定めた予定作業情報（第１情報）を入力する。入力された予定作業情報は、予定作業情報ＤＢ３４０に格納される。

図６は、予定作業情報の一例を示す。予定作業情報は、各編成に実施日が決まっている作業（予定作業）の計画情報である。各編成の予定作業の実施日が含まれる。予定作業の種類としては、計画対象作業（列車検査）、及び計画対象作業と異なる作業のいずれの場合も含む。計画対象作業と異なる作業の例は、上位検査（月検査、重要部検査など）、及び上位検査以外の作業（清掃など）を含む。図７の一番上の例は、０２編成は、４／８に清掃を実施すことが予定されている。また、０４編成は、１／１０～４／３の長期間にわたり、重要部検査を実施することが予定されている。

予定作業が計画対象作業（検査）の場合、予定をできるだけ守りたい、必ず守りたいなどのバリエーションが存在する。本実施形態では、予定を必ず守ることとする。この場合、その予定日に編成に作業を割り当てることを制約条件（第３制約条件）とする。

上位検査は、基本的には固定された作業であり、周期制約条件の判定では、上述したように、この日に計画対象の作業が実施されたとみなす。つまり、上位作業の実施は、計画対象作業の実施とみなす。上位検査は計画対象作業とは別の施設で行うため、上位検査は、キャパシティ値のカウントの対象から除外してもよい。上位検査も計画対象作業と同じ施設で行う場合に、キャパシティ値のカウントの対象とすることも排除されない。本実施形態では上位検査は、キャパシティ値のカウントの対象から除外する。

その他の作業（清掃等）は、計画対象作業とは別の場所で行われる場合や、計画対象作業との同時作業が難しい場合も有り得るため、以下の制約条件を与えてもよい。例としては、当該その他の作業が行われる日に対する計画対象作業の割り当てを不可とする。また、その他の作業と計画対象作業とが重複した場合のルールを予め定義しておき、ルールを満たすように作業計画を作成してもよい。その他の作業に関する制約条件は、一例として、その他の作業が行われる日又は日時には計画対象作業を割り当てない第４制約条件に対応する。

各入力部１１０～１５０で入力された情報は、作業計画作成部２００で行う演算の制約条件として用いられる。

図７は、図２～図６の各種情報を１つにまとめた、検査の制約条件テーブルである。計画期間の各日付を表す列と、各編成を表す行とがある。さらに、キャパシティの行があり、キャパシティの行には、各日付のキャパシティ値が格納されている。予定作業を識別する情報が、日付の列と編成の行とが交差しているセルに格納されている。各編成の行には、編成ＩＤと、周期日数と、最終実施日とが格納されている。

本例では、計画期間は４／１～１１、計画対象の編成は０１編成～０５編成、各編成の周期日数は５日である。各日のキャパシティ値は、平日は２回、土日は０回である。４／１より前の最終実施日が編成ごとに示されている。予定作業として、月検査（４／４，０３編成），重要部検査（４／１～４／３，０４編成），清掃（４／８，０２編成），検査（４／５，移動体０５）が登録されている。

［運行情報］
運行情報入力部１６０は、計画対象期間内の各日について列車の運行情報を入力する。入力された運行情報は、運行情報ＤＢ３５０に格納される。

運行情報は、計画対象期間内の各日に行う必要のある運行のセットを含む。その他、運行情報は、計画対象期間の初日の各移動体の場所（出発場所）の情報を含んでもよい。また、運行情報は、各作業の指定運行（後述）の情報を含んでもよい。

図８は、運行情報の一例を概略的に示す。平日運行と休日運行の２つが示される。計画対象期間内において、平日は平日運行が適用され、休日は休日運行が適用される。平日運行は５つの運行１～５を含む。休日運行は２つの運行６、７を含む。平日（月～金）においては、運行１～５のすべてを重複なく、計画対象の編成群（本例では０１～０５編成）に割り当てる必要がある。休日（土、日、祝日）においては、運行６、７のすべてを、重複なく、当該編成群に割り当てる必要がある。なお運行の割り当ては、計画対象作業（検査）の割り当ての後に行われる。なお、運行が割り当てられない編成が存在してもよい。

図８において各運行は矩形によって表されている。矩形内の番号は運行番号である。矩形内で出発場所と到着場所が矢印で結ばれている。出発場所は列車の出発場所、到着場所は列車の到着場所である。例えば、平日運行の運行１の場合、出発場所は場所Ｃであり、到着場所は場所Ａである。なお、場所Ａ、Ｃ等は、駅でもよいし、駅以外の場所（車両基地）でもよいし、それ以外の場所でもよい。最後の到着場所がＡであれば、途中場所Ａを通過しても、場所Ａで折り返ししてもよい。例えば場所Ａと場所Ｃを複数回往復して、最後の場所Ａに到着してもよい。

凡例に示すように、各運行の出発時刻と到着時刻が矩形の両端に付記されていてもよいが、本例では簡単のため省略している。出発時刻及び到着時刻に応じて、午前運行、午後運行、１日運行の種類がある。横幅の短い矩形は、午前運行又は午後運行に対応し、横幅の長い矩形は１日運行に対応する。一例として、午前運行は７：００～１０：００、午後運行は１５：００～１９：００、１日運行は５：００～２４：００などである。本例では、午前運行は、運行１、２である。午後運行は、運行４、５である。１日運行は運行３、６、７である。計画対象作業は、例えば、数時間程度である運行の合間（午前運行と午後運行の間）に実施する。

入力部１１０～１６０は、本装置１０１のオペレータが操作するキーボード、マウス、タッチパネル等の入力手段である。この場合、情報を入力するためのインタフェース画面を提示する機能を、本装置１０１は備える。インタフェース画面は、出力部５００に表示される。入力部１１０～１６０は、情報を外部の装置又は記憶媒体から取得する取得手段でもよい。この場合、外部の装置は、一例として、本装置１０１と有線又は無線の通信ネットワークを介して接続された外部サーバである。また、記憶媒体は、一例として、本装置１０１の内部に配置された記憶媒体又は外部接続された記憶媒体である。記憶媒体の例は、メモリ装置、ハードディスク、ＳＳＤ、光学ディスクなどを含む。ダイヤの取得のトリガーは、本装置１０１のオペレータの指示でもよいし、その他の条件（例えば所定の時刻になったなど）でもよい。

作業計画作成部２００は、キャパシティ制約条件、周期制約条件及びＮＧ日制約条件をそれぞれ制約条件として生成し、これらの制約条件の下での最適解又は準最適解として、作業計画（検査計画）を作成する。作業計画作成部２００は、この作業計画に基づき、計画対象の編成群に、予定されている全ての運行の割り当てを行う。全ての運行が割り当てできたときは、この作業計画は実施可能と判断し、出力作業計画として出力作業計画ＤＢ４３０に出力する。実施不能であると判断される場合は、作業計画作成部２００は、検査が割り当てられていたために運行を割り当てできなかった日・編成の組を特定し、特定した組をエントリとして失敗情報（ＴａｂｕＬｉｓｔ）に登録する。失敗情報に登録された日付・編成に作業を割り当てないことを追加の制約条件として、再び作業計画の最適化処理（作業計画の再作成）を行う。以上の処理を、全ての運行を割り当て可能な作業計画が作成されるまで、再帰的に繰り返す。実施可能と判断される前の作業計画を仮作業計画と称する。

出力部５００は、出力作業計画ＤＢ４３０から出力作業計画を読み出して、画面に表示する。ユーザは、表示された出力作業計画を見て、各編成の作業計画を確認する。

以下、作業計画作成部２００について詳細に説明する。

上述した図７の制約条件テーブルの場合を例として、作業計画を作成する例について述べる。図７において、重要部検査及び月検査は、検査に対して上位の検査であり、当該日は検査が実施されたとみなされる。なお重要部検査のように複数日連続して実施される場合は、全ての日が検査の実施日とみなされる。また清掃実施日には、検査は実施できないものとする。

キャパシティ制約条件生成部２１０は、キャパシティ情報ＤＢ３１０からキャパシティ情報を読み出し、読み出した情報を作業計画最適化部２４０で実行可能な式に変換する。これにより作業計画最適化部２４０で実行可能な形式でキャパシティ制約条件を作成する。キャパシティ制約条件は、一例として、単位期間あたりに実施可能な作業の回数に関する第１制約条件に対応する。

周期制約条件生成部２２０は、周期情報ＤＢ３２０から周期情報を読み出し、読み出した情報を作業計画最適化部２４０で実行可能な式に変換する。これにより作業計画最適化部２４０で実行可能な形式で周期制約条件（第２制約条件）を作成する。

ＮＧ日制約条件生成部２３０は、上位作業情報ＤＢ３３０及び予定作業情報ＤＢ３４０からそれぞれ上位作業情報及び予定作業情報を読み出し、ＮＧ日制約条件を生成する。ＮＧ日制約条件は、３つの集合ＦｉｘＳＥＴ，ＵｐｐｅｒＳＥＴ，ＮＧＳＥＴを含む。

ＦｉｘＳＥＴは、予め計画対象作業（検査）を行うとして予定した日付と編成の組を登録するための集合である。ＦｉｘＳＥＴは、予定作業情報ＤＢ３４０における計画対象作業の情報から作成する。図７の例では、４／５に０５編成の検査を行うことが予め決められているため、ＦｉｘＳＥＴを以下のように生成する。ＦｉｘＳＥＴは、ＦｉｘＳＥＴに登録された日付と編成の組に作業を割り当てることを定めた制約条件（第３制約条件）として用いられる。
ＦｉｘＳＥＴ＝｛（０５編成，４／５）｝ （１）

ＵｐｐｅｒＳＥＴは、上位作業（上位検査）が予定されている日付と編成の組を登録するための集合である。ＵｐｐｅｒＳＥＴは、上位作業情報ＤＢ３３０と予定作業情報ＤＢ３４０とを対応づけることで作成する。本例では、上位作業情報ＤＢ３３０で月検査と重要部検査とが上位作業として設定されており、これらの上位作業の予定日は、予定作業情報ＤＢ３４０に設定されている。よって、ＵｐｐｅｒＳＥＴは、以下のように生成される。
ＵｐｐｅｒＳＥＴ＝｛（０３編成，４／４），（０４編成，４／１），（０４編成，４／２），（０４編成，４＝３）｝ （２）

ＮＧＳＥＴは、計画対象の作業を実施できない、日付と編成の組を登録するための集合である。ＮＧＳＥＴは、予定作業情報ＤＢ３４０における計画対象以外の作業の情報から作成する。計画対象以外の作業は、図６の例では清掃である。０２編成は４／８に清掃が行われるため、この日には検査を実施できない。この例では、ＮＧＳＥＴは以下のように作成される。ＮＧＳＥＴは、他の作業の予定日には計画対象作業を割り当てないことを定めた第４制約条件として用いられる。
ＮＧＳＥＴ＝｛（０２編成，４／８）｝ （３）

なお、ある日、ある編成に対して、計画対象の作業と、これとは別の作業（例えば清掃）との両方を設定することを許容する場合には、編成及び日付の組を、ＮＧＳＥＴに登録する必要はない。

作業計画最適化部２４０による作業計画（検査計画）の作成について述べる。ここでは、以上で得た制約条件の下で、以下のような数理モデルに基づくモデル化を行う。

ここで、各文字は下の通り定義される。
・日の集合｛１，２，…，Ｄ’｝（≡Ｄ）
・編成の集合｛１，２，…，Ｈ’｝（≡Ｈ）
・変数ｘ_ｄ，ｈ：ｄ日目ｈ編成で検査を実施するか否かの０又は１の変数
・定数Ｔ：周期日数
・定数Ｃ_ｄ：ｄ日目の最大検査実施回数（キャパシティ値）
・ＦｉｘＳＥＴ：検査が予め設定された（日，編成）の組の集合
・ＵｐｐｅｒＳＥＴ：上位検査が予め設定された（日，編成）の組の集合
・ＮＧＳＥＴ：他の作業が設定されているために検査を実施できない（日，編成）の組の集合
・ＴａｂｕＬｉｓｔ：ＴａｂｕＬｉｓｔに登録されている、検査を実施できない（日，編成）の組の集合

式（４）は、編成の集合に対して計画する作業回数（検査回数）を最小化するための目的関数を表す。式（５）～（９）は制約式である。
式（５）は１日の検査の回数がキャパシティ値以下であることを表す。式（５）は第１制約条件に対応する。
式（６）は周期制約条件（周期日数内に少なくとも１回の検査を行う必要がある）を表す。式（６）は、一例として第２制約条件に対応する。この場合、ｄ日目から、ｄ＋Ｔ日目までの間に少なくとも１回検査又は上位検査を必ず実施することを表す。なお, ｄ＝１の場合は、最終実施日からＴ日以内に検査または上位検査を必ず実施しなければならないことを制約式に反映しても良い。たとえば編成０１は最終実施日が３日前であるため、x_１,01 + x_2,01 + x_3,01≦1 のように表し、1～3日目のいずれかで検査または上位検査を実施することを表せばよい。
式（７）はＦｉｘＳＥＴ又はＵｐｐｅｒＳＥＴに登録されている（日付、編成）について、当該日付に当該編成は、検査又は上位検査を必ず実施することを表す。式（７）は、第３制約条件に対応する。
式（８）はＮＧＳＥＴ又はＴａｂｕＬｉｓｔに登録されている（日付、編成）について、当該日付に当該編成の検査を実施できないことを表す。式（８）は第４制約条件に対応する。
式（９）は変数が０又は１であることを表す。

なお、上記のモデルに対して、計画対象作業の実施場所ごとにキャパシティ値を定義してもよい。また、上位検査分のキャパシティ値を予め定数Ｃ_ｄに加算してもよい。周期制約条件に関して、各編成の初回の実施日のみ、最終実施日に応じて実施日を調整してもよい。

作業計画最適化部２４０は、（５）～（９）の制約条件を満たすように、目的関数（評価関数）を最小化又は準最小化することで、変数（ｘ_ｄ，ｈ）の最適解もしくは準最適解を求める。解法としては、GurobiOptimizer,CPLEXなどの数理計画ソルバーを用いてもよいし、シミュレーティッドアニーリング(SimulatedAnnealiＮＧ)、遺伝的アルゴリズム(GeneticAlgorithm)などのメタヒューリスティック解法を用いてもよい。結果として最適解もしくは準最適解を求めることができる。上記の数理モデルに対し、全ての制約条件を充足できない場合に、充足できない理由を出力してもよい。なお、ここで示した定式化は一例であり、他の目的関数や制約式を用いても構わない。

図９は、変数（ｘ_ｄ，ｈ）の最適解もしくは準最適解を求めた結果の一例のテーブルである。このテーブルは、図７の制約条件テーブルのセルに、各編成に対する検査の割り当て結果を格納したものである。

この例では、（４／１，０１編成），（４／６，０１編成），（４／１１，０１編成），（４／４，０２編成），（４／７，０２編成），（４／８，０３編成），（４／８，０４編成），（４／１，０５編成），（４／７，０５編成）に新たに検査が割り当てられている。結果的に、周期制約条件、キャパシティ制約条件及びＮＧ日制約条件などを満たす計画となっている。

周期制約条件については、例えば、０１編成についてみると、最終実施日３／２８に対し、４／１，４／６，４／１１の順に検査が実施されることとなり、実施間隔は、それぞれ４日、５日、５日となる。よって、全ての間隔は５日以内となっているので、周期制約条件を満たしている。

また、例えば０３編成では、４／８に検査が実施されることとなり、４／４の月検査に対して実施間隔は４日である。また４／４の月検査は、検査の最終実施日３／３０に対して実施間隔は５日である。前述したように月検査を行った場合、検査も行われたとみなす。よって、０３編成でも、周期制約条件は満たされている。

他の編成についても同様に、周期制約条件が満たされている。

作業計画最適化部２４０は、目的関数の最小化又は準最小化により求めた変数（ｘ_ｄ，ｈ）の解に基づき、０１～０５編成の検査の作業計画（仮作業計画）を作成する。前述の図９は仮作業計画の一例である。作業計画最適化部２４０は、仮作業計画を仮作業計画ＤＢ４２０に格納する。

運行充当処理部２５０は、仮作業計画ＤＢ４２０から仮作業計画を読み出し、運行情報ＤＢ３５０から運行情報を読み出す。運行充当処理部２５０は、仮作業計画を前提とした場合に、運行情報において仮作業計画の各日に予定されている全ての運行を計画対象の編成群に重複なく割り当てる処理を行う（運行充当処理）。すべての運行を編成群に割り当てることができた場合は、仮作業計画は実施可能であると判断する。少なくとも１つの運行をいずれの編成にも割り当てることができない場合は、仮作業計画は実施不可と判断する。

運行充当処理部２５０は、仮作業計画は実施可能と判断した場合は、当該仮作業計画を、出力作業計画として出力作業計画ＤＢ４３０に格納する。

運行充当処理部２５０は、仮作業計画は実施不可と判断した場合は、運行が割り当てできない原因となっている日付・編成を特定する。すなわち、計画対象作業（検査）が割り当てられたために運行を割り当てることができなかった日付と編成との組を特定する。特定した組を失敗情報（ＴａｂｕＬｉｓｔ）に登録する。失敗情報を失敗情報ＤＢ４１０に格納する。ＴａｂｕＬｉｓｔには、本処理が再帰的に繰り返されるごとに、累積的に日付と編成の組が追加される。なお、初期状態ではＴｕｂｕＬｉｓｔには何も登録されていない。

作業計画最適化部２４０は、失敗情報ＤＢ４１０からＴａｂｕＬｉｓｔを読み出し、これを最新のＴａｂｕＬｉｓｔとして用いて、再度、最適化処理を行う。求めた変数（ｘ_ｄ，ｈ）の解に基づき、仮作業計画を再度作成する。作業計画最適化部２４０は、再作成した仮作業計画を仮作業計画ＤＢ４２０に格納する。

運行充当処理部２５０は、仮作業計画ＤＢ４２０から再作成された仮作業計画を読み出す。運行充当処理部２５０は、読み出した仮作業計画に対して、運行充当処理を行う。運行情報に示されるすべての運行を計画対象の編成群に割り当てることができた場合は、仮作業計画は実施可能であると判断する。少なくとも１つの運行をいずれの編成にも割り当てることができない場合は、仮作業計画は実施不可と判断する。

以降、運行充当処理部２５０で実施可能と判断される仮作業計画が得られるまで、作業計画最適化部２４０による仮作業計画の作成と、運行充当処理部２５０による運行充当処理とを繰り返す。繰り返し回数が所定回数に達した場合は、処理を終了し、その時点での仮作業計画を出力してもよい。

以下、図１０～図１２を用いて、運行充当処理の具体例を説明する。

運行充当処理では、各編成に対して、連続する運行に関して、つなぎ制約を満たす必要がある。ここで、つなぎ制約とは、
前の運行の到着場所=次の運行の出発場所 (10)
前の運行の到着時刻<次の運行の出発時刻 (11)
の２つの条件を満たすことである。

連続する運行は、検査、清掃等の作業を介在して連続する場合や、日をまたいで連続する場合などがあるが、いずれの場合も、つなぎ制約を満たす必要がある。

図１０は、つなぎ制約の具体例を示す。前の運行の到着場所がＢの場合、次の運行の出発場所もＢである必要がある。図で丸がついている運行１→運行４は式（１０）を満たす。よって、式（１１）を満たせば、つなぎ制約を満たす。×がついている運行１→運行５は、式（１０）を満たさない。よって、つなぎ制約を満たさない。

図１１は、運行情報に示される各日の運行のセットを仮作業計画に基づき編成群に割り当てる例を示す。図１１の例は、運行割り当てに成功した例である。

ここでは簡単のため０１編成、０２編成、０３編成のみ存在する場合を示す。仮作業計画で、４／１には、０１編成に清掃が割り当てられており、０３編成には検査が割り当てられている。

検査の場所は場所Ａ、清掃の場所は場所Ｂであることが予め定められている。検査の場所及び清掃の場所は、編成ごとに予め定められている。この情報は計画条件又は予定作業情報等に含まれていてもよいし、別途ユーザが入力することにより与えてもよい。

検査及び清掃は、例えば、日中の予め定めた時間の範囲内で行われる。例えば１１：３０～１５：００までの間の任意の連続する２時間で行われるとする。

本実施形態では、午前運行の列車は、午前運行の到着場所が検査の場所に一致していれば、当該列車の検査を実施可能である（検査に間に合う）とする。つまり、到着駅が検査の場所に一致している運行のみを編成に割り当てることができる。換言すれば、到着駅が検査の場所に一致していない運行を当該検査が行われる編成に割り当てることはできない。清掃についても同様である。１日運行の列車は、その日は、検査も清掃も実施できないとする。

また午後運行の列車は、上記のつなぎ制約を満たす限り、検査又は清掃等が行われた後、その日に割り当てることができるとする。

図１１の例では、４／１に０２編成に検査が割り当てられている。０２編成の初日場所（計画対象期間の最初の日の出発場所）は場所Ｃであり、検査の場所は場所Ａであるため、出発場所が場所Ｃで到着場所が場所Ａの午前運行を０２編成に割り当て可能である。また場所Ａを出発場所とする午後運行を０２編成に割り当て可能である。これらを考慮して、０２編成には、午前運行１（Ｃ→Ａ）と、午後運行４（Ａ→Ａ）とが割り当てられている。つまり０２編成は、午前運行と午後運行との合間に、場所Ａで作業（検査）を実施できる。

また、４／２に０１編成に検査が割り当てられているが、運行は割り当てられていない。その場合、直前の最後の運行（例えば前日の午後運行）として、場所Ａを到着場所とする運行を割り当てておく。本例では、前日の４／１の午後運行として場所Ａを到着場所とする運行５を０１編成に割り当てている。このように、その日の編成に余裕がある場合には、前日までに場所Ａに編成を移動させておき、当日当該編成に運行を割り当てないような運用を行ってもよい。運行を割り当てられない編成は、予備列車として機能する。

ここでは午前及び午後と、到着場所及び出発場所を考慮して、運行を割り当て可能かどうか判断したが、各運行の出発時刻及び到着時刻、検査、清掃等の開始時刻及び終了時刻を具体的に考慮して、運行の割り当て可能可否を判断してもよい。例えば、午前運行の到着時刻が、検査の開始時刻から一定時間内の場合は、午前運行を割り当てるとしてもよい。

図１２は、運行情報に示される各日の運行のセットを、仮作業計画に基づき編成群に割り当てる他の例を示す。図１１では運行割り当てに成功した例を示したが、図１２の例は運行割り当てに失敗した例である。

図１１の例と異なり、仮作業計画で４／１に０２編成でなく、０３編成に検査が割り当てられている。その他の条件は、図１１の例と同じである。

つなぎ制約を満たすように各運行を割り当てていくと 割り当てることができない運行が発生する。０１編成、０２編成にそれぞれ図示のように午前運行及び午後運行を割り当てると、１日運行３（Ｂ→Ｂ）が残る。この運行３では、０３編成は、午前中に検査場所である場所Ａに到着できないため、運行３を０３編成に割り当てることができない。

本例では、すべての運行を重複しないように編成群に割り当てることができない。すなわち、運行充当条件を満たすことができない。よって、この仮作業計画は実行不可と判定される。この場合、（４／１，０３編成）を失敗情報ＤＢ４１０の失敗情報（ＴａｂｕＬｉｓｔ）に追加し、作業計画最適化部２４０により再計画を行う。ＴａｂｕＬｉｓｔに（４／１，０３編成）を追加したことにより、４／１に編成（０３編成）に検査を割り当てないことを制約条件（第５制約条件）として、再計画が行われる。したがって、次回以降に作成される仮作業計画では、４／１に０３編成に検査が割り当てられない。

運行充当条件を満たすかを判定する具体的な方法は、一例として、運行と編成とのすべての組み合わせパターンについて運行充当条件を満たすかを判断してもよい。これらのうち２以上のパターンが運行充当条件を満たす場合は、これらの中から任意のパターンを採用してもよい。

あるいは、パターンの選択する順序に関するルールを定めて置き、ルールに従って、パターンを順番に選択し、選択したパターンについて、全ての運行が割り当てできるか判断してもよい。全ての運行が割り当てできた時点で、そのときのパターンを採用する。

複数のパターンの全てで運行充当条件を満たさない場合は、これらのうち任意のパターンを選択し、当該選択したパターンについて、日付・編成の組を特定し、特定した組を、ＴａｂｕＬｉｓｔに追加してもよい。なお、選択するパターンによって、ＴａｂｕＬｉｓｔに追加する日付・編成の組は変わり得る。

なお、運行充当条件の判定処理は、特許５０７５５７７号に開示された手法などを用いてもよいし、それ以外の方法を用いてもよい。

ここではＴａｂｕＬｉｓｔに追加する日付・編成の組を自動的に抽出したが、ユーザが図１２のような割り当て結果又は仮作業計画の画面を見て、ＴａｂｕＬｉｓｔに登録する日と編成との組を入力装置から直接入力してもよい。この場合、作業計画作成部２００は、ユーザから入力された組を、ＴａｂｕＬｉｓｔに追加する。

［指定運行方式を用いる場合の運行充当条件の判定処理］
ある日・ある編成にある作業（検査）が設定された場合に、その編成に対する運行を具体的に１つ又は複数指定する場合(このような運行を「指定運行」という)がある。このような場合、指定運行を満たすように、編成に運行を割り当てる必要がある。また、指定運行がある場合、運行充当条件の成否の判定処理を、下記のいずれか条件が成立した場合に高速化できる。

（条件１）その日に設定された作業（検査）の数が、指定運行の数を上回った場合などに、運行充当条件を満たさないと判定することができる。

例えば、作業ｗ１の指定運行がｕ１，ｕ２である場合を考える。編成ｈ１，ｈ２，ｈ３に作業ｗ１が割り当てられている場合は、編成ｈ１、ｈ２、ｈ３のそれぞれに対してｕ１，ｕ２の少なくとも一方を割り当てる必要がある。しかしながら、ｈ１，ｈ２，ｈ３の３編成の中に、ｕ１，ｕ２の２指定運行のいずれも割り当てることができない編成が発生する。このため、この時点で、運行充当条件は満たさないと判断できる。ＴａｂｕＬｉｓｔには、編成ｈ１、ｈ２、ｈ３の少なくともいずれか１つの編成についてその日に検査を割り当てないよう日付・編成を追加する。日付・編成の指定はユーザが行ってもよいし、運行充当処理部２５０が行ってもよい。

（条件２）その日に複数種類の作業があり、それらの作業の指定運行に重複がある場合には、運行充当条件を満たさないと判定することができる。

例えば、作業ｗ１の指定運行がｕ１，ｕ２，作業ｗ２の指定運行がｕ１であるとする。編成ｈ１，ｈ２に作業ｗ１，編成ｈ４に作業ｗ２が割り当てられている場合、編成ｈ１，ｈ２，ｈ４の３編成のいずれか１つは指定運行を割り当てることができなくなる。例えば、編成ｈ１にｕ１、編成ｈ２にｕ２を割り当てると、編成４にｕ１を割り当てることができなくなる。また、編成１にｕ２、編成ｈ４にｕ１を割り当てると、編成ｈ２にｕ１又はｕ２を割り当てることができなくなる。このため、この時点で、運行充当条件は満たさないと判断できる。ＴａｂｕＬｉｓｔには、編成ｈ１、ｈ２、ｈ４の少なくともいずれか１つの編成について、その日に検査を割り当てないよう日付・編成を追加する。日付・編成の指定はユーザが行ってもよいし、運行充当処理部２５０が行ってもよい。

（条件３）さらに、作業の設定日が計画対象期間の初日の場合等において、指定運行の中に、編成に割り当てできない運行が存在する場合には、運行充当条件を満たさないと判定することができる。

例えば、作業ｗ１の指定運行がｕ１，ｕ２，作業ｗ２の指定運行がｕ１であるとする。編成ｈ１，ｈ２の初日にそれぞれ作業ｗ１が割り当てられており、編成ｈ１，ｈ２のいずれにもｕ１を割り当てられない場合がある。例えば、編成ｈ１，ｈ２いずれも初日の出発場所が場所Ａであり（場所Ａからの出庫であり）、指定運行ｕ１の出発場所が場所Ｂである場合を考える。編成ｈ１，ｈ２のいずれかに指定運行ｕ２を割り当てできたとしても、指定運行ｕ１をいずれにも割り当てできない。よって、この場合には、運行充当条件を満たさないと判定することができる。ＴａｂｕＬｉｓｔには、例えば、出発場所が場所Ｂである他の編成について、その日（初日）に検査を割り当てないよう日付・編成を追加する。つまり、運行が割り当てできない原因となっている日付・編成に検査を割り当てないようにする。日付・編成の指定はユーザが行ってもよいし、運行充当処理部２５０が行ってもよい。

図１３は、本実施形態に係る作業計画作成部２００の動作のフローチャートである。
キャパシティ情報ＤＢ３１０、周期情報ＤＢ３２０、上位作業情報ＤＢ３３０、予定作業情報ＤＢ３４０を用いて、制約条件を生成する（Ｓ１１）。より詳細には、キャパシティ情報ＤＢ３１０からキャパシティ情報を読み出し、キャパシティ情報からキャパシティ制約条件を生成する。周期情報ＤＢ３２０から周期情報を読み出して、周期制約条件を生成する。上位作業情報ＤＢ３３０及び予定作業情報ＤＢ３４０からそれぞれ上位作業情報及び予定作業情報を読み出して、ＮＧ日制約条件を生成する。また、失敗情報（ＴａｂｕＬｉｓｔ）を初期化する。

作業計画最適化部２４０は、ステップＳ１１で生成された各種制約条件と、計画条件ＤＢ３００の計画条件に基づき、目的関数を生成し、目的関数を最適化又は準最適化する。これにより、各編成に計画対象作業（検査）を割り当てる日を特定した解を求める（Ｓ１２）。求めた解に基づき、各編成に作業（計画対象作業、上位作業、他の作業）を割り当てた仮作業計画を作成する（Ｓ１２）。仮作業計画を仮計画ＤＢ４２０に格納する。

運行充当処理部２５０は、仮計画ＤＢ４２０から仮作業計画を読み出し、運行情報ＤＢ３５０から運行情報を読み出す。運行情報に示される各運行を計画対象の編成群に割り当てる運行充当処理を行う（Ｓ１３）。

全ての運行を割り当てることができたら（Ｓ１４のＹＥＳ）、仮作業計画を出力作業計画として出力作業計画ＤＢ４３０に格納する。出力部５００は、出力作業計画ＤＢ４３０内の出力作業計画を画面に表示する。

運行情報に示される運行のうち割り当てることができない運行が存在する場合は（Ｓ１４のＮＯ）、運行が割り当てできない原因となっている日付・編成を特定する（Ｓ１５）。すなわち、作業（計画対象作業）が割り当てられているために運行を割り当てることができない日付・編成の組（ｄ、ｈ）を特定する（Ｓ１５）。特定した組をＴａｂｕＬｉｓｔに追加する（Ｓ１５）。割り当てることができない運行が複数存在する場合は、割り当てることができないすべての運行についてそれぞれ（ｄ、ｈ）を特定する。ただし、割り当てることができないすべての運行のうち、少なくとも１つの運行について（ｄ、ｈ）を特定するだけでもよい。

仮作業計画の作成回数をカウントし、所定回数以下であれば、ステップＳ１２に戻り、仮作業計画を再作成する。この際、ＴａｂｕＬｉｓｔを制約条件として追加する。これにより、ＴａｂｕＬｉｓｔに含まれる日・編成の組には、計画対象作業が割り当てられない。ＴａｂｕＬｉｓｔにはステップＳ１５が繰り返されるごとに累積的に（ｄ、ｈ）が追加される。

仮作業計画の作成回数が所定回数を超えた場合は、本処理を終了する。この際、現時点の仮作業計画とＴａｂｕＬｉｓｔを出力作業計画ＤＢ４３０に格納してもよい。出力部５００は、出力作業計画ＤＢ４３０内の仮作業計画とＴａｂｕＬｉｓｔを画面に表示してもよい。ユーザは、ＴａｂｕＬｉｓｔを参照して、仮作業計画を手動で調整し、出力作業計画を作成してもよい。

なお図１３のフローチャートでは、作業計画の後に、運行を割り当てる構成となっているが、ステップＳ１１，Ｓ１２により作業計画を作成した後、運行の割り当てのステップＳ１３～Ｓ１６を省略してもよい。例えば、運行の割当可能性を重視しない場合や、どのような作業計画であっても運行は割り当てられる場合に、このような動作を行うことが有り得る。

以上、本実施形態によれば、各編成の周期制約条件と、単位期間あたりに実施可能な作検査の回数のキャパシティ制約条件に基づき、各編成に割り当てる作業の日を決定することにより、各編成の個別の制約（例えば検査の周期）や、検査の実施能力等の制約を考慮した作業計画を作成することができる。

また、各編成に上位検査が設定されている場合、その日は計画対象作業が実施されたとみなすことにより、上位検査も考慮して、周期制約条件の成否を判定できる。また、作業の実施総回数を最小化するように作業計画を作成することで、検査の費用を削減することができる。

予め割り当てた検査（計画対象作業）が存在する場合にその日に必ず検査を割り当てることで、編成の個別の制約を考慮した作業計画を作成できる。

また計画対象以外の作業が予め編成に割り当てられている場合、当該日には編成に検査を割り当てないようにすることで、編成の個別の制約を考慮した作業計画を作成できる。

また作成した作業計画を前提として、計画対象の編成群に、予定されている運行を割り当てる運行充当処理を行い、割り当てできない運行が存在する場合は、当該作業計画を再作成する。これにより、予定されている運行の実施を保証可能な作業計画を作成することができる。

また、ある作業に対して指定運行が定められている場合も、当該指定運行を実施可能な作業計画を作成できる。

（第２の実施形態）
第１の実施形態では、計画対象作業が検査であり、周期日数の上限値を満たす必要がある場合について記載したが、第２の実施形態では計画対象作業が清掃であり、周期日数の目標値を満たす場合について記載する。例えば、計画対象作業が清掃などの場合は、作業（清掃の）の間隔は周期日数を超過してもよいが、できるだけ間隔を周期日数の目標値に近づけたい場合がある。本実施形態のブロック図は第１の実施形態と同じ図１である。以下、第１の実施形態との差分を中心に説明する。

本実施形態では、キャパシティ値は、清掃の種類ごともしくは清掃の種類の組合せに対して定められる。清掃の種類に応じて、作業量や作業施設が異なる場合を想定したものである。このためキャパシティ情報入力部１２０から入力されるキャパシティ情報には、種類別のキャパシティ値が含まれる。

図１４は、本実施形態のキャパシティ情報の一例を示す。この例では、平日に関して、大清掃、小清掃のキャパシティがそれぞれ１である。すなわち、平日では、大清掃、小清掃をそれぞれ１回行うことができる。休日に関して、大清掃、小清掃のキャパシティがそれぞれ０である。

大清掃の方が小清掃よりも作業量が多いことから、大清掃、小清掃のキャパシティがそれぞれ１の場合、１日に小清掃のみを２回実施することも可能であるとする。ただし、１日に大清掃を２回実施することはできない。あるいは、小清掃だけなら１日３回実施することを可能としてもよい。大清掃と小清掃の回数の可能な組合せを定義し、任意の組合せを選択できるようにしてもよい。

また、本実施形態では、編成ごとに、各種類の清掃の実行順序が予め決められている。本例では、大清掃及び小清掃の２種類があり、最終実施回の清掃の種類に応じて、交互に実施される。例えば、大清掃→小清掃→大清掃→小清掃→の順に実行する。このため周期情報入力部１３０から入力される周期情報には、最終実施日に行った清掃の種類が含まれている。

また、本実施形態では、第１の実施形態の周期日数の制約条件が作業間の日数の上限値から目標値（目標周期）に変更される。目標周期は必ず守らなければならない条件ではなく、努力目標となる。周期情報入力部１３０から入力される周期情報には、周期日数ではなく、目標周期が含まれている。

図１５は、本実施形態に係る周期情報の一例を示す。目標周期は各編成とも５日になっている。また各編成について最終実施日に行った清掃の種類が含まれている。

図１６は、清掃計画の制約条件テーブルの一例を示す。制約条件テーブルは、本実施形態に係る各種入力部１１０～１５０から入力された情報をまとめて含む。第１の実施形態と異なり、最終実施日に実施された清掃の種類が含まれている。また、第１の実施形態の周期日数が目標周期に変更されている。また、キャパシティ値が、清掃の種類に応じて定められている。例えば４／１は、大清掃のキャパシティ値が１、小清掃のキャパシティ値が１である。

以下、作業計画最適化部２４０による作業計画（清掃計画）の最適化モデルについて説明する。１～Ｄ日目を含む期間について、編成１～Ｈに対して、各Ｋ個ずつの清掃を実施する清掃計画を得るためのモデルは、下記のような数理計画問題として与えられる。

ここで、各文字は下の通り定義される。
・日の集合｛１，２，…，Ｄ’｝（≡Ｄ）
・編成の集合｛１，２，…，Ｈ’｝（≡Ｈ）
・回数の集合｛１，２，…，Ｋ’｝（≡Ｋ）
・清掃の種類の集合｛１，２，…，Ｔ’｝（≡Ｔ）
・変数ｘ_{ｄ，ｈ，ｋ}：ｄ日目ｈ編成でｋ回目の清掃を実施するか否かの０又は１の変数。
・変数 y_ｄ，t：ｄ日目に種類tの清掃を実施する回数を表す変数。
・定数Ｐ：目標周期の日数（Ｄ／Ｋにより計算しても良い）
・定数Ｃ_ｄ，ｔ：ｄ日目の種類ｔの最大清掃実施回数
・kind(h,k) ：ｈ編成のｋ回目の作業の種類を表す。
・ＦｉｘＳＥＴ：清掃が予め設定された（日，編成）の集合
・ＵｐｐｅｒＳＥＴ：上位検査が予め設定された（日，編成）の集合
・ＮＧＳＥＴ：他の作業が予め設定されているために清掃を実施できない（日，編成）の集合
・ＴａｂｕＬｉｓｔ：ＴａｂｕＬｉｓｔに登録されている、清掃を実施できない（日，編成）の集合

第１の実施形態との違いは、変数ｘの添え字がｄ日目ｈ編成を表す（ｄ，ｈ）ではなく、ｄ日目ｈ編成でｋ回目を表す（ｄ，ｈ，ｋ）となっている点である。

式（１２）は目標周期Ｐからのずれの総和の最小化を表す目的関数を表す。なぜなら、

は、ｈ編成のｋ－１回目の実施日からｋ回目の実施日までの経過日数を表し、

により経過日数と目標周期とのずれが表されるからである。

なお, ｋ＝１の場合

は便宜上、最終実施日と１回目の実施日との間隔を表すものとする。

式（１３ａ）及び式（１３ｂ）は、１日のキャパシティ制約条件を表す。なお作業員が休日であり、清掃を実施できない日に関してはＣ_ｄ，ｔを0とすればよい。また、ここでは清掃の種類ごとにキャパシティを超えないようにする制約式を用いたが、前述したように、たとえば「大清掃、小清掃のキャパシティはそれぞれ１であるが、大清掃の方が小清掃よりも作業量が多いことから、１日に小清掃のみを２回実施することも可能であるとする」ことを許容することも可能である。この場合、例えば、小清掃をt=1,大清掃をt=2と定義し式（１３ｂ）の代わりに、以下の式（１３ｃ）及び式（１３ｄ）を採用すればよい。

式（１３c）は、d日目の大清掃の変数とd日目の小清掃の変数との合計が２以下であることを表している。式（１３ｄ）はd日目の大清掃の変数が1以下であることを表している。これらの不等式の組み合わせにより、結果的に上記の「大清掃、小清掃のキャパシティはそれぞれ１であるが、大清掃の方が小清掃よりも作業量が多いことから、１日に小清掃のみを２回実施することも可能である」とのキャパシティ条件を表すことができている。このキャパシティ条件は、１日あたりに実施可能な複数の種類の清掃の回数の組み合わせに関する制約を表している。

式（１４）と式（１５）とは合わせて、１回目～Ｋ回目の清掃が順序どおり実行されることを表す。

式（１６）～式（１８）は、変数が第１の実施形態と異なる点を除き、第１の実施形態の場合と同様の制約である。

目標周期に関しては、周期の目標値そのものを与えるのではなく、計画期間の長さとその間の計画対象作業（清掃）の実施回数に基づき、「計画期間の長さ÷計画対象作業の実施回数」として算出してもよい。例えば、計画期間の長さが３０日で、計画対象作業の実施回数が４の場合には、目標周期は３０／４＝７．５（日）となる。

図１７は、図１６のテーブルに示される制約条件に基づき作業計画最適化部２４０により作成された清掃計画の一例を示す。「大」は大清掃、「小」は小清掃を表す。各編成は、大清掃→小清掃→大清掃→小清掃→の順に実施されている。また各編成の清掃間隔は必ず５日以内というわけではないが、５日に近くなっている。また、各日の小清掃と大清掃の合計回数は4/11を除きそれぞれ高々１回であり、4/11は小清掃が2回である。これは「大清掃、小清掃のキャパシティはそれぞれ１であるが、大清掃の方が小清掃よりも作業量が多いことから、１日に小清掃のみを２回実施することも可能である」とする、式（１３ｃ）及び（１３ｄ）のキャパシティ条件を満たしている。

本実施形態では清掃の種類別にキャパシティ値を設けたが、清掃の種類は１つであってもよい。この場合、第１の実施形態と同様にキャパシティ値を設定すればよい。

本実施形態によれば、１日（単位期間）に実施可能な作業の回数の制約を作業の種類ごとに定めることで、種類ごとの実施能力を考慮して、作業計画を作成することができる。また、編成ごとに作業の種類の実施順序が決められている場合も、当該実施順序を満たす作業計画を作成することができる。また、編成ごとに目標周期の制約条件を定めることで、作業間隔ができるだけ目標周期に近づけるように各編成の作業計画を作成することができる。このように編成ごとの個別の制約を考慮して作業計画を作成することができる。

（その他の実施形態）
第１及び第２の実施形態では、計画対象作業は１種類であったが、同時に複数種類の計画対象作業について作業計画を作成してもよい。この場合、１種類ずつ作業計画を作成してもよいし、複数種類同時に作業計画を作成してもよい。同時に作業計画を作成する場合、例えば式（４）～式（９）の定式化において、計画対象作業毎に、変数と制約式を導入すればよい。目的関数は、それぞれの計画対象作業の実施回数の和（もしくは重み和）により定義すればよい。

また、第１及び第２の実施形態では、作業計画を全て０から作成することを前提としたが、既存の計画（人手もしくは何らかのシステムにより作った暫定計画、もしくは周期に従って単に作業を割り当てた計画）に対し、計画対象作業の割り当てを微調整するものであってもよい。例えば、既存の計画を仮計画として与え、以降、第１又は第２の実施形態と同様の処理を行う。この場合、目的関数である式（４）もしくは式（１２）において、総実施回数だけでなく、元の計画からの乖離度（例えば、総実施回数の差）も目的関数に含めてもよい。あるいは、乖離度を表す評価関数を別に定義し、評価関数と目的関数の重み和を最小化してもよい。

上記の既存の計画において、計画対象作業の間隔が周期に比べて十分に狭い場合（例えば周期が５日であり、計画対象作業の間隔が２日であるような場合など）、計画対象作業を時間的に後ろ方向にずらすことにより、結果的に総実施回数を減らすような計画を作成することができる。具体的には、このような計画は、既存の計画で割り当てられている計画対象作業を時間方向に後ろにずらせるか否かを判定し、可能なら当該作業を１日ずつ後ろに下げていくことを逐次的に繰り返す単純な処理によって実現することができる。

（ハードウェア構成）
図１８に、本実施形態に係る作業計画作成装置（情報処理装置）１０１のハードウェア構成を示す。本実施形態に係る情報処理装置１０１は、コンピュータ装置１７０により構成される。コンピュータ装置１７０は、ＣＰＵ１５１と、入力インタフェース１５２と、表示装置１５３と、通信装置１５４と、主記憶装置１５５と、外部記憶装置１５６とを備え、これらはバス１５７により相互に接続されている。

ＣＰＵ（中央演算装置）１５１は、主記憶装置１５５上で、情報処理装置１０１の上述の各機能構成を実現するコンピュータプログラムを実行する。ＣＰＵ１５１が、コンピュータプログラムを実行することにより、各機能構成は実現される。

入力インタフェース１５２は、キーボード、マウス、及びタッチパネルなどの入力装置からの操作信号を、情報処理装置１０１に入力するための回路である。入力部１００の入力機能を担う部分は、入力インタフェース１５２上に構築されることができる。

表示装置１５３は、情報処理装置１０１から出力されるデータ又は情報を表示する。表示装置１５３は、例えば、ＬＣＤ（液晶ディスプレイ）、ＣＲＴ（ブラウン管）、及びＰＤＰ（プラズマディスプレイ）であるが、これに限られない。コンピュータ装置１７０から出力されたデータ又は情報は、この表示装置１５３により表示することができる。出力部５００は、表示装置１５３上に構築されることができる。

通信装置１５４は、情報処理装置１０１が外部装置と無線又は有線で通信するための回路である。通信装置１５４を介して外部装置から情報を入力することができる。外部装置から入力した情報を、ＤＢに格納することができる。入力部１００の通信機能を担う部分は、通信装置１５４上に構築されることができる。

主記憶装置１５５は、本実施形態の処理を実現するプログラム、及びプログラムの実行に必要なデータ、及びプログラムの実行により生成されたデータなどを記憶する。プログラムは、主記憶装置１５５上で展開され、実行される。主記憶装置１５５は、例えば、ＲＡＭ、ＤＲＡＭ、ＳＲＡＭであるが、これに限られない。各実施形態における各種ＤＢ及び記憶部は、主記憶装置１５５上に構築されてもよい。

外部記憶装置１５６は、上記プログラム及びプログラムの実行に必要なデータ、及びプログラムの実行により生成されたデータなどを記憶する。これらのプログラムやデータは、本実施形態の処理の際に主記憶装置１５５に読み出される。外部記憶装置１５６は、例えば、ハードディスク、光ディスク、フラッシュメモリ、及び磁気テープであるが、これに限られない。各実施形態における各種ＤＢ及び記憶部は、外部記憶装置１５６上に構築されてもよい。

なお、上述のプログラムは、コンピュータ装置１７０に予めインストールされていてもよいし、ＣＤ－ＲＯＭなどの記憶媒体に記憶されていてもよい。また、当該プログラムは、インターネット上にアップロードされていてもよい。

なお、コンピュータ装置１７０は、プロセッサ１５１、入力インタフェース１５２、表示装置１５３、通信装置１５４、及び主記憶装置１５５を、それぞれ１つ又は複数備えてもよいし、プリンタやスキャナなどの周辺機器を接続されていてもよい。

また、情報処理装置１０１は、単一のコンピュータ装置１７０により構成されてもよいし、相互に接続された複数のコンピュータ装置１７０からなるシステムとして構成されてもよい。

なお、本発明は上記各実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記各実施形態に開示されている複数の構成要素を適宜組み合わせることによって種々の発明を形成できる。また例えば、各実施形態に示される全構成要素からいくつかの構成要素を削除した構成も考えられる。さらに、異なる実施形態に記載した構成要素を適宜組み合わせてもよい。

１０１：作業計画作成装置
１００：入力部
２００：作業計画作成部
５００：出力部
３００：計画条件ＤＢ
３１０：キャパシティ情報ＤＢ
３２０：周期情報ＤＢ
３３０：上位作業情報ＤＢ
３４０：予定作業情報ＤＢ
３５０：運行情報ＤＢ
４１０：失敗情報ＤＢ
４２０：仮計画ＤＢ
４３０：出力作業計画ＤＢ
１１０：計画条件入力部
１２０：キャパシティ情報入力部
１３０：周期情報入力部
１４０：上位作業情報入力部
１５０：予定作業情報入力部
１６０：運行情報入力部
２１０：キャパシティ制約条件生成部
２２０：周期制約条件生成部
２３０：ＮＧ日制約条件生成部２３０
２４０：作業計画最適化部
２５０：運行充当処理部
１５１：プロセッサ（ＣＰＵ）
１５２：入力インタフェース
１５３：表示装置
１５４：通信装置
１５５：主記憶装置
１５６：外部記憶装置
１５７：バス
１６０：コンピュータ装置

Claims (19)

1. 作業計画の作成期間内の各単位期間について複数の作業対象に作業を割り当てるか否かを表す複数の変数を用いて前記作業計画の作成期間内の各単位期間について複数の作業対象に行われる作業回数の合計を計算する項を含む目的関数を生成し、
   前記複数の変数を含む、前記単位期間あたりに実施可能な作業の回数に関する第１制約条件と、前記複数の変数を含む、前記作業対象に対する作業間の期間の長さに関する第２制約条件とに基づき、前記目的関数を最小化又は準最小化することにより、前記複数の変数の値を決定し、前記複数の変数の値に基づいて前記作業対象の作業計画を作成する、作業計画作成部
   を備えた情報処理装置。
2. 作業計画の作成期間内の各単位期間について複数の作業対象に作業を割り当てるか否かを表す複数の変数を用いて、前記作業計画の作成期間内において複数の作業対象について前記作業を前回行ってから次に前記作業を行うまでの期間長と前記作業の目標周期との差分の合計を表す項を含む目的関数を生成し、
   前記複数の変数を含む、前記単位期間あたりに実施可能な作業の回数に関する第１制約条件と、前記複数の変数を含む、前記作業対象に対する作業間の期間の長さに関する第２制約条件とに基づき、前記目的関数を最小化又は準最小化することにより、前記複数の変数の値を決定し、前記複数の変数の値に基づいて前記作業対象の作業計画を作成する、作業計画作成部
   を備えた情報処理装置。
3. 前記作業には複数の種類が存在し、
   前記作業計画作成部は、前記作業対象ごとの前記複数の種類の作業の実施順序に関する第３制約条件に基づき、前記目的関数を最小化又は準最小化する
   請求項１又は２に記載の情報処理装置。
4. 前記作業計画作成部は、前記作業計画の作成期間の長さを前記作業対象に対して行うべき作業の実施回数で除算することにより、前記目標周期を算出する
   請求項２に記載の情報処理装置。
5. 前記作業には複数の種類が存在し、
   前記作業の種類ごとに前記変数を定義し、
   前記作業の種類ごとに前記第１制約条件と前記第２制約条件を定義し、
   前記目的関数は、前記作業の種類ごとの前記合計を総和する項を含む関数である
   請求項１又は２に記載の情報処理装置。
6. 前記作業計画作成部は、前記作業対象に前記作業を包含する作業である上位作業を行う予定日を含む第１情報に基づき、前記上位作業の実施は前記作業の実施と見なして、前記上位作業を実施する作業対象には前記予定日に前記作業を割り当てる
   請求項１～５のいずれか一項に記載の情報処理装置。
7. 前記作業計画作成部は、前記作業対象に前記作業を行う予定日を含む第２情報に基づき、前記予定日に前記作業対象に前記作業を割り当てることを示す第４制約条件を生成し、前記第４制約条件に基づき、前記作業計画を作成する
   請求項１～６のいずれか一項に記載の情報処理装置。
8. 前記作業計画作成部は、前記作業対象に前記作業とは異なる別の作業を行う予定日を含む第３情報に基づき、前記予定日に前記作業を割り当てないことを示す第５制約条件を生成し、前記第５制約条件に基づいて、前記作業計画を作成する
   請求項１～７のいずれか一項に記載の情報処理装置。
9. 前記第２制約条件は、前記作業間の期間の長さを上限値以下にすることを含む
   請求項１～８のいずれか一項に記載の情報処理装置。
10. 前記複数の作業対象に作業が行われる場所を示す情報と、
    前記単位期間において前記複数の作業対象に作業が行われる時間範囲を示す情報と、
    出発場所と出発時刻と到着場所と到着時刻とを含み、前記出発時刻から前記到着時刻までの運行時間を有する複数の運行の情報と、に基づき、
    複数の運行のそれぞれを前記複数の作業対象のいずれか１つに割り当てる運行充当処理を行う運行充当処理部と、を備え、
    前記運行充当処理部は、
    前記運行を前記運行時間が作業対象の作業が行われる時間範囲に重ならず、かつ、前記出発場所及び前記到着場所が前記作業対象の作業が行われる場所に一致する場合に前記作業対象に割り当てことができるとの制約に基づき、前記運行充当処理を行い、
    各前記単位期間においていずれの作業対象にも割り当てることができない運行が存在する場合に、各前記単位期間においていずれの運行も割り当てられていない作業対象を特定し、
    前記作業対象が特定された前記単位期間において前記特定された作業対象に作業を割り当てないとの制約と、前記第１制約条件及び前記第２制約条件とに基づき、各単位期間に前記複数の作業対象に作業を行うか否かを示した前記作業計画を再作成し、
    前記運行充当処理と前記作業計画を作成する処理とを再帰的に繰り返す
    請求項１～９のいずれか一項に記載の情報処理装置。
11. 前記第１制約条件は、前記単位期間あたりに実施可能な作業の回数に関する制約を、前記作業の実施場所、前記作業の種類、又は前記実施場所と前記作業の種類との組み合わせごとに含む
    請求項１～１０のいずれか一項に記載の情報処理装置。
12. 前記作業には複数の種類が存在し、
    前記第１制約条件は、前記単位期間あたりに実施可能な前記複数の種類の作業の回数の組み合わせを含む
    請求項１～１０のいずれか一項に記載の情報処理装置。
13. 前記単位期間は１日である
    請求項１～１２のいずれか一項に記載の情報処理装置。
14. 前記作業計画を表示する出力部
    を備えた請求項１～１３のいずれか一項に記載の情報処理装置。
15. 前記作業対象は、移動体である
    請求項１～１４のいずれか一項に記載の情報処理装置。
16. 作業計画の作成期間内の各単位期間について複数の作業対象に作業を割り当てるか否かを表す複数の変数を用いて前記作業計画の作成期間内の各単位期間について複数の作業対象に行われる作業回数の合計を計算する項を含む目的関数を生成し、
    前記複数の変数を含む、前記単位期間あたりに実施可能な作業の回数に関する第１制約条件と、前記複数の変数を含む、前記作業対象に対する作業間の期間の長さに関する第２制約条件とに基づき、前記目的関数を最小化又は準最小化することにより、前記複数の変数の値を決定し、前記複数の変数の値に基づいて前記作業対象の作業計画を作成する、
    コンピュータが実行する情報処理方法。
17. 作業計画の作成期間内の各単位期間について複数の作業対象に作業を割り当てるか否かを表す複数の変数を用いて、前記作業計画の作成期間内において複数の作業対象について前記作業を前回行ってから次に前記作業を行うまでの期間長と前記作業の目標周期との差分の合計を表す項を含む目的関数を生成し、
    前記複数の変数を含む、前記単位期間あたりに実施可能な作業の回数に関する第１制約条件と、前記複数の変数を含む、前記作業対象に対する作業間の期間の長さに関する第２制約条件とに基づき、前記目的関数を最小化又は準最小化することにより、前記複数の変数の値を決定し、前記複数の変数の値に基づいて前記作業対象の作業計画を作成する、
    コンピュータが実行する情報処理方法。
18. 作業計画の作成期間内の各単位期間について複数の作業対象に作業を割り当てるか否かを表す複数の変数を用いて前記作業計画の作成期間内の各単位期間について複数の作業対象に行われる作業回数の合計を計算する項を含む目的関数を生成するステップと、
    前記複数の変数を含む、前記単位期間あたりに実施可能な作業の回数に関する第１制約条件と、前記複数の変数を含む、前記作業対象に対する作業間の期間の長さに関する第２制約条件とに基づき、前記目的関数を最小化又は準最小化することにより、前記複数の変数の値を決定し、前記複数の変数の値に基づいて前記作業対象の作業計画を作成するステップと、
    をコンピュータに実行させるためのコンピュータプログラム。
19. 作業計画の作成期間内の各単位期間について複数の作業対象に作業を割り当てるか否かを表す複数の変数を用いて、前記作業計画の作成期間内において複数の作業対象について前記作業を前回行ってから次に前記作業を行うまでの期間長と前記作業の目標周期との差分の合計を表す項を含む目的関数を生成するステップと、
    前記複数の変数を含む、前記単位期間あたりに実施可能な作業の回数に関する第１制約条件と、前記複数の変数を含む、前記作業対象に対する作業間の期間の長さに関する第２制約条件とに基づき、前記目的関数を最小化又は準最小化することにより、前記複数の変数の値を決定し、前記複数の変数の値に基づいて前記作業対象の作業計画を作成するステップと、
    をコンピュータに実行させるためのコンピュータプログラム。

Images