JP5096698B2

JP5096698B2 - スケジュール修正装置

Info

Publication number: JP5096698B2
Application number: JP2006172537A
Authority: JP
Inventors: 達広佐藤; 修一郎崎川; 豊久森田; 暢高上木
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 2006-06-22
Filing date: 2006-06-22
Publication date: 2012-12-12
Anticipated expiration: 2026-06-22
Also published as: JP2008001223A

Description

本発明は、スケジュールの作成を計算機で支援する装置、特にサービスを提供する際、サービスや各種条件の変更に合わせて、各種リソースの運用に関するスケジュールを効率良く修正する技術に関するものである。

従来のスケジュール修正装置として、鉄道の列車運行乱れ時における乗務員スケジュールの修正装置がある(特許文献１)。鉄道事業者は運行ダイヤに沿って列車の運行をおこなうが、運行乱れが発生した場合には、乱れ回復のために運行ダイヤを変更する。また、ダイヤ変更と矛盾がないように車両・乗務員の運用スケジュールも変更する。列車の運行を「サービス」とみなせば、運行ダイヤの変更案である「運転整理案」はサービスの変更スケジュールであり、車両・乗務員の運用スケジュールの変更案である「運用整理案」はサービス提供に必要なリソース(車両・乗務員)の変更スケジュールと言える。上記の修正装置は、列車運行乱れ時における運用整理案を作成するものであり、乗務員、あるいは運行ダイヤを乗務員が交代可能な駅で区切った一区間(スジと呼ぶ)を順番に選択し、乗務員をスジへ、あるいはスジを乗務員へ順次割当て運用整理案の全体を作成する。割当て中に複数の乗務員が候補として存在する場合には、所定の評価式に基づき各乗務員毎の割当ての適切さを計算し、良好のものを割当てる、更に最も適切な乗務員が複数ある場合には、途中案のコピーを複数生成し、各コピーに対してそれぞれ異なる候補を割り当て、複数案を同時に保持しながら割り当てを並行に進めている。

特開２００４−２２４２９０号公報

事故や機材の故障といった実施当日の外乱などにより提供サービスの内容や各種条件に狂いや変更が生じた場合には、関連するリソースのスケジュールを迅速に修正することが求められる。一般的に、リソースの運用変更においてはサービスの変更時刻を睨みながら関係者間の調整、連絡、準備等の各種手配を行う必要があり、スケジュールの修正自体は手配作業が可能な時刻までに完了させなければならない。また、スケジュールの修正にあたっては、不具合を生じたスケジュールを物理的に実施可能とするのは勿論のこと、種々の評価指標に基づいて「良い」と評価されるスケジュールを組み立てることが望ましい。例えば、分野や業種を問わず普遍的に重要な評価指標として「元のスケジュールからの変更の少なさ」が挙げられる。従来技術においては、これらの点については考慮されていなかった。

本発明の目的は、サービスや各種条件の変更に伴う各種リソースの運用に関するスケジュールを効率良く修正可能なスケジュール修正装置、その方法、及びそのプログラムを提供することにある。

上記目的を達成するため、本発明においては、サービス提供のためのリソースの運用に関するスケジュールを修正するスケジュール修正装置であって、サービスの実施予定を示すサービススケジュールと、サービスを実施するためのリソースの運用予定を示すリソーススケジュールと、サービススケジュールの変更を示すサービス変更情報とから、リソースを割当てる最小単位である単位サービスと単位サービス間の可能な実施順序とリソースの単位サービスへの割当並びに割当順序とを表わす運用ネットワークを生成する運用ネットワーク作成部と、運用ネットワークと前記リソースの単位サービスへの割当に関する制約条件を示す割当制約情報とを用いて、検出されたリソーススケジュールの実行可能性違反を解消し、リソーススケジュールの実行可能解を生成する実行可能解生成部とからなるスケジュール修正装置、方法、及びプログラムを提供する。

また、本発明にあっては、上記構成に加え、リソーススケジュールの修正を完了すべき限界時刻である締切時刻を設定する締切時刻設定部を有するスケジュール修正装置を提供する。本発明は、更に加えて、事前設定した評価指標値を改善するように運用ネットワークの構造を締切時間まで繰返し改良することにより、実行可能解生成部で生成した実行可能解の実行可能な代替案を生成するスケジュール改良部を有するスケジュール修正装置等を提供する。

本発明のスケジュール変更装置によれば、サービスを提供するにあたり必要とされる各種リソースに関する運用スケジュールを、サービスや各種条件の変更に合わせて効率良く修正することができる。

特に、実行可能性に関わる条件違反の解消だけを目的として運用ネットワークを部分的に修正して実行可能解を得るので、元のスケジュールをできるだけ変更することなく、効率良く実行可能解を得ることができる。また、実行可能解の生成後、設定した締切時刻まで実行可能解を繰返し修正することにより評価指標の値を改善した代替案を生成するので、残された時間の長さに応じたスケジュール修正、及び完了時間の事前把握が可能になる。また、評価指標の値が改善されるように運用ネットワークを繰り返し改良して代替案を生成するので、任意の評価指標を考慮した修正スケジュールを作成することができる。更に、複数の代替案が得られるので、スケジュール修正の担当者に対して複数の代替案を提示することが可能になる。

以下、本発明の具体的な実施例を鉄道分野における乗務員運用整理案作成システムを例示して説明するが、本発明は、鉄道以外の他のサービスにおけるスケジュール管理、例えば、物流、介護、福祉などのサービス、更には電力保守、エレベータ等の機器管理などのサービスのスケジュール管理にも適用できるものである。

以下では本発明の第一の実施形態である鉄道分野における乗務員運用整理案作成システムについて、図１から図１５を用いて説明する。

図１は乗務員運用整理案作成システムの機能並びに機器構成を表す図である。乗務員運用整理案作成システムは計算機システムであり、処理装置0110と、記憶装置0120と、入力装置0130と、表示装置0140ととから構成される。記憶装置0120と処理装置0110は同一計算機の構成要素であっても良いし、図示しない通信ネットワークを介して接続する、相異なる計算機の構成要素であっても良い。

記憶装置0120には、列車の運行をサービスと解釈し、その提供スケジュールである運行ダイヤを表すサービススケジュール0121、乗務員をサービス提供に必要なリソースと解釈し、その運用スケジュールである乗務員運用計画を表すリソーススケジュール0122、サービススケジュールの変更を表すサービス変更情報を蓄積するサービス変更テーブル0123、サービス変更及びそれに伴うリソース変更に必要な手配時間を設定する手配時間テーブル0124、乗務員(リソース)の運行ダイヤ（サービス）への割り当て、あるいはその逆における制約条件（割当制約情報）を設定する割当制約テーブル0125、修正されたリソーススケジュール（運用整理案）を評価するための評価指標を設定する評価指標テーブル0126が少なくとも格納される。

入力装置0130は、運用整理案の作成担当者(運用指令員と呼ぶ)によるシステムの操作に用いる装置であり、少なくともキーボード及びマウス等のポインティングデバイスを備える。表示装置は、運行ダイヤ、乗務員運用計画等、運用指令員による運用整理案作成作業に必要な情報を提示するために用いる装置である
処理装置0110が内蔵するメモリには、運用整理案作成の締切時刻を設定する締切時刻設定部0111、サービススケジュールとその変更内容を加味してリソーススケジュール（乗務員運用計画）をネットワーク形式のデータ表現に変換する運用ネットワーク作成部0112、リソーススケジュールの実行可能性に関わる条件違反を検出する違反検出部0113、条件違反のない実行可能なスケジュール（運用整理案）を構成する実行可能解生成部0114、設定された評価指標に沿って評価値の高いスケジュールを生成するスケジュール改良部0115、がプログラムとして格納され、処理装置0110によって実行される。ワークエリア0116はプログラム実行の作業領域として使用されるメモリ上の領域である。上記のプログラムは、記憶装置0120に格納し、この記憶装置0120の起動装置あるいは図示しない通信ネットワークを介して処理装置0110に伝送した上で実行される。

図１に示した乗務員運用整理案作成システムは、列車の運行を管理する列車運行管理システムの部分機能（サブシステム）である。図２に列車運行管理システムの機器構成例を示す。列車運行管理システムは、広域エリアネットワーク0260に接続された２つのサブシステムから構成される。現場サブシステムは、走行中の列車との情報送受をおこなう車上通信装置0270、信号機や転轍機等を制御するための信号制御装置0280、駅、車両基地、乗務員区所といった現場の各部署と中央の統制部署との間で各種の情報をやり取りするための現場情報端末0290を含む。

一方、中央システムは、列車走行を管理する列車指令員が列車の走行を監視したり、必要に応じて信号設備を直接制御したり、或いは運行が乱れた際に運行ダイヤを修正するための列車指令員端末0210と、運用指令員が車両や乗務員の列車への充当状況を監視したり、充当可能な車両／乗務員を現場に問い合わせたり、或いは車両・乗務員の整理案を作成するための運用指令員端末0220と、端末を介した各指令員からの指示や、現場サブシステムからの列車位置情報の送信といった特定のイベントに基づいて必要な処理を実行するホスト計算機0230、各種演算に必要な情報を格納するストレージ装置0240とから構成される。

図１の乗務員運用整理案作成システムにおける処理装置0110は、図２のホスト計算機0230に対応する。処理装置0110に含まれる各機能部はホスト計算機により実行される処理の一部である。同様に、記憶装置0120はストレージ装置0240に対応し、記憶装置0120に含まれる各情報はストレージ装置0240に格納されるデータの一部である。また、入力装置0130及び出力装置0140は併せて運用指令員端末0220に対応する。

図３は、本発明における修正スケジュールの作成処理を示す処理フロー図である。以下ではこの処理フロー図に基づいて本実施例における乗務員運用整理案の作成処理を詳細に説明していく。なお、図３の処理は、運用指令員が図１の入力装置0130を介して運用整理案の作成を指示する、あるいは同じく図１の記憶装置0120のサービス変更テーブル0123にサービス変更情報（運行ダイヤの変更情報）が格納されるといった、あらかじめ決められた何らかのイベントをトリガーとして開始されるものとする。

まず、ステップ0301において図１の記憶装置0120に格納されている情報を読込み、処理装置0110のワークエリア内に配置する。以降の説明では、特に断らない限り必要な情報はワークエリアから取得するものとする。次にステップ0302において、締切時刻設定部0111が運用整理案作成の締切時刻の設定をおこなう。締切時刻は、運用指令員が入力装置0130を介して直接指定するか、あるいは機械的に算出することとしても良い。どちらを実行するかは事前に決めておいても良いし、運用整理案を作成する度に図１の表示装置0140を介して運用指令員に問いかけをおこない、設定方法を運用指令員に判断させることとしても良い。いずれにせよ、得られた締切時刻をワークエリアに格納して以降の処理で使用できるようにする。

締切時刻を計算により求める場合は、まず入力データとして図１のサービススケジュール（運行ダイヤ）0121、その変更内容を表すサービス変更テーブル0123、及び手配時間テーブル0124を読込む。図４は運行ダイヤの例である。これは、横軸に時間、縦軸に列車位置をとったグラフ形式で運行ダイヤを表現したものである。この中で、ひと続きの斜線(例えば0401）が列車1個の走行スケジュールを表している。斜線0401は「列車１」の走行スケジュールであり、駅Ｂを始発駅として駅Ｃを経由し駅Ａへ向かうものである。また、各斜線のアルファベットは、乗務員が交代可能な駅で走行スケジュールを区切った部分を識別するために便宜的に付けた記号である。例えば先の「列車１」の場合は、駅Ａ，Ｂ，Ｃにおいて乗務員交代が可能であるとして、駅Ｂから駅Ｃ、及び駅Ｃから駅Ａの２つの区間が存在し、それぞれ「a」及び「b」という記号が与えられる。これらの区間はリソースである乗務員を充当する上でのサービス（運行ダイヤ）の最小単位を意味している。以降ではこのサービスの最小単位を「単位サービス」と呼ぶこととする。

図５は、サービス変更テーブル0123の例である。これはサービスの変更内容を表す情報（サービス変更情報）であり、図５では、各列車毎に変更の種類及びその具体内容が示されている。例えば変更番号「１」は、列車「Ａレ」を対象とした順序変更であり、その内容は次の通りである「元の運行ダイヤにおいてはＡレはＱ駅において列車Ｃレの後続列車であったが、これをＣレの前に出発させる」。主な運行ダイヤの変更としては、この「順序変更」の他に、列車の着発時刻を変更する「時刻変更」、端末駅での折り返し列車を変更する「折り返し変更」、元の運行ダイヤに含まれない新たな臨時列車を仕立てる「臨時列車設定」等が挙げられる。

図６は、手配時間テーブル0124の例である。これは各変更種類毎に、その手配作業に必要な時間を設定したものである。この例では、新たな乗務員を確保するために現場との調整に時間を要する臨時列車設定(60分)の方が、当該列車に乗務中の乗務員への連絡だけで手配が済むことが多い時刻変更(15分)よりも手配時間が長く設定されている。なお、手配時間テーブル0124は図６のようにダイヤ変更種類だけで分類することに制限されるものではなく、列車の種類や実施時間帯(ラッシュ時間帯等)等を考慮してさらに細分化して定義しても良い。

上記の各データを読込んだ後に、次の手順で締切時刻を算出する。まず、サービススケジュール0121とサービス変更テーブル0123を参照し、各変更毎にその実施時刻を特定する。次に、各変更の実施時刻から手配時間テーブル0124に設定された手配時間を引いた時刻を算出する。最後に、先に算出した時刻の最小値を計算し、それを締切時刻とする。すなわち、変更に必要な手配時間を加味して各変更毎の個別の締切時刻を算出した上で、その中で時間的に最も早いものを全体の締切時刻とする。

図７は、締切時刻算出部0111で実行される締切時刻設定ステップ0302の実行例である。グラフ形式で表現した運行ダイヤの上に変更を「×」記号で表記している。ここでは説明のわかりやすさのために各列車の走行スケジュールを表す斜線は省略している。「×」記号から伸びる矢印は、変更時刻から変更手配に要する時間を差し引くことを意味しており、矢印の先端の位置が手配時間を加味した締切時刻に対応する。この例で時間的に最も早いものは「臨時列車設定」の締切時刻であり、これが全体の締切時刻となる。

図３に戻り運用整理案作成処理の説明を続ける。ステップ0302で締切時刻を設定した後に、ステップ0303において運用ネットワーク作成部0112が運用ネットワークの生成をおこなう。運用ネットワークは、リソーススケジュール（乗務員運用計画）をネットワーク、すなわち「ノード」と呼ばれる複数の点を「リンク」と呼ばれる線で結んだ図形として表現したデータである。運用ネットワークのデータ構造についてさらに詳しく説明する前に、図８の乗務員運用計画の例を用いてリソーススケジュール0122の概要を説明する。

図８は図４の運行ダイヤに対する乗務員運用計画の一例であり、図の最上段を除く各行が乗務員１人分の乗務スケジュールを表している。各乗務スケジュールはその乗務員が従事する単位サービス（ここでは列車の走行スケジュールを乗務員交代可能駅で分割したもの）を実施順序に沿って並べたものとして表現される。この例では横方向を時間軸としてサービススケジュールで規定された実施時間帯に対応した位置に単位サービスが配置されており、単位サービスの開始時刻や実施順序等が視覚的にわかるように工夫されている。例えば「乗務員ア」のスケジュールは、「a」、「b」、「g」、「h」の順序でこれらの単位サービス（列車運行）に従事することが読み取れる。

図９は、運用ネットワーク作成部0112によって作成される運用ネットワークの例である。この例は、サービス変更テーブル0123中のサービス変更情報を考慮せず、図８の乗務員運用計画を運用ネットワークにそのまま変換したものである。運用ネットワークはノードとリンクとから構成される。運用ネットワークの各ノードはサービススケジュールにおける単位サービスに対応しており、図９ではノードを表す丸印の中に対応する単位サービスのアルファベットが記されている。一方、運用ネットワークのリンクは２種類存在する。ひとつは、リソースの単位サービスへの割り当てとその順序を表すものであり、リソーススケジュールにおいて同一のリソース（ここでは乗務員）が割り当てられ、なおかつその順序が連続する２つの単位サービスに対して、割り当て順序が早いものに対応するノードから割り当て順序が遅いものに対応するノードに対してこの向きにリンクを設定する。この種類のリンクを「実リンク」と呼ぶ。図９の例では実線のリンクが実リンクを表す。なお、この「実リンク」は、「第二の有向リンク」とも呼ばれる。

第二の有向リンクである実リンクは、どのリソースに関するものかを識別するため、リソースに対応する識別ＩＤを値として持つ。図の例では、記号「ア」「イ」「ウ」が乗務員を表す識別ＩＤである。運用ネットワークにおいて、同じリソースの識別ＩＤを持つ実リンクを辿って得られた単位サービスの系列が、そのリソースの運用スケジュールを表す。例えば図９の場合、識別ＩＤ「ア」を辿って得られる単位サービスの系列「a」「b」「g」「h」が「乗務員ア」のスケジュールであり、これは運用ネットワーク作成の元となった図８の乗務員運用計画の情報と一致する。

さて、運用ネットワーク作成部0112が運用ネットワークを実際に作成する際、サービス変更テーブル0123のサービス変更情報を加味する。サービス変更テーブル0123に「列車の休止」といったサービスを取り消す類のサービス変更情報が含まれる場合、それに該当する単位サービスは運用ネットワークのノードに含めず、かつ実リンクはその単位サービスを飛び越えて設定する。すなわち、ある単位サービスa,b,cがリソーススケジュールにおいてこの順番で実施するものとされており、変更により単位サービスbが取り消された場合、bに対応するノードは生成せず、なおかつbを飛び越えてaとcの間にaからcの向きに実リンクを設定する。

これとは逆に、「臨時列車設定」といった新たなサービスを追加する類のサービス変更情報がある場合は、それに該当する単位サービスを運用ネットワークのノードに追加することとし、なおかつ実リンクが設定された任意の単位サービスの組を選択して、追加したノードを経由するように実リンクの張替えをおこなうこととする。すなわち、ある単位サービスaが追加された場合、任意の単位サービスb,c、及びbからcへの実リンクを選択し、その実リンクを一旦削除した後に、aを経由するように「bからa」、「aからc」の2本の実リンクを設定しなおす。

サービス変更情報に基づくこのようなサービスの取消、追加に対して、以上のように設定した実リンクは、物理的に実施することが不可能な、いわば違反リンクとなる可能性が高い。しかし、本実施例においては、この違反リンクは図３の全体処理フローにおける違反検出ステップ0304で検出され、実行可能解生成ステップ0305において解消されることとなる。

図９におけるもう一つのリンクは、単位サービスの間に設定可能な実施順序を表すものであり、例えばある単位サービスaとbについて、aを実施した後に引続きbを実施することが可能である場合に、aからbの向きに設定する。この種類のリンクを「可能リンク」と呼ぶ。図９の例では点線のリンクが可能リンクを表す。この「可能リンク」は「第一の有向リンク」とも呼ぶ場合がある。なお、実施可能かどうかの判定は、少なくともサービススケジュールで規定された単位サービスの実施時刻を考慮しておこなう。すなわち、単位サービスaとbについて、（aの終了時刻）＋（任意の正の間合い時間）＜＝（bの開始時刻）なる関係が成立する場合に「a⇒b」なる順序で実施が可能と判断してaからbの向きに可能リンクを設定する。この判定は左記の時間的な関係だけでなく、必要に応じてその他の情報を加味しておこなっても良い。例えば本実施例においては、各単位サービスはどの駅でサービスを開始し（乗務開始駅）、どの駅でサービスを終了するか（乗務終了駅）という場所に関する情報を持っていることから、例えば単位サービスaとbについて、先の時間的な関係が成立し、さらにaの乗務終了駅とbの乗務開始駅が同じ場合に限りaからbの向きに可能リンクを設定する（これが成立しない場合、場所が不一致なので連続して実施することは物理的に不可能）。

なお、判定に際して利用する単位サービスの実施時刻や場所などの各種情報は、サービス変更テーブル0123で設定された内容を加味・適用した変更後のサービススケジュールから取得するものとする。例えば変更前のサービススケジュールにおいて、ある単位サービスaの終了時刻が「10:00」、もうひとつの単位サービスbの開始時刻が「10:05」である場合、変更がなければaからbの向きに可能リンクを設定可能であるが（a,bの実施場所は同じで、間合い時間を0とする）、変更によりaの終了時刻が「10:10」とされた場合には、時刻が逆転するため可能リンクは設定不可となる。

図３に戻り運用整理案作成処理の説明を続ける。ステップ0303で運用ネットワーク作成部0112がサービス変更情報を加味して運用ネットワークを生成した後に、ステップ0304において図１の違反検出部0113を用いて運用ネットワークに含まれる違反の検出をおこなう。検出対象の違反は運用整理案（リソーススケジュール）が実施可能であるための条件に関するものであり、２種類存在する。この２種類の条件は、後で詳述する実施可能解を得るための条件でもある。ひとつは単位サービスの実施順序に関わる条件であり、可能リンクが存在しないノード間に設定された実リンクを違反とみなす。２つのノードの間に可能リンク（第一の有向リンク）が存在しなければ、それらの単位サービスは時刻の制約などから連続して実施することが物理的に不可能である。したがって、それらを連続しておこなうことを意味する実リンク（第二の有向リンク）の設定は矛盾となるため、これを違反として検出する。この違反に関する条件を以降は「順序条件」と呼ぶ。

検出するもう一種類の違反は、単位サービスへのリソースの割当てに関するものであり、図１の割当制約テーブル0125を参照し、そこで設定された条件に矛盾する割当てを違反として検出する。ここで、リソースＡが単位サービスaに割り当てられるとは、リソースＡを値とする実リンクが存在し、なおかつその始点もしくは終点のいずれかが単位サービスaを表すノードである場合を指す。

図１０は、割当制約情報を示す割当制約テーブルの例である。横軸が乗務員の識別ＩＤ、縦軸が単位サービスからなるマトリックス形式のデータであり、乗務員と単位サービスの組合せに対して割り当ての可・不可を表すものである。例えば、「乗務員ア」と単位サービス「a」の組合せは記号「○」であり、これはその組合せでの割当が可能であることを意味する。一方、「乗務員イ」と単位サービス「a」の組合せは記号「×」であり、その割り当てが不可能であることがわかる。なお、図１０は割当制約テーブルの一例を示したに過ぎず、かならずしもこの形式に制約されるものではない。例えば、図１０のように可能・不可能な割り当てを示すのではなく、指定した組合せで必ず割り当てをおこなうことを意味するものや、単位サービスに複数のリソースを割り当てる場合のリソースの可能な組合せを指定するもの、同じく複数のリソースを割り当てる場合のリソース数の上限値や下限値など、リソースと単位サービスの割り当てに関わる制約条件であり、かつ違反を正しく検出可能なものであればどのような情報・形式でも良い。以降ではこの割り当てに関わる条件を総称して「割当条件」と呼ぶ。

さて、図３に戻り運用整理案作成処理の説明を続ける。違反検出部0113がステップ0304で運用ネットワークに含まれる違反を検出した後に、実行可能解生成部0114がステップ0305で運用整理案の実行可能解を生成する。ここで、実行可能解とは物理的に実施可能なリソーススケジュールを意味し、より具体的には上述した順序条件と割当条件の違反を含まない運用ネットワークを指す。本実施例では、そのような運用ネットワークを、図３のステップ0303で得た違反含みの運用ネットワークの構造を修正することにより生成する。修正の基本的な考え方は、ステップ0304で得た違反に関連する実リンクを他のリソースの実リンクと交換するというものである。すなわち、ある実リンクと別の実リンクを選択し、リンクのつなぎ先(終点)を相互に交換することにより違反を解消する。ここで、違反に関連する実リンクとは、順序条件の違反であれば違反している実リンクそのものである。一方、割当条件の違反であれば、違反するノードを始点あるいは終点とし、なおかつ違反リソースを値とする実リンクを指す。以降ではこれらの違反に関連する実リンクのことを単に「違反リンク」と呼ぶこととする。

図１１は、実行可能解生成ステップ0305において実行される、実リンクの交換による運用ネットワーク構造の修正の例である。aからhまでの8個のノードから構成される運用ネットワークであり、説明のわかりやすさのため実リンクの識別ＩＤの値は省略しているが、交換前のネットワークにおいては、aからdまでをつなぐ4本の実リンクの識別ＩＤの値は「乗務ア」、eからhまでをつなぐ4本の実リンクの識別ＩＤの値は「乗務イ」である。これに対して、「乗務ア」の実リンク「b⇒c」と「乗務イ」の実リンク「f⇒g」を交換した結果が図１１中の矢印の下である。「b⇒c」と「f⇒g」の終点を相互に交換して「乗務ア」の実リンク「b⇒g」と「乗務イ」の実リンク「f⇒c」を新たに設定すると共に、交換したノード以降につながる全ての実リンクの値を互いに交換する。この操作は、「乗務ア」のノードc以降のスケジュールと、「乗務イ」のノードg以降のスケジュールとを全て入れ替えることを意味する。

上記の交換操作にあたっての交換相手の選択基準は以下の通りである。(1)交換により違反リンクの条件違反が解消される、かつ(2)交換することにより新たな違反が発生しない。上記の基準を満足する実リンクと交換操作をおこなうことにより、１回の交換で違反件数を少なくとも１つは確実に削減することができる。したがって、これを連続的に実行することができれば、最終的に違反のない運用ネットワーク、すなわち実行可能解を確実に得ることができる。

ただし、上記の基準を満たす実リンクが常に存在する保証はないため、交換操作を連続して適用する中で、交換相手の実リンクが存在しない場合が想定される。そこで、その場合に限って選択基準を緩和し、基準(1)だけを満たす相手を選択して交換操作を実行する。これにより新たな違反が発生することになるが、その新たな違反に関係する実リンクを対象として再び交換操作をおこなう。その結果、再び新たな違反が生じる場合には、同様に新たな違反を対象としてさらに交換操作をおこなう。このように交換操作を繰り返せばいつかは違反が解消されることを期待して違反を他の実リンクへ次々に移していくことを違反解消の基本的な考え方とする。以降では、条件(1)(2)の双方を満たす実リンクとの交換操作を「通常交換」、条件(1)のみを満たす実リンクとの交換操作を「強制交換」と呼ぶ。なお、初期状態において違反リンクが複数ある場合は、それらの中で時間的に最も早い、すなわちリンクの始点に対応する単位サービスの終了時刻が最も早いものから順番に選択して解消をおこなうこととする。

以上説明した実行可能解生成ステップ0305における処理の考え方を整理したものが図１２に示す実行可能解生成処理の処理フロー図である。まずステップ1301において、交換操作により新たに生じたものも含めて全ての違反を解消したかどうかをチェックする。その結果、全ての違反を解消した場合には全体処理を終了する。違反が残っている場合はステップ1302へ進み、時間的に最も早い、すなわち始点の終了時刻が最も早い違反リンクを選択し、これを違反リンクＡとする。次にステップ1303では違反リンクＡと交換する相手リンクの候補を抽出し、ステップ1304では、抽出結果の中に先の選択基準(1)と(2)の双方を満足する、すなわち違反を生じずに交換可能な候補が含まれているかを判定する。そのような候補が存在する場合にはステップ1305へ進み、その中から候補をひとつ選択して通常交換を実施し、再びステップ1301へ戻る。そのような候補が存在しない場合はステップ1306へ進み、選択基準(1)のみを満足する候補をひとつ選択して強制交換を実行する。その後は再びステップ1301へ戻り処理を繰り返す。このように「順序条件」、「割当条件」の２つの条件違反の解消だけを目的としてスケジュールの部分的な修正により実行可能解を生成する方法であることから、元のスケジュールをできるだけ変更することなく妥当な整理案を効率良く得ることができる。

図３に戻り運用整理案作成処理の説明を続ける。実行可能解生成部0114に相当するステップ0305で実行可能解、すなわち条件違反のない運用ネットワークを生成した後に、スケジュール改良部0115であるステップ0306において代替案の生成をおこなう。

スケジュール改良部0115で実行される代替案の生成は、ステップ0305で得られた実行可能解を表す運用ネットワークを出発点として、図１の評価指標テーブル0126に格納された評価指標の値が改善されるように運用ネットワークを繰り返し修正することを基本的な考え方とする。図１３は評価指標テーブルの例である。これは乗務員運用整理案を作成する際に考慮すべき評価指標の一例であり、最上段を除く各行が１個の評価指標に対応している。これらは設定可能な評価指標を一覧として示したものであり、整理案作成において実際に考慮させるかどうかは、各行の「使用」欄の設定値に基づいて決定する。すなわち、「使用」欄が「○」であればその評価指標を考慮し、「×」であれば考慮しない。複数の評価指標を考慮する場合は、各評価値に重みを掛けて足し合わせることにより総合評価値を算出する。各行の「重み」欄はその際に使用する評価指標の重み設定値である。

スケジュール改良部0115の代替案生成ステップ0306における運用ネットワークの修正方法は、「識別ＩＤの値が異なる任意の２つの実リンクを選択し、順序条件と割当条件に違反しない限りにおいて両者を対象とした交換操作をおこなう」というものである。２つの実リンクの組合せは何通りもあり、それぞれについて(可能であるならば)交換操作をおこなうことで異なる代替案を得ることができる。実リンクの全ての組合せについて交換操作を施して得られた代替案の集合を「近傍」と呼ぶ。図１４は近傍の生成例である。この図から明らかな通り、近傍は任意の２つのリソースのスケジュールを、違反が生じない限りにおいて途中から全て入れ替えることで得られる代替案の集合に対応している。

図３の代替案生成ステップ0306は、(1)暫定解に対して近傍を生成し、(2)近傍の各要素に対して評価値を算出し、(3)その中で評価値が最も良いものを抽出し、(4)抽出した解の評価値が暫定解よりも良ければその解をあらためて暫定解とする、ことを基本的な考え方とし、これを最初に設定した締切時刻を過ぎる、あるいは暫定解を更新する見込みがなくなるまで順次繰り返すことにより代替案を次々に生成していく。

以上、スケジュール改良部0115で実行される代替案生成ステップ0306の考え方を整理したものが図１５に示す代替案生成処理の処理フロー図である。まずステップ1501において、初期解、すなわち図３の実行可能解生成処理0305で得られた解を暫定解Ｘに設定する。次にステップ1502において暫定解Ｘの近傍を生成し、これをＮ（Ｘ）とする。さらにステップ1503では近傍Ｎ（Ｘ）の各要素の評価値を算出する。ステップ1504では、Ｎ（Ｘ）の中で評価値が最も良い解を抽出し、それをＹとする。ステップ1505では、ＹはＸよりも評価値が良く、なおかつ現在時刻は締切時刻以内であるかを判定する。これがYesであればステップ1506へ進み、Ｙを改めて暫定解Ｘとして再びステップ1502へ戻る。ステップ1505の判定結果がNoの場合は、ステップ1507において暫定解を最終結果として出力して全体処理を終了する。
ここで、ステップ1505の終了判定は、Ｙが暫定解Ｘよりも評価値が悪い場合には「暫定解を更新する見込みがない」として即座に処理を終了することとしているが、その代わりに別の基準に基づいて暫定解の更新見込みを判断しても良い。例えば暫定解を更新できなかった回数を数え、その回数が基準値を上回ったら「見込みなし」と判定する等である。また、暫定解の候補であるＹの選択方法についても、評価値が最も良いものを選択することに限定するものではなく、例えば近傍の各要素に対して評価値に応じた選択確率を与え、その確率に基づいてランダムに選択する、といった方法でも良い。ただし、そのような選択方法を採用した場合には、処理結果を出力する際に評価値が最も良い解を必要とするため、これを別途記憶しておく。さらには、暫定解は必ずしも１個に限定されるものではなく、複数の暫定解を同時に保持するようにしても良い。

図３に戻り運用整理案作成処理の説明を続ける。ステップ0306において評価値の高い代替案を生成した後は、ステップ0307において、運用ネットワーク形式の代替案を運用整理案の形式に戻した上で図２の運用指令員端末0220を介して運用指令員へ提示した後に全体処理を終了する。

なお、本実施例は、図３の処理フローを最後まで実行した後で最終的に得られた最も評価値の良い代替案を出力することとしているが、ステップ0305の実行可能解生成処理が終了した段階で実行可能解を、さらには代替案生成の繰り返し処理の途中で新たな代替案が生成される度にその代替案を、図２の運用指令員端末0220を介して運用指令員へ提示することとしても良い。また、運用指令員が代替案生成の繰り返し処理における任意のタイミングで、図２の運用指令員端末0220を介して処理の停止、あるいは途中結果の出力を指示し、これを受けてその時点で得られた代替案を提示するようにしても良い。

第一の実施例では、実行可能性に関わる条件違反の解消だけを目的として、運用ネットワークの構造を修正することにより実行可能解を生成した。この運用ネットワークの構造の修正は、(1)違反に関連するネットワークのリンクと他のリンクとを選択し、両者の終点を相互に交換し、かつ両者の終点を起点としてリンクを辿り、リンクに設定されたリソースの識別ＩＤを相互に交換すること、また(2)交換操作により少なくとも１つの違反が解消すると共に、新たな実行可能性違反が生じないものの中から他のリンクを優先的に選択し、該当がない場合には、交換操作により少なくとも１つの違反が解消されるものの中から選択した。

この第一の実施例によれば、実行可能性に関わる条件違反の解消だけを目的として運用ネットワークを部分的に修正するので、元のスケジュールをできるだけ変更することなく、かつ効率良く実行可能解を得ることができる。

次に、本発明の第２の実施形態について、図１６〜１８、数式１〜６を中心に用いて説明する。本発明の第２の実施形態も、第１の実施形態と同じく運行乱れ時の乗務員スケジュールの修正をおこなう乗務員運用整理案作成システムである。機能構成や入出力データは図１、図２に示す第１の実施の形態と全く同一であり、整理案作成の全体処理フローも図３に示す第１の実施形態と同じである。第１の実施の形態と異なるのは、図３の全体処理フローにおけるステップ0305の実行可能解を生成する部分の処理方法であり、実行可能解を数理的演算手法の一種である制約プログラミングを用いて生成するものである。

制約プログラミングは、数理的に表現された制約条件の集まりとして定式化された問題を対象として、制約伝播と呼ばれる制約式同士の相互作用により変数の取り得る値の集合（ドメインと呼ぶ）を絞り込んでいく探索手法である。(1)非線形や論理型、あるいは問題独自の多様な制約条件を柔軟に扱うことができる、(2)解探索の途中で制約条件を動的に追加したり、他の探索手法との組合せが比較的容易である、といった性質を備えており、大規模で複雑な条件を持つ離散的な問題に対して有効な手法とされている。

図１６は、制約プログラミングを用いた実行可能解作成処理の処理フロー図である。まずステップ1601において、実行可能解作成を離散的な問題として扱うために、数理的に表現された制約条件と目的関数の集まりから構成される数理モデルを生成する。本問題における数理モデルを以下に説明するが、その準備としてまず各種記号の定義をおこなう。なお、記号の後に付加された「^」は後に続く記号が上添え字、「_」は同じく下添え字であることを意味する。

(1)集合
・Ｔ:全ての単位サービスの集合 {0,1,...,n}
※0はサービススケジュールに含まれない特別な要素とする。
・Ｒ:全てのリソースの集合 {1,...,m}
・Ｔ_r:リソースrを割当可能な単位サービスの集合(⊆Ｔ）
※0は必ず含む
・Ｓ_r:リソースrの開始可能単位サービスの集合(⊆Ｔ_r）
・Ｅ_r:リソースrの終了可能単位サービスの集合(⊆Ｔ_r)
(2)ネットワーク
・Ｇ：拡張可能リンクネットワーク
※ノード集合をＴ，リンク集合をＥ⊆Ｔ×Ｔとするグラフ
※リンク（0,i） ∀i∈Ｓ_r 及び
リンク（i,0） ∀i∈Ｅ_r （∀r∈Ｒ）はＥに必ず含まれる
※その他のリンクは、運用ネットワークの可能リンクと一致する
(3)定数
・Ｃ_ij：実リンク(i,j)の設定コスト
・1 … リンク(i,j)がＥの要素でないとき(ただし、i≠jとする）
・0 … 上記以外
・Ｌ_i：単位サービスiのリソース使用量の下限（≧０）
・Ｕ_i：単位サービスiのリソース使用量の上限（≦Ｌ_i）
※Ｌ_0=0, Ｕ_0 = (リソース数)とする
(4)論理記号
・A⇒B : AならばB
・A||B : AまたはB
・A&&B : AかつB
・Or{A_k} (k=1,...,n) : A_1 || A_2 || ... || A_n
・And{A_k} (k=1,...,n) : A_1 && A_2 && ... && A_n
(5)決定変数
・ｘ_ri ：値(リソース)をr、始点ノードをiとする実リンクの終点ノード
※自分自身へのリンク（ｘ_ri = i）を許す。

⇒この場合、リソースrを単位サービスiに割当てないことを意味する
※ｘ_r0はリソースrが最初に実施する単位サービス(開始サービス)を意味する
※ｘ_ri=0を満たす単位サービスiは、リソースrが最後に実施する単位サービス(終了サービス)を意味する
※ｘ_riの初期ドメイン(とりうる値)は以下の通り
−ｘ_ri∈Ｓ_r∪{i} … i=0のとき
−ｘ_ri∈Ｔ_r∪{i} … i∈Ｅ_rのとき
−ｘ_ri∈Ｔ_r∪{i}/{0} … 上記以外のとき

・ｙ_ri ：リソースrの単位サービスiへの割当識別用変数
・1 … リソースrを単位サービスiに割当てる
・0 … それ以外
・ｚ_i ：タスクiに割当られたリソース数
※ｚ_iの下限値はＬ_i、上限値はＵ_iにそれぞれ等しい
ここで、決定変数ｘ_riの値を定めることは、運用ネットワークの実リンクを設定することに対応する。ただし、リソースの開始及び終了サービスを識別するために、特別な単位サービスのノード0を導入し、0と他のノードとの間に対しても実リンクを設定可能としている。また、自分自身への実リンク（自己ループ）により、特定のリソースによって実施されない単位サービスを表現する。

あるリソースrのスケジュールは、ノード0を出発点として決定変数ｘによって定められた実リンクを辿り、再びノード0に戻ってくる閉路において、0以外のノードを閉路に現れる順番に並べた系列として表現することができる。図１７は、あるリソースrのスケジュール表現の例である。黒丸のノードが特別なノード0であり、これを出発点として再び0に戻る閉路は図の実線の矢印で表される。これより、リソースrのスケジュールはノード系列{1,2,5,7,8,12}であることが見て取れる。閉路に含まれないその他のノードには自己ループの実リンクが設定されており、リソースrによっては実施されないことを表す。

上記の記号の定義の下で、リソーススケジュールの実行可能解作成問題の制約条件は下記の通りとなる。

全ての単位サービスには少なくとも１つのリソースが割当てられる。

決定変数xとyのリンク条件（１）閉路用

決定変数xとyのリンク条件（２）自己ループ用

同じ値を持ち終点も等しい実リンクは複数存在しない（合流禁止条件）。

各リソースの閉路は０を含み、なおかつ同一リソースに関する他の閉路は存在しない。

※ただし、Loop(r)は、リソースrに関する0を含む閉路に含まれるノードの集合を意味する。

上記の制約条件に加えて、図１の割当制約テーブル0125で定義された各制約に対しても数式表現を与える。その具体的な形式は設定する条件に応じて異なるが、例えば、「あるリソースrは単位サービスiとjのいずれかに割当可能である」といった制約の場合、制約式は「ｙ_ri = 1 || y_rj = 1」となる。

次に、数理モデルの目的関数は以下の通りである。

上記の制約条件に加えて、図１の割当制約テーブル0125で定義された各制約に対しても数式表現を与える。その具体的な形式は設定する条件に応じて異なるが、図10のマトリックス形式の様に「あるリソース(乗務員)rが単位サービス(スジ)i,j,k,...のいずれかに割当可能である」ことを意味する場合、それに対応する制約式は「ｙ_ri = 1 || y_rj = 1 || y_rk = 1 ... 」となる。このように割当制約テーブルに対応する制約式をもれなく設定することにより、先に説明した実行可能解の条件の１つである「割当条件」を満足する解を生成することができる。

次に、数理モデルの目的関数は以下の通りである。

この目的関数を最小化することにより、可能リンクが存在しない実リンク、すなわち違反リンクをできるだけ使用しないスケジュールが得られる。特に目的関数の値が０の場合には違反リンクを全く使わないことから、実行可能解の条件の１つである「順序条件」をもれなく満足することができる。さらに、生成される解は割当制約テーブルに対応する数式表現された制約式を常に満たしているはずであるから、実行可能解のもう１つの条件である「割当条件」も同時に満足する。したがって、目的関数の値を0にすることにより「順序条件」と「割当条件」の双方を満足する実行可能解を得ることができる。

図１６に戻り実行可能解作成処理の説明を続ける。数理モデルを生成した後に、ステップ1602において制約プログラミングにより暫定解Ｘを探索する。制約プログラミングは線形計画法等と同様に、一般的原理を実装した汎用ライブラリが広く流通しており、数理モデルをそうした汎用ライブラリに与えることにより探索をおこなわせることが可能である。したがって、本ステップでは汎用ライブラリをコールすることにより解探索を実行することとしても良いし、制約プログラミングをベースとした探索メカニズムを独自に実装することとしても良い。制約プログラミングの探索メカニズムを独自に実装する場合、適用対象に合わせて探索処理をチューニングできることから、ライブラリを単純に用いるよりも解を効率良く探索することが期待できる。また、本問題の場合は、実行可能解として元のスケジュールからの変更ができるだけ少ないものを得ることが望ましいが、独自の実装によりそうした性質を満たす解が得られるように探索をきめ細かく制御することも可能となる。以上から、本実施例では制約プログラミングの考え方をベースとした独自処理により探索をおこなうことし、図１８の処理フロー図を用いてその内容を以下に説明する。

まずステップ1801において、未選択のリソースをひとつ選択し、これをrとする。次にステップ1802において、割り当て対象の単位リソースを識別するための変数iに特別な単位サービス0を設定する。ステップ1803では、決定変数ｘ_riの値をドメインの中から選択し、これをtとする。探索が進行するにつれて制約伝播が繰り返し実行されることから、決定変数のドメインは動的に変化するが、この値の選択に際して、ある値を選ぶことにより元のスケジュールと同じ実リンクが設定できるのであれば、その値を優先的に選択する。このように値の選択を制御することにより、元のスケジュールからの変更ができるだけ少ない解を得ることができる。次にステップ1804において制約伝播を実行し、ｘ_riの値をtとしたことによる他の決定変数への影響度を踏まえてそれらのドメインを更新する。

ステップ1805では、制約伝播により矛盾が発生したかどうか、すなわち値を定めていない決定変数のいずれかについて、ドメインが空となったかどうかを判定する。矛盾が発生した場合にはステップ1806へ進み、バックトラックを実行する。バックトラックとは、それまでに実行してきた探索処理の一部をキャンセルする処理であり、探索の任意の時点へ後戻りした上でステップ1801へ戻り処理をやりなおす。ステップ1805において矛盾が発生しない場合はステップ1807へ進み、tが特別な単位サービス0であるかどうかを判定する。tが0でない場合はステップ1808へ進み、iにtをセットして再びステップ1803から実行する。これは0を起点としてノードを辿りながら実リンクを設定していくことを意味する。tが0の場合は、ノードを辿って再び0に戻ってきたことを意味する。そこでステップ1809において、それまでに選択されなかった全てのノードjに対して、ｘ_rj=j、すなわち値をrとする自己ループを設定する。次にステップ1810において、全てのリソースを選択したかどうかを判定し、全て選択した場合には全体処理を終了する。未選択のリソースがある場合は、再びステップ1801へ戻り処理を繰り返す。

図１６に戻り実行可能解作成処理の説明を続ける。暫定解Ｘを探索した後は、ステップ1603において、Ｘの目的関数値pが0であるかどうかを判定する。これが0であれば、暫定解Ｘは違反リンクを含まない実行可能解であるので、暫定解を出力して全体処理を終了する。0でない場合にはステップ1604へ進み、「目的関数値はpより小さい」ということを意味する制約式を生成して数理モデルに追加し、さらにステップ1602へ戻り再び暫定解を探索する。ここでは新たに追加された制約式が作用するため、前回の探索で得られたものよりも目的関数値が小さい暫定解を探索することとなる。このように目的関数値に関する制約を次第に厳しくしながら暫定解探索を繰り返しおこなうことにより、最終的に目的関数値が0の実行可能解を得ることができる。

以上詳述した第二の実施例においては、実行可能解生成部0114で、リソーススケジュールの実行可能解生成に関わる条件を制約式とし、運用ネットワークに含まれる違反リンクの本数を最小化することを目的関数とした数理モデルを構築し、数理モデルの解を制約プログラミングの適用により算出することとし、その中で(1)運用ネットワークのノードを辿りながらリンクを繰返し設定すること、かつその際に、(2)修正前のリソーススケジュールと一致するリンクを優先的に設定した。

この第二の実施例によれば、対象問題を数式表現した数理モデルを生成し、その解を制約プログラミングを適用して算出することとし、さらに運用ネットワークのノードを辿りながらリンクを繰返し設定する中で、修正前のリソーススケジュールと一致するリンクを優先的に設定するので、同じく元のスケジュールをできるだけ変更することなく、かつ効率良く実行可能解を得ることができる。

本発明のスケジュール修正装置の機能並びに機器構成を示す図である。本発明の実施例である乗務員運用整理システムをサブシステムとする列車運行管理システムの機器構成例を示す図である。本発明による修正スケジュールの作成手順を示す処理フロー図である。サービススケジュールである運行ダイヤの例を示す図である。サービス変更テーブルの例を示す図である。変更手配テーブルの例を示す図である。締切時刻算出処理の実行例を示す図である。リソーススケジュールである乗務員運用計画の例を示す図である。運用ネットワークの例を示す図である。割当制約テーブルの例を示す図である。実リンクの交換操作の例を示す図である。実施例１における実行可能解生成処理の具体的な手順を示す処理フロー図である。評価指標テーブルの例を示す図である。代替案生成処理における近傍の生成例を示す図である。代替案生成処理の具体的な手順を示す処理フロー図である。実施例２における実行可能解生成処理の具体的な手順を示す処理フロー図である。実施例２におけるリソーススケジュールの表現例を示す図である。実施例２における暫定解探索処理の具体的な手順を示す処理フロー図である。

符号の説明

０１１０：処理装置、０１１１：締切時刻算出手段、０１１２：運用ネットワーク作成部、０１１３：違反検出部、０１１４：実行可能解生成部、０１１５：スケジュール改良部、０１１６：ワークエリア、０１２０：記憶装置、０１２１：サービススケジュール、０１２２：リソーススケジュール、０１２３：サービス変更テーブル、０１２４：手配時間テーブル、０１２５：割当制約テーブル、０１２６：評価指標テーブル、０１３０：入力装置、０１４０：表示装置。

Claims

サービス提供のためのリソースの運用に関するスケジュールを修正するスケジュール修正装置であって、
サービスの実施予定を示すサービススケジュールと、前記サービスを実施するためのリソースの運用予定を示すリソーススケジュールと、前記サービススケジュールの変更を示すサービス変更情報とから、前記リソースを割当てる最小単位である単位サービスと前記単位サービス間の可能な実施順序と前記リソースの前記単位サービスへの割当並びに割当順序とを表わす運用ネットワークを生成する運用ネットワーク作成部と、
前記運用ネットワークと前記リソースの前記単位サービスへの割当に関する制約条件を示す割当制約情報とを用いて検出された、前記リソーススケジュールの実行可能性違反を解消し、前記リソーススケジュールの実行可能解を生成する実行可能解生成部と、
前記リソーススケジュールの修正を完了すべき締切時刻を設定する締切時刻設定部とからなり、
前記締切時刻設定部は、サービスの変更時刻からサービス変更の手配時刻を引いた時刻を変更毎の締切時刻とし、前記変更毎の締切時刻の最小値を前記締切時刻として設定する
スケジュール修正装置。
サービス提供のためのリソースの運用に関するスケジュールを修正するスケジュール修正装置であって、
サービスの実施予定を示すサービススケジュールと、前記サービスを実施するためのリソースの運用予定を示すリソーススケジュールと、前記サービススケジュールの変更を示すサービス変更情報とから、前記リソースを割当てる最小単位である単位サービスと前記単位サービス間の可能な実施順序と前記リソースの前記単位サービスへの割当並びに割当順序とを表わす運用ネットワークを生成する運用ネットワーク作成部と、
前記運用ネットワークと前記リソースの前記単位サービスへの割当に関する制約条件を示す割当制約情報とを用いて検出された、前記リソーススケジュールの実行可能性違反を解消し、前記リソーススケジュールの実行可能解を生成する実行可能解生成部と、
前記リソーススケジュールの修正を完了すべき締切時刻を設定する締切時刻設定部と、
評価指標を用いて前記リソーススケジュールの評価値を算出し、前記評価値を改善し、かつ実行可能性違反を生じないように前記運用ネットワークの構造を前記締切時刻まで繰返し改良することにより、前記実行可能解生成部で得られた前記実行可能解の代替案を生成するスケジュール改良部とを有し、
前記運用ネットワークは、ネットワークＧ（Ｎ、Ｅ１、Ｅ２）で、Ｎは前記単位サービスを示すノードの集合であり、Ｅ１は前記可能な実施順序を示す第一の有向リンクの集合であり、Ｅ２は前記リソースの前記単位サービスへの割当並びに割当順序を示し、かつ前記リソースの識別ＩＤを値とする第二の有向リンクの集合であり、
前記スケジュール改良部における前記運用ネットワークの改良は、前記第二の有向リンクを２つ選択し、実行可能性違反を生じない限りにおいて両者の終点を相互に交換し、かつ両者の終点を起点として前記第二の有向リンクを辿り、前記識別ＩＤの値を相互に交換するスケジュール修正装置。
サービス提供のためのリソースの運用に関するスケジュールを修正するスケジュール修正装置であって、
サービスの実施予定を示すサービススケジュールと、前記サービスを実施するためのリソースの運用予定を示すリソーススケジュールと、前記サービススケジュールの変更を示すサービス変更情報とから、前記リソースを割当てる最小単位である単位サービスと前記単位サービス間の可能な実施順序と前記リソースの前記単位サービスへの割当並びに割当順序とを表わす運用ネットワークを生成する運用ネットワーク作成部と、
前記運用ネットワークと前記リソースの前記単位サービスへの割当に関する制約条件を示す割当制約情報とを用いて検出された、前記リソーススケジュールの実行可能性違反を解消し、前記リソーススケジュールの実行可能解を生成する実行可能解生成部と、
前記リソーススケジュールの修正を完了すべき締切時刻を設定する締切時刻設定部と、
評価指標を用いて前記リソーススケジュールの評価値を算出し、前記評価値を改善し、かつ実行可能性違反を生じないように、前記運用ネットワーク中の前記リソースの前記単位サービスへの割当並びに割当順序を示し、かつ前記リソースの識別ＩＤを値とする実リンクを二つ選択し、選択した前記実リンクを対象とした交換操作を行い、前記運用ネットワークの構造を前記締切時刻まで繰返し改良することにより、前記実行可能解生成部で得られた前記実行可能解の代替案を生成するスケジュール改良部
を有するスケジュール修正装置。
請求項３記載のスケジュール修正装置であって、
前記運用ネットワーク作成部において、前記可能な実施順序は、少なくとも２つの前記単位サービスの実行時刻に関する時間的な前後関係と矛盾が生じないように設定する
スケジュール修正装置。
請求項３記載のスケジュール修正装置において、
前記実行可能解生成部は、前記運用ネットワークの構造を修正することにより前記リソーススケジュールの前記実行可能解を生成する
スケジュール修正装置。
請求項３記載のスケジュール修正装置において、
前記運用ネットワークは、ネットワークＧ（Ｎ、Ｅ１、Ｅ２）で、Ｎは前記単位サービスを示すノードの集合であり、Ｅ１は前記可能な実施順序を示す第一の有向リンクの集合であり、Ｅ２は前記実リンクの集合である
スケジュール修正装置。
請求項５記載のスケジュール修正装置において、
前記運用ネットワークは、ネットワークＧ（Ｎ、Ｅ１、Ｅ２）で、Ｎは前記単位サービスを示すノードの集合であり、Ｅ１は前記可能な実施順序を示す第一の有向リンクの集合であり、Ｅ２は前記実リンクの集合であり、
前記実行可能解生成部における前記運用ネットワークの構造の修正は、実行可能性違反に関連する前記実リンクと、他の前記実リンクとを選択し、両者の終点を相互に交換し、かつ両者の終点を起点として前記実リンクを辿り、前記識別ＩＤの値を相互に交換することで実行する
スケジュール修正装置。
請求項７記載のスケジュール修正装置において、
前記実行可能解生成部における前記他の実リンクの選択は、交換により実行可能性違反に関連する前記実リンクの実行可能性違反が解消すると共に、新たな実行可能性違反が生じないものの中から優先的に選択し、該当するものがない場合には、交換により実行可能性違反に関連する前記実リンクの実行可能性違反が解消されるものの中から選択する
スケジュール修正装置。
請求項６記載のスケジュール修正装置において、
前記実行可能解生成部において、前記リソーススケジュールの実行可能性違反に関わる条件を制約式とし、前記第一の有向リンクと始点及び終点が一致しない前記実リンクの数を最小限にすることを目的関数とした数理モデルを構築し、前記実行可能解を該数理モデルの解として制約プログラミング手法を適用して算出する
スケジュール修正装置。
請求項９記載のスケジュール修正装置において、
前記実行可能解生成部における、前記制約プログラミング手法を適用した前記実行可能解の算出は、前記ノードを辿りながら前記実リンクを繰返し設定し、かつ修正前の前記リソーススケジュールと一致する前記実リンクを優先的に設定する
スケジュール修正装置。