JP6674875B2 - 計画作成装置および計画作成方法 - Google Patents

Description

本発明は、計画作成装置および計画作成方法に関するものであり、具体的には、所定時間内に計画作成者の意図に沿った好適な計画作成を可能とする技術に関する。

輸送サービス業や製造業などの分野では、一日に実施する作業手順を示した計画に則り、日々の業務が行われている。そのため、こうした計画の有効性や精度が、そのまま当該業務の質に直結する傾向にある。従って、計画作成に際しては、様々な観点から入念に検討を行うことが理想である。

しかし実際の業務では、そのような検討に割ける時間が限られる場合も多い。たとえば鉄道事業において、車両故障等の輸送障害に伴うサービス停止状態に対処し、迅速なサービス再開を図るためには、限られた時間の中で乱れた運行計画の再計画（運転整理）や鉄道車両や乗務員の運用再計画（運用整理）を完了する必要がある。加えて、サービス再開以降の業務の非効率化を未然に防ぐことも考慮に入れて、これらを計画する必要がある。

そこで、上述の運転整理や運用整理の計画作成業務は、知識と経験が豊富な熟練者が担当することが一般的であった。しかし熟練者であっても、計画対象が複雑な事象であれば、計画作成に時間がかかる状況は依然として改善できていない。

この状況を背景として、所定時間内に質の良い計画を作成することを目的とした、計画作成技術に関する研究開発が進んでいる。

このような技術としては、例えば、乗物の運行ダイヤに基づいて運行機材又は乗務員の運用計画を作成する運用計画作成装置において、計画の作成手段を複数有する作成手段格納部と、前記各作成手段に対する特徴情報を格納する作成手段特徴格納部と、計画作成にかかる許容時間を格納する許容時間格納部と、計画作成開始からの経過時間を取得する経過時間取得部と、前記運行機材又は乗務員の割り当て状況、前記特徴情報、前記許容時間、及び、計画作成途中における前記経過時間に基づいて、前記複数の作成手段の中から前記許容時間内に計画作成できる最適な作成手段を計画作成途中で逐次選択する作成手段選択部とを備えたことを特徴とする運行機材又は乗務員の運用計画作成装置（特許文献１参照）などが提案されている。

特開２０１２−１４８７４２号公報

一般的な計画作成技術では、実行可能な計画の構成要素を解候補として、無数にある解候補の組合せの中から可能な限り良い組合せ（解）を探索する、数理的な計画作成手段を用いるケースが多い。こうした従来技術において、様々な計画作成手段を許容時間に応じて暗黙的に切り替えるとした場合、探索時間にぶれが生じれば、探索のある時点において用いられる計画作成手段が不明になる。

このため、最終的にどのような解（計画）が得られるか、計画作成者は事前に把握できない。その結果、計画作成者の望まない解が生成されるという問題点があった。また、こ
うした技術によって同じ問題を解いたとしても、同じ探索手段を同じ時点で適用する保証がなく、再現性がない解となる。その場合、計画作成者による解の検証が困難になり、解の妥当性や信頼性が損なわれる恐れがあった。

そこで本発明の目的は、所定時間内に計画作成者の意図に沿った好適な計画作成を可能とする技術を提供することにある。

上記課題を解決する本発明の計画作成装置は、所定計画の作成に要する演算時間を推定する演算時間推定部と、前記推定した演算時間を所定装置に出力し、当該計画の作成における解空間を限定する求解条件をユーザから受け付けるに際し、所定の求解条件格納部に格納した、前記計画の対象となる所定問題に応じた求解条件の内容と当該求解条件を示す数式を含む求解条件を、所定装置にて出力すると共に、当該出力した求解条件のうち当該計画の作成に適用する又は適用除外する求解条件の指定を、所定のインターフェイスを介して個別または一括で受け付ける求解条件設定部と、前記求解条件にて当該計画の作成を行う計画作成部とを備え、前記演算時間推定部が、前記求解条件設定部で求解条件を受け付けた場合に、当該求解条件に基づき演算時間を再度推定し、前記再度の推定に際し、前記出力した求解条件のうち前記指定を受けた求解条件を適用した場合の、前記演算時間の削減効果を算定し、当該削減効果の情報を所定装置に出力し、前記求解条件設定部が、前記演算時間推定部が再度推定した演算時間を、所定装置に出力するものである、ことを特徴とする。

また、本発明の計画作成方法は、情報処理装置が、所定計画の作成に要する演算時間を推定する演算時間推定処理と、前記推定した演算時間を所定装置に出力し、当該計画の作成における解空間を限定する求解条件をユーザから受け付けるに際し、所定の求解条件格納部に格納した、前記計画の対象となる所定問題に応じた求解条件の内容と当該求解条件を示す数式を含む求解条件を、所定装置にて出力すると共に、当該出力した求解条件のうち当該計画の作成に適用する又は適用除外する求解条件の指定を、所定のインターフェイスを介して個別または一括で受け付ける求解条件設定処理と、前記求解条件にて当該計画の作成を行う計画作成処理とを実行し、前記演算時間推定処理にて、前記求解条件設定処理で求解条件を受け付けた場合に、当該求解条件に基づき演算時間を再度推定し、前記再度の推定に際し、前記出力した求解条件のうち前記指定を受けた求解条件を適用した場合の、前記演算時間の削減効果を算定し、当該削減効果の情報を所定装置に出力し、前記求解条件設定処理にて、前記演算時間推定処理で再度推定した演算時間を、所定装置に出力する、ことを特徴とする。

本発明によれば、所定時間内に計画作成者の意図に沿った好適な計画作成が可能となる。

本実施形態における列車の運行計画と乗務員の行路の例を示す図である。 本実施形態における計画作成装置の構成例を示す図である。 本実施形態における計画作成装置のハードウェア構成例を示す図である。 本実施形態における計画作成方法のフロー例１を示す図である。 本実施形態の求解条件格納部に格納された求解条件情報例を示す図である。 本実施形態の求解条件設定部として実現される求解条件設定画面例を示す図である。 本実施形態における計画作成方法のフロー例２を示す図である。

−−−計画対象の例について−−−

以下に本発明の実施形態について図面を用いて詳細に説明する。ここで、本実施形態において計画作成の対象となる事例として、鉄道乗務員運用計画の例について説明する。

当該鉄道乗務員運用計画とは、列車の運行ダイヤ上の各乗務に対して一人以上の乗務員を割当てたスケジュールであって、いわゆる乗務員の運用スケジュールである。

ここで、「乗務」とは、乗務の開始時刻、開始場所、終了時刻、終了場所の組合せからなる作業の単位である。また、「行路」とは、一人の乗務員の勤務を構成する一連の乗務の集合のことである。各行路を担当する乗務員は、勤務時間の上限や乗務時間の上限など
の様々な制約条件を満たしつつ、担当行路の各乗務を遂行する必要がある。

ここで上述した「乗務」と「行路」の具体的な関係について運行ダイヤを踏まえて説明する。図１は、本実施形態における列車の運行ダイヤと乗務員の行路の例を示す図である。図１の例において、各斜線２１は乗務を表しており、各太線２２は行路を表している。鉄道事業者の所定担当者あるいは所定システム等は、図１に示す様な一連の行程で構成される行路を多数生成し、すべての乗務が被覆されるように行路を選択することとなる。ここで、行程が乗務に「被覆される」とは、その乗務に行路（あるいはそれに対応する乗務員）が割り当たっていることを意味する。

鉄道乗務員運用計画の自動作成方法は二段階に分かれており、まず、第一段階として、制約条件を満たす行路を解候補として多数列挙する。次に、第二段階として、列挙した解候補の中から、評価値を最適化し、全ての乗務が選択した解候補のいずれかに割当たるように、無数にある解候補の組合せから一つの組合せを選択して運用計画を作成する。

上述の制約条件を満たす解候補を列挙する方法として、バックトラック法や列生成法などの公知の方法が知られている。また、解候補の組合せを選択する方法についても、分枝限定法や貪欲法などの公知の方法が知られている。

以降では、「問題」とは無数にある解候補の組合せから一つの組合せを選択し、計画を作成する問題とし、また選択された解候補の組合せを「解」とする。また、「計画作成手段」とは上述のような公知の方法を指し、「演算時間」とは、単一の計画作成手段によって、対象とする問題の解（計画）を取得するまでにかかる時間のことを指す。

上述した計画作成手段は、演算時間は長いが良い評価値（例：総残業時間が最小など）を持つ解が得られる方法、演算時間は短いが相応の質の解しか得られない方法など、方法に応じて様々な特徴を持つ。例えば、計画作成手段のうち分枝限定法は、二分木構造状に問題を分割しながら演算することで、全ての組合せの中から最適な組合せを選ぶ方法であり、問題規模が大きくなると指数的に演算時間が増加する。一方、貪欲法は、行路候補に順位をつけ、順位の高い行路候補から採用していく方法であり、演算時間は短いが、相応の評価値をもつ解しか得られない。仮に良い評価値の解が得られたとしても、個々の行路について見ると、一人の乗務員に負担が集中しているなど、実際の運用にそぐわない結果となる場合もある。

鉄道乗務員運用計画のような計画を自動作成する際、可能な限り速く問題を解き、かつ計画作成者の意図に沿う解を得ることが望ましい。ところが、上述の様な様々な計画作成手段を用いて所定時間内に解を得ても、計画作成者の意図しない解を生成する可能性があると、その解を改めて検討する必要が生じる。すると結果的に計画作成に時間がかかってしまう。そこで本実施形態の計画作成方法においては、計画作成者との対話的な操作によって、求める解に望む条件（求解条件）を事前に定めることで、問題を解く前に実質的な問題規模を縮小した上で、計画作成手段を変更することなく所定時間内に計画作成者の意図を反映した解を得る。
−−−計画作成装置の機能構成−−−

図２は、本実施形態における計画作成装置１００の機能構成を示す図である。前提として、当該計画作成装置１００は、対象とする問題から解を得るための単一の計画作成手段を有しているものとする。

計画作成装置１００は、計画情報格納部１に格納された計画情報を基に、特徴解析部２にて対象とする問題の演算時間に関わる解空間情報を生成する。また計画作成装置１００
は演算時間推定部３において、上述のように生成した解空間情報と演算時間算出式格納部４より取得した演算時間算出式情報とを用いて、対象とする問題の推定演算時間を推定する。

また計画作成装置１００は演算時間推定部３において、これらの情報と求解条件格納部５から取得した複数の求解条件とに基づいて、求解条件毎の演算時間削減効果を推定する。また計画作成装置１００は、求解条件設定部６において、計画作成者に上述の推定演算時間および求解条件毎の演算時間削減効果を提示し、当該計画作成者による求解条件の設定を受け付ける。

上述の求解条件の設定が終了し、計画作成者による計画作成指示を受け付けると、計画作成装置１００の求解条件設定部６は、適用求解条件格納部１１に現在の求解条件設定状況を格納した上で、それらの削減効果と上述の推定演算時間とから目標演算時間を算出し、これを計画作成部７に渡す。

計画作成装置１００は、計画作成部７において、上述の適用求解条件格納部１１に求解条件設定状況を適用した状態で、単一の計画作成手段を用いて演算を開始する。当該演算中は、適宜解空間の探索状況を探索状況格納部８に格納する。目標演算時間内に解が得られた場合、計画作成部７は、作成した計画を作成結果格納部９に格納し、解空間情報と演算時間の履歴情報を演算時間履歴情報格納部１０に格納する。他方、演算の途中で、目標演算時間に達した場合、計画作成部７は、演算を一時停止し、求解条件設定部６に対して再度条件を設定するよう指示を与える。

求解条件設定部６は、演算時間推定部３に現在の解探索状況と、求解条件の適用状況から残りの推定演算時間と求解条件毎の削減効果を取得し、再度計画作成者による求解条件の設定を受け付ける。

−−−計画作成装置のハードウェア構成−−−

図３は、本実施形態における計画作成装置１００のハードウェア構成例を示す図である。本実施形態の計画作成装置１００のハードウェア構成は以下の如くとなる。

当該計画作成装置１００は、ＳＳＤ（Ｓｏｌｉｄ Ｓｔａｔｅ Ｄｒｉｖｅ）やハードディスクドライブなど適宜な不揮発性記憶素子で構成される記憶装置１０１、ＲＡＭなど揮発性記憶素子で構成されるメモリ１０３、記憶装置１０１に保持されるプログラム１０２をメモリ１０３に読み出すなどして実行し装置自体の統括制御を行なうとともに各種判定、演算及び制御処理を行なうＣＰＵなどの演算装置１０４、ユーザからのキー入力や音声入力を受け付ける入力装置１０５、処理データの出力を行うディスプレイ等の出力装置１０６、を備える。

なお、記憶装置１０１内には、本実施形態の計画作成装置１００として必要な機能を実装する為のプログラム１０２に加えて、上述の計画情報格納部１、演算時間算出式格納部４、求解条件格納部５、探索状況格納部８、作成結果格納部９、演算時間履歴情報格納部１０、および、適用求解条件格納部１１、を構成する各情報が少なくとも記憶されている。
−−−フロー例１−−−

以下、本実施形態における計画作成方法の実際手順について図に基づき説明する。以下で説明する計画作成方法に対応する各種動作は、計画作成装置１００がメモリ等に読み出して実行するプログラムによって実現される。そして、このプログラムは、以下に説明さ
れる各種の動作を行うためのコードから構成されている。

図４は、本実施形態における計画作成方法のフロー例１を示す図である。具体的には、図４に示すフローは計画作成装置１００における基本的な動作手順を示すフローである。以下、当該フローが示す本動作手順について、図１で例示した鉄道乗務員運用計画の例を適宜用いつつ説明する。

まず、計画作成装置１００の特徴解析部２は、計画情報格納部１から計画情報として運行ダイヤを読み込む（Ｓ１）。

次に、計画作成装置１００の特徴解析部２は、上述のＳ１で読み込んだ運行ダイヤから、対象とする問題の多数の解候補を生成し、解空間情報を生成する（Ｓ２）。ここで、解空間情報とは、対象とする問題の解候補に関する情報を指す。例えば、鉄道乗務員運用計画では、解候補は行路候補に相当する。そのため解空間情報は、生成された行路候補の集合としての情報（全行路候補数や全乗務員数、全乗務数など）と、各行路の詳細情報（識別子や被覆している一連の乗務、残業時間、行路開始点、行路終了点など）とによって構成する。また、ステップＳ２において、特徴解析部２は、生成した全ての解候補を、演算時間推定部３における推定対象とするため、対象解候補集合として記憶装置１０１で保持する。

次に、計画作成装置１００の演算時間推定部３は、求解条件格納部５より、求解条件を取得する（Ｓ３）。当該求解条件とは、計画作成手段を用いて、対象とする問題の解を求める際に、得られる解が満たす条件を指す。こうした求解条件の詳細を図５に示す。

図５は、鉄道乗務員運用計画を対象とした場合における求解条件格納部５の例である。求解条件格納部５に格納された一つの求解条件情報は、求解条件ＩＤ５１、条件内容５２、求解条件５３、パターン番号５４の一レコードで定義される。

求解条件ＩＤ５１は、求解条件情報を区別するための識別子である。また条件内容５２は、求解条件情報の条件内容を説明した記述である。また求解条件５３は、条件内容５２で示した説明と合致するよう、対象とする問題の解候補の情報、またはその組合せから導かれる情報を用いて定式化した条件式である。例えば、図５において、求解条件ＩＤが「１」の求解条件情報について、「残業時間を３時間以下に設定する」という条件内容を実現するため、「行路候補（解候補）のうち残業時間が３時間を超えない行路候補に限定する」という意の条件式を求解条件として設定している。

また、パターン番号５４は、求解条件設定部６において求解条件を一括で適用設定するための識別子である。例えば、図５においてパターン番号「１」が計画作成者から指定されると、求解条件ＩＤが１，２，４である求解条件情報が一括で適用状態に設定される。

本実施形態において、上述の要素から構成される求解条件情報は、求める解に対して計画作成者が望む条件であり、計画作成手段に与える解候補を事前に削減するための条件である。このような求解条件情報は、対象とする問題のドメイン知識・ノウハウから事前に類推され、各解候補の情報またはその組合せから導かれる情報を用いた条件式として定式化できる新たに得たドメイン知識・ノウハウに基づいて、求解条件情報を編集、追加することも可能である。

続いて演算時間推定部３は、上述のＳ２で得ている対象解候補集合に対して、Ｓ３で得た求解条件の適用によって縮小する解候補集合（縮小解候補集合）と解空間情報を求解条件毎に生成する（Ｓ４）。

当該Ｓ４の処理には、特徴解析部２で生成した解空間情報を利用する。例えば、鉄道乗務員運用計画では、「行路開始点と行路終了点を一致させる」という求解条件を適用する場合、解空間情報に含まれる行路候補の情報に基づき、行路開始点と行路終了点が一致しない行路候補を対象解候補集合から除外できる。このような行路候補を全て除外した結果として、縮小解候補集合が得られる。

上述の求解条件毎の縮小解候補集合が得られると、演算時間推定部３は、演算時間算出式格納部４から演算時間算出式情報を取得し、当該演算時間算出式情報に対象解候補集合の解空間情報を当てはめることで、対象とする問題に対する推定演算時間を算出する（Ｓ５）。ここで、演算時間算出式情報は、推定演算時間を目的変数、解空間情報の所定要素を説明変数として表される関係式のことを指す。当該演算時間算出式情報の詳細は、図７に基づき後述する。

次に、演算時間推定部３は、上述の演算時間算出式情報に、Ｓ４で生成した縮小解候補集合の解空間情報を当てはめることで、Ｓ５のステップと同様に、各求解条件を適用した場合の推定演算時間を算出する（Ｓ６）。当該ステップＳ６における演算時間推定部３は、さらに、各求解条件を対象の問題に適用した場合の削減効果として、当該ステップＳ６で算出した推定演算時間と、上述のステップＳ５で得た（求解条件を適用しない場合の）推定演算時間との差分を算出する。

求解条件設定部６は、上述のステップＳ６までに求めた推定演算時間と削減効果を、出力装置１０６における画面やファイルなどに出力し、適用すべき求解条件に関する計画作成者の選択を、個別または一括で入力装置１０５で受け付ける（Ｓ７）。

例えば、鉄道乗務員運用計画において、「行路開始点と行路終了点を一致させる」という求解条件に関する削減効果が１０分と出力されている場合、この求解条件の適用により演算時間を１０分削減可能と推定していることを意味している。本実施形態の計画作成装置１００は、計画作成者にこのような情報を提示することで、計画作成者の望む条件と演算時間に基づく計画の作成を支援する。こうした求解条件設定部６による出力例（求解条件設定画面６１）を図６に示す。

図６は、求解条件設定部６で計画作成者に推定演算時間と各求解条件の削減効果、またその組合せによる総削減効果を提示しつつ、計画作成者から求解条件の選択を受け付け、探索開始の指示を受け付ける求解条件設定画面６１の例である。

本実施形態における求解条件設定画面６１は、探索開始ボタン６２、キャンセルボタン６３、計画対象問題表示部６４、推定演算時間表示部６５、総削減効果表示部６６、求解条件一括設定部６７、求解条件適用選択部６８、求解条件ＩＤ表示部６９、条件内容表示・入力受付部７０、および個別削減効果表示部７１、で構成される。

このうち探索開始ボタン６２は、計画作成者が求解条件の設定を終了して計画作成開始を指示するためのボタンである。また、キャンセルボタン６３は、計画作成者が計画作成のキャンセルを指示するボタンである。

また、計画対象問題表示部６４は、計画作成の対象となっている問題名称を出力する表示部である。また、推定演算時間表示部６５は、上述のステップＳ５で算出された求解条件未適用時の推定演算時間を出力する表示部である。また、総削減効果表示部６６は、計画作成によって選択された求解条件をもとに、後述するステップＳ９で算出される総削減効果を出力する表示部である。

また、求解条件一括設定部６７は、求解条件情報に設定されたパターン番号５４（図５）に基づき、求解条件を一括で適用設定する設定部である。また、求解条件適用選択部６８は、対応する求解条件を計画作成時に適用するか否かを計画作成者から受け付けるインターフェイスである。また、求解条件ＩＤ表示部６９は、対応する求解条件の識別子を出力する表示部である。また、条件内容表示・入力受付部７０は、対応する求解条件の内容説明を出力し、また計画作成者による求解条件への値設定を受け付けるインターフェイスである。また、個別削減効果表示部７１は、対応する求解条件を適用した際に得られる、上述のステップＳ６で算出した削減効果を出力する表示部である。

なお、求解条件設定部６が計画作成者から選択を受け付ける求解条件としては、計画作成者による値指定が可能な求解条件も含まれるものとする。例えば、鉄道乗務員運用計画においては、「乗務員Ｘは必ず乗務Ｙを担当する」などの値指定が可能な求解条件が存在する。この条件例では、ＸとＹに計画作成者による値指定が可能となっている。計画作成者によって、そのような求解条件の適用が選択され、計画作成者による入力値を受け付けた場合、求解条件設定部６は、当該求解条件において当該入力値を反映した状態に更新し、例えば適用求解条件格納部１１で保持する（Ｓ８）。そして求解条件設定部６は、当該求解条件による削減効果を算出して出力するため、処理をＳ４へ戻す。

また、求解条件設定部６は、上述の計画作成者によって複数の求解条件が選択されている場合の総削減効果を、計画作成者が選択した求解条件に対応する縮小解候補集合の解空間情報に基づいて算出し、出力装置１０６に出力する（Ｓ９）。具体的には、計画作成者が選択した求解条件に対応する、それぞれの縮小解候補集合の共通部分をとることで、新たな縮小解候補集合と解空間情報を生成する。そして求解条件設定部６は、上述のステップＳ７と同様の処理によって、総削減効果を算出して出力装置１０６に出力する。

計画作成装置１００は、ユーザの計画作成指示を入力装置１０５にて受け付けるまでは（Ｓ１０：ｎ）、求解条件の選択を受け付ける。一方、計画作成指示を受けた場合（Ｓ１０：ｙ）、計画作成装置１００は求解条件の設定を終了し、Ｓ１１に処理を遷移させ、計画作成を開始する。

計画作成を開始する場合、求解条件設定部６は、求解条件の設定状況を適用求解条件格納部１１に格納する。また求解条件設定部６は、上述の求解条件を適用しない場合の推定演算時間と総削減効果の差分を目標演算時間として算出し、計画作成部７に渡す。

Ｓ１１において、計画作成装置１００の計画作成部７は、適用求解条件格納部１１に格納された求解条件の設定状況に基づいて、上述のステップＳ９と同様に、適用中の求解条件に共通する縮小解候補集合を生成する。そして当該Ｓ１１における計画作成部７は、この縮小解候補集合を対象に、当該計画作成装置１００が有する計画作成手段を用いて計画作成を開始する。計画作成部７は、当該計画作成の間、どの解候補まで探索を終了したかを探索状況として探索状況格納部８に適宜格納する。

次に、計画作成部７は、目標演算時間内に探索が終了したか判定し（Ｓ１２）、終了していない場合はＳ１３、終了している場合はＳ１４を実行する。

目標演算時間内に探索が終了していない場合（Ｓ１２：ｎ）、計画作成部７は、計画作成を一時停止し、求解条件設定部６に対して再度求解条件を設定するよう指示を与え、Ｓ４に戻る。この場合の演算時間推定部３は、演算対象を残りの問題に絞るため、探索状況格納部８に格納された探索状況を基に、未探索の解候補集合を特定し、それを対象解候補集合として改めて設定する（Ｓ１３）。

他方、目標演算時間内に探索が終了している場合（Ｓ１２：ｙ）、計画作成部７は、得られた解を作成結果格納部９に格納し、上述のステップＳ１１で求めた縮小解空間情報と実際の演算時間を演算時間履歴情報として演算時間履歴情報格納部１０に格納し（Ｓ１４）、計画作成を終了する。
−−−フロー例２−−−

続いて、上述の演算時間推定部３における処理の詳細について説明する。図７は、本実施形態の演算時間推定部３において、所与の解候補集合を対象として演算時間を推定する処理の手順を示したフローである。

当該フローにおいて、演算時間推定部３は、指定された解候補集合の解空間情報を読み込み（Ｓ２１）、演算時間算出式格納部４から演算時間算出式情報を読み込む（Ｓ２２）。 ここで、演算時間算出式情報は、推定演算時間を目的変数、解空間情報の所定要素を説明変数として表される関係式のことを指す。この関係式は、演算時間履歴情報格納部１０に格納された過去の演算時間履歴情報をもとに事前に作成される。例えば、計画作成装置１００が、鉄道乗務員運用計画に関して、演算時間履歴情報格納部１０内の演算時間履歴情報（解空間情報とその演算時間）を重回帰分析にかけ、演算時間演算時間を目的変数、行路候補数や乗務数、乗務員数を説明変数とする重回帰式を予め作成し、演算時間算出式情報として演算時間算出式格納部４に格納する。また、計画作成装置１００は、演算時間履歴情報格納部１０の更新を契機に上述のような解析を都度行うことで、計画作成に先だって演算時間算出式情報を更新する。

次に、演算時間推定部３は、上述のＳ２１で得た解空間情報から、上述のＳ２２で得た演算時間算出式情報にて用いられる説明変数に対応する属性値を抽出する（Ｓ２３）。上述の例では、行路候補数や乗務数、乗務員数を説明変数とする重回帰式を演算時間算出式情報として利用するため、解空間情報から行路候補数や乗務数、乗務員数を抽出することとなる。

最後に、演算時間推定部３は、上述の演算時間算出式情報に、Ｓ２３で解空間情報より抽出した属性値を当てはめることで、指定の解候補集合に対する推定演算時間を算出する（Ｓ２４）。

なお本実施形態では鉄道の計画を例に説明したが、本発明の適用を鉄道に限るものではない。例えば、製造・販売分野を例にとると、臨時発注を受けた場合の生産計画の作成にも適用できる。また物流分野を例にとると、経路の混雑状況に応じた配送計画の作成にも適用できる。

以上、本発明を実施するための最良の形態などについて具体的に説明したが、本発明はこれに限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能である。

こうした本実施形態によれば、計画作成装置における演算時間推定部および求解条件設定部の機能により、選択された求解条件に従って計画を作成する場合の推定所要時間を計画作成者に逐次提示し、当該計画作成者との対話的処理を受けて求解条件を定めることが出来る。こうした処理によって実質的な問題規模を縮小し、計画作成手段を変えることなく所定時間内に計画作成者の意図を反映した計画を得ることができる。

すなわち、所定時間内に計画作成者の意図に沿った好適な計画作成が可能となる。

本明細書の記載により、少なくとも次のことが明らかにされる。すなわち、本実施形態
の計画作成装置において、前記求解条件設定部は、前記求解条件の受け付けに際し、所定の求解条件格納部に格納した求解条件を所定装置にて出力すると共に、当該出力した求解条件のうち当該計画の作成に適用する求解条件の指定を受け付けるものであり、前記演算時間推定部は、前記演算時間の再度の推定に際し、前記出力した求解条件のうち前記指定を受けた求解条件を適用した場合の、前記演算時間の削減効果を算定し、当該削減効果の情報を所定装置に出力するものである、としてもよい。

これによれば、計画作成者は求解条件の設定によって、どれほど演算時間を削減出来るのか認識することが可能となり、より削減効果の高い求解条件の設定も容易となる。ひいては、より短時間に計画作成者の意図に沿った好適な計画作成が可能となる。

本実施形態の計画作成装置において、前記求解条件格納部は、前記求解条件として、前記計画の対象となる所定問題に応じた求解条件の内容と当該求解条件を示す数式を格納しており、前記求解条件設定部は、前記求解条件の受け付けに際し、前記求解条件格納部に格納した求解条件として、前記求解条件の内容と当該求解条件を示す数式、を所定装置にて出力すると共に、当該出力した求解条件のうち当該計画の作成に適用する又は適用除外する求解条件の指定を、所定のインターフェイスを介して個別または一括で受け付けるものである、としてもよい。

これによれば、計画作成者は求解条件の内容についてより簡便かつ明確に認識し、より削減効果の高い求解条件の設定を随意に行うことが容易となる。ひいては、より短時間により計画作成者の意図に沿った好適な計画作成が可能となる。

本実施形態の計画作成装置において、前記計画作成部は、所定時間内に計画作成ができない場合、計画作成を一時停止し、前記演算時間推定部は、前記計画作成の一時停止に伴い、現在適用中の前記求解条件と前記計画作成部での計画作成の処理状況に基づき、計画作成完了までの残りの演算時間と前記求解条件毎の前記削減効果を再度算定して所定装置に出力し、前記求解条件設定部は、前記再度算定し出力した求解条件のうち当該計画の作成に適用する求解条件の指定を再度受け付けるものである、としてもよい。

これによれば、計画作成者は、計画作成装置での計画作成処理の状況に応じた臨機応変な求解条件の再設定を行えることとなり、演算時間を徒に増大させる事態を回避出来る。ひいては、より短時間に計画作成者の意図に沿った好適な計画作成が可能となる。

本実施形態の計画作成装置において、前記演算時間推定部は、前記計画の対象となる所定問題に関して、所定アルゴリズムにて演算時間に関わるパラメータ値を算出し、当該パラメータ値を所定の演算時間算出式に適用することで演算時間の推定を行うものである、としてもよい。

これによれば、演算時間の推定がより効率的かつ精度良く行えることとなり、ひいては、より短時間に計画作成者の意図に沿った好適な計画作成が可能となる。

また、本実施形態の計画作成方法において、前記情報処理装置が、前記求解条件設定処理において、前記求解条件の受け付けに際し、所定の求解条件格納部に格納した求解条件を所定装置にて出力すると共に、当該出力した求解条件のうち当該計画の作成に適用する求解条件の指定を受け付け、前記演算時間推定処理において、前記演算時間の再度の推定に際し、前記出力した求解条件のうち前記指定を受けた求解条件を適用した場合の、前記演算時間の削減効果を算定し、当該削減効果の情報を所定装置に出力する、としてもよい。

また、本実施形態の計画作成方法において、前記情報処理装置が、前記求解条件格納部において、前記求解条件として、前記計画の対象となる所定問題に応じた求解条件の内容と当該求解条件を示す数式を格納しており、前記求解条件設定処理において、前記求解条件の受け付けに際し、前記求解条件格納部に格納した求解条件として、前記求解条件の内容と当該求解条件を示す数式、を所定装置にて出力すると共に、当該出力した求解条件のうち当該計画の作成に適用する又は適用除外する求解条件の指定を、所定のインターフェイスを介して個別または一括で受け付ける、としてもよい。

また、本実施形態の計画作成方法において、前記情報処理装置が、前記計画作成処理において、所定時間内に計画作成ができない場合、計画作成を一時停止し、前記演算時間推定処理において、前記計画作成の一時停止に伴い、現在適用中の前記求解条件と前記計画作成処理での計画作成の処理状況に基づき、計画作成完了までの残りの演算時間と前記求解条件毎の前記削減効果を再度算定して所定装置に出力し、前記求解条件設定処理において、前記再度算定し出力した求解条件のうち当該計画の作成に適用する求解条件の指定を再度受け付ける、としてもよい。

また、本実施形態の計画作成方法において、前記情報処理装置が、前記演算時間推定処理において、前記計画の対象となる所定問題に関して、所定アルゴリズムにて演算時間に関わるパラメータ値を算出し、当該パラメータ値を所定の演算時間算出式に適用することで演算時間の推定を行うとしてもよい。

１ 計画情報格納部
２ 特徴解析部
３ 演算時間推定部
４ 演算時間算出式格納部
５ 求解条件格納部
６ 求解条件設定部
７ 計画作成部
８ 探索状況格納部
９ 作成結果格納部
１０ 演算時間履歴情報格納部
１１ 適用求解条件格納部
２１ 斜線
２２ 太線
６１ 求解条件設定画面
１００ 計画作成装置
１０１ 記憶装置
１０２ プログラム
１０３ メモリ
１０４ 演算装置
１０５ 入力装置
１０６ 出力装置

Claims (6)

1. 所定計画の作成に要する演算時間を推定する演算時間推定部と、前記推定した演算時間を所定装置に出力し、当該計画の作成における解空間を限定する求解条件をユーザから受け付けるに際し、所定の求解条件格納部に格納した、前記計画の対象となる所定問題に応じた求解条件の内容と当該求解条件を示す数式を含む求解条件を、所定装置にて出力すると共に、当該出力した求解条件のうち当該計画の作成に適用する又は適用除外する求解条件の指定を、所定のインターフェイスを介して個別または一括で受け付ける求解条件設定部と、前記求解条件にて当該計画の作成を行う計画作成部とを備え、
   前記演算時間推定部が、前記求解条件設定部で求解条件を受け付けた場合に、当該求解条件に基づき演算時間を再度推定し、前記再度の推定に際し、前記出力した求解条件のうち前記指定を受けた求解条件を適用した場合の、前記演算時間の削減効果を算定し、当該削減効果の情報を所定装置に出力し、
   前記求解条件設定部が、前記演算時間推定部が再度推定した演算時間を、所定装置に出力するものである、
   ことを特徴とする計画作成装置。
2. 前記計画作成部は、
   所定時間内に計画作成ができない場合、計画作成を一時停止し、
   前記演算時間推定部は、
   前記計画作成の一時停止に伴い、現在適用中の前記求解条件と前記計画作成部での計画作成の処理状況に基づき、計画作成完了までの残りの演算時間と前記求解条件毎の前記削減効果を再度算定して所定装置に出力し、
   前記求解条件設定部は、
   前記再度算定し出力した求解条件のうち当該計画の作成に適用する求解条件の指定を再度受け付けるものである、
   ことを特徴とする請求項１に記載の計画作成装置。
3. 前記演算時間推定部は、
   前記計画の対象となる所定問題に関して、所定アルゴリズムにて演算時間に関わるパラメータ値を算出し、当該パラメータ値を所定の演算時間算出式に適用することで演算時間の推定を行うものである、
   ことを特徴とする請求項１に記載の計画作成装置。
4. 情報処理装置が、
   所定計画の作成に要する演算時間を推定する演算時間推定処理と、
   前記推定した演算時間を所定装置に出力し、当該計画の作成における解空間を限定する求解条件をユーザから受け付けるに際し、所定の求解条件格納部に格納した、前記計画の対象となる所定問題に応じた求解条件の内容と当該求解条件を示す数式を含む求解条件を、所定装置にて出力すると共に、当該出力した求解条件のうち当該計画の作成に適用する又は適用除外する求解条件の指定を、所定のインターフェイスを介して個別または一括で受け付ける求解条件設定処理と、
   前記求解条件にて当該計画の作成を行う計画作成処理とを実行し、
   前記演算時間推定処理にて、前記求解条件設定処理で求解条件を受け付けた場合に、当該求解条件に基づき演算時間を再度推定し、前記再度の推定に際し、前記出力した求解条件のうち前記指定を受けた求解条件を適用した場合の、前記演算時間の削減効果を算定し、当該削減効果の情報を所定装置に出力し、
   前記求解条件設定処理にて、前記演算時間推定処理で再度推定した演算時間を、所定装置に出力する、
   ことを特徴とする計画作成方法。
5. 前記情報処理装置が、
   前記計画作成処理において、
   所定時間内に計画作成ができない場合、計画作成を一時停止し、
   前記演算時間推定処理において、
   前記計画作成の一時停止に伴い、現在適用中の前記求解条件と前記計画作成処理での計画作成の処理状況に基づき、計画作成完了までの残りの演算時間と前記求解条件毎の前記削減効果を再度算定して所定装置に出力し、
   前記求解条件設定処理において、
   前記再度算定し出力した求解条件のうち当該計画の作成に適用する求解条件の指定を再度受け付ける、
   ことを特徴とする請求項４に記載の計画作成方法。
6. 前記情報処理装置が、
   前記演算時間推定処理において、
   前記計画の対象となる所定問題に関して、所定アルゴリズムにて演算時間に関わるパラメータ値を算出し、当該パラメータ値を所定の演算時間算出式に適用することで演算時間の推定を行う、
   ことを特徴とする請求項４に記載の計画作成方法。

Images