JP7784982B2 - 移動体作業計画作成システム、移動体作業計画作成方法および移動体作業計画作成プログラム - Google Patents

Description

本開示は、移動体に対する作業についての構内作業計画を作成する移動体作業計画作成システム、移動体作業計画作成方法および移動体作業計画作成プログラムに関する。

鉄道に代表される軌道系交通機関において、列車に対する車両基地での作業について構内作業計画が作成され、構内作業計画に従って作業が実施されることがある。従来、構内作業計画の作成は、構内作業計画の作成を担当する担当者の手作業により主に行われていた。

近年、コンピュータの使用による構内作業計画の自動作成技術が提案されている。構内作業計画の自動作成技術の１つとして、作業および入換の行程についてのテンプレートを登録しておき、所望される構内作業計画の内容に応じたテンプレートの適用によって制約違反の解消を図る技術が知られている。また、特許文献１には、在線、入換または作業といった各事象の発生順序と事象間の時間的関係とを規定する構内計画ネットワークをＰＥＲＴ（Program Evaluation and Review Technique）の適用によって作成し、制約違反が少なくなるようにメタヒューリスティクスで解を探索する構内計画作成装置が開示されている。

特開２００９－５１４４４号公報

テンプレートの適用によって制約違反の解消を図る場合、対象となる構内の構造に従ったテンプレートが使用される。特定の構内の構造に従って登録されたテンプレートを使用すると、当該特定の構内とは異なる構造の構内についての構内作業計画を作成することができない場合がある。このため、テンプレートを適用する場合、構内作業計画の作成方法として、構内の構造に依らない一般的な作成方法を実現することは難しい。メタヒューリスティクスで解を探索する場合、作成される構内作業計画は探索方法に依存したものとなることから、任意の条件で解を得られることを保証することは難しく、構内作業計画の条件または構内の構造によっては構内作業計画を作成することができない場合がある。さらに、テンプレートの適用によって制約違反の解消を図る場合と、メタヒューリスティクスで解を探索する場合とのいずれにおいても、得られる解は制約充足解にとどまり、より効率的な構内作業計画を得ることが難しいという問題があった。

本開示は、上記に鑑みてなされたものであって、構内作業計画の条件または構内の構造によらず構内作業計画を作成でき、かつより効率的な構内作業計画を得ることを可能とする移動体作業計画作成システムを得ることを目的とする。

上述した課題を解決し、目的を達成するために、本開示にかかる移動体作業計画作成システムは、移動体が留置される留置区と移動体に対する作業を実施する作業区とを含む複数の区域を有する施設の構内における複数の移動体の各々の移動および作業のスケジュールである構内作業計画を作成する移動体作業計画作成システムである。本開示にかかる移動体作業計画作成システムは、各移動体が構内へ入る時刻である到着時刻と各移動体が構内から出る時刻である出発時刻とを示す発着時刻情報と、各移動体についての作業の予定を示す作業予定情報とを取得する取得部と、各区域を表す第１軸と時刻を表す第２軸とを含む平面を想定するとして、各区域についてある時間間隔で刻まれた時刻ごとに配置されるノードとノード同士を結ぶリンクとを有するグラフを、施設の構成を示す情報を基に、各移動体について生成するグラフ生成部と、複数の区域に含まれる区域同士の間における各移動体の移動または複数の区域における各移動体の配置についての制約条件を表す制約式を、生成されたグラフと発着時刻情報と作業予定情報とに基づいて生成する制約式生成部と、制約式を充足する解であって、各移動体の移動についてあらかじめ設定された評価関数に基づいた解を求めることによって、構内作業計画を算出する構内作業計画算出部と、を備える。グラフ生成部は、移動体の移動が可能であるノード間をつないだリンクと、区域に移動体がとどまることを示すリンクとを含む複数のリンクを有するグラフを移動体ごとに生成する。構内作業計画算出部は、グラフに含まれるリンクを決定変数として、制約式を充足しかつ評価関数を最小化させる決定変数を解として求める。

本開示にかかる移動体作業計画作成システムは、構内作業計画の条件または構内の構造によらず構内作業計画を作成でき、かつより効率的な構内作業計画を得ることができるという効果を奏する。

実施の形態１にかかる移動体作業計画作成システムの構成例を示す図 実施の形態１において構内作業計画を作成する対象である車両基地の構成例を模式的に示す図 実施の形態１にかかる移動体作業計画作成システムによって作成される構内作業計画の概略について説明するための図 実施の形態１にかかる移動体作業計画作成システムによる構内作業計画を作成する処理の概要について説明するための図 実施の形態１にかかる移動体作業計画作成システムの制約式生成部のうち開始時所在制約生成部によって生成される制約式について説明するための図 実施の形態１にかかる移動体作業計画作成システムの制約式生成部のうち移動制約生成部によって生成される制約式について説明するための図 実施の形態１にかかる移動体作業計画作成システムの制約式生成部のうち作業実施制約生成部によって生成される制約式について説明するための図 実施の形態１にかかる移動体作業計画作成システムの制約式生成部のうち進路競合制約生成部によって生成される制約式について説明するための図 実施の形態１にかかる移動体作業計画作成システムによる処理の手順を示すフローチャート 実施の形態１にかかる移動体作業計画作成システムにおいて演算負荷を低減させる第１の機能について説明するための図 実施の形態１にかかる移動体作業計画作成システムにおいて演算負荷を低減させる第２の機能について説明するための図 実施の形態１にかかる移動体作業計画作成システムにおいて演算負荷を低減させる第３の機能について説明するためのフローチャート 実施の形態１にかかる移動体作業計画作成システムにおいて対象期間の区切りの時刻を設定する例について示す図 実施の形態１にかかる移動体作業計画作成システムを実現するハードウェア構成例を示す図

以下に、実施の形態にかかる移動体作業計画作成システム、移動体作業計画作成方法および移動体作業計画作成プログラムを図面に基づいて詳細に説明する。

実施の形態１．
図１は、実施の形態１にかかる移動体作業計画作成システム１０の構成例を示す図である。移動体作業計画作成システム１０は、施設の構内における複数の移動体の各々の移動および作業のスケジュールである構内作業計画を作成する。実施の形態１において、施設は、鉄道車両の編成が留置される車両基地とする。移動体は、例えば、鉄道車両の編成である。なお、鉄道車両の編成には、１両編成も含まれる。実施の形態１では、移動体が鉄道車両の編成である例について説明するが、移動体は、鉄道車両の編成に限られず、バス、トラック、または自動車等の輸送機器であっても良い。以下、鉄道車両の編成を、単に「編成」と称する。

ここで、移動体作業計画作成システム１０の構成についての説明に先立ち、構内作業計画を作成する対象である車両基地の構成について説明する。図２は、実施の形態１において構内作業計画を作成する対象である車両基地の構成例を模式的に示す図である。

車両基地の構内には、編成が進入可能な複数の区域が設けられている。複数の区域には、編成が留置される留置区と、編成に対する作業を実施する作業区とが含まれる。留置区に設けられている線である留置線へ編成が進入し、留置線上にて編成が停止することによって、編成は留置される。以下の説明では、留置線を留置区とみなす。作業が実施される編成は、作業区に設けられている線である作業線へ進入する。作業線上にて編成が停止している状態において、編成に対する作業が実施される。作業線では、交番検査、列車検査、または車内清掃といった作業が実施される。作業線ごとに決められた作業が実施される。以下の説明では、作業線を作業区とみなす。なお、構内に複数の留置線が設けられている場合、各留置線を留置区とみなす。構内に複数の作業線が設けられている場合、各作業線を作業区とみなす。

入区線は、車両基地の外から構内へ編成が入る際に通る線である。営業運転のための線である本線を走行した編成は、入区線を通って構内へ進入する。出区線は、構内から車両基地の外へ編成が出る際に通る線である。構内の編成は、出区線を通って本線へ戻る。なお、入区線と出区線との各々は、編成が進入可能な複数の区域に含まれる区域とみなす。

図２に示す例では、構内には、入区線、出区線、Ｉ本の留置線、および２本の作業線が設けられている。Ｉは、２以上の任意の整数とする。Ｉ本の留置線の各々を、第１留置線、第２留置線、第３留置線、・・・、第Ｉ留置線とする。２本の作業線の各々を、第１作業線、第２作業線とする。入区線と出区線とは、互いに並列に接続されている。Ｉ本の留置線は、互いに並列に接続されている。２本の作業線は、互いに並列に接続されている。入区線および出区線の束とＩ本の留置線の束とは、１本の接続線によりつながれている。Ｉ本の留置線の束と２本の作業線の束とは、１本の接続線によりつながれている。

図２に示す車両基地についての構内作業計画は、入区線、出区線、Ｉ本の留置線、および２本の作業線のうちの線同士の間における各編成の移動と、各編成に対する作業とのスケジュールである。図３は、実施の形態１にかかる移動体作業計画作成システム１０によって作成される構内作業計画の概略について説明するための図である。

図３には、第１留置線、第２留置線、第３留置線、・・・、第Ｉ留置線、第１作業線、および第２作業線における３つの編成の各々の移動および作業のスケジュールの例を示す。図３において「Ａ」、「Ｂ」、および「Ｃ」は、それぞれ編成を表す。図３では、線ごとに、編成が線に存在している期間を棒グラフにより表す。また、図３では、線同士の間における編成の移動を、棒グラフ同士をつなぐ直線により表す。図３に示す例において、例えば編成「Ａ」は、第２留置線にて留置された後、第２留置線から第２作業線へ移動し、第２作業線にて作業が実施される。その後、編成「Ａ」は、第２作業線から第３留置線へ移動し、第３留置線にて留置される。このように、構内では、留置線と作業線とを編成が行き来して作業が実施される。

なお、構内作業計画を作成する対象である車両基地の構成は、図２に示す構成に限られない。構内における作業線の数は２本に限られず任意であるものとする。また、各線の接続の態様は、適宜変更可能である。構内には、留置線と作業線との間の移動の際に必要に応じて編成を退避させる線である引上線が設けられていても良い。この場合、引上線が設けられている区域も、編成が進入可能な複数の区域に含まれる。また、図２に示す例では入区線と出区線とを互いに別の線としたが、共通の線を入区線および出区線として使用することとしても良い。

次に、移動体作業計画作成システム１０の構成について説明する。図１に示すように、移動体作業計画作成システム１０は、入力部１１と、グラフ生成部１２と、取得部１３と、制約式生成部１４と、構内作業計画算出部１５と、出力部１６とを備える。グラフ生成部１２、取得部１３、制約式生成部１４、および構内作業計画算出部１５は、情報を処理する処理部を構成する。

入力部１１には、本線における各編成の運行ダイヤの情報と、各編成について実施すべき作業の予定を示す作業予定情報と、車両基地の構成を示す情報とが入力される。運行ダイヤの情報には、各編成が構内へ入る時刻である到着時刻の情報と、各編成が構内から出る時刻である出発時刻の情報とが含まれる。

グラフ生成部１２は、各区域を表す第１軸と時刻を表す第２軸とを含む平面を想定するとして、各区域についてある時間間隔で刻まれた時刻ごとに配置されるノードとノード同士を結ぶリンクとを有するグラフを各編成について生成する。グラフ生成部１２は、車両基地の構成を示す情報を入力部１１から取得し、取得された情報を基にグラフを生成する。グラフの詳細については後述する。グラフ生成部１２は、生成されたグラフを制約式生成部１４へ出力する。

取得部１３は、発着時刻情報取得部２１と作業予定情報取得部２２とを備える。発着時刻情報取得部２１は、運行ダイヤの情報を入力部１１から取得し、運行ダイヤの情報の中から発着時刻情報を取得する。発着時刻情報は、各編成が車両基地の構内へ入る時刻である到着時刻と各編成が車両基地の構内から出る時刻である出発時刻とを示す情報である。作業予定情報取得部２２は、作業予定情報を入力部１１から取得する。このように、取得部１３は、発着時刻情報と作業予定情報とを取得する。取得部１３は、取得された発着時刻情報と取得された作業予定情報とを制約式生成部１４へ出力する。

制約式生成部１４は、複数の区域に含まれる区域同士の間における各編成の移動または複数の区域における各編成の配置についての制約条件を表す制約式を生成する。制約式生成部１４は、グラフ生成部１２によって生成されたグラフと、発着時刻情報と、作業予定情報とに基づいて、制約式を生成する。制約式は、構内作業計画が充足すべき制約条件を表す。

制約式生成部１４は、開始時所在制約生成部２３と、移動制約生成部２４と、区域競合制約生成部２５と、作業実施制約生成部２６と、進路競合制約生成部２７とを備える。制約式生成部１４は、開始時所在制約生成部２３と、移動制約生成部２４と、区域競合制約生成部２５と、作業実施制約生成部２６と、進路競合制約生成部２７との各々において制約式を生成する。制約式生成部１４に備えられる各部の詳細については後述する。制約式生成部１４は、生成された制約式を構内作業計画算出部１５へ出力する。

構内作業計画算出部１５は、制約式を充足する解であって、各編成の移動についてあらかじめ設定された評価関数に基づいた解を求めることによって、構内作業計画を算出する。構内作業計画算出部１５は、算出された構内作業計画を出力部１６へ出力する。出力部１６は、移動体作業計画作成システム１０の外部へ構内作業計画を出力する。

図４は、実施の形態１にかかる移動体作業計画作成システム１０による構内作業計画を作成する処理の概要について説明するための図である。実施の形態１では、移動体作業計画作成システム１０は、構内作業計画問題を整数計画問題として定式化し、評価指標に基づく最適解を求めることによって構内作業計画を算出する。

図４には、グラフ生成部１２により生成されるグラフの例を示す。図４において、縦軸は、各区域の線を表す。すなわち、縦軸は、構内の各区域を表す第１軸である。構内における各線は、構内作業計画において利用可能な資源に相当する。横軸は、時刻を表す第２軸である。なお、グラフ生成部１２は、図４に示すようなグラフにより表される情報を生成するものとする。グラフは、グラフ生成部１２により生成される情報の内容を概念的に表現したものとする。

グラフは、複数のノードと複数のリンクとを有する。各線について、ある時間間隔で刻まれた時刻ごとにノードが配置される。図４では、各線を表す破線と一定の時間間隔おきの時刻を表す破線とが格子状に配列されており、各線を表す破線と一定の時間間隔おきの時刻を表す破線との交点にノードが配置される。以下、ノードが配置される時間間隔を、「単位時間」と称する。なお、図４に示す例では、第１作業線についてはノードが配置されていない。実施の形態１により作成される構内作業計画には第１作業線での作業のスケジュールが含まれないため、グラフ生成部１２は、第１作業線におけるノードを含まないグラフを生成するものとする。

また、図４では、ノード同士の間の細線矢印により各リンクを表す。縦軸に示される各線のうち任意の２つを第１の線および第２の線として、第１の線におけるノードと第２の線におけるノードとの間のリンクは、第１の線と第２の線との間における編成の移動を表す。構内に設けられている線同士の間での編成の移動は、入換と称される。

グラフでは、編成の移動が可能なノード間にリンクが張られる。縦軸に示される各線について、同じ線におけるノード間のリンクは、当該線から編成が移動せず当該線に編成が存在することを表す。図４に示す例において、第２作業線におけるノード間のリンクは、第２作業線での作業のために第２作業線に編成がとどまることを表す。作業のために編成がとどまることを表すリンクは、その作業のために要する時間だけ離れたノード間を結ぶ。図４に示す例では、単位時間の３倍が第２作業線での作業時間に相当する。グラフ生成部１２は、複数の編成の各々について、図４に示すようなグラフを作成する。なお、図４では、構内に設けられている留置線のうちの一部についてはノードおよびリンクの図示を省略している。

構内作業計画算出部１５は、各リンクを決定変数として、制約式を充足しかつ評価関数を最小化させる決定変数を解として求める。各リンクについて、当該リンクを使う場合における決定変数の値を「１」、当該リンクを使わない場合における決定変数の値を「０」とする。第１の線におけるあるノードと第２の線におけるあるノードとの間のリンクが「１」であることは、当該リンクにより示される移動が構内作業計画に含まれることを表す。同じ線におけるノード間のリンクが「１」であることは、当該リンクの期間に当該線に編成がとどまることが構内作業計画に含まれることを表す。実施の形態１において、評価関数である評価式は、各編成の区域同士の間における移動の回数を表す。構内作業計画算出部１５は、構内作業計画における制約条件を満たした上で評価関数を最小化させる決定変数を、整数計画問題ソルバーにより求める。

図４において、太線矢印は、「１」であるリンクを表す。また、図４では、「１」であるリンクが出るノードと「１」であるリンクが入るノードとを、白抜きの丸により表す。それ以外のノードを、黒塗りの丸により表す。構内作業計画算出部１５は、編成ごとに、「１」であるリンクを組み合わせることによって、構内作業計画を算出する。時刻ｔ₀は、構内作業計画の対象期間の始点である。出区線から編成が出る時刻ｔ_outは、編成が構内から出る出発時刻である。入区線へ編成が入る時刻ｔ_inは、編成が構内へ入る到着時刻である。編成は、時刻ｔ_outから時刻ｔ_inまでの期間において、本線において運用される。各編成の時刻ｔ_outと各編成の時刻ｔ_inとは、各編成の発着時刻情報に基づいて決定される。

次に、制約式生成部１４の各部により生成される各制約式について説明する。図５は、実施の形態１にかかる移動体作業計画作成システム１０の制約式生成部１４のうち開始時所在制約生成部２３によって生成される制約式について説明するための図である。開始時所在制約生成部２３は、開始時所在制約条件を表す制約式を生成する。開始時所在制約条件とは、構内作業計画の対象期間の始点にて編成が存在する区域によって決まる制約条件とする。

対象期間の始点である時刻ｔ₀において編成ｖが線ｒ_vに存在するとして、開始時所在制約条件は、次の式（１）である制約式により表される。

Ｅ^O _v,t,rは、編成ｖのグラフにおいて、資源である線ｒにおける時刻ｔのノードから出るリンクの集合を表す。式（１）において、ｅは、編成ｖのグラフにおいて、線ｒ_vにおける時刻ｔ₀のノードから出るリンクの集合に含まれるリンクを表す。ｘ_eは、リンクｅの決定変数を表す。Ｖは、編成の集合を表す。式（１）は、編成ｖについて、線ｒ_vにおける時刻ｔ₀のノードから出るリンクの集合に含まれる全てのリンクについての決定変数の合計が「１」であることを表す。

図５において楕円３０で囲われたリンクは、第２留置線の時刻ｔ₀におけるノードから出るリンクである。例えば、時刻ｔ₀においてある編成が第２留置線に存在する場合に、楕円３０で囲われたリンクのうちの１つが使われることが、開始時所在制約条件となる。この場合、楕円３０で囲われたリンクのうちの１つは決定変数が「１」であって、楕円３０で囲われたリンクのうちその他全ては決定変数が「０」である。このため、楕円３０で囲われた全てのリンクについて決定変数の合計は「１」となる。なお、時刻ｔ₀において編成が存在する線は、現在の対象期間の１つ前の対象期間における構内作業計画の内容に基づいて決定される。開始時所在制約生成部２３は、編成の集合であるＶに含まれる全ての編成について、開始時所在制約条件を表す制約式を生成する。なお、時刻ｔ₀において本線上に存在する編成については、構内のいずれの線にも編成が存在しないことが開始時所在制約条件となる。

図６は、実施の形態１にかかる移動体作業計画作成システム１０の制約式生成部１４のうち移動制約生成部２４によって生成される制約式について説明するための図である。移動制約生成部２４は、移動制約条件を表す制約式を生成する。移動制約条件とは、各区域について、区域への編成の進入と区域からの編成の退出との組合せについての制約条件とする。

移動制約条件は、次の式（２）である制約式により表される。

Ｅ^I _v,t,rは、編成ｖのグラフにおいて、資源である線ｒの時刻ｔにおけるノードへ入るリンクの集合を表す。Ｎ^IO _vは、編成ｖのグラフにおいて、リンクが１本でも出入りしているノードの集合を表す。式（２）は、編成ｖについて、時刻ｔおよび線ｒのノードへ入る全てのリンクの決定変数の合計と、時刻ｔおよび線ｒのノードから出る全てのリンクの決定変数の合計とは互いに等しいことを表す。

図６において実線の楕円３１で囲われたリンクは、第２留置線のある時刻におけるノードへ入るリンクである。図６において破線の楕円３２で囲われたリンクは、第２留置線のある時刻におけるノードから出るリンクである。図６に示す例では、当該時刻において第２留置線に編成は存在するため、楕円３１で囲われたリンクのうちの１つの決定変数は「１」であって、楕円３１で囲われたリンクのうちその他全ては決定変数が「０」である。また、楕円３２で囲われたリンクのうちの１つの決定変数は「１」であって、楕円３２で囲われたリンクのうちその他全ては決定変数が「０」である。楕円３１で囲われた全てのリンクについて決定変数の合計は「１」となり、かつ、楕円３２で囲われた全てのリンクについて決定変数の合計も「１」となる。このため、編成が存在するノードについて、当該ノードへ入る全てのリンクの決定変数の合計と、当該ノードから出る全てのリンクの決定変数の合計とは互いに等しくなる。

また、編成が存在しないノードでは、当該ノードへ入る全てのリンクの決定変数の合計は「０」となり、当該ノードから出る全てのリンクの決定変数の合計も「０」となる。このため、編成が存在しないノードについて、当該ノードへ入る全てのリンクの決定変数の合計と、当該ノードから出る全てのリンクの決定変数の合計とは互いに等しくなる。移動制約生成部２４は、編成の集合であるＶに含まれる全ての編成について、移動制約条件を表す制約式を生成する。

区域競合制約生成部２５は、区域競合制約条件を表す制約式を生成する。区域競合制約条件とは、２以上の編成が同じ期間において同じ区域に存在する区域競合についての制約条件とする。実施の形態１では、１つの線に同時に存在可能な編成は最大１つとする。区域競合制約条件は、１つの線において同時に２以上の編成が存在する区域競合を除外する制約条件といえる。

区域競合制約条件は、次の式（３）である制約式により表される。

Ｅ^R _v,t,rは、編成ｖのグラフにおいて、資源である線ｒにおける時刻ｔのノードに入るリンクと、時刻ｔよりも以前から時刻ｔをまたいで線ｒに編成が存在しているリンクとの集合を表す。Ｔは、時刻の集合を表す。Ｒは、資源である線の集合を表す。

式（３）における２重和のうちの一方である、ｅについての合計は、編成ｖのグラフにおいて、Ｅ^R _v,t,rに含まれる全てのリンクについての決定変数の合計を表す。式（３）における２重和のうちの他方は、Ｖに含まれる全ての編成ｖについての合計を表す。式（３）は、Ｅ^R _v,t,rに含まれる全てのリンクの決定変数の合計を、全ての編成ｖについて合計した結果が１以下であることを表す。すなわち、式（３）は、時刻ｔにおいて線ｒを使用する編成ｖの数の合計は１以下であることを表す。区域競合制約生成部２５は、Ｖに含まれる全ての編成ｖについての区域競合制約条件を表す制約式を生成する。

図７は、実施の形態１にかかる移動体作業計画作成システム１０の制約式生成部１４のうち作業実施制約生成部２６によって生成される制約式について説明するための図である。作業実施制約生成部２６は、作業実施制約条件を表す制約式を生成する。作業実施制約条件とは、作業予定情報に示される作業を各編成に対して実施することについての制約条件とする。

作業実施制約条件は、次の式（４）である制約式により表される。

Ｅ^W _v,d,wは、編成ｖのグラフにおいて、日ｄにおける実施が予定された作業ｗについてのリンクの集合を表す。作業ｗについてのリンクとは、作業ｗが実施される作業線におけるノード間のリンクとする。Ｄは、日の集合を表す。Ｗは、作業の集合を表す。式（４）は、編成ｖについて、作業ｗについてのリンクの集合に含まれる全てのリンクについての決定変数の合計が「１」であることを表す。

図７において楕円３３で囲われたリンクは、第２作業線についてのリンクである。例えば、第２作業線にて実施される作業が列車検査であって、対象期間である日に編成ｖに対する列車検査が予定されているとする。楕円３３で囲われたリンクのうちの１つの決定変数は「１」であって、楕円３３で囲われたリンクのうちその他全ては決定変数が「０」である。このため、楕円３３で囲われた全てのリンクについて決定変数の合計は「１」となる。構内の各作業線は作業に紐付けられているため、作業線におけるノード間のリンクを基に作業実施制約条件を設定することができる。作業実施制約生成部２６は、編成の集合であるＶに含まれる全ての編成のうち作業が予定されている編成について、作業実施制約条件を表す制約式を生成する。

なお、ここでは、各作業線に１つの作業が紐付けられているものとして説明した。例えば、作業ｗが２以上の作業線のどちらで行っても良い場合、すなわち、作業ｗに２以上の作業線が紐付けられている場合は、作業実施制約生成部２６は、当該２以上の作業線のリンクについて決定変数の合計が「１」となる制約式を生成する。

図８は、実施の形態１にかかる移動体作業計画作成システム１０の制約式生成部１４のうち進路競合制約生成部２７によって生成される制約式について説明するための図である。進路競合制約生成部２７は、進路競合制約条件を表す制約式を生成する。進路競合制約条件とは、２以上の編成が同じ期間において同じ進路に進入する進路競合についての制約条件とする。

図２に示す構成の場合、例えば、第２作業線から第２留置線への編成「Ａ」の入換と、第１留置線から第１作業線への編成「Ｂ」の入換とは、各留置線と各作業線との間の接続線にて進路競合が生じることから、同時に行うことはできない。

進路競合制約条件は、次の式（５）である制約式により表される。

Ｅ^C _v,t,r1,r2は、第１の線ｒ１から第２の線ｒ２への入換との進路競合を生じさせる入換を表現するリンクの集合を表す。式（５）における２重和のうちの一方である、ｅについての合計は、編成ｖのグラフにおいて、Ｅ^C _v,t,r1,r2に含まれる全てのリンクについての決定変数の合計を表す。式（５）における２重和のうちの他方は、Ｖに含まれる全ての編成ｖについての合計を表す。式（５）は、Ｅ^C _v,t,r1,r2に含まれる全てのリンクの決定変数の合計を、全ての編成ｖについて合計した結果が１以下であることを表す。

図８において楕円３４で囲われたリンクは、編成ｖのグラフのうちある時刻におけるリンクである。楕円３４で囲われたリンクのうち互いに進路競合を生じる関係にあるリンクについての決定変数の合計を、全ての編成ｖについて合計した結果が１以下であることによって、当該時刻における進路競合を除外できる。進路競合制約生成部２７は、Ｖに含まれる全ての編成ｖについての進路競合制約条件を表す制約式を生成する。

構内作業計画算出部１５は、式（１）から式（５）に示される各制約式を充足する解を求める。これにより、移動体作業計画作成システム１０は、開始時所在制約条件、移動制約条件、区域競合制約条件、作業実施制約条件、および進路競合制約条件の全てを充足する構内作業計画を作成することができる。

なお、ここでは、開始時所在制約条件、移動制約条件、区域競合制約条件、作業実施制約条件、および進路競合制約条件を制約条件としたが、これらの制約条件以外の制約条件が追加されても良い。例えば、使用時間に制限が設けられている線がある場合において、使用時間の制約条件が追加されても良い。作業に携わる作業員の勤務時間、または作業に携わる作業員の数についての制約条件、あるいは、入換を実施する作業員の数についての制約条件が追加されても良い。

次に、評価関数について説明する。評価関数は、各編成の区域同士の間における移動の回数、すなわち、各編成の入換回数を表す。評価関数は、次の式（６）により表される。

Ｅ^M _vは、編成ｖのグラフにおいて入換を表すリンクの集合を表す。構内作業計画算出部１５は、評価関数を最小化させる決定変数を解として求める。これにより、移動体作業計画作成システム１０は、各編成の入換回数を低減可能とする構内作業計画を作成することができる。すなわち、移動体作業計画作成システム１０は、制約条件の全てを充足し、かつ、より効率的な構内作業計画を作成することができる。

なお、ここでは、各編成の入換回数を評価基準としたが、評価基準には、入換回数以外の評価基準が組み合わされても良い。例えば、構内作業計画の基本である基本計画を変更することによって構内作業計画を作成する場合に、構内作業計画の要素のうち基本計画から変更される要素の数を評価基準としても良い。基本計画から変更される要素の数を低減可能であることによって、構内作業計画の作成効率を向上できる。また、構内作業計画の作成のために制約条件の緩和が必要である場合において、制約条件の緩和の程度を評価基準としても良い。制約条件の緩和の程度を低減させることができる。

次に、移動体作業計画作成システム１０による処理の手順について説明する。図９は、実施の形態１にかかる移動体作業計画作成システム１０による処理の手順を示すフローチャートである。

ステップＳ１において、移動体作業計画作成システム１０は、取得部１３により発着時刻情報と作業予定情報とを取得する。取得部１３は、入力部１１へ入力された運行ダイヤの情報から発着時刻情報を取得する。取得部１３は、入力部１１へ入力された作業予定情報を取得する。なお、取得部１３は、運行ダイヤの情報以外から発着時刻情報を取得しても良い。発着時刻情報は、移動体作業計画作成システム１０を操作する操作者による入力操作によって入力部１１へ入力されても良い。この場合、取得部１３は、入力部１１へ入力された発着時刻情報を取得する。取得部１３は、取得された発着時刻情報と取得された作業予定情報とを制約式生成部１４へ出力する。

ステップＳ２において、移動体作業計画作成システム１０は、グラフ生成部１２により編成ごとのグラフを生成する。グラフ生成部１２は、車両基地の構成を示す情報を入力部１１から取得する。グラフ生成部１２は、車両基地の構成を示す情報に基づいて、編成ごとのグラフを生成する。グラフ生成部１２は、生成されたグラフを制約式生成部１４へ出力する。グラフ生成部１２によって生成されたグラフは、移動体作業計画作成システム１０内に格納されても良い。

ステップＳ３において、移動体作業計画作成システム１０は、制約式生成部１４により、発着時刻情報と作業予定情報とに基づいて制約式を生成する。制約式生成部１４は、開始時所在制約条件、移動制約条件、区域競合制約条件、作業実施制約条件、および進路競合制約条件の各々についての制約式を生成する。制約式生成部１４は、グラフ生成部１２から入力されるグラフに基づいて制約式を生成する。制約式生成部１４は、移動体作業計画作成システム１０内に格納されているグラフを読み出し、読み出されたグラフに基づいて制約式を生成しても良い。制約式生成部１４は、生成された制約式を構内作業計画算出部１５へ出力する。

ステップＳ４において、移動体作業計画作成システム１０は、構内作業計画算出部１５により、制約式と評価関数とに基づいて構内作業計画を算出する。構内作業計画算出部１５は、ステップＳ３において生成された制約式を充足し、かつあらかじめ設定された評価関数を最小化させる解を求めることによって、構内作業計画を算出する。

ステップＳ５において、移動体作業計画作成システム１０は、出力部１６により、構内作業計画を出力する。出力部１６は、例えば、構内作業計画のデータを含むファイルを端末装置等へ出力する。以上により、移動体作業計画作成システム１０は、図９に示す手順による処理を終了する。

移動体作業計画作成システム１０は、構内作業計画を算出する際における演算負荷を低減させる機能を備えても良い。以下、移動体作業計画作成システム１０において演算負荷を低減させる３つの機能について説明する。

図１０は、実施の形態１にかかる移動体作業計画作成システム１０において演算負荷を低減させる第１の機能について説明するための図である。第１の機能により、制約式生成部１４は、各編成について、出発時刻から次の到着時刻までの期間におけるノードおよびリンクを省略して制約式を生成する。

図１０の上部には、出発時刻である時刻ｔ_outから次の到着時刻である時刻ｔ_inまでの期間におけるノードおよびリンクを省略する前のグラフを示す。図１０の下部には、時刻ｔ_outから時刻ｔ_inまでの期間におけるノードおよびリンクが省略されたグラフを示す。制約式生成部１４は、各編成の発着時刻情報に基づいて、各編成のグラフにおけるノードおよびリンクを省く処理を行う。移動体作業計画作成システム１０は、第１の機能により、時刻ｔ_outから時刻ｔ_inまでの期間におけるノードおよびリンクと、当該ノードおよびリンクに関連する制約式が省略されることによって、当該ノードおよびリンクが省略される前と比べて演算負荷を低減できる。

各編成について、時刻ｔ_outから時刻ｔ_inまでの期間において構内での作業または入換は実施されないため、各編成について時刻ｔ_outから時刻ｔ_inまでの期間におけるノードおよびリンクが省略されても、構内作業計画算出部１５により得られる解の最適性は損なわれない。これにより、移動体作業計画作成システム１０は、算出される構内作業計画の精度を維持しながら演算負荷を低減できる。

図１１は、実施の形態１にかかる移動体作業計画作成システム１０において演算負荷を低減させる第２の機能について説明するための図である。第２の機能により、制約式生成部１４は、各編成について、出発時刻までの一定期間と、到着時刻からの一定期間と、作業が行われる期間の開始時刻までの一定期間と、作業が行われる期間の終了時刻までの一定期間とを除いた期間におけるノードおよびリンクを省略して制約式を生成する。

図１１には、出発時刻である時刻ｔ_outまでの期間Ｐよりも前の期間におけるノードおよびリンクを省略する例を示す。図１１の上部には、ノードおよびリンクを省略する前のグラフを示す。図１１の下部には、ノードおよびリンクが省略されたグラフを示す。期間Ｐは、単位時間の２倍に相当する一定期間とする。図１１に示す例では、編成は、第２留置線にて留置された後に出区線へ移動するものとする。なお、期間Ｐの長さは任意に設定可能であっても良い。

図１１において時刻ｔ_outよりも前の期間について、時刻ｔ_outまでの期間Ｐにおいて出区線へ編成が進入する場合のノードおよびリンクと、第２留置線における編成の留置を表すノードおよびリンクとが残され、それ以外のノードおよびリンクが省かれている。また、図１１に示す例では、第１留置線および第Ｉ留置線の各々のノードと、それらのノードにつながるリンクとが省かれている。

図１１には、出発時刻までの一定期間を除いた期間におけるノードおよびリンクを省略する例を示した。制約式生成部１４は、出発時刻までの一定期間と、到着時刻からの一定期間と、作業が行われる期間の開始時刻までの一定期間と、作業が行われる期間の終了時刻までの一定期間とのうちの少なくとも１つを除いた期間におけるノードおよびリンクを省略して制約式を生成する。なお、時間帯が指定されている作業については、作業が行われる期間の開始時刻は、当該指定された時間帯の始点であって、作業が行われる期間の終了時刻は、当該指定された時間帯の終点とする。時間帯が指定されていない作業については、当該作業を開始可能な時刻を、当該作業が行われる期間の開始時刻とし、当該作業を終了可能な時刻を、当該作業が行われる期間の終了時刻とする。

移動体作業計画作成システム１０は、第２の機能により、一定期間を除いた期間におけるノードおよびリンクを省略することで、当該ノードおよびリンクに関連する制約式も省略できる。移動体作業計画作成システム１０は、一定期間を除いた期間におけるノードおよびリンクと、当該ノードおよびリンクに関連する制約式が省略されることによって、当該ノードおよびリンクが省略される前と比べて演算負荷を低減できる。

第２の機能によると、入換が可能な期間が制約されることとなる。入換が可能な期間が制約されると、構内作業計画算出部１５により得られる解の最適性が損なわれることがあり得る。移動体作業計画作成システム１０は、一定期間である期間Ｐの長さが適宜設定されることによって、最適性の低下の影響を少なくすることができる。これにより、移動体作業計画作成システム１０は、算出される構内作業計画の精度低下を防ぐとともに演算負荷を低減できる。

図１２は、実施の形態１にかかる移動体作業計画作成システム１０において演算負荷を低減させる第３の機能について説明するためのフローチャートである。第３の機能により、制約式生成部１４の進路競合制約生成部２７は、構内作業計画算出部１５によって求めた解に進路競合が含まれる場合に、進路競合制約条件を表す制約式を生成する。

図１２に示すフローチャートは、移動体作業計画作成システム１０が第３の機能により制約式を生成する場合における処理の手順を示す。ステップＳ１１において、移動体作業計画作成システム１０は、制約式生成部１４により、開始時所在制約条件、移動制約条件、区域競合制約条件、および作業実施制約条件についての各制約式を生成する。制約式生成部１４は、ステップＳ１１では、進路競合制約条件を表す制約式を生成しない。制約式生成部１４は、開始時所在制約条件、移動制約条件、区域競合制約条件、および作業実施制約条件について生成された各制約式を構内作業計画算出部１５へ出力する。

ステップＳ１２において、移動体作業計画作成システム１０は、構内作業計画算出部１５により、ステップＳ１１にて生成された各制約式を充足し、かつ評価関数を最小化させる解を求める。

ステップＳ１３において、移動体作業計画作成システム１０は、構内作業計画算出部１５により、ステップＳ１２において得られた解に進路競合があるか否かを判断する。進路競合がある場合（ステップＳ１３，Ｙｅｓ）、移動体作業計画作成システム１０は、ステップＳ１４へ手順を進める。

ステップＳ１４において、移動体作業計画作成システム１０は、構内作業計画算出部１５において、進路競合がある箇所に、進路競合制約条件についての制約式を追加する。構内作業計画算出部１５は、求めた解のうち進路競合があった箇所を検出し、検出された箇所についての制約式の生成を進路競合制約生成部２７に指示する。進路競合制約生成部２７は、指示に従って進路競合制約条件についての制約式を生成する。制約式生成部１４は、生成された制約式を構内作業計画算出部１５へ出力する。移動体作業計画作成システム１０は、進路競合制約条件についての制約式を、ステップＳ１１にて生成された各制約式に追加して、手順をステップＳ１２へ戻す。

一方、進路競合がない場合（ステップＳ１３，Ｎｏ）、ステップＳ１５において、移動体作業計画作成システム１０は、得られた解である構内作業計画を出力部１６により出力する。以上により、移動体作業計画作成システム１０は、図１２に示す手順による処理を終了する。

移動体作業計画作成システム１０は、第３の機能により、求めた解に進路競合があった場合に限り、進路競合があった箇所について進路競合制約条件の制約式を生成する。移動体作業計画作成システム１０は、進路競合があった箇所以外については進路競合制約条件の制約式が省略されることによって、当該制約式が省略されない場合と比べて演算負荷を低減できる。移動体作業計画作成システム１０は、進路競合があった箇所については進路競合制約条件の制約式を生成することで、進路競合を含まない構内作業計画を作成することができる。これにより、移動体作業計画作成システム１０は、演算負荷を低減しつつ、進路競合を含まない構内作業計画を作成することができる。

移動体作業計画作成システム１０は、日単位の構内作業計画を作成する場合において、構内作業計画の対象期間の区切りとする時刻を任意に設定可能であっても良い。図１３は、実施の形態１にかかる移動体作業計画作成システム１０において対象期間の区切りの時刻を設定する例について示す図である。

構内作業計画算出部１５は、任意に設定された時刻を対象期間の区切りの時刻として、日単位の構内作業計画を算出する。対象期間の区切りの時刻とは、対象期間の始点および対象期間の終点とする時刻である。対象期間の区切りの時刻は、例えば、移動体作業計画作成システム１０を操作する操作者による入力操作によって設定される。

図１３の上部には、０時を区切りの時刻とする例を示す。図１３の下部には、０時から１２時の間におけるある時刻を区切りの時刻とする例を示す。図１３では、構内に編成が到着する到着時刻と、構内において編成が留置される期間と、構内から編成が出発する出発時刻とを、実線矢印または一点鎖線矢印によって概念的に表す。また、図１３では、対象期間の区切りの時刻を破線により表す。

編成の多くは、通常、朝の通勤時間帯において営業運転を開始する。その後、編成ごとに決められた時刻に営業運転を終了し、深夜には編成の多くが車両基地に留置された状態となる。このような事情に対し、対象期間の区切りを一律に０時とした場合、編成の多くが車両基地に存在している時刻が区切りとなる。この場合、編成の多くについて、次の対象期間において編成が出発する際の事情が考慮されずに構内作業計画が作成されることとなる。

図１３の下部に示す例では、朝の通勤時間帯を過ぎた時刻が区切りの時刻に設定されている。当該区切りの時刻は、多くの編成が車両基地から出発した後であって、かつ、多くの編成が車両基地へ到着する前の時刻である。このように区切りの時刻が設定されることによって、移動体作業計画作成システム１０は、編成の多くについて、編成が出発する際の事情が考慮された構内作業計画を作成することができる。

次に、実施の形態１にかかる移動体作業計画作成システム１０を実現するハードウェア構成について説明する。図１４は、実施の形態１にかかる移動体作業計画作成システム１０を実現するハードウェア構成例を示す図である。

移動体作業計画作成システム１０は、処理回路４０を備えるコンピュータシステムにより実現される。処理回路４０は、プロセッサ４２およびメモリ４３を備える。処理回路４０は、プロセッサ４２がソフトウェアを実行する回路である。

入力部４１は、外部から入力されたデータを受信してプロセッサ４２に与えるインターフェース回路である。出力部４４は、プロセッサ４２またはメモリ４３からのデータを外部に送るインターフェース回路である。移動体作業計画作成システム１０は、ソフトウェア、ファームウェア、またはソフトウェアとファームウェアとの組み合わせにより実現される。ソフトウェアまたはファームウェアはプログラムとして記述され、メモリ４３に格納される。処理回路４０では、メモリ４３に記憶されたプログラムである移動体作業計画作成プログラムをプロセッサ４２が読み出して実行することにより、移動体作業計画作成システム１０の機能を実現する。すなわち、処理回路４０は、移動体作業計画作成システム１０の処理が結果的に実行されることになる移動体作業計画作成プログラムを格納するためのメモリ４３を備える。メモリ４３に記憶された移動体作業計画作成プログラムは、移動体作業計画作成システム１０の手順および方法をコンピュータに実行させるものともいえる。

プロセッサ４２は、ＣＰＵ（Central Processing Unit）、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサ、またはＤＳＰ（Digital Signal Processor）である。メモリ４３は、例えば、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、フラッシュメモリ、ＥＰＲＯＭ（Erasable Programmable Read Only Memory）、ＥＥＰＲＯＭ（登録商標）（Electrically Erasable Programmable Read Only Memory）等の、不揮発性または揮発性の半導体メモリ、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ミニディスクまたはＤＶＤ（Digital Versatile Disc）等が該当する。

なお、メモリ４３に格納される移動体作業計画作成プログラムは、例えば、ＣＤ（Compact Disc）－ＲＯＭ、ＤＶＤ（Digital Versatile Disc）－ＲＯＭなどの記憶媒体に書き込まれた状態で提供される形態でも良く、通信回線を介して提供される形態でも良い。

移動体作業計画作成システム１０は、１つの装置で構成可能である。移動体作業計画作成システム１０は、互いに異なる位置に配置された２以上の装置で構成されても良い。この場合、２以上の装置の各々は、例えば、図１４に示すハードウェア構成により実現される。２以上の装置は、互いに通信可能に接続される。移動体作業計画作成システム１０は、２以上のサーバ装置で構成されても良い。例えば、移動体作業計画作成システム１０は、処理サーバとデータサーバとで構成されても良い。

実施の形態１によると、移動体作業計画作成システム１０は、発着時刻情報と作業予定情報とを取得する取得部１３と、各移動体の移動または複数の区域における各移動体の配置についての制約条件を表す制約式を発着時刻情報と作業予定情報とに基づいて生成する制約式生成部１４と、制約式を充足する解であって、各移動体の移動についてあらかじめ設定された評価関数に基づいた解を求めることによって、構内作業計画を算出する構内作業計画算出部１５とを備える。移動体作業計画作成システム１０は、制約式生成部１４によって制約式を生成し、制約式および評価関数に基づいて構内作業計画を算出することによって、構内作業計画の条件または構内の構造に関わらず、構内作業計画を作成することができる。移動体作業計画作成システム１０は、評価関数に基づいた解を求めることによって、より効率的な構内作業計画を得ることが可能となる。以上により、移動体作業計画作成システム１０は、構内作業計画の条件または構内の構造によらず構内作業計画を作成でき、かつより効率的な構内作業計画を得ることができるという効果を奏する。

なお、構内作業計画を作成する対象である施設は、車両基地以外の施設、例えば駅などであっても良い。移動体作業計画作成システム１０は、鉄道車両の編成以外の移動体についての構内作業計画を作成しても良い。

以上の実施の形態に示した構成は、本開示の内容の一例を示すものである。実施の形態の構成は、別の公知の技術と組み合わせることが可能である。本開示の要旨を逸脱しない範囲で、実施の形態の構成の一部を省略または変更することが可能である。

以下、本開示の諸態様を付記としてまとめて記載する。

（付記１）
移動体が留置される留置区と前記移動体に対する作業を実施する作業区とを含む複数の区域を有する施設の構内における複数の前記移動体の各々の移動および前記作業のスケジュールである構内作業計画を作成する移動体作業計画作成システムであって、
各前記移動体が前記構内へ入る時刻である到着時刻と各前記移動体が前記構内から出る時刻である出発時刻とを示す発着時刻情報と、各前記移動体についての前記作業の予定を示す作業予定情報とを取得する取得部と、
複数の前記区域に含まれる区域同士の間における各前記移動体の移動または複数の前記区域における各前記移動体の配置についての制約条件を表す制約式を前記発着時刻情報と前記作業予定情報とに基づいて生成する制約式生成部と、
前記制約式を充足する解であって、各前記移動体の移動についてあらかじめ設定された評価関数に基づいた解を求めることによって、前記構内作業計画を算出する構内作業計画算出部と、
を備えることを特徴とする移動体作業計画作成システム。
（付記２）
前記制約式生成部は、前記構内作業計画の対象期間の始点にて前記移動体が存在する前記区域によって決まる前記制約条件を表す前記制約式を生成する開始時所在制約生成部を有することを特徴とする付記１に記載の移動体作業計画作成システム。
（付記３）
前記制約式生成部は、各前記区域について、前記区域への前記移動体の進入と前記区域からの前記移動体の退出との組合せについての前記制約条件を表す前記制約式を生成する移動制約生成部を有することを特徴とする付記１または２に記載の移動体作業計画作成システム。
（付記４）
前記制約式生成部は、２以上の前記移動体が同じ期間において同じ前記区域に存在する区域競合についての前記制約条件を表す前記制約式を生成する区域競合制約生成部を有することを特徴とする付記１から３のいずれか１つに記載の移動体作業計画作成システム。
（付記５）
前記制約式生成部は、前記作業予定情報に示される前記作業を各前記移動体に対して実施することについての前記制約条件を表す前記制約式を生成する作業実施制約生成部を有することを特徴とする付記１から４のいずれか１つに記載の移動体作業計画作成システム。
（付記６）
前記制約式生成部は、２以上の前記移動体が同じ期間において同じ進路に進入する進路競合についての前記制約条件を表す前記制約式を生成する進路競合制約生成部を有することを特徴とする付記１から５のいずれか１つに記載の移動体作業計画作成システム。
（付記７）
各前記区域を表す第１軸と時刻を表す第２軸とを含む平面を想定するとして、各前記区域についてある時間間隔で刻まれた時刻ごとに配置されるノードとノード同士を結ぶリンクとを有するグラフを各前記移動体について生成するグラフ生成部を備え、
前記構内作業計画算出部は、前記リンクを決定変数として、前記制約式を充足しかつ前記評価関数を最小化させる前記決定変数を解として求めることを特徴とする付記１から６のいずれか１つに記載の移動体作業計画作成システム。
（付記８）
前記評価関数は、各前記移動体の前記区域同士の間における移動の回数を表すことを特徴とする付記７に記載の移動体作業計画作成システム。
（付記９）
前記制約式生成部は、各前記移動体について、前記出発時刻から次の前記到着時刻までの期間における前記ノードおよび前記リンクを省略して前記制約式を生成することを特徴とする付記７または８に記載の移動体作業計画作成システム。
（付記１０）
前記制約式生成部は、各前記移動体について、前記出発時刻までの一定期間と、前記到着時刻からの一定期間と、前記作業が行われる期間の開始時刻までの一定期間と、前記作業が行われる期間の終了時刻までの一定期間とのうちの少なくとも１つを除いた期間における前記ノードおよび前記リンクを省略して前記制約式を生成することを特徴とする付記７から９のいずれか１つに記載の移動体作業計画作成システム。
（付記１１）
前記構内作業計画算出部によって求めた解に、２以上の前記移動体が同じ期間において同じ進路に進入する進路競合が含まれる場合に、前記進路競合が生じる進路についての前記制約条件を表す前記制約式を生成する進路競合制約生成部を備え、
前記構内作業計画算出部は、前記進路競合制約生成部によって生成された前記制約式を充足する解を求めることを特徴とする付記１から５のいずれか１つに記載の移動体作業計画作成システム。
（付記１２）
前記構内作業計画算出部は、任意に設定された時刻を前記構内作業計画の対象期間の区切りの時刻として、日単位の前記構内作業計画を算出することを特徴とする付記１から１１のいずれか１つに記載の移動体作業計画作成システム。
（付記１３）
移動体が留置される留置区と前記移動体に対する作業を実施する作業区とを含む複数の区域を有する施設の構内における複数の前記移動体の各々の移動および前記作業のスケジュールである構内作業計画を移動体作業計画作成システムによって作成する移動体作業計画作成方法であって、
各前記移動体が前記構内へ入る時刻である到着時刻と各前記移動体が前記構内から出る時刻である出発時刻とを示す発着時刻情報と、各前記移動体についての前記作業の予定を示す作業予定情報とを取得するステップと、
複数の前記区域に含まれる区域同士の間における各前記移動体の移動または複数の前記区域における各前記移動体の配置についての制約を表す制約式を前記発着時刻情報と前記作業予定情報とに基づいて生成するステップと、
前記制約式を充足する解であって、各前記移動体の移動についてあらかじめ設定された評価関数に基づいた解を求めることによって、前記構内作業計画を算出するステップと、
を含むことを特徴とする移動体作業計画作成方法。
（付記１４）
移動体が留置される留置区と前記移動体に対する作業を実施する作業区とを含む複数の区域を有する施設の構内へ複数の移動体の各々が入る時刻である到着時刻と各前記移動体が前記構内から出る時刻である出発時刻とを示す発着時刻情報と、各前記移動体についての前記作業の予定を示す作業予定情報とを取得するステップと、
複数の前記区域に含まれる区域同士の間における各前記移動体の移動または複数の前記区域における各前記移動体の配置についての制約を表す制約式を前記発着時刻情報と前記作業予定情報とに基づいて生成するステップと、
前記制約式を充足する解であって、各前記移動体の移動についてあらかじめ設定された評価関数に基づいた解を求めることによって、前記構内における各前記移動体の移動および前記作業のスケジュールである構内作業計画を算出するステップと、
をコンピュータに実行させることを特徴とする移動体作業計画作成プログラム。

１０ 移動体作業計画作成システム、１１，４１ 入力部、１２ グラフ生成部、１３ 取得部、１４ 制約式生成部、１５ 構内作業計画算出部、１６，４４ 出力部、２１ 発着時刻情報取得部、２２ 作業予定情報取得部、２３ 開始時所在制約生成部、２４ 移動制約生成部、２５ 区域競合制約生成部、２６ 作業実施制約生成部、２７ 進路競合制約生成部、３０，３１，３２，３３，３４ 楕円、４０ 処理回路、４２ プロセッサ、４３ メモリ。

Claims (13)

1. 移動体が留置される留置区と前記移動体に対する作業を実施する作業区とを含む複数の区域を有する施設の構内における複数の前記移動体の各々の移動および前記作業のスケジュールである構内作業計画を作成する移動体作業計画作成システムであって、
   各前記移動体が前記構内へ入る時刻である到着時刻と各前記移動体が前記構内から出る時刻である出発時刻とを示す発着時刻情報と、各前記移動体についての前記作業の予定を示す作業予定情報とを取得する取得部と、
   各前記区域を表す第１軸と時刻を表す第２軸とを含む平面を想定するとして、各前記区域についてある時間間隔で刻まれた時刻ごとに配置されるノードとノード同士を結ぶリンクとを有するグラフを、前記施設の構成を示す情報を基に、各前記移動体について生成するグラフ生成部と、
   複数の前記区域に含まれる区域同士の間における各前記移動体の移動または複数の前記区域における各前記移動体の配置についての制約条件を表す制約式を、生成された前記グラフと前記発着時刻情報と前記作業予定情報とに基づいて生成する制約式生成部と、
   前記制約式を充足する解であって、各前記移動体の移動についてあらかじめ設定された評価関数に基づいた解を求めることによって、前記構内作業計画を算出する構内作業計画算出部と、
   を備え、
   前記グラフ生成部は、前記移動体の移動が可能であるノード間をつないだ前記リンクと、前記区域に前記移動体がとどまることを示す前記リンクとを含む複数の前記リンクを有する前記グラフを前記移動体ごとに生成し、
   前記構内作業計画算出部は、前記グラフに含まれる前記リンクを決定変数として、前記制約式を充足しかつ前記評価関数を最小化させる前記決定変数を解として求めることを特徴とする移動体作業計画作成システム。
2. 前記制約式生成部は、前記構内作業計画の対象期間の始点にて前記移動体が存在する前記区域によって決まる前記制約条件を表す前記制約式を生成する開始時所在制約生成部を有することを特徴とする請求項１に記載の移動体作業計画作成システム。
3. 前記制約式生成部は、各前記区域について、前記区域への前記移動体の進入と前記区域からの前記移動体の退出との組合せについての前記制約条件を表す前記制約式を生成する移動制約生成部を有することを特徴とする請求項１に記載の移動体作業計画作成システム。
4. 前記制約式生成部は、２以上の前記移動体が同じ期間において同じ前記区域に存在する区域競合についての前記制約条件を表す前記制約式を生成する区域競合制約生成部を有することを特徴とする請求項１に記載の移動体作業計画作成システム。
5. 前記制約式生成部は、前記作業予定情報に示される前記作業を各前記移動体に対して実施することについての前記制約条件を表す前記制約式を生成する作業実施制約生成部を有することを特徴とする請求項１に記載の移動体作業計画作成システム。
6. 前記制約式生成部は、２以上の前記移動体が同じ期間において同じ進路に進入する進路競合についての前記制約条件を表す前記制約式を生成する進路競合制約生成部を有することを特徴とする請求項１に記載の移動体作業計画作成システム。
7. 前記評価関数は、各前記移動体の前記区域同士の間における移動の回数を表すことを特徴とする請求項１に記載の移動体作業計画作成システム。
8. 前記制約式生成部は、各前記移動体について、前記出発時刻から次の前記到着時刻までの期間における前記ノードおよび前記リンクを省略して前記制約式を生成することを特徴とする請求項１に記載の移動体作業計画作成システム。
9. 前記制約式生成部は、各前記移動体について、前記出発時刻までの一定期間と、前記到着時刻からの一定期間と、前記作業が行われる期間の開始時刻までの一定期間と、前記作業が行われる期間の終了時刻までの一定期間とのうちの少なくとも１つを除いた期間における前記ノードおよび前記リンクを省略して前記制約式を生成することを特徴とする請求項１に記載の移動体作業計画作成システム。
10. 前記構内作業計画算出部によって求めた解に、２以上の前記移動体が同じ期間において同じ進路に進入する進路競合が含まれる場合に、前記進路競合が生じる進路についての前記制約条件を表す前記制約式を生成する進路競合制約生成部を備え、
    前記構内作業計画算出部は、前記進路競合制約生成部によって生成された前記制約式を充足する解を求めることを特徴とする請求項１から５のいずれか１つに記載の移動体作業計画作成システム。
11. 前記構内作業計画算出部は、任意に設定された時刻を前記構内作業計画の対象期間の区切りの時刻として、日単位の前記構内作業計画を算出することを特徴とする請求項１から６のいずれか１つに記載の移動体作業計画作成システム。
12. 移動体が留置される留置区と前記移動体に対する作業を実施する作業区とを含む複数の区域を有する施設の構内における複数の前記移動体の各々の移動および前記作業のスケジュールである構内作業計画を移動体作業計画作成システムによって作成する移動体作業計画作成方法であって、
    各前記移動体が前記構内へ入る時刻である到着時刻と各前記移動体が前記構内から出る時刻である出発時刻とを示す発着時刻情報と、各前記移動体についての前記作業の予定を示す作業予定情報とを取得するステップと、
    各前記区域を表す第１軸と時刻を表す第２軸とを含む平面を想定するとして、各前記区域についてある時間間隔で刻まれた時刻ごとに配置されるノードとノード同士を結ぶリンクとを有するグラフを、前記施設の構成を示す情報を基に、各前記移動体について生成するステップと、
    複数の前記区域に含まれる区域同士の間における各前記移動体の移動または複数の前記区域における各前記移動体の配置についての制約条件を表す制約式を、生成された前記グラフと前記発着時刻情報と前記作業予定情報とに基づいて生成するステップと、
    前記制約式を充足する解であって、各前記移動体の移動についてあらかじめ設定された評価関数に基づいた解を求めることによって、前記構内作業計画を算出するステップと、
    を含み、
    前記グラフを生成する前記ステップでは、前記移動体の移動が可能であるノード間をつないだ前記リンクと、前記区域に前記移動体がとどまることを示す前記リンクとを含む複数の前記リンクを有する前記グラフを前記移動体ごとに生成し、
    前記構内作業計画を算出する前記ステップでは、前記グラフに含まれる前記リンクを決定変数として、前記制約式を充足しかつ前記評価関数を最小化させる前記決定変数を解として求めることを特徴とする移動体作業計画作成方法。
13. 移動体が留置される留置区と前記移動体に対する作業を実施する作業区とを含む複数の区域を有する施設の構内へ複数の移動体の各々が入る時刻である到着時刻と各前記移動体が前記構内から出る時刻である出発時刻とを示す発着時刻情報と、各前記移動体についての前記作業の予定を示す作業予定情報とを取得するステップと、
    各前記区域を表す第１軸と時刻を表す第２軸とを含む平面を想定するとして、各前記区域についてある時間間隔で刻まれた時刻ごとに配置されるノードとノード同士を結ぶリンクとを有するグラフを、前記施設の構成を示す情報を基に、各前記移動体について生成するステップと、
    複数の前記区域に含まれる区域同士の間における各前記移動体の移動または複数の前記区域における各前記移動体の配置についての制約条件を表す制約式を、生成された前記グラフと前記発着時刻情報と前記作業予定情報とに基づいて生成するステップと、
    前記制約式を充足する解であって、各前記移動体の移動についてあらかじめ設定された評価関数に基づいた解を求めることによって、前記構内における各前記移動体の移動および前記作業のスケジュールである構内作業計画を算出するステップと、
    をコンピュータに実行させ、
    前記グラフを生成する前記ステップでは、前記移動体の移動が可能であるノード間をつないだ前記リンクと、前記区域に前記移動体がとどまることを示す前記リンクとを含む複数の前記リンクを有する前記グラフを前記移動体ごとに生成し、
    前記構内作業計画を算出する前記ステップでは、前記グラフに含まれる前記リンクを決定変数として、前記制約式を充足しかつ前記評価関数を最小化させる前記決定変数を解として求めることを特徴とする移動体作業計画作成プログラム。