(57)【要約】【課題】各参加者の適切な需給関係（需給先、需給量）を発見して、その需給関係を各ユーザに情報提供することにより需給を仲介するための技術を提供すること。【解決手段】  複数ユーザの間における必要なリソースと提供を希望するリソースとについて、各ユーザの間の需給関係を決定することを支援する需給仲介システムにおいて、需給対象とする複数のリソースと、リソース間で満たすべき組み合わせ条件とをそれぞれ有する複数のエントリーを収集してエントリー集合を形成するエントリー収集手段と前記エントリー集合の中から、基点として指定された一つ以上のエントリーを含む複数のエントリーからなる候補グループを抽出する際に、この候補グループ中に含まれる全てのエントリーが各々のエントリーの持つ組み合わせ条件を満足するように候補グループを抽出し、当該候補グループに属する各々のエントリー間の要求側リソースと提供側リソースの間の需給関係の有無と需給する数量とを決定する候補グループ決定手段とを備えた。【選択図】      図１
2005063426.tif 000002
【特許請求の範囲】
【請求項１】
複数ユーザの間における必要なリソースと提供を希望するリソースとについて、各ユーザの間の需給関係を決定することを支援する需給仲介システムにおいて、
需給対象とする複数のリソースと、リソース間で満たすべき組み合わせ条件とをそれぞれ有する複数のエントリーを収集してエントリー集合を形成するエントリー収集手段と
前記エントリー集合の中から、基点として指定された一つ以上のエントリーを含む複数のエントリーからなる候補グループを抽出する際に、この候補グループ中に含まれる全てのエントリーが各々のエントリーの持つ組み合わせ条件を満足するように候補グループを抽出し、当該候補グループに属する各々のエントリー間の要求側リソースと提供側リソースの間の需給関係の有無と需給する数量とを決定する候補グループ決定手段とを備えることを特徴とする需給仲介システム。
【請求項２】
請求項１に記載の需給仲介システムにおいて、前記候補グループ決定手段は、候補グループ中に含まれる全てのエントリーに対して、それぞれのエントリーに指定された組み合わせ条件に違反する程度を示す組み合わせ条件ペナルティ値の総和を最小化する組み合わせ最適化演算を実行して、候補グループを抽出することを特徴とする需給仲介システム。
【請求項３】
請求項１又は請求項２に記載の需給仲介システムにおいて、
前記複数のエントリーを登録する登録手段と、
前記グループ候補に関する情報と前記候補グループ内の需給関係に関する情報とを出力する需給候補出力手段とを更に具備し
前記候補グループに含まれるエントリーを登録した各ユーザに、当該ユーザの登録したエントリーに含まれる各リソースの需給成立の有無と需給数量に関する情報を通知し、承諾するか否かの確認を行うことを特徴とする需給仲介システム。
【請求項４】
請求項３に記載の需給仲介システムにおいて、
前記エントリーは、ユーザがそのリソースを需要する側か供給する側かを識別するためのフラグ及び当該リソースの数量を示す数量を対として指定するリソース記述データと、当該エントリー内に含まれる複数リソース間の組み合わせ条件を定義する組み合わせ条件データとを有し、
前記組み合わせ条件は、前記エントリー中のリソースの一部の集合において需給関係の成立すべき数量もしくは当該リソース全体量に対する割合を目標値として指定する条件、もしくは需給関係の成立すべき数量もしくは当該リソース全体量に対する割合の下限値を目標値として指定する条件のいずれかを含むことを特徴とする需給仲介システム。
【請求項５】
請求項４に記載の需給仲介システムにおいて、前記エントリーに複数の組み合わせ条件を指定することが可能であることを特徴とする需給仲介システム。
【請求項６】
請求項４に記載の需給仲介システムにおいて、前記エントリーに複数の組み合わせ条件を階層的に組み合わせることが可能であって、この階層上位の組み合わせ条件は、当該複数の組み合わせ条件の全体集合の一部の部分集合において、成立すべき組み合わせ条件の数もしくは全体数に対する割合を目標値として指定する条件、もしくは成立すべき組み合わせ条件の数もしくは全体数に対する割合の下限値を目標値として指定する条件のいずれかを含むことを特徴とする需給仲介システム。
【請求項７】
請求項２に記載の需給仲介システムにおいて、
前記エントリーは、各リソースの単位量当たりの売買希望価格と、需給相手の売買希望価格との差額であるエントリー全体の余剰の総和の目標値を指定するデータを含み、
前記候補グループ決定手段は、前記エントリー全体の余剰の総和の目標値を用いて、候補グループを抽出することを特徴とする需給仲介システム。
【請求項８】
請求項７に記載の需給仲介システムにおいて、前記候補グループ決定手段は、それぞれのエントリーにおいて需給の成立したリソースの余剰の総和の値が前記の余剰総和目標値を下回る値を評価ペナルティ値とした場合に、候補グループ中に含まれる全てのエントリーの評価ペナルティ値の総和を、上記の組み合わせ条件ペナルティ値と加えた値を最小化することで、候補グループを抽出することを特徴とする需給仲介システム。
【請求項９】
請求項１から請求項３のいずれか１項に記載の需給仲介システムにおいて、
各リソースの単位量当たりの売買希望価格のデータが前記リソースに付加され、
前記基点として指定されたエントリーにおいて需給の成立したリソースの余剰の総和を、最大化することで、候補グループを抽出することを特徴とする需給仲介システム。
【請求項１０】
請求項１から請求項３のいずれか１項に記載の需給仲介システムにおいて、
前記エントリーの各リソースの単位量当たりの売買希望価格と、需給相手の売買希望価格との差額であるエントリー全体の余剰の総和の目標値を指定するデータが付加され、
それぞれのエントリーにおいて需給の成立したリソースの余剰の総和の値が前記の余剰総和目標値を下回る値を評価ペナルティ値とした場合に、候補グループ中に含まれる全てのエントリーの評価ペナルティ値の総和を最小化することで、候補グループを抽出することを特徴とする需給仲介システム
【請求項１１】
請求項３に記載の需給仲介システムにおいて、前記候補グループ決定手段は、候補グループに含まれるエントリーの数の上限値を指定することを特徴とする需給仲介システム。
【請求項１２】
請求項２に記載の需給仲介システムにおいて、前記候補グループ決定手段は、最良優先探索を用いて組み合わせ最適化演算を実行することを特徴とする需給仲介システム。
【請求項１３】
請求項１から請求項３のいずれか１項に記載の需給仲介システムにおいて、前記エントリー収集手段が、物理的に分散して入力ないしは蓄積されたエントリーを、通信手段を用いて取得することを特徴とする需給決定支援システム。
【請求項１４】
請求項１から請求項３のいずれか１項に記載の需給仲介システムにおいて、前記エントリー収集手段は、物理的に分散して入力ないしは蓄積されたエントリーを、ユーザからのアクセス要求があった場合に通信手段を用いて問い合わせ処理を実行することによりアクセスすることを特徴とする需給仲介システム。
【請求項１５】
請求項９又は請求項１０に記載の需給仲介システムにおいて、前記候補グループ決定手段は、登録された各エントリーにおいて需給の成立したリソースの余剰の総和を目的関数とし最大化した、最適値を当該エントリーの余剰の目標値とする第１段階の最適化と、それぞれのエントリーにおいて需給の成立したリソ−スの余剰の総和の値が当該エントリーの目標値を下回る値を評価ペナルティ値とし、候補グループ中に含まれる全てのエントリーの評価ペナルティ値の総和を、最小化することで、候補グループを抽出する第２段階の最適化を行うことを特徴とする需給仲介システム。
【請求項１６】
請求項９から請求項１５のいずれか１項に記載の需給仲介システムにおいて、
前記エントリーは、ユーザがそのリソースを需要する側か供給する側かを識別するためのフラグ及び当該リソースの数量を示す数量を対として指定するリソース記述データと、当該エントリー内に含まれる複数リソース間の組み合わせ条件を定義する組み合わせ条件データとを有し、
前記組み合わせ条件は、前記エントリー中のリソースの一部の集合において需給関係の成立すべき数量もしくは当該リソース全体量に対する割合を目標値として指定する条件、需給関係の成立すべき数量もしくは当該リソース全体量に対する割合の下限値を目標値として指定する条件、上記組み合わせ条件を複数組み合わせた条件、上記組み合わせ条件を階層的に組み合わせ、階層上位の組み合わせ条件のいずれかの条件は、当該複数の組み合わせ条件の全体集合の一部の部分集合において、成立すべき組み合わせ条件の数もしくは全体数に対する割合を目標値として指定する条件、もしくは成立すべき組み合わせ条件の数もしくは全体数に対する割合の下限値を目標値として指定する条件のいずれかであり、
各ユーザが登録した各エントリーに記述された、前記組み合わせ条件を一個以上の一次の制約式に変換する手段と；
基点として指定されたエントリーが前記候補グループに属する制約を一個以上の一次の制約式に変換する手段と；
リソース間の需給を需給可能なリソース間に限定する制約を一個以上の一次の制約式に変換する手段と；
最適化目標を一次式の目的関数に変換する手段と；
前記制約式と目的関数からなる混合整数線型計画問題を解き、対応する最適化パラメータの組の値または問題解決不能を知らせる信号を出力する混合整数線形計画問題解決手段と；を更に具備し、
前記候補グループ決定手段は、前記混合整数線形計画問題解決エンジン手段の出力結果をもとに、候補グループと当該候補グループに属する各々のエントリー間の要求側のリソースと提供側のリソースの間の需給関係の有無と需給する数量を決定することを特徴とする需給仲介システム。
【請求項１７】
複数ユーザの間における必要なリソースと提供を希望するリソースとについて、各ユーザの間の需給関係を決定することを支援する需給仲介方法において、
需給対象とする複数のリソースと、リソース間で満たすべき組み合わせ条件とをそれぞれ有する複数のエントリーを収集してエントリー集合を形成する工程と；
前記エントリー集合の中から、基点として指定された一つ以上のエントリーを含む複数のエントリーからなる候補グループを抽出する際に、この候補グループ中に含まれる全てのエントリーが各々のエントリーの持つ組み合わせ条件を満足するように候補グループを抽出し、当該候補グループに属する各々のエントリー間の要求側リソースと提供側リソースの間の需給関係の有無と需給する数量とを決定する工程と；を備えることを特徴とする需給仲介システム。
【請求項１８】
複数ユーザの間における必要なリソースと提供を希望するリソースとについて、各ユーザの間の需給関係を決定することを支援するプログラムにおいて、
需給対象とする複数のリソースと、リソース間で満たすべき組み合わせ条件とをそれぞれ有する複数のエントリーを収集してエントリー集合を形成する処理と；
前記エントリー集合の中から、基点として指定された一つ以上のエントリーを含む複数のエントリーからなる候補グループを抽出する際に、この候補グループ中に含まれる全てのエントリーが各々のエントリーの持つ組み合わせ条件を満足するように候補グループを抽出し、当該候補グループに属する各々のエントリー間の要求側リソースと提供側リソースの間の需給関係の有無と需給する数量とを決定する処理と；を実行するためのコンピュータで読み取り可能なプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワークを利用した電力取引市場システムを始めとする需給取引市場システムや、会社・部門間の人・物・設備・サービス等の需給決定支援システムなどに適用され、複数ユーザの間で、必要なリソースと提供を希望するリソースの、各ユーザの間の適切な需給関係を決定することを支援する技術に関し、各参加者の適切な需給関係（需給先、需給量）を発見（抽出）して、その需給関係を各ユーザに情報提供することにより需給を仲介するための技術に関する。
【背景技術】
【０００２】
ネットワークを利用した需給取引市場システムや、複数の会社・部門間を跨り人・物・設備・サービス等のリソースの需給計画を支援するシステムなどの、いわゆる需給仲介システムが様々な分野で実用化されている。なお、本明細書においては、「需給仲介システム」とは、システムの各ユーザにリソースの需給対象となる相手ユーザと需給量の候補を提示することで円滑な需給関係が成立することを支援する、いわゆる意思決定支援システムを指すものとし、個人認証や決済支援・セキュリティ支援などの付加機能は対象外とする。
【０００３】
従来の需給仲介システムは、データベースを利用した情報検索システム、すなわち掲示板方式と呼ばれる方式が最も一般的である。複数のユーザがネットワークを介して提供希望リソースや入手希望リソースを登録し、それぞれのユーザが条件に合うリソースの候補を検索・確認し、各々が希望するリソースの登録者であるユーザと需給の合意に至ることを支援することが基本となる。
【０００４】
取引市場における代表的な需給仲介システムとしては、リソース（商品）登録を一斉に締め切り、同種のリソースについて、最も設定価格の安い提供者と最も設定価格の高い需要者を順次需給取引成立させ、提供者の設定価格が需要者の設定価格を下回るまで取引を成立させる、板寄せ方式に基づくシステムがある。また、リソース登録と需給確定のタイミングは自由とし、同種のリソースについて、最も設定価格の安い提供者と最も設定価格の高い需要者を即時に需給取引成立させる、ダブルオークション方式（ザラバ方式もほぼ同じ）もあり、株式取引システムなどで利用されている。
【０００５】
電力取引の自由化に伴い、今後は電力の需給取引においても需給仲介システムが活用されることが予想される。現時点で日本での実施が検討されているスポット電力市場システムは、３０分単位のスポット取引については板寄せ方式、長期的な取引を仲介する先渡し市場はザラ場方式を採用。スポット市場で連系線送電量が託送可能量を上回った場合は市場を分断し、約定価格の安いエリアから高いエリアへ連系線容量分だけ電力を流すことが予定されている。
【０００６】
需給仲介では、リソースの種類毎の需給仲介のほか、リソースの組み合わせで条件を指定し需給を行いたい場合がある。たとえば、「パソコン、ディスプレイ、プリンターのセットを１セット２０万円で入手したい」という要求があり得る。一つの種類のリソースの数が複数個数になることも予想され、たとえば「パソコン１００台、ディスプレイ１００台のセットを計２０００万円で提供したい」というような要求も有りえる。
【０００７】
電力取引支援システムを例として考える。発電側ユーザにおいては、一度発電を開始したら一定時間以上は一定量以上の発電を継続しないと採算ラインにのらない場合や、一定量の発電しかできない場合など、発電装置の運用上の特性によって可能な発電量の上下限制約が時系列パタンとして与えられるのが一般的である。需要側ユーザにおいては、製造などの業務を遂行するため、時間帯毎の自らの電力消費パタンを全て満たすような電力を安定して確保する必要がある。電力卸売り業者（アグリゲータ）の立場で参加するユーザにおいては、大量の電力の保存が極めて困難なため、入手電力量と転売電力量が各時間帯で均衡する必要がある。送電設備を提供するユーザは、各送電設備を流れる電力の総量を指定範囲に抑える必要がある。
【０００８】
従来の需給仲介システム（非特許文献１に記載のものを除く）では、ユーザが複数のリソースを同時に登録しリソース間で満たすべき制約条件を指定すると、特定の１ユーザの指定した制約条件を満足することはできても、相手側の制約条件も同時に満足することまで考慮した仲介を行うことが技術的に困難であった。これは、従来の需給仲介システムがデータベースを利用した単純な情報検索システムに留まり、複数のユーザの指定した制約条件を同時に考慮するために必要な組み合わせ最適化演算による支援機能がなかったためである。
【０００９】
このため、複数のユーザが複数リソース間の制約条件を自由に指定することができなかった。
【００１０】
電力取引支援システムにおいても、板寄せ方式や単純なダブルオークション方式による仲介システムでは、単位電力量毎、単位時間帯毎に各々無関係な商品として登録（入札）されることを前提としており、同一のユーザが登録した商品の間であっても、商品相互の関連付けを指定することができない。このため、従来の単純な需給仲介システムでは、上に示した発電装置の運用上の特性や業務上必要な電力消費パタンなどの特性を考慮した条件指定を汎用的に扱えない。
【００１１】
組み合わせオークションと呼ばれる方法（特許文献１、特許文献２参照）を用いると、特定の条件下で、リソースの組み合わせで条件を指定した上での入札によるオークションが可能となる。組み合わせオークションは、リソース提供側のユーザ、もしくは需要側のユーザのいずれか一方の入札が一つに限定されるが、さらに組み合わせオークションを拡張した最新方式として、リソース提供側の入札と需要側の入札の双方とも複数同時に扱うことを可能とする方式が提案されている（例えば、非特許文献１参照）。非特許文献１は、仲介システムが全入札について取引に参加可能か否かのみを同時に決定（勝者決定）し、全てのユーザが仲介システムの決定に従うことを前提としている。
【００１２】
参考のため非特許文献１の最適化のための数式（１）を示す。  
【００１３】
【数１】
2005063426.tif 000003
【００１４】
数式（１）において第一式が最適化の目標関数であり、各ユーザの入札した希望需給価格の差額の総和（surplus＝社会的余剰）と呼ばれる経済学的な指標を市場全体で最大化することを目標とした最適化演算を行う。第二式は、市場全体で各リソースの需給バランスが成立するための制約式である。本式は代表的な数式であり、他に取引成立数などの経済学的な指標を市場全体で最大化するなどのバリエーションもあるが、詳細に関しては非特許文献１を参考とされたい。本式でも明らかなように、非特許文献１は、勝者（取引に参加するユーザ）は決定できるが、個々のユーザ間の需給関係（いわゆるマッチング）を具体的に決定できないため、あるユーザが決定に従わないことにより指定した制約条件が成立しなくなる波及効果の及ぶ入札の範囲が不明である。このため、一人でも仲介システムの決定に従わないユーザがいると、全体の需給バランスが崩れ、全ての決定を一旦無効としなければならなくなる。また、非特許文献１では、上記に示した経済学的な指標を市場全体で最大化することを目標とした最適化演算を行うため、一部のユーザが不利益を被る恐れがあり、ますます全体の決定が成立し難くなるという問題点がある。よって、各ユーザに仲介システムの決定内容の合意を求めた上で需給を確定したり、ユーザに複数の候補案を見せて自由に選択させたり、入札の条件を変更させるなどの、ユーザ側の意思決定の自由度を残した柔軟な需給仲介システムを実現するのは困難である。
【特許文献１】特開２００２−１６３４８６号公報
【特許文献２】米国特許第６２７２４７３号
【非特許文献１】A.Kothari, T.Sandholm, Subhash Suri, "Solving Combinatorial Exchanges: Optimality via a Few Partial Bids"
【発明の開示】
【発明が解決しようとする課題】
【００１５】
先に背景において述べた様に、Combinatorial Exchangesを除く従来の需給仲介システムでは、複数のユーザの指定した制約条件を同時に考慮するために必要な組合わせ最適化演算による支援機能がなかったため、ユーザが複数のリソースを同時に登録しリソース間で満たすべき制約条件を指定すると、特定の１ユーザの指定した制約条件を満足することはできても、相手側の制約条件も同時に満足することまで考慮した仲介を行うことが技術的に困難であった。このため、複数のユーザが複数リソース間の制約条件を自由に指定することができず、電力取引支援システムにおいても、発電装置の運用上の特性や業務上必要な電力消費パタンなどの各ユーザの考慮すべき様々な運用特性を同時に考慮した需給仲介を行うことが困難であった。
【００１６】
Combinatorial Exchangesやその派生技術においても、勝者（取引に参加するユーザ）は決定できるが、個々のユーザ間の需給関係（いわゆるマッチング）を具体的に決定できないため、あるユーザが決定に従わないことにより指定した制約条件が成立しなくなる波及効果の及ぶ入札の範囲が不明であるため、ユーザに複数の候補案を見せて自由に選択させるなどの、ユーザ側の意思決定の自由度を残した柔軟な需給仲介システムを実現するのは困難であった。
【課題を解決するための手段】
【００１７】
本発明による需給仲介システムでは、需給仲介を希望する各ユーザは、需給対象とする複数のリソースと、リソース間で満たすべき組み合わせ条件を、セットでエントリーという単位データとして登録する。各ユーザは、マッチングを成立させたいリソースの数量もしくは割合を指定するか、もしくは、マッチングを成立させたいリソースの数量もしくは割合の下限値を指定する条件を階層的に組み合わせることで、需要側リソースと供給側リソースの組み合わせなど、複雑な組み合わせ条件の設定も可能とする。
【００１８】
需給仲介システムは、現時点で新規登録されたエントリーや重要なユーザの登録したエントリーを基点エントリーとして指定し、一つ以上の基点エントリーを含み、かつ、候補グループ中に含まれる全てのエントリーが組み合わせ条件を満足するようなエントリーの候補グループを、組み合わせ最適化演算により自動発見する。候補グループを発見するための、組み合わせ最適化演算では、探索的解法や混合整数計画法を用いる。
【００１９】
探索的解法の場合は、それぞれのエントリーに指定された組み合わせ条件に違反する程度を示す組み合わせ条件ペナルティ値を定義し、候補グループ中に含まれる全てのエントリーの組み合わせ条件ペナルティ値の総和を目的関数として最小化することで、候補グループを発見する。これらの最適化条件に加えて、発見する候補グループに含むエントリーの数の上限値の制約を設ける場合もあり得る。組み合わせ最適化演算の方法としては、最良優先探索などの探索手法を用いる。
【００２０】
混合整数計画法を利用する場合は、それぞれのエントリーに指定された組み合わせ条件を制約式に自動変換し、既存の混合整数計画法の解法などを利用して最適化問題として解く。前記エントリーの各リソースの単位量当たりの売買希望価格と、エントリー全体の余剰（需給相手の売買希望価格との差額）の総和の目標値を指定するデータが付加される場合は、それぞれのエントリーにおいて需給の成立したリソースの余剰の総和の値が前記の余剰総和目標値を下回る値を評価ペナルティ値とし、候補グループ中に含まれる全てのエントリーの評価ペナルティ値の総和を、上記の組み合わせ条件ペナルティ値と加えた値を目的関数とし最小化することで、候補グループを発見する。また、最適化基準として、各ユーザの利益の目標値を自動的に計算する第一段階の最適化と、この自動的により得られた目標値を基準にして、この目標値と実際に得られる利益との差分であるペナルティを最小化する第二段階の最適化を行う。
【発明の効果】
【００２１】
本発明による需給仲介システムでは、各ユーザが自分の登録した複数のリソース間で満たすべき組み合わせ条件を自由に指定した場合でも、基点となるエントリーのみならず、それぞれのエントリーの指定した組み合わせ条件を全て同時に考慮した需給先と需給量を候補として求めることが可能となる。エントリーの候補グループは、互いに影響が波及するエントリーの範囲に対応するため、候補グループに含まれる各エントリーについて登録した各ユーザの承諾が得られれば、候補グループに含まれないエントリーを登録したユーザと無関係に需給を決定することが可能になる。
【００２２】
また、経済学的な指標を市場全体で最大化することを目標とした勝者決定演算ではなく、基点となるエントリーの利益最大化や、候補グループ中に含まれる全てのエントリーのユーザが設定した目標利益を下回る値（評価ペナルティ値）総和を最小化する目標関数とした組み合わせ最適化を行うことにより、現時点で新規登録されたエントリーの登録ユーザが不利益を被るような候補グループを除いたり、候補グループ内の一部のユーザが不利益を被るような候補グループを除くことが可能となる。
【００２３】
これにより、需要側と供給側の双方複数のユーザがそれぞれリソースの組み合わせで条件を指定した場合でも、いわゆる掲示板方式による相対取引の支援と同等のユーザ側の意思決定の自由度を残した柔軟な需給仲介が実現可能となる。例えば電力取引支援システムにおいては、発電装置の運用上の特性や業務上必要な電力消費パタンなどの各ユーザの考慮すべき様々な運用特性を同時に考慮した需給仲介を、統一した枠組みで容易に行うことが可能となる。
【発明を実施するための最良の形態】
【００２４】
図面を参照して本発明の実施の形態を説明する。
【００２５】
（第１の実施形態）  
まず、本発明の第１の実施形態に係る需給仲介システムの基本構成を説明する。  
図１は、第１の実施形態に係る需給仲介システム全体の概略構成例を示した図である。図１において、グルーピング装置１と、複数の端末ＴＥとがネットワークに接続されている。各複数の端末ＴＥは、ネットワークを介してグルーピング装置１へ接続して、エントリーを送信する。なお、「エントリー」とは、ユーザが複数のリソースを同時に登録し、相互で満足すべき関連条件を指定して登録するための、各ユーザの登録データの基本単位である。
【００２６】
図１において、グルーピング装置１は、大きく分けて、グルーピングモジュール３０と、エントリー記憶部１５と、インデックス記憶部１６と、辞書データ記憶部１７とを備えている。グルーピングモジュール３０は、エントリー入力部１１と、リソース名照合部１２と、候補グループ決定部１３と、候補グループ出力部１４とを備えている。候補グループ決定部１３は、仮グループ決定部２１と、グループ内マッチング決定部２２と、グループ評価値演算部２３と、ペナルティ演算部２４と、候補グループ記憶部２５とを有している。
【００２７】
エントリー入力部１１は、グルーピング装置１のグルーピングモジュール３０が、図示しない汎用データベース（ＤＢ）やデータファイル、主記憶上に保持されたデータなどにアクセスしエントリーを得るためのインタフェースである。また、エントリー入力部１１は、ネットワーク上に接続された端末から送信されたエントリーを受信して、当該エントリーをエントリー記憶部１５へ記憶する。なお、エントリー入力部１１からネットワーク上に接続された端末ＴＥにアクセスし、エントリーを収集するようにしてもよい。  
エントリーは、例えばユーザ側端末からネットワークを介してエントリー入力部１１からグルーピング装置１へ入力される。エントリーには内部で管理するためのＩＤがＩＤ発行部１９により付与される。
【００２８】
図２は、本発明の一実施形態に係る需給仲介システムを電力取引支援システムとして利用した場合の一例を示す図である。グルーピング装置１は、幹事業者のサーバなどにインストールされている。また、取引に参加する可能性のある各業者（発電業者、需要家、及び需発電業者）がグルーピング装置１とデータを収受するための端末を有している。なお、同じ業者内において、意思決定が独立した異なる部門間での外部調達も含めた適切な電力バランスを保つために、本需給仲介システムを利用しても良い。
【００２９】
各端末ＴＥからの新しいエントリーのグルーピング装置１へ送信する方法として以下の方法がある。第１の方法は、エントリーが生成されたタイミングで当該エントリーをグルーピング装置１へ送信する方法である。第２の方法は、グルーピング装置１のエントリー入力部１１が各端末ＴＥを定期的に監視し、エントリーが追加されていれば該当する端末ＴＥにエントリー送信要求を出す方法である。この場合において、エントリー入力部１１は、新規エントリーが追加された場合、もしくは端末ＴＥから新たなグルーピング演算の要求があった場合に、グルーピングモジュール３０を動作させるためのトリガーを発する。
【００３０】
候補グループ決定部１３は、エントリー入力部１１から入力されたエントリー集合の部分集合として、各エントリーで指定された組み合わせ条件を全て満たすマッチングが成立するような、複数のエントリーで構成される候補グループを自動発見する。
【００３１】
以下、ユーザがエントリーを登録する際に記述されるべきデータについて説明する。  
まず、各ユーザの登録の基本単位となるエントリーについて説明する。  
エントリーは、需給対象とするリソースを定義するリソース記述データと、１つのエントリー内に含まれるリソース間の組み合わせ条件に関する組み合わせ条件を定義する組み合わせ条件データとで構成される。リソース記述データは、提供もしくは要求される対象となるリソースの種類や名前を規定するリソース名データと、ユーザがそのリソースを需要する側か供給する側かを識別するための需給識別フラグと、そのリソースの数量を示す数量データとを１組として定義される。リソースの売買の仲介を目的として利用する場合は、リソース記述データに、リソースの単位数量当たりの希望単価を指定する希望価格データを付加する。需給識別フラグは、以降の説明では、「−」符号で需要側リソースを表すものとし、「＋」符号で供給側リソースを表すものとする。リソース名照合部１２は、異なるエントリー間において、供給側リソースと需要側リソースの間でマッチングが成立可能か否かを、リソース名データから判定する。なお、以降、「マッチング」とは異なるエントリー間で供給側リソースと需要側リソースの需給のペアを決定することを指す。
【００３２】
「組み合わせ条件」は、例えばｋ個のリソースのうちｃ個のみのマッチングを成立させたいというように、マッチングを成立させたいリソースの数量もしくは割合を指定するか、もしくは、マッチングを成立させたいリソースの数量もしくは割合の下限値を指定するための条件データである。以降の説明では、組み合わせ条件Ｃ［＝ｎ］｛｝は｛｝内に列挙されたリソースの内でｎ個のマッチングを成立させたいという条件を示し、組み合わせ条件Ｃ［≧ｎ］｛｝は｛｝内に列挙されたリソースの内でｎ個以上のマッチングを成立させたいという組み合わせ条件を示すものとする。以降の説明では、リソース記述データは、「需給識別フラグ＋数量＋リソース名＋￥単位量当たりの希望価格」の順で並べて記述するものとする。なお、数量が１の場合は数量の数字は省略し、希望価格を指定しない場合は価格の数字を省略する。
【００３３】
例えば、Ａ、Ｂ、Ｃはリソース名とすると、  
Ｃ［＝５０］｛＋１００Ａ￥１０｝｝  
は、Ａを１００単位中から５０単位、１個あたり￥１０で提供することを希望するエントリーを示し、  
Ｃ［≧１０］｛＋２０Ａ、＋３０Ｂ、＋５Ｃ｝  
は、Ａを２０単位とＢが３０単位とＣが５単位ある中からＡ、Ｂ、Ｃを合計で１０単位以上を提供することを希望することを示す。また、あるリソースが他のリソースの材料になっている場合など、一つのエントリーの中で提供側リソースと需要側リソースが混在してもよく、例えば、  
Ｃ［＝２０］｛−１０Ａ、＋１０Ｂ｝  
は、Ａを１０単位入手し、同時にＢを１０単位提供することを希望することを示す。
【００３４】
なお、特に利用する頻度の高い組み合わせ条件については、ユーザに簡便に記述させるため、予め基本演算子を用意しても良い。そのため、論理積（ＡＮＤ）、排他的論理和（ＸＯＲ）、ＡＮＹなどの演算記号を用意することが好ましい。ここで、「ＡＮＤ」は｛｝内に列挙されたリソースの全てのマッチングを成立させたいという組み合わせ条件を示す。「ＸＯＲ」は｛｝内に列挙されたリソースの中の一つのみのマッチングを成立させたいという組み合わせ条件を示す。また、「ＡＮＹ」は｛｝内に列挙されたリソースの中の何単位のマッチングが成立してもよく、｛｝内のリソースに関して組み合わせ条件が指定されないことを示す。
【００３５】
エントリーを複数の組み合わせ条件からなる階層構造（入れ子構造）で表現して、より複雑なリソース間の関係に対する組み合わせ条件を表しても良い。この場合において、階層構造で親となる組み合わせ条件から見ると、子となる組み合わせ条件はリソース記述と等価な扱いとし、子となる組み合わせ条件が成立した場合は、リソースのマッチングが成立したものと同じ扱いとする。例えば、「部品Ｂ、Ｃを入手して製品Ａを提供したい、もしくは部品Ｂ、Ｄを入手してＥを提供したい」という要求をエントリーとして登録する場合は、次のような、２つの組み合わせ条件ＡＮＤ｛＋Ａ、−Ｂ、−Ｃ｝と、ＡＮＤ｛＋Ｅ、−Ｂ、−Ｄ｝とを演算子ＸＯＲで結びつけた、階層的なエントリーで表す。下記の例では、ＡＮＤ｛＋Ａ、−Ｂ、−Ｃ｝が成立するか、ＡＮＤ｛＋Ｅ、−Ｂ、−Ｄ｝が成立するか、いずれかが成立すればよいことを示す。  
ＸＯＲ｛ＡＮＤ｛＋Ａ、−Ｂ、−Ｃ｝、ＡＮＤ｛＋Ｅ、−Ｂ、−Ｄ｝｝  
また、下記は、ＡＮＤ｛＋Ａ、−Ｂ｝が１００組ある場合に、５０組以上成立させたいことを示す。すなわち、例えば、Ｂを材料としてＡを生産するため、ＡとＢを等量としたい場合などを表現している。  
Ｃ［≧５０］｛１００ＡＮＤ｛＋Ａ、−Ｂ｝｝
図３及び図４は、本発明の一実施形態に係る需給仲介システムを電力取引支援システムとして利用した場合のエントリーの１例と、それぞれのエントリーと併せて示す図である。エントリーでＰ１、Ｐ２等は所定の時間帯の電力商品に相当するリソース名である。図３は発電業者、図４は需要家を示す。２つの子エントリーの組み合わせ条件において、ＡＮＤで指定された部分が、発電機器の特性や需要家の業務のスケジュールで決まる基本運用パタンに相当する部分であり、必ず所定価格で売買したい部分となる。ＡＮＹで囲まれたその他の部分は、売買が成立してもしなくても良いが、基本運用パタン部分の売買が成立した場合に限り売買するオプションに相当する部分である。本発明の実施形態では、基本運用パタンの時系列の長さがエントリー毎に異なっていたり、図４のように分離していたりした場合でも問題なく扱える。
【００３６】
なお、リソース名としては、リソースをユニークに識別できる名称を利用する方法以外に、リソースを指定する属性情報を列挙する方法があり得る。例えば、ユーザがテキスト形式でエントリーを記述する場合は、リソースの型を特定する情報（リソースの型名）や属性値情報に対応する値を列挙して、  
（記述フォーマットＡ、フレーム、ステンレス製、サイズＭ）  
と記述する。また、登録されるリソースの型が統一されている場合は、型名を省略し、単に  
（フレーム、ステンレス製、サイズＭ）  
と属性値情報だけ指定する。属性には、品目を示すＩＤ番号、色、形、材質、場所、時間、主体の名称など、リソースを特定する様々な情報を指定し、扱う属性の種類は限定しない。リソース名照合部１２が、リソース名データを照合する際、型名が一致すれば、以降の属性が対応することが分かり、以降の属性値をそれぞれ比較することでマッチングを取り得るか否かが判断できる。ワイルドカード文字を用いて属性値が記述されている場合にも両者は一致すると判定する場合もある。例えば、以下の２つのリソース名の間ではマッチングが成立するとみなす場合もある。  
＋｛記述フォーマットＡ、フレーム、ステンレス製、＊｝  
−｛記述フォーマットＡ、フレーム、＊、サイズＭ｝  
２つのリソース間の属性値が一致する記述か否かを判定するために、外部の辞書データを参照しても良い。この場合には、例えば、＋｛テレビ、関西｝と−｛テレビ、大阪｝の間で「関西」に「大阪」が含まれると辞書により判断し、マッチングが成立し得ると判定する。また、特定の目的にカスタマイズされた外部の処理モジュールを利用し、例えば数値の大小関係などで属性値が一致する記述か否かを判定しても良い。この場合には、例えば、＋｛テレビ、Ｄａｙ＝５｝、−｛テレビ、Ｄａｙ＝７｝の間で、２番目のリソース値が日を示し、供給側の指定日より需要側の指定日が遅いのでマッチングが成立し得ると判定する場合もある。
【００３７】
なお、属性情報を列挙する方式の場合、各エントリー中の各リソース名には、ＩＤ発行部１９よりシステム内部でのリソース名管理用のＩＤが発行される。これにより、同一のリソース名が異なるエントリーで多用された場合に記憶すべきデータが削減される。新たなエントリーが入力される度に、新しく登録されたエントリーのリソース記述データで新たに出現したリソース名のＩＤと、既に蓄えられているエントリーで使用されているリソース名のＩＤとを参照し、いずれのリソース名の間でマッチングが可能かの判定結果を表形式などのデータによりインデックス情報として記録する。
【００３８】
なお、エントリーのリソース記述データと組み合わせ条件データは、ユーザが入力したエントリーが、グルーピングモジュール３０が処理する前にパーサ（ｐａｒｓｅｒ）などで前処理されることを前提としているので、グルーピング装置１のグルーピングモジュール３０に渡る時点で論理的に等価な情報量を含んでいれば上記の記述方式に限定されない。パーサの前処理は、リソース記述データやエントリーの構造などを予め定義した文法に従い解読する処理であり、従来の文字列処理技術の範囲で対処する。また、端末におけるエントリーの入力方法と候補グループ出力部における候補グループの出力形式は特に限定するものではなく、エントリーは、ユーザが直接テキストとして端末から入力する場合以外に、電力取引支援など特定の目的に応じた入力用ＧＵＩを利用する場合があり得る。
【００３９】
本発明の一実施形態に係るグルーピング機能を説明する。  
なお、以下の議論では。リソースが分割可能リソースであるか、分割不可能リソースであるかを区別する。「分割可能リソース」とは、リソースに需給の基本単位量がなく、需給量を連続量として扱えることを意味する。たとえば、電力、石油、布などは分割可能リソースの例である。パソコン、ディスプレイ、プリンターなどは分割不可能リソースの例である。
【００４０】
まず、図５、図６に示す単純な例で、候補グループ決定部１３で、エントリーをグルーピングする効果について補足説明する。図５において、添付の番号順に需給仲介システムにエントリーが登録されたとすると、組み合わせ条件を考慮せずに既にあるリソースを早い順に順次マッチングしていくと図のようなマッチングとなる（矢印でマッチングされたリソースを繋げて表している）。エントリー２番目、３番目、６番目、９番目に登録されたエントリーは組み合わせ条件を満足しているが、それ以外の１番目、４番目、５番目、７番目、８番目、１０番目に登録されたエントリーが組み合わせ条件を満たさないため、この影響で２番目、３番目、６番目、９番目のエントリーについてもマッチングを確定することができない。図６は、同じ順番でエントリーが登録された場合の、９番目のエントリーが登録された際に候補グループ決定部１３が発見する候補グループとマッチングの例を示す。９番目のエントリーを基点として含み、グループに含まれる全てのエントリーの組み合わせ条件が満足されるような候補グループを組み合わせ演算により発見する。基点となるエントリーは、候補グループ中に必ず含まれなくてはならないと指定されたエントリーであり、必ず１つ以上指定される。基点エントリーは、新規に登録されたエントリーである。あるいは、グルーピング装置１の演算がユーザごとに独立して処理される詳細は後述する第４の実施形態の場合では、対応するユーザの登録したエントリーが基点エントリーとして設定される。あるいは、特に重要なユーザの登録したエントリーで最も重要なエントリーを常に基点エントリーとする場合がある。さらに、基点エントリーが複数個指定される場合もあり、例えば、重要なユーザの登録したエントリーと、新規に登録されたエントリーの２つを基点エントリーとする場合もあり得る。
【００４１】
図７、図８に、本発明による需給仲介システムを電力取引支援システムとして利用した場合に、グルーピング装置１が作成するグループの一例を示す。図７の例では、各事業者が時系列パタンとしてエントリーを登録し、グルーピング装置１は基点となる事業所Ａの登録したエントリーを含み、グループ内の発電量と消費量が全ての時間帯でほぼ均等となる候補グループを発見する。図８はエントリーの記述とグルーピング装置１が作成するグループを対応付けた一例である。ＡＭ，ＰＭはそれぞれリソース名であり、午前、午後それぞれの電力量に相当する。矢印に添えられた数字は、マッチングした電力量を示す。この場合、電力の量の最小単位をきめてやりとりする場合には分割不可能リソースとなり、決めない場合は分割可能リソースとなることに注意する。
【００４２】
本発明における需給仲介システムで候補グループを作成するための組み合わせ最適化演算には「基点エントリーについての最適化」と「候補グループに含まれる全てのエントリーについての最適化」の２種類の基準がある。組み合わせ最適化演算を数式で表現した例を数式（２）及び数式（３）に示す。
【００４３】
【数２】
2005063426.tif 000004
【００４４】
【数３】
2005063426.tif 000005
【００４５】
数式（２）において、第一式が基点エントリーについての最適化の目標関数であり、基点となるエントリーに含まれるリソースに関するマッチング重みの和を最大化することを目標とした最適化演算を行う。例えば、リソース毎に希望販売、希望購買価格が設定されていると、マッチングされたリソース間の希望販売、希望購買価格価格の差額をマッチング重みとすることで、エントリーを登録したユーザの売買利益を反映する（差額の一部がユーザにキャッシュバックされる前提とする）。第二式は、リソースが一対一でマッチングするための制約式であり、第三式は組み合わせ条件の制約式、第四式は基点エントリーが候補グループに含まれる制約式である。
【００４６】
数式（３）において、第一式が、候補グループに含まれる全てのエントリーについての最適化のための目標関数である。それぞれのエントリーの含むリソースに関するマッチング重みの和の値が、各エントリーに設定された目標値を下回る値をペナルティ値とし、これを最少とすることを目標とした最適化演算を行う。第二式と第三式は数式（２）と同じ意味である。なお、候補グループを発見した後の合意成立を容易にするため、グループに含まれるエントリーの数が、予め定められた最大値以下である条件も加わる場合もある。
【００４７】
上記の数式（２）の最適化目標の設定によると、基点となるユーザが幹事事業者や系列における親会社などであり、基点となるユーザの利益が最優先でその他のユーザは組み合わせ条件を満足すること以外は考慮されないような需給仲介となる。
【００４８】
また、上記の数式（３）の最適化目標の設定によると、基点となるユーザ以外のユーザも候補グループに含まれるユーザについては各々の利益目標が考慮されるような需給仲介となり、候補グループに含まれるエントリーの数を小さく抑える効果と、候補グループ中に含まれる全てのエントリーに対して評価基準を高くすることを両立できる。このため、候補グループに対し各ユーザの合意を取ることが容易になることが期待できる。
【００４９】
本発明における需給仲介システムで候補グループを作成するための組み合わせ最適化演算（数式（２）および数式（３））は、混合整数計画法と呼ばれるオペレーションリサーチの方法を用いて、厳密に組み合わせ条件に関する制約を守る最適解（候補グループ）を得ることが可能である。ただし、問題の規模が大きくなると最適解を得ることが困難になることが予想されるため、第一の実施形態においては探索的手法を用いて準最適な解を高速に得る方式を中心に述べる。混合整数計画法を用いる場合は、第二の実施形態として説明する
本発明の一実施形態に係る候補グループ決定部１３の処理動作概要を、図９に示すフローチャートを参照して説明する。候補グループの決定のための処理動作は、上記のように、新たなエントリーの登録をトリガーとして実行するか、ユーザから新しいグルーピング演算の要求があった場合に実行する。
【００５０】
まず、基点となるエントリーを指定する（ステップＳ１）。すると、仮グループ決定部２１は、当該基点のエントリーとを含む仮グループを生成する（ステップＳ２）。
【００５１】
グループ内マッチング決定部２２は、仮グループ中のエントリーにマッチング対象を限定した、グループ内マッチングを行う（ステップＳ３）。すなわち、本ステップでは、仮グループ内のエントリー間で需給関係にある（マッチングの成立する）リソース間を決定する。次に、組み合わせ条件ペナルティ演算部２４は、仮グループ内のエントリーのマッチングを基に、各エントリーの組み合わせ条件ペナルティを演算する（ステップＳ４）。
【００５２】
グループ評価値演算部２３は、組み合わせ条件ペナルティを元に仮グループ全体のグループ評価値を演算して（ステップＳ５）、候補グループを評価値とともに候補グループ記憶部２５に一時記憶する（ステップＳ６）。
【００５３】
一時記憶した仮グループの数が所定数を越えた場合は（ステップＳ７のＮＯ）、ステップＳ９に進む。そうでない場合は（ステップＳ７のＹＥＳ）、評価値の最も悪い仮グループを候補グループ記憶部２５から削除し、ステップＳ９へ進む（ステップＳ８）。
【００５４】
処理を開始してからの時間が予め定められた制限時間内であるとき、あるいは、得られた仮グループの評価値が予め定めた終了条件を満たしていないとき（ステップＳ９のＮＯ）、ステップＳ２へ戻り、今まで生成したとのとは異なる他の仮グループを生成し、上記ステップＳ３〜ステップＳ９を繰り返す。ステップＳ９で、制限時間になったか、あるいは、終了条件を満たす評価値の仮グループが得られたときには（ステップＳ９のＹＥＳ）、候補グループ記憶部２５に記憶されている仮グループを候補グループ出力部１４から候補グループとして出力する（ステップＳ１０）。
【００５５】
組み合わせ条件ペナルティは、各エントリーに指定された組み合わせ条件を満足する候補グループとグループ内マッチングを、探索的手法により決定する際に、探索途中の暫定解の取捨選択の指針として用いる値である。基点エントリーを含み、かつグループに含まれる全てのエントリーのペナルティ値が０となる候補グループを求めることが探索的手法による最適化演算の目的となる。
【００５６】
以下に組み合わせ条件ペナルティの演算方法の一例を説明する。ここで、エントリーｅ内の各リソースをｅｉ（ｉ＝１、２、…、ｍ）と表し、組み合わせ条件が複数個あり入れ子構造となる一般的なエントリーを考え、それぞれの組み合わせ条件をｅｉ（ｉ＝ｍ＋１、…、ｎ）と表す。ｅｉ（ｉ＝１、２、…、ｎ）に対して、「０」と「１」のいずれか一方の値をとる変数Ｘｉを定める。各リソースｅｉ（ｉがｍ以下）については、それが仮グループの中でマッチング成立すればＸｉ＝１とし、さもなくばＸｉ＝０とする。各組み合わせ条件ｅｉ（ｉがｍ＋１以上）については、指定された制約が満足されればＸｉ＝１、満足されていなければＸｉ＝０とする。エントリーの組み合わせ条件ペナルティは、エントリー内の各組み合わせ条件につきそれぞれ演算されたペナルティ値Ｐｉを総和した値とする。各組み合わせ条件ｅｉのペナルティ値Ｐｉは、階層構造におけるｅｉの子となる組み合わせ条件とリソースの変数Ｘｊの和をもとに算出する。
【００５７】
組み合わせ条件ｅｉの子ｅｊ（ｊ＝１、２、３、…）の集合をＣｉと表す。マッチングの成立を希望する子の数の目標値ｋｉと、階層構造におけるｅｉの子となる組み合わせ条件とリソースの変数Ｘｊの和の差を「−１．０」から「１．０」の間に正規化した値で表すために、数式（４）で変数Ｄを算出する。そして、このＤの値から、組み合わせ条件ペナルティを算出する方法は、ｅｉの組み合わせ条件によって異なり、数式（４）のようになる。
【００５８】
【数４】
2005063426.tif 000006
【００５９】
グループ評価値は、数式（２）の目的関数の符号を反転した値か、もしくは数式（３）の目的関数の値を、組み合わせ条件ペナルティ値の総和数式（４）と合計し、仮グループ全体のグループ評価値として利用する。
【００６０】
図９のステップＳ２では、処理時間が制限時間に達するまで、あるいは、終了条件を満たす評価値をもつ候補グループが得られるまで、異なる複数の仮グループを生成する。仮グループを生成するには、演算の途中段階で既に一部演算を試みた他の仮グループや記憶されている候補グループを変形して用いても良い。例えば、新たにエントリーを追加したり、エントリーを削減したり、複数の仮グループを１つの仮グループにまとめたり、逆に１つの仮のグループを複数に分割したりする処理が例として考えられる。
【００６１】
図９のステップＳ３では、同一仮グループに含まれるエントリー間で需給関係のあるリソース間を具体的に対応付け、仮グループ内のマッチングを決定する。通常は、具体的にどの供給側のリソースと需要側のリソースを対応付けるのか、エントリー間の各リソースの需給関係がグループ内で一意に決まらない。グループ内マッチングの取り方によって各エントリーの評価値や仮グループの評価値も変化する場合がある。例えば、図１０において、供給リソースを表すリソース記述データから需要リソースを表すリソース記述データへ向けた矢印で、需給関係のリソース間のマッチング（対応付け）を表しているが、同じエントリー（Ｅ１１からＥ１３）からなる仮グループＴＧ１でもグループ内マッチングの決め方は複数パタンある。このため、グルーピング装置１が特定のルールに従い各エントリー中のリソースやグループ内のエントリーにマッチングのための優先度を設定し、この優先度を利用してグループ内マッチングを一意に決定する。優先度の設定方法の例については後述する。また、以前の仮グループを再利用して新たに仮グループを作成する時に、以前の仮グループの中で既にマッチングした部分は変更しないことで、グループ内マッチングが一度に大きく変化することを防止する。グループ内マッチングの決定方法の例については後に具体例を述べる。
【００６２】
リソース記述データにリソースの数量を指定する付加データが付加されている場合は、意味的には全く同じリソースが複数有り、それぞれに同じ組み合わせ条件が定義されたと解釈する。このため、これらのリソース間のマッチングの取り方でエントリーのペナルティ値は変化しない。
【００６３】
グループ内マッチングの決め方は、全てのマッチングの取り方の中でグループの評価値の最も良いものを採用するか（この場合は、マッチングリソースを変更しながら、上記ステップＳ３〜ステップＳ６を繰り返して最も評価値のよいグループ内マッチングを求める）、予め決めたルールに従い一意にグループ内マッチングを決定する方法がある。
【００６４】
具体的な探索的解法の一例として、途中で生成した順列のうちで評価の良い順列を一時記憶するリストを設け、このリストに記録されている順列のなかで一番評価の大きい順列を常に最優先で調べる、最良優先探索と呼ばれる探索的解法を用いる場合について簡単な例を用いて、図１１、１２に示すフローチャートを参照して説明する。
【００６５】
この場合、基点エントリーにエントリーを順次追加して決まった手順でマッチングし、その後にグループ評価値を演算することを反復して、仮グループを徐々に大きくしながら探索していく解法が一例として考えられる。探索する対象は、仮グループにマッチング可能なエントリーを追加する順番であり、言い換えると、基点エントリーを先頭とするエントリーの順列である。リストに記録する順列の数は最大サイズを予め決めておき、リストに記録された順列の数がこれを越えた場合、評価値の悪い順列から削除する。順列内の各エントリーについてペナルティ値を算出し、本例ではマッチング重みは全て０と設定し、組み合わせ条件ペナルティの総和をグループ評価値とする。
【００６６】
ここでは、以下の５つのエントリーＥＮ１からＥＮ５がエントリー記憶部１５に記憶されている。これは、図８で示したように、電力取引支援におけるエントリーの記述を単純化したものに対応する。ここでは売買単価は設定されていないとする。エントリーＥＮ１〜ＥＮ５は、この順に登録されたものとする。  
ＥＮ１：  
ＡＮＤ｛  
ＡＮＤ｛＋５ＡＭ，＋１５ＰＭ｝，  
ＡＮＹ｛＋２ＡＭ，＋２ＰＭ｝  
｝  
ＥＮ２：  
ＡＮＤ｛  
ＡＮＤ｛−２０ＡＭ｝，  
ＡＮＹ｛−２ＡＭ，−２ＰＭ｝  
｝  
ＥＮ３：  
ＡＮＤ｛＋１５ＡＭ，＋５ＰＭ｝  
ＥＮ４：  
ＡＮＤ｛＋１５ＡＭ，−２ＰＭ｝  
ＥＮ５：  
ＡＮＤ｛＋２ＡＭ，＋２０ＰＭ｝  
ここに新たにエントリーＥＮ６：ＡＮＤ｛−２０ＰＭ｝がエントリー入力部１１から入力されたとする。
【００６７】
まず、仮グループ決定部２１は、第１のリストＬ１と第２のリストＬ２を初期化して空にする（ステップＳ１０１）。リストＬ１は探索の途中結果を一時的に記憶し、リストＬ２は出力する候補グループとなり得る仮のグループが発見された際に、探索を継続しながら一時的に記憶するために用意する。
【００６８】
基点エントリーをエントリーＥＮ６とし（ステップＳ１０２）、第１のリストＬ１に記録する（ステップＳ１０３）。この基点エントリーに対し（ステップＳ１０４）、マッチング可能なリソース（＋ＰＭ）を持つエントリーであるエントリーＥＮ１、ＥＮ３、ＥＮ５をそれぞれ追加し、図１３の探索木の（１）−（３）の部分のように順列（ＥＮ６、ＥＮ１）、順列（ＥＮ６、ＥＮ３）、順列（ＥＮ６、ＥＮ５）という３つの順列を作成する（ステップＳ１０５）。なお、基点エントリーが複数個指定された場合は、基点エントリーからなる順列を最初に作成してから探索処理に移行する。例えば、ＥＮ６、ＥＮ１、ＥＮ３の３つが基点エントリーに指定された場合は、  
（１）  順列（ＥＮ６、ＥＮ１）のグループ内マッチング  
（２）  順列（ＥＮ６、ＥＮ１、ＥＮ３）のグループ内マッチング  
の順でマッチングを実施した後に順列（ＥＮ６、ＥＮ１、ＥＮ３）から探索を開始する。
【００６９】
グループ内マッチング決定部２２は、この作成された各順列について、需給関係にあるリソース間を対応付ける（ステップＳ１０６）。グループ内マッチング決定部２２は、各順列で、リソース間でマッチングの成立するリソース間をマッチングし、このときまだ、マッチングの成立していないリソースをそれぞれの順列毎に記憶する。本実施形態のようにリソース名に複数のリソースが対応付けられている場合は、需給関係にあるリソース間を対応付ける際に、リソースに指定された数量から、マッチングの成立したリソースの数を差し引きし、今だマッチングのされていないリソースの数を記憶する。例えば、順列（ＥＮ６、ＥＮ１）だと、図１４に示すように、ＥＮ６の「−２０ＰＭ」とＥＮ１のＡＮＤ条件の下の「＋１５ＰＭ」およびＡＮＹ条件の下の「＋２ＰＭ」が対応付けられる。図１４において、矢印は需給方向、矢印に添付されたリソース名と数値はマッチングしたリソース名と数量に相当する。また、マッチングの成立していなリソースはＥＮ６の「−３ＰＭ」とＥＮ１の「＋５ＡＭ」およびＡＮＹで指定されたリソースである。
【００７０】
ペナルティ演算部２４は、上記の各順列中のエントリーのそれぞれについて組み合わせ条件ペナルティ値を算出する（ステップＳ１０７）。順列の各エントリーのペナルティ値が、全て０であるときは、当該順列が求めるべき候補グループの一つとなり得るので（ステップＳ１０８）、それをリストＬ２へ記憶する（ステップＳ１０９）。
【００７１】
ここでは、２つの順列いずれもそのような順列ではないので、ステップＳ１１０へ進み、上記数式（４）を用いて、各順列について、数式４で仮グループ（順列）に含まれるエントリーのペナルティ値の総和を計算する。例えば順列（ＥＮ６、ＥＮ１）を例に演算する。ＥＮ６のＡＮＤ条件が一つでその子であるリソース２０単位の内で計１７単位がマッチング成立するため、ペナルティは、−（２０−１７）／２０＝−０．１５である。ＥＮ１のＡＮＤ条件は２つだが最上位の階層のＡＮＤ条件は子のＡＮＤ条件さえ成立すればいつでも成立するため無視し、下位のＡＮＤ条件の子であるリソース２０単位の内で１５単位がマッチング成立するため、ペナルティは、−５／２０＝−０．２５である。よって順列（ＥＮ６、ＥＮ１）についてのペナルティ総和は−０．４となる。他の順列のグループ評価値も演算した結果を以下に示す。
【００７２】
順列（ＥＮ６、ＥＮ１）  ペナルティ値：−０．４  
順列（ＥＮ６、ＥＮ３）  ペナルティ値：−０．７５−０．７５＝−１．５  
順列（ＥＮ６、ＥＮ５）  ペナルティ値：−０．０−０．２＝−０．２  
上記３つの順列のエントリーの数は、予め定められた最大数（ここでは仮に５とする）に満たないで（ステップＳ１１１）、これら３つの順列を第１のリストＬ１に追加し（ステップＳ１１２）、第１のリストＬ１に記録された順列をグループ評価値の大きい順に並び替える（ステップＳ１１４）。第１のリストＬ１上の順列の数が、予め定められた最大数を超えるときは、末尾の方から順に（ぺナルティ値の最も大きいものから順に）順列を削除する（ステップＳ１１５）。さらに、処理を開始してからの経過時間が予め定められた制限時間内であれば（ステップＳ１１６）、ステップＳ１０４へ戻る。
【００７３】
ステップＳ１０４では、第１のリストＬ１の先頭から順に次ぎの処理対象の順列を取り出す。すなわち、最もグループ評価値の大きい順列（ＥＮ６、ＥＮ５）にさらにエントリーを追加する。ＥＮ５の「＋２ＡＭ」が残っている状態なので、マッチング可能なのはリソース（−ＡＭ）を含むエントリーＥＮ２、のみであり、図１３の（４）に示したように、順列（ＥＮ６、ＥＮ５、ＥＮ２）が作成される（ステップＳ１０５）。順列（ＥＮ６、ＥＮ５、ＥＮ２）のマッチング結果は図１５のようになる。
【００７４】
なお、原則として仮グループ内で一度マッチングしたリソースはマッチング相手を変更せず、まだマッチングされていないリソースのみマッチング対象と考えることで、マッチングを高速に一意に決定する。ただし組み合わせ条件でＡＮＹで指定されたリソースに関しては組み合わせ条件がないため例外となり、ステップＳ１０５でＡＮＹで指定されたリソースに関してマッチングを一旦切断する。同じ順列内でマッチングの方法が複数ある場合、順列に対しマッチングが高速に一意に決定でき、かつ基点エントリーに有利となるよう、以下の原則に従いマッチングの優先度を決定し、優先度の高いリソースから順番にマッチング可能なリソースを対応付ける。
【００７５】
（１）  先に順列に追加されたエントリーのリソースから優先的にマッチングを行う。  
（２）  エントリー内で同じリソースが複数ある場合、エントリー内の予め定められたリソースの優先順位に従いマッチングを行う。優先順位は、ＡＮＹで組み合わせ条件を指定されたリソースが最低であり、Ｃ［≧ｎ］｛｝、Ｃ［＝ｎ］｛｝で組み合わせ条件を指定されたリソースは組み合わせ条件が満足されるまでは最大の優先度とする。すなわち、ＡＮＤで組み合わせ条件を指定されたリソースは常に最大の優先度となる。
【００７６】
例えば、図１６（ａ）のように順列（ＥＮ６、ＥＮ１）にＥＮ２を追加すると、優先度は添付の番号の順となり、ＥＮ６の−５ＰＭから順次マッチングを決定し、図１６（）のグループ内マッチングとなる。
【００７７】
同様にして、順列（ＥＮ６、ＥＮ５、ＥＮ２）について、各エントリーのペナルティ値とグループ評価値を算出する（ステップＳ１０６〜ステップＳ１１０）。その結果を以下に示す。  
順列（ＥＮ６、ＥＮ５、ＥＮ２）ペナルティ値：−０．０−０．０−０．９＝−０．９  
これら順列中のエントリーの数は、予め定められた最大数５より小さいので、これら順列は第１のリストＬ１に登録される（ステップＳ１１２）。
【００７８】
ステップＳ１１４で第１のリストＬ１に登録された順列をグループ評価値の高い順にソートした結果、バックトラックが発生する。すなわち、順列（ＥＮ６、ＥＮ５、ＥＮ２）よりも、先に生成した第１のリストＬ１に保存した順列（ＥＮ６、ＥＮ１）の方がグループ評価値が良いため、第１のリストＬ１の先頭は、順列（ＥＮ６、ＥＮ１）となる。従って、次回のステップＳ１０４以下の処理では、この順列（ＥＮ６、ＥＮ１）を処理対象の順列として、前述同様の処理を行う。
【００７９】
順列（ＥＮ６、ＥＮ１）は、リソース（＋ＰＭ）もしくは（−ＡＭ）を含むエントリーＥＮ２もしくはＥＮ３とマッチング可能であるので、図１３の（５）（６）に示すように、順列（ＥＮ６、ＥＮ１、ＥＮ２）、順列（ＥＮ６、ＥＮ１、ＥＮ３）が生成される（ステップＳ１０５）。前述同様にして各エントリーのペナルティ値とグループ評価値を算出する（ステップＳ１０６〜ステップＳ１１０）。その結果を以下に示す。  
順列（ＥＮ６、ＥＮ１、ＥＮ２）  ペナルティ値：  −０．８  
順列（ＥＮ６、ＥＮ１、ＥＮ３）  ペナルティ値：  −１．０  
ステップＳ１１４で第１のリストＬ１に登録された順列をグループ評価値の高い順列（ＥＮ６、ＥＮ１、ＥＮ２）にさらにエントリーを追加し、図１３の（７）に示したように、順列（ＥＮ６、ＥＮ１、ＥＮ２、ＥＮ３）が作成される。エントリーＥＮ６、ＥＮ１、ＥＮ２、ＥＮ３の全てのペナルティ値が０となるので（ステップＳ１０８）、探索を終了する（ステップＳ１０９）。順列（ＥＮ６、ＥＮ１、ＥＮ２、ＥＮ３）のグループ内マッチングを図１７に示す。
【００８０】
（第２の実施形態）  
本第２の実施形態では、候補グループを発見する最適化演算方法として探索的解法ではなく混合整数計画法を用いて解くことを想定している。
【００８１】
図１８は、第２の実施形態に関わる需給仲介システム全体の概略構成例を示した図であり、図１と同じ部分には、同じ符号を付し、詳細な説明は省略する。図１８に示す構成において、候補グループ決定部１３の構成が図１に示す構成と異なり、候補グループ決定部１３が、制約式・目的関数作成部２６と混合整数線形計画問題解決部２７と候補グループ記憶部２５を有している。
【００８２】
混合整数計画問題解決手段は、目的関数の値を最大または最小にする変数の組の１つおよびそのときの最適値を線形不等式および変数の整数制約により与えられた制約条件を満たす範囲内で探し出し出力する。また、そのような最適解が存在しない場合や非有界である場合は、その旨を出力する。さらに、時間制限を設けることにより、その制限時間内に得られた最良値を返すことも可能である。混合整数線形計画問題の解法としては、線形計画問題の解法である単体法と、分枝限定法、切除法といった手法とを組み合わせる手法などが知られており、それらを利用した高速かつ汎用の混合整数計画問題解決手段としては、ＩＬＯＧ社が開発したＣＰＬＥＸと呼ばれるソフトウェアがよく知られている（参考ｈｔｔｐ：／／ｗｗｗ．ｉｌｏｇ．ｃｏｍ／ｐｒｏｄｕｃｔｓ／ｃｐｌｅｘ）。
【００８３】
本実施形態における需給仲介システムにおいて、候補グループを作成するための組み合わせ最適化演算は、基点エントリーの効用値の最大化を目的関数とするか、あるいは、個々のエントリーの目標値との差分の最小化を目的関数とするかの二種類の最適化基準を有する点を特長とする。  
ここで、個々のエントリーの効用値とは、各エントリーが各需給マッチングの結果得られる満足度を数値化した値のことであり、この値が大きい程、エントリーを登録したユーザの満足度は大きいものとする。
【００８４】
二種類の最適化基準を用いたそれぞれの最適化問題の構成を、数式（５）および数式（６）に示す。  数式（５）は数式（２）を、数式（６）は数式（３）をそれぞれ一般化した最適化問題（記号の対応が一部変更されていることに注意）の定義となっている
【００８５】
【数５】
2005063426.tif 000007
【００８６】
【数６】
2005063426.tif 000008
【００８７】
なお、数式（５）および数式（６）において、集合の定義は、  
I: リソースの集合  
Ik: エントリーｋに対するリソースの集合  
MIi: ｉとマッチング可能なリソースの集合  
E: エントリーの集合  
変数は、  
xk: エントリーｋの決定変数(候補グループに参加: 1, 不参加: 0)  
yij: リソースｉとｊのマッチング決定変数(マッチング成立: 1, 不成立: 0)  
zi: リソースｉの決定変数(マッチング成立: 1, 不成立: 0)  
zk: エントリーｋに属するリソース決定変数を集めたベクトル  
Uk: エントリーｋが得る効用値  
定数は、  
Uk*: エントリーｋに設定された目標値  
wij: リソースｉとリソースｊのマッチング重み(マッチング成立: 1, 不成立: 0)  
mi: リソースｉの成立量の最小値  
Mi: リソースｉの成立量の最大値  
b: 基点エントリー  
関数は、  
fk(zk): エントリーｋのリソースzkの組み合わせ条件を表す関数  
(zkが組み合わせ条件を満足: 1, 全て未成立: 0, 組み合わせ条件を満たさない: 0, 1以外)  
で定義される。
【００８８】
数式（５）は基点となるユーザの効用値の最大化をおこなう最適化問題である。この場合基点となるユーザは、たとえば幹事事業者や系列における親会社などであり、基点となるユーザの利益が最優先でその他のユーザは組み合わせ条件を満足すること以外は考慮されないような需給仲介となる。
【００８９】
一方、数式（６）は、各エントリーが目標値を設定した下で、候補グループに含まれるエントリーに関して、目標値との差分を最小化する最適化問題である。この場合、基点となるユーザ以外のユーザに関しても目標値を考慮するような需給仲介となり、候補グループに含まれるエントリーの数を小さく抑える効果と、候補グループ中に含まれる全てのエントリーに対して評価基準を高くすることを両立できる。このため、候補グループに対し各ユーザの合意を取ることが容易になることが期待できる。
【００９０】
数式（６）の最適化の手法は多目的最適化の分野でよく知られた、目標計画法と呼ばれる手法（参考ｈｔｔｐ：／／ｌｅｃｔｕｒｅ．ｅｃｃ．ｕ−ｔｏｋｙｏ．ａｃ．ｊｐ／ｏｋａｔｕ／Ｐｌａｎｎｉｎｇ／６０ｍｕｌｔｉｏｂｊ．ｈｔｍｌ）に類似している。しかし、従来の目標計画法では全エントリーに関するペナルティを考慮するのに対し、本発明では候補グループに参加するエントリーに関してのみのペナルティの総和を計算する点が異なる。
【００９１】
これらの二種類の最適化問題が、本発明により提案するグルーピング手法と等価な混合整数計画として表現できることを以下に説明する。
【００９２】
なお以下の議論において、リソースｉとリソースｊのマッチング決定変数ｙｉｊは、リソースが分割不可能リソースである場合は非負整数であり、リソースが分割可能リソースである場合は非負実数であることに注意する。それ以外の式や変数は、リソースが分割可能リソースであるか、分割不可能リソースであるかに依存しない。
【００９３】
数式（５）における目的関数（Ｏ１）は、基点エントリーの効用値Ｕｂを最大化することを目的とした目的関数である。ここで、各エントリーの効用値Ｕｋの値は、数式（５）および数式（６）における式（ＣＵ）で定義されているように、当該エントリーに属する各リソースにおける、マッチング相手のリソースとのマッチングに付加された重みの総和の値である。
【００９４】
例えば、リソース毎に希望販売、希望購買価格が設定されている場合に、マッチングされたリソース間の希望販売、希望購買価格の差額をマッチング重みとすることができる。この場合、差益がユーザにキャッシュバックされるとすると、エントリーを登録したユーザの売買利益を反映できる。
【００９５】
数式（６）における目的関数（Ｏ２）は、候補グループに含まれる全てのエントリーに関するペナルティ値の総和を最小化するための目的関数である。ここでペナルティ値とは、各エントリーが定めた目標値打と実際に得られた効用値との差分のこととする。なお、各エントリーの効用値Ｕｉは、グループに参加しない場合（ｘｉ＝０）は、必ずＵｉ＝０となることから、ｘｉＵｉ＝Ｕｉが成立するので、目的関数を括弧内のような変数に関する一次式に変形することができる（Ｕｉ＊は定数であることに注意する）。
【００９６】
次に、数式（５）および数式（６）における制約式（Ｇ）は、基点エントリーが候補グループに含まれることを表す制約式である。
【００９７】
数式（５）および数式（６）における制約式（ＣＭ）は、各リソースｉを含むエントリーがもしもマッチングするならば、最低量ｍｉ以上、最大量Ｍｉ以下のリソースをマッチングするという需給制約を表す。これは、リソースが分割可能リソースであるか、分割不可能リソースであるかによらない。なおリソースが分割不可能リソースでありかつリソースの量が丁度１単位である場合など、最小量と最大量が一致しｍｉ＝Ｍｉとなる場合は、括弧内の等式制約となる。
【００９８】
数式（５）および数式（６）における制約式（ＣＬ）は、各エントリーに属するリソースの組み合わせ条件を（簡単のために一本の式で）形式的に表現した組み合わせ制約に相当する。この制約式における組み合わせ関数ｆは、リソースの組み合わせが、エントリーが許容する組み合わせである場合に１、全てのリソースの決定変数が０である場合に０、それ以外の場合には０又は１以外の値を取る関数であるとする。このように定めると、形式的に各エントリーの組み合わせ条件を表現できる。
【００９９】
実際の問題ではエントリーが定めた条件に応じて、複数の線形不等式および等式に変換を行う。本発明においては、この組み合わせ制約を複数の線形不等式および等式によって表現し、混合整数計画問題解決手段に入力可能な形に変形する。
【０１００】
この組み合わせ制約の最も単純な例は、エントリーが全てのリソースの成立を必要条件とする場合である。エントリーｘ１の３個全てのリソース（ｚ１，ｚ２，ｚ３）のマッチング成立に相当する条件（ＡＮＤ｛ｚ１，ｚ２，ｚ３｝）は、数式（７）の線形な等式によって表現できる。数式（７）は、ｚ１，ｚ２，ｚ３の全てのリソースがマッチング成立する場合に限り、ｘ１が候補グループに参加するという許容解を有する。  
（ｚ１＋ｚ２＋ｚ３）／３＝ｘ１  （７）  
この他たとえば、エントリーｘ１の３個のリソース（ｚ１，ｚ２，ｚ３）のうち丁度２個のリソースのマッチング成立に相当する条件（Ｃ［＝２］｛ｚ１，ｚ２，ｚ３｝）は、数式（８）の線形等式によって表現できる。数式（８）は、ｚ１，ｚ２のリソースがマッチング成立、ｚ２，ｚ３のリソースがマッチング成立、ｚ１，ｚ３のリソースがマッチング成立、のいずれかの場合に限り、ｘ１が候補グループに参加するという許容解を有する。  
（ｚ１＋ｚ２＋ｚ３）／２＝ｘ１  （８）
一般に、あるエントリーに属するリソースの間にどのような組み合わせ条件を希望する場合にも、いくつかの整数変数を追加することで、一個以上の線形な等式および不等式によって表現可能であることが分かる。たとえば、マッチング成立させたいリソース数量の下限値が組み合わせ条件として指定された場合は、線形不等式に変形される。
【０１０１】
組み合わせ条件を階層的に組み合わせた場合においても、同様の変換が可能であり、たとえば、３個のリソース（ｚ１，ｚ２，ｚ３）を含むエントリーｘ１が、「ｚ１，ｚ２のどちらかもしくは両方が成立し（Ｃ［≧１］｛ｚ１，ｚ２｝）、かつｚ３が成立するならば、グループに参加する」いう組み合わせ条件ＡＮＤ｛Ｃ［≧１］｛ｚ１，ｚ２｝，ｚ３｝を希望する場合を考える。この場合、組み合わせ条件はたとえば、数式（９）の２本の制約式によって表現できる。数式（９）は、ｚ１，ｚ２，ｚ３の全てのリソースがマッチング成立、ｚ１，ｚ３が成立、ｚ２，ｚ３が成立、のいずれかの場合のみ、ｘ１が候補グループに参加するという許容解を有する。
【０１０２】
（１／３）ｚ１＋（１／３）ｚ２＋（２／３）ｚ３≧ｘ１
（１／３）ｚ１＋（１／３）ｚ２＋（２／３）ｚ３≦（４／３）ｘ１    （９）
数式（５）および数式（６）における制約（ＣＸ）（ＣＹ１）（ＣＹ２）は、変数の変域に関する制約である。（ＣＸ）は、エントリーおよびリソースの決定変数であるｘｉおよびｚｋが０−１変数であることに相当する。一方、（ＣＹ１）（ＣＹ２）は変数ｙに関する条件であり、マッチングに対応するリソースｉとリソースｊが共に分割可能リソースの場合は、非負実数制約（ＣＹ１）が必要であり、分割可能リソースの場合は非負整数制約（ＣＹ２）が必要である。
【０１０３】
なお、数式（５）および数式（６）による最適化問題は一例であり、候補グループに含まれるエントリーの数に関する最大最小制約、同一エントリー内の複数リソース間にまたがるマッチング量の最大最小制約、同一エントリー内の複数リソース間の和や差、あるいはその組み合わせに関する制約などが加わる場合もある。これらの付加的な制約はいずれも一個以上の一次の等式または一次の不等式によって表現可能である。
【０１０４】
電力取引の例において具体的に説明する。下記の４個のエントリー  
Ｅｎｔｒｙ  ｘ１：  
ＡＮＤ｛  
Ｃ［≧１］｛＋３ＡＭ￥１０｝，（ｚ１とする）  
Ｃ［≧１］｛＋３ＰＭ￥８｝（ｚ２とする）  
｝  
Ｅｎｔｒｙ  ｘ２：  
Ｃ［≧１］｛＋２ＡＭ￥６｝  （ｚ３とする）  
Ｅｎｔｒｙ  ｘ３：  
ＸＯＲ｛  
Ｃ［≧１］｛−３ＡＭ￥８｝，（ｚ４とする）  
Ｃ［≧１］｛−３ＰＭ￥１２｝（ｚ５とする）  
｝  
Ｅｎｔｒｙ  ｘ４：  
ＡＮＤ｛  
Ｃ［≧１］｛一２ＡＭ￥１１｝，  （ｚ６とする）  
Ｃ［≧１］｛−３ＰＭ￥９｝  （ｚ７とする）｝  
が登録された状態で、エントリーｘ２を基点エントリーとして、数式（５）の目的関数を用いて定式化すると、数式（１０）となる。
【０１０５】
【数７】
2005063426.tif 000009
【０１０６】
エントリーｘ１，ｘ２は、電力供給者であり、エントリーｘ３，ｘ４は電力需要者である。リソースの種類は（ＡＭ，ＰＭ）の二種類があり、各リソースには単位量あたりの価格が付いている。なおここでのリソースの需給には取引単位が存在する、分割不可能リソースであるとする。
【０１０７】
エントリーｘ１，ｘ２，ｘ３，ｘ４は、それぞれ２種類、１種類、２種類、２種類のリソースの必要または提供の希望を有しており、それらをｚ１からｚ７とする。なお、各リソースの需給最低量は、左側のＡＮＤ条件に対応する量であり、需給最大量はこの値に、右側のＡＮＹ条件に対応する量を加えた童である。
【０１０８】
異符号のリソース間は、内容（ＡＭ又はＰＭ）が一致し、かつ買値が売値を上回る場合にマッチング可能である。この場合、ｚ１，ｚ６間、ｚ２，ｚ５間、ｚ２，ｚ７間、ｚ３，ｚ４間、ｚ３，ｚ６間のマッチングが可能である。このマッチングに対応する需給量を表す変数をｙ１６，ｙ２５，ｙ２７，ｙ３４，ｙ３６とする。
【０１０９】
このマッチングに対応する重みは、売値と買値の差額であり、ｚ１，ｚ６間、ｚ２，ｚ５間、ｚ２，ｚ７間、ｚ３，ｚ４間、ｚ３，ｚ６に対応する重みは、それぞれ、１，４，１，２，５となる。
【０１１０】
各エントリーの効用値は、このマッチングの重みの総和となる。たとえば、ｘ２の効用値Ｕ２は数式（１０）の制約式の第一式で与えられる。
【０１１１】
ここで考えている、エントリーｘ２を基点エントリーとした基点エントリーの効用値の最大化の条件は、目的関数（Ｏ１）および、基点エントリーの参加条件に関する制約（Ｃｂ）に相当する。
【０１１２】
数式（１０）の制約式の第三式から第九式は、需給制約（ＣＭ）に相当する。ここで、各リソースは複数のリソースとマッチング可能であることに注意する。
【０１１３】
数式（１０）の制約式の第十式から第十三式は、組み合わせ制約（ＣＬ）に相当する。エントリーｘ１（第十式）およびｘ４（第十三式）は二個のリソースが同時にマッチングしないと、候補グループに参加しないというＡＮＤ制約に相当し、ｘ３に関する制約式（第十二式）は二個のリソースｚ４）ｚ５のどちらか一方のみがマッチングする場合に限り、候補グループに参加するというＸＯＲ制約に相当する。
【０１１４】
この最適化問題を、混合整数計画問題解決手段を用いて解くと、最適値はＵ２＝７となり、そのときの最適解の１つである、（Ｕ１，Ｕ２，Ｕ３、Ｕ４）＝（２，７，２，７）、（ｘ１，ｘ２，ｘ３，ｘ４）＝（１，１，１，１）、（ｙ１６，ｙ２５，ｙ２７，ｙ３４、ｙ３６）＝（１，０、１，１，１）等が得られる。これは、エントリーｘ１，ｘ２，ｘ３，ｘ４が参加する候補グループにおいて、リソースｚ１，ｚ６間で１単位，ｚ２，ｚ７間で１単位，ｚ３，ｚ４間で１単位，ｚ３，ｚ６間で１単位，の需給マッチングをおこなった場合に、エントリーｘ２の効用値の最大値７が得られ、それ以外のエントリーｘ１，ｘ３，ｘ４の効用値は、それぞれ２，２，７であると解釈できる。
【０１１５】
数式（６）の形式での最適化ついて考慮すると、上記の４個のエントリーが登録された状態で、エントリーｘ２を基点エントリーとし、各エントリーｘ１，ｘ２，ｘ３，ｘ４の目標値をそれぞれ１１，７，８，９と設定すると、この目標値からの差分であるペナルティを最小化する目的関数（Ｏ２）が定まる。なお、制約式は数式（１０）と同じである。
【０１１６】
この最適化問題を混合整数計画問題解決手段を用いて解くと、ペナルティの最小値７および、最適解の１つである、Ｕ２＝４，Ｕ３＝４，（ｘ１，ｘ２，ｘ３，ｘ４）＝（０，１，１，０），（ｙ１６，ｙ２５，ｙ２７，ｙ３４，ｙ３６）＝（０，０，０，２，０）等が得られる。これは、エントリーｘ２，ｘ３が参加する候補グループにおいて、リソースｚ３，ｚ４間で２単位量のやりとりをおこなった場合に、エントリーｘ２の効用値が４、エントリーｘ３の効用値が４になると解釈できる。
【０１１７】
この数数式（１１）の場合の結果Ｕ２＝４，Ｕ３＝４を数式（１０）の場合の結果である、（Ｕ１，Ｕ２，Ｕ３，Ｕ４）＝（２，７，２，７）と比較する。数式（１０）の場合は、エントリーｘ１，ｘ３が得る効用値の値がそれぞれの設定した目標値に比べて小さく、仮にこのグループが推奨されたとしても、エントリーｘ１，ｘ３の合意は得にくいと考えられる。一方、数数式（１１）の場合の結果は、基点エントリーｘ２以外の候補グループに含まれているエントリーであるｘ３の効用値も目標値からの差分によって評価しているために、より合意の得られやすい解が得られたと解釈できる。
【０１１８】
【数８】
2005063426.tif 000010
【０１１９】
上記の二種類の最適化問題を組み合わせた二段階の最適化手法を説明する。  
第一段階では、数式（５）を用いた各エントリーの効用値の最大化を考え、第二段階では、第一段階で得られた最適化問題の解を目標値とする最適化をおこなう。  
この二段階の最適化を行うことにより、各エントリーの目標値を自動的に計算し、基点となるエントリー以外のエントリーの効用値をある程度考慮できることが、本手法の大きな特長である。
【０１２０】
以下では、基点エントリーをｘｂとして、二段階の最適化手法を用いた基点エントリーｘｂを含む候補グループの推奨手法に関するアルゴリズムを説明する。  
（Ｓｔｅｐ１−１）入力された基点エントリーをｘｂとする。  
（Ｓｔｅｐ１−２）各エントリーとマッチングテーブルの情報から効用値制約（ＣＵ），マッチング制約（ＣＭ）および組み合わせ制約（ＣＬ）を作成する。
【０１２１】
（Ｓｔｅｐ２−１）目標値未決定のエントリーがあれば、そのエントリーをｘｉとして、Ｓｔｅｐ２−２へ進む。エントリーがなければＳｔｅｐ３−１へ進む。  
（Ｓｔｅｐ２−２）ｘｉの効用値Ｕｉを最大化する目的関数（Ｏ１）を生成する。  
（Ｓｔｅｐ２−３）ｘｉが参加する制約式（Ｃｉ）を生成する。  
（Ｓｔｅｐ２−４）必要ならその他の制約式（Ｃ１）を生成する。  
（Ｓｔｅｐ２−５）（Ｏ１），（ＣＵ），（ＣＭ），（ＣＬ），（Ｃｉ），（Ｃ１）からなる混合整数線形計画問題を混合整数計画問題解決手段に入力し、得られた最適解をエントリーｘｉの目標値Ｕｉ＊として、Ｓｔｅｐ２−１へ進む。
【０１２２】
（Ｓｔｅｐ３−１）候補グループに参加するエントリーに関してＳｔｅｐ２−５で得られた目標値Ｕｉ＊を下回る値（ペナルティ）の総和を最小化する目的関数（Ｏ２）を生成する。  
（Ｓｔｅｐ３−２）ｘｂが参加する制約式（Ｃｂ）を生成する。  
（Ｓｔｅｐ３−３）必要ならその他の制約式（Ｃ２）を生成する。  
（Ｓｔｅｐ３−４）（Ｏ２），（ＣＵ），（ＣＭ），（ＣＬ），（Ｃｂ），（Ｃ２）からなる混合整数線形計画問題を混合整数計画問題解決手段に入力し、得られた最適値がエントリーｘｂの効用値、得られた最適解を推称する候補グループとする。
【０１２３】
本実施形態では、まずはじめに各エントリーｘｉを順に基点エントリーとして、基点の効用値を最大化する候補グループの導出（一回日の最適化）を行い、このときの最大値、すなわち基点エントリーｘｉの最大効用値を各エントリーの目標値Ｕｉ＊とする。次に、もとの基点エントリーｘｂが参加し、かつグループに参加するエントリーに関してこの目標値からの差分（ペナルティ）を最小化するような候補グループを求める（二回目の最適化）という二段階の最適化を行うことを特長としている。  
なお、具体的な変数の設定法、目的関数（Ｏ１，Ｏ２）や制約式（ＣＭ，ＣＬ等）の生成法の説明は上記のとおりである。
【０１２４】
（Ｓｔｅｐ１−１）から（Ｓｔｅｐ１−２）は前処理である。まず（Ｓｔｅｐ１−１）では、基点エントリーを登録する。次に（Ｓｔｅｐ１−２）では以下の定式化において共通である、効用値制約（ＣＵ））マッチング制約（ＣＭ）および組み合わせ制約（ＣＬ）を生成する。
【０１２５】
（Ｓｔｅｐ２−１）から（Ｓｔｅｐ２−５）は第一段階の最適化であり、個々のエントリーの目標値を定める。  
（Ｓｔｅｐ２−１）では、目標値未決定のエントリーがあればそのエントリーをここでの起点エントリーｘｉとしＳｔｅｐ２−２へ進む。全てのエントリーの目標値が決定している場合は、Ｓｔｅｐ３−１へ進む。  
（Ｓｔｅｐ２−２）（Ｓｔｅｐ２−３）（Ｓｔｅｐ２−４）において、基点エントリーｘｉの効用値の最適化に必要な目的関数と制約式を生成する。なお、ここで生成する候補グループは、基点エントリーの効用値の最適化のみを考慮した解であり、候補グループに参加する他のエントリーの効用値は全く考慮されないことに注意する。
【０１２６】
（Ｓｔｅｐ２−５）において、前Ｓｔｅｐまでで得られた最適化問題（数式（５））を混合整数計画問題解決手段に入力し、その最適解と最適値を得る。なお、最適解を得るのに、極端に時間がかかる場合は、制限時間を設け、その時点までに得られた最良解を最適解とみなすことにする。ここで得られた最適値がエントリーｘｉの効用値の最大値であり、この値を以下では、エントリーｘｉの目標値Ｕｉ＊であるとする。なお、混合整数計画問題解決手段が解なしを出力する場合があるが、その場合は、エントリーｘｉが参加する解が存在しないということなので、以下のＳｔｅｐでは、エントリーｘｉを除いてよいことに注意する。
【０１２７】
（Ｓｔｅｐ３−１）から（Ｓｔｅｐ３−４）は第二段階の最適化であり、候補グループおよびマッチングと、その場合に基点エントリーが得る効用値を出力する。  
（Ｓｔｅｐ３−１）（Ｓｔｅｐ３−２）（Ｓｔｅｐ３−３）において、候補グループを得るために必要な目的関数と制約式を生成する。なお、（Ｓｔｅｐ３−１）の目的関数の生成においては（Ｓｔｅｐ２−５）で生成したエントリーｘｉの目標値町の情報をもちいる。  
（Ｓｔｅｐ３−４）において、前Ｓｔｅｐまでで得られた最適化問題（たとえば、数式（６））を混合整数計画問題解決手段に入力し、その最適解と最適値を得る。なお、最適解を得るのに、極端に時間がかかる場合は、制限時間を設け、その時点までで得られた最良な解を最適解とみなすことにする。ここで得られた最適解が、候補グループのエントリーの組み合わせと候補グループ内のリソース間のマッチングを与える。
【０１２８】
前出の電力取引の例において、二段階の最適化を用いる手法の適用結果を挙げる。ここでは、ｘ２を基点エントリーとする。
【０１２９】
まず、Ｓｔｅｐ１は前述の例と同一であるので省略する。
【０１３０】
次に、Ｓｔｅｐ２において、各エントリーｘ１からｘ４それぞれの効用値を最大化する最適化問題を考える。この例ではｘ２の効用値を最大化する最適化問題が、数式（１０）となり、それ以外の場合は、目的関数と基点制約のみが数式（１０）と異なる最適化問題が生成される。
【０１３１】
生成された最適化問題を混合整数計画問題解決手段に入力すると、それぞれの最適値Ｕ１＊＝１１，Ｕ２＊＝７，Ｕ３＊＝８，Ｕ４＊＝９が得られる。
【０１３２】
次に、Ｓｔｅｐ３において第二段階の最適化をおこなう。基点エントリーをｘ２とし、数式（６）の手順で、最適化問題を生成する。この場合、各エントリーの目標値は、Ｕ１＊＝１１，Ｕ２＊＝７，Ｕ３＊＝８，Ｕ４＊＝９であるので、作成した最適化問題は、数式（１１）と一致する。
【０１３３】
この最適化問題を混合整数計画問題解決手段に入力すると、解としては前例と同じく、エントリーｘ２，ｘ３が参加し、エントリーｘ２の効用値が４、エントリーｘ３の効用値が４となる候補グループが得られる。  
ここでは、各エントリーの目標値を、本発明のグルーピング装置が自動的に指定しているので、より客観性の高い基準により基点以外のエントリーの目標値を考慮した候補グループが推奨されると考えられる。
【０１３４】
上記の第１及び第２の実施形態に係る需給仲介システムを複数ユーザで利用した場合の全体の流れを、図１９のフローチャートを用いて説明する。ここでは、ユーザとして基点となるユーザＡ，その他Ｂ，Ｃの３ユーザ以上のユーザがいるものとし、サーバ側の動作と合わせて示す。その他のユーザもフローはＢ，Ｃと同じである。また、基点となるユーザは誰であっても構わない。ここでは、ユーザＢは幹事業者などの重要ユーザであり、ユーザＢの登録したエントリーの内少なくとも一つは候補グループに含むものとする。
【０１３５】
まず、基点となるユーザは、新しく登録するエントリーについて、既に他のユーザによって需給仲介システムに登録済のエントリーと候補グループをつくることが可能かどうかを、正式に登録する前にシミュレーションし、エントリーの条件を修正する（サーバのＳ２−Ｓ５およびユーザＡのＳＡ１−ＳＡ６の処理）。シミュレーションの過程では、既に他のユーザによって需給仲介システムに正式に登録済の各エントリー（本例では、ユーザＢ、Ｃが登録済のエントリー）のデータは、それぞれのユーザの端末で最新の内容のデータを共有する。しかし、正式に登録していないエントリーのデータは他のユーザのための演算には反映されない。例えば、ユーザＡのＳＡ８の本登録処理が終了するまでは、ユーザＡのＳＡ１で仮登録したエントリーはその他のユーザの候補グループ決定に一切反映されない。ユーザＢ、ユーザＣ、その他ユーザも各々のエントリーを登録する際に同様のシミュレーション処理を行う。
【０１３６】
なお、登録されているエントリーが少ない段階ではシミュレーション過程で候補グループが発見されない場合（Ｓ３のＮｏの場合）もある。また、シミュレーション過程を省略しても良い。
【０１３７】
次に、サーバのＳ８−Ｓ９の処理では、発見された候補グループに内部ＩＤを付け、候補グループに含まれる各エントリーを登録した各ユーザ（ここではユーザＡ、Ｂ、Ｃ）をリストアップし、各ユーザに候補グループのグループ内マッチング結果を通知する。なお、シミュレーション処理で示された候補グループをエントリー本登録時に同時に承認する場合（ＳＡ８でＹｅｓの場合）があり、その場合は当該ユーザへの通知処理は行わない。
【０１３８】
ユーザ側のＳＡ９−ＳＡ１１、ＳＢ２−ＳＢ４、ＳＣ２−ＳＣ４の処理では、それぞれのユーザ側の端末が通知されたマッチング結果を受信、各ユーザが閲覧し、マッチング結果を承認するか否かの情報をサーバ側に送信する。なお、ユーザ側の選択により、如何なるマッチング結果でも指定した組み合わせ条件が満足されれば自動的に承認するように予め設定しても良い。
【０１３９】
各ユーザに送信する閲覧させる候補グループの情報の範囲に関しては、需給仲介システムの目的や各ユーザのレベルに応じて以下の制限を設ける。下のレベルほど閲覧可能な情報が少ないが、他のユーザにエントリーの内容を知られたくない場合などは、下記の（４）のレベルの閲覧のみに限定する。  
（１）候補グループの全てのエントリーの内容とその登録ユーザを閲覧可能  
（２）閲覧するユーザの登録したエントリーと直接にマッチングするエントリーの内容とその登録ユーザまで閲覧可能  
（３）閲覧するユーザ自身の登録したエントリーのマッチング成立した数量と、その相手の登録ユーザを閲覧可能  
（４）閲覧するユーザ自身の登録したエントリーのマッチング成立した数量のみ閲覧可能  
閲覧のためのＧＵＩは、需給仲介システムのターゲットに応じて様式を変えるものとする。
【０１４０】
電力取引支援システムにおいて、（４）のレベルで閲覧する場合のＧＵＩの一例を図２０に、（３）のレベルで閲覧する場合のＧＵＩの一例を図２１に示す。
【０１４１】
サーバ側のＳ１０−Ｓ１４の処理では、候補グループの確定処理を行う。候補グループに含まれる全てのユーザの承諾が得られた段階で、マッチング成立を各ユーザに通知し、当該候補グループに含まれるエントリーを削除する。
【０１４２】
（第３の実施形態）  
図２２は、第３の実施形態に係るシステム全体の構成例を示した図である。なお、図１と同一部分には同一符号を付し、異なる部分についてのみ説明する。
【０１４３】
図２２に示すグルーピング装置１は、エントリー記憶部１５、辞書データ記憶部１７を含む汎用データベースシステムを利用し、グルーピングモジュール３１は、エントリー入力部１１と、インデックス記憶部１６と、候補グループ決定部１３とから構成されている。
【０１４４】
図１のグルーピングモジュール３０と異なり、グルーピングモジュール３１は、エントリー自体の内容記憶に汎用データベースシステムを利用し、リソース名照合部１２も、汎用データベースシステムに付随する検索用のデータ照合機能などの関数を外部から呼び出して利用する。
【０１４５】
（第４の実施形態）  
図２３は、第４の実施形態に係るシステム全体の構成例を示した図である。図１と同一部分には同一符号を付し、異なる部分についてのみ説明する。
【０１４６】
図２３に示すグルーピング装置１は、エントリー入力部１１とリソース名照合部１２と、候補グループ決定部１３と候補グループ出力部１４から構成され、エントリー記憶部１５、インデックス記憶部１６、辞書データ記憶部１７は、汎用データベースシステム４０内に構成されている。そして、グルーピング装置１はネットワークを介して所望の汎用データベースシステム４０にアクセスし、必要なデータを取得するようになっている。そして、複数のグルーピング装置１が端末側にも存在し、ネットワーク上でこれら複数のグルーピング装置１が並列に動作する。エントリーやインデデックスデータは共有して演算を行うようになっている。共有するデータは一部もしくは全てのコピーを作成して複数のサーバーや端末上に置くこともあり得るが、それぞれのコピーデータに相違が生じないように既存のデータベース技術により管理される。
【０１４７】
候補グループ決定においては、グルーピング装置１を有するユーザが異なるため、グルーピング装置を有するユーザの登録したエントリーを基点エントリーの一つとし、他のユーザにより新たなエントリーが登録された場合には、新たなエントリーとグルーピング装置を有するユーザの登録したエントリーの２つを基点エントリーとする。
【０１４８】
なお、本発明の実施の形態に記載した本発明の手法（特に、グルーピングモジュール３０の処理動作）は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フレキシブルディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、半導体メモリなどの記録媒体に格納して頒布することもできる。
【０１４９】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成リソースを変形して具体化できる。また、上記実施形態に開示されている複数の構成リソースの適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成リソースから幾つかの構成リソースを削除してもよい。さらに、異なる実施形態にわたる構成リソースを適宜組み合わせてもよい。
【図面の簡単な説明】
【０１５０】
【図１】第１の実施形態に係る需給仲介システム全体の概略構成例を示した図。
【図２】本発明の一実施形態に係る需給仲介システムを電力取引支援システムとして利用した場合の一例を示す図。
【図３】本発明の一実施形態に係る需給仲介システムを電力取引支援システムとして利用した場合のエントリーの１例と、それぞれのエントリーと併せて示す図。
【図４】本発明の一実施形態に係る需給仲介システムを電力取引支援システムとして利用した場合のエントリーの１例と、それぞれのエントリーと併せて示す図。
【図５】本発明の一実施形態に係るグルーピング機能を説明するための図。
【図６】本発明の一実施形態に係るグルーピング機能を説明するための図。
【図７】本発明による需給仲介システムを電力取引支援システムとして利用した場合に、グルーピング装置１が作成するグループの一例を示す図。
【図８】本発明による需給仲介システムを電力取引支援システムとして利用した場合に、グルーピング装置１が作成するグループの一例を示す図。
【図９】本発明の一実施形態に係る候補グループ決定部１３の処理動作概要を示すフローチャート。
【図１０】仮グループ内のマッチングを決定方法を説明するための図。
【図１１】最良優先探索と呼ばれる探索的解法を用いる場合の流れを示すフローチャート。
【図１２】最良優先探索と呼ばれる探索的解法を用いる場合の流れを示すフローチャート。
【図１３】探索木の例を示す図。
【図１４】マッチング結果例を示す図。
【図１５】マッチング結果例を示す図。
【図１６】マッチング結果例を示す図。
【図１７】マッチング結果例を示す図。
【図１８】第２の実施形態に関わる需給仲介システム全体の概略構成例を示した図。
【図１９】第１及び第２の実施形態に係る需給仲介システムを複数ユーザで利用した場合の全体の流れを示すフローチャート。
【図２０】電力取引支援システムにおいて、（４）のレベルで閲覧する場合のＧＵｉの一例を示す図。
【図２１】電力取引支援システムにおいて、（３）のレベルで閲覧する場合のＧＵｉの一例を示す図。
【図２２】第３の実施形態に係るシステム全体の構成例を示した図。
【図２３】第４の実施形態に係るシステム全体の構成例を示した図。
【符号の説明】
【０１５１】
１…グルーピング装置
１１…エントリー入力部
１２…リソース名照合部
１３…候補グループ決定部
１４…候補グループ出力部
１５…エントリー記憶部
１６…インデックス記憶部
１７…辞書データ記憶部
１９…ＩＤ発行部
２１…仮グループ決定部
２２…グループ内マッチング決定部
２３…グループ評価値演算部
２４…ペナルティ演算部
２５…候補グループ記憶部
２６…制約式・目的関数作成部
２７…混合整数線形計画問題解決部
３０…グルーピングモジュール
３１…グルーピングモジュール
４０…汎用データベースシステム
【図１】
2005063426.tif 000011
【図２】
2005063426.tif 000012
【図３】
2005063426.tif 000013
【図４】
2005063426.tif 000014
【図５】
2005063426.tif 000015
【図６】
2005063426.tif 000016
【図７】
2005063426.tif 000017
【図８】
2005063426.tif 000018
【図９】
2005063426.tif 000019
【図１０】
2005063426.tif 000020
【図１１】
2005063426.tif 000021
【図１２】
2005063426.tif 000022
【図１３】
2005063426.tif 000023
【図１４】
2005063426.tif 000024
【図１５】
2005063426.tif 000025
【図１６】
2005063426.tif 000026
【図１７】
2005063426.tif 000027
【図１８】
2005063426.tif 000028
【図１９】
2005063426.tif 000029
【図２０】
2005063426.tif 000030
【図２１】
2005063426.tif 000031
【図２２】
2005063426.tif 000032
【図２３】
2005063426.tif 000033