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

Description

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

あらかじめ与えられた輸送依頼（貨物の積港、揚港等の依頼）に従って貨物等の商品を輸送媒体（トラック、船舶等）で配送するための配送計画を生成する方法が知られている。しかしながら、商品を生産者から買い取って、購入者に商品を輸送及び販売するビジネスを考えた場合に、ビジネスによる利益を最大化するような配送計画を生成する手法は知られていない。

特許第5339230号

浅野孝夫, 情報の構造, 日本評論社, 1994.

本実施形態は、第１取引主体から商品を買い取って、第２取引主体に商品を売るビジネスの利益を向上させるのに用いて有効な情報処理装置、情報処理方法及びコンピュータプログラムを提供する。

本実施形態の情報処理装置は、第１取引主体が商品を売る売り条件と、第２取引主体が商品を買う買い条件とを、前記商品を輸送する第１輸送媒体の情報に基づき組み合わせ、組み合わせた前記売り条件と前記買い条件とを含むマッチング情報を生成する生成部と、前記マッチング情報に基づき、前記第１輸送媒体に前記商品の輸送を割り当て、前記輸送のスケジューリングを行うスケジューリング部と、を備える。

本実施形態に係る情報処理装置としての輸送計画装置のブロック図。 生産者リストの一例を示す図。 購入者リストの一例を示す図。 輸送媒体リストの一例を示す図。 特定取引価格リストの一例を示す図。 最大マッチング数計算グラフの一般的に示した図。 利益最大マッチンググラフ（辺重み付き有効グラフ）の例を一般的に示した図。 輸送媒体kに対して各種条件を満たす例を具体的に示す図。 頂点vpr1から頂点v1r2への辺を生成する例を示す図。 頂点vir1から頂点vjr2への辺を生成する例を示す図。 スケジューリンググラフの例を示す図。 各種記号の説明図。 利益Z1及び利益Z2を具体的に説明する図。 最小費用流問題を解いた結果として得られたパスの例を示す図。 本実施形態に係る輸送計画装置の動作の一例のフローチャート。 変形例３に係る情報処理装置としての輸送計画装置のブロック図。 輸送計画装置（情報処理装置）のハードウェア構成を示す図。

本実施形態は、商品を第１取引主体（販売者等）から買い取って、買い取った商品を第２取引主体（購入者等）に輸送及び売るビジネスにおいて、当該ビジネスの主体となる取引主体による利益を最大化又は最適化する。商品を本ビジネスの取引主体に売る第１取引主体は、商品の生産者である場合を想定するが、第１取引主体は生産者である必要はなく、例えば他の取引主体から購入した商品を本ビジネスの取引主体に転売する事業者でもよい。第２取引主体は本ビジネスの取引主体から買った商品を消費者等に販売する事業者でも、自ら消費する消費者であってもよい。商品は輸送可能なものであれば、食物、物品、動植物など何でもよい。商品を輸送する輸送媒体は、トラック、船舶、飛行機、ドローン、列車、自動車、ロボットなど、地上、空中、水上又は水中等で商品を輸送可能な媒体であれば何でもよい。輸送する商品の種類又は量に応じて、利用する輸送媒体が決まっていてもよい。本実施形態では、第１取引主体がりんごの生産者であり、商品がりんごであり、輸送媒体がトラックである場合の例を示す。

以下、図面を参照しつつ、本実施形態について詳細に説明する。

図１は、本実施形態に係る情報処理装置としての輸送計画装置１００のブロック図である。輸送計画装置１００は、入力データ取得部１０１、優先順位決定部１０２、輸送媒体選択部１０３、マッチング候補生成部１０４、スケジューリング部１０５、後処理部１０６、結果出力部１０７及び地理データベース（ＤＢ）１０８を備えている。

入力データ取得部１０１は、本実施形態の動作に必要なデータ（入力データ）を内部の記憶部又は外部の装置から取得し、取得した入力データを取得する。入力データは、生産者リスト（第１リスト）、購入者リスト（第２リスト）、輸送媒体リスト、特定取引価格リストを含む。その他、入力データは、輸送計画装置１００の各ブロックの動作（例えば関数の実行）に必要なパラメータを含んでもよい。入力データの取得先となる内部の記憶部は、メモリ装置、ハードディスク装置、光ディスク装置など任意の記録媒体でよい。外部の装置は、通信ネットワーク上のストレージサーバでもよいし、輸送計画装置１００にケーブル接続された装置でもよい。あるいは輸送計画装置１００の操作者がキーボード又はマウス等の入力デバイスを用いて入力したデータを入力データ取得部１０１が取得してもよい。

生産者リストは、生産者（第１取引主体）ごとに、生産者が商品を売る条件である売り条件を含む。具体的には、生産者リストには、生産者、商品の売り場所（生産者が指定する場所）、商品を売ることが可能な期間（売却可能期間）、商品の質、及び商品の量のうちの少なくとも１つと、商品の売り価格とが含まれる。なお商品を売ることを、商品を販売するとも記載する。

図２は、生産者リストの一例を示す。生産者リストには、３つのエントリが含まれている。売りID（P1, P2, P3）は生産者の識別子である。生産者P1は、10/1～10/5の間であれば糖度10～13度のりんご100kg～120kgを、単価400[円/kg]でA市にて販売できる。

生産者P2は、10/2～10/4の間であれば、糖度13～14度のりんご150kg～160kgを単価410[円/kg]で、B市にて販売できる。

生産者P3は、10/3～10/7の間であれば糖度10～11度のりんご100kg～150kgを単価380[円/kg]でC市にて販売できる。

糖度は商品の質に相当する。販売量は商品の量に相当する。単価は商品の売り価格に相当する。

本実施形態では、時間の粒度は日とする。ただし、時間の粒度は、10分、１時間、１週間など、他の粒度でもよい。

購入者リストは、購入者（第２取引主体）が商品を買う条件（買い条件）を含む。具体的には、購入者リストには、購入者、商品の買い場所（購入者が指定する場所）、商品を買うことが可能な期間、商品の質、及び商品の量のうちの少なくとも１つと、商品の買い価格とが含まれる。なお商品を買うことを、商品を購入するとも記載する。

図３は、購入者リストの一例を示す。購入者リストには、３つのエントリが含まれている。買いID（S1, S2, S3）が購入者の識別子である。

購入者S1は、D市にて10/1～10/5の間に150kg～160kgのりんごの購入を考えているが、糖度に応じて２つの価格を設定している。糖度が10度～12度の場合は450[円/kg]、糖度が12度～14度の場合は490[円/kg]で買い取る。ただし、買い取るのはどちらか一方の条件でのみである。すなわち、購入者S1は選択可能な複数（本例では２つ）の買い条件を設定している。このように商品の条件によって価格設定を変える条件を補助条件と呼び、補助条件を付与することを補助条件設定と呼ぶ。補助条件が付けられている買いIDには、補助条件を区別するため補助条件IDが付けられる。補助条件は、購入者リストに加えて、あるいは購入者リストの代わりに、生産者リストに設定することも可能である。すなわち、生産者は選択可能な複数の売り条件を設定することが可能である。例えば補助条件付きでない売り条件と、補条件付きの売り条件との２つを設定することが可能である。

購入者S2は、10/3～10/7の間であれば糖度10～11度のりんご100kg～180kgを単価420[円/kg]でD市にて買い取ることができる。

購入者S3は、10/6～10/10の間であれば糖度12～13度のりんご90kg～98kgを単価550[円/kg]でF市にて買い取ることができる。

輸送媒体リストは、輸送媒体に関する情報として、輸送媒体が商品を輸送する輸送条件を１つ以上含む。輸送条件は、一例として、積載量、移動速度（平均速度）、商品の輸送コスト及び商品の廃棄レートの少なくとも１つを含む。その他の項目、例えば、燃費等が輸送条件に含まれていてもよい。積載量、移動速度、燃費等は輸送媒体の性能の一例である。

図４は、輸送媒体リストの一例を示す。輸送媒体リストには２つのエントリが含まれている。具体的には、りんごを輸送するための2台のトラックに関する情報が含まれている。トラックID（T1,T2）はトラックの識別子である。

トラックT1は、90kg～110kg（積載量）のりんごを運ぶことができ、平均50km/hの速度で走行することができる。1日当たり4000円の費用（輸送コスト）が発生する。

トラックT2は、120kg～160kgのりんごを運ぶことができ、平均40km/hの速度で走行することができる。1日当たり6000円の費用が発生する。

廃棄レートは、りんごの輸送中にどのくらいりんごが痛み、売り物にならなくなるかを表す。例えば、廃棄レートが1[%/日]の場合、1日あたり1%のりんごが売り物にならなくなる。具体例として、廃棄レートが1[%/日]の場合に、100kgのりんごを3日かけて輸送するのであれば、100kg×0.01×3 = 3kg のりんごが売り物にならなくなる。すなわち、買い手が買い取れるりんごは97kgとなる。3kg のりんごが売れなくなることは、りんご3kgに相当する金額だけ、事業者の販売額が減少することを意味する。

１台のトラックが１回の輸送で運ぶりんごは、１つの売りIDの生産者の売り場所から１つの買いIDの購入者の買い場所に輸送するりんごのみとする。言い換えると、複数の売りIDの生産者のりんごを１つのトラックに同時に混載したり、複数の買いIDの購入者向けのりんごを１つのトラックに同時に混載したりすることはないものとする。

特定取引価格リストは、特定の生産者と特定の購入者との間にのみ適用する特定取引価格を含む。特定取引価格は、特定の売り価格及び特定の買い価格のうちの少なくとも一方を含む。特定の生産者と特定の購入者との間に適用する売り価格は、生産者が商品を売る売り条件の一例に相当する。特定の生産者と特定の購入者との間に適用する買い価格は、購入者が商品を買う買い条件の一例に相当する。生産者に選択可能な複数の売り条件が設定されている場合に、複数の売り条件のうちの１つが特定取引価格（特定の売り価格）を含んでもよい。購入者に選択可能な複数の買い条件が設定されている場合に、複数の買い条件のうちの１つが特定取引価格（特定の買い価格）を含んでもよい。

図５は、特定取引価格リストの一例を示す。特定取引価格リストには２つのエントリが含まれている。各エントリには、特定の生産者と購入者の間の取引の場合にのみ適用される特定取引価格（特定の売り単価と特定の買い単価）の設定が含まれている。

生産者P1と購入者S2の間の場合、売り単価は395[円/kg]、買い単価を925[円/kg]である。つまり事業者は生産者P1から395[円/kg]でりんごを買い取って、925[円/kg]で購入者にりんごを販売できる。

また、生産者P2と購入者S2の間で、購入者の補助条件(ID:2)を採用する場合、売り単価は405[円/kg]、買い単価は1000[円/kg]である。つまり、事業者は生産者P2から405[円/kg]でりんごを買い取って、1000[円/kg]で購入者にりんごを販売できる。

本実施形態では、生産者リストと購入者リストと輸送媒体リストと特定取引価格リストが入力として与えられる場合に、生産者の売り条件と、売り条件にマッチする購入者の買い条件を組み合わせて、マッチング情報（以下、マッチング候補と呼ぶ）を生成する。売り条件にマッチする買い条件が存在しない場合、生成されるマッチング情報は０個になる場合もあり得る。マッチング候補の全部又は一部を輸送媒体に割り当て、輸送媒体の輸送スケジュールを生成する。本実施形態は、マッチング候補の生成及び輸送スケジュールの生成を、ビジネスの事業者の利益を最大化又は最適化するように行う。ここで、ビジネスの利益は、購入者に対するりんごの販売額から、生産者からのりんごの購入額、廃棄レートに応じた廃棄額及びトラックの輸送費用等を減じることにより算出される。ただし、利益の定義は他の定義でもよい。例えば輸送媒体を操作する操作者の人件費をさらに購入者に対するりんごの販売額から減じて利益を算出してもよい。

優先順位決定部１０２は、輸送媒体リストに基づき輸送媒体の優先順位を決定する。すなわち、優先順位決定部１０２は、どの輸送媒体から優先的に利用するかを決定する。優先順位の決定方法として、コストの安い順、積載量の多い順、又は廃棄レートの低い順等、任意の選択基準を用いることができる。本実施形態ではコストの安い順を用いる。図４の例では、トラックT1のコストがトラックT2のコストより安いため、トランクT1の順位がトラックT2より高い。

輸送媒体選択部１０３は、優先順位決定部１０２で決定した優先順位に従って、輸送媒体リストに含まれる輸送媒体から１つの輸送媒体を選択する。選択した輸送媒体をkとする。上述の例では、トランクT1の順位がトラックT2より高いため、トラックT1が最初に選択される。

地理データベース（ＤＢ）１０８は、輸送媒体リストに含まれる各輸送媒体が移動する環境の地図情報を格納した記憶部である。地図情報は、マッチング候補生成部１０４及びスケジューリング部１０５によって用いられる。地図情報は、例えば、任意の２つの地点間の距離、及び、任意の２つの地点間の移動時間を計算するために用いることができる。地理ＤＢ＿１０８は、輸送計画装置１００の外部の通信ネットワークにサーバとして配置されていてもよい。この場合、輸送計画装置１００は、通信ネットワークを介して、サーバから地図情報を受信する。地理ＤＢ＿１０８は、メモリ装置、ハードディスク装置、又は光ディスク装置など任意の記録媒体として構成されることができる。

マッチング候補生成部１０４は、輸送媒体選択部１０３により選択された輸送媒体kの情報に基づき、生産者の売り条件と購入者の買い条件とを１つずつ組み合わせた組を、マッチング候補（ペア）として生成する。

マッチング候補生成部１０４は、生産者が商品を売る売り条件と、売り条件にマッチする、購入者が商品を買う買い条件とを含むマッチング候補を、生産者から購入者に商品の輸送を行う輸送媒体（第１輸送媒体）の情報に基づき生成する生成部の一例に相当する。

以下、マッチング候補生成部１０４の動作について詳細に説明する。マッチング候補生成部１０４の動作は、以下の２つの処理（処理1及び処理2）を実行する。

[処理1]
マッチング候補生成部１０４はマッチング候補の最大数を算出する。マッチング候補の最大数は、後述する最大マッチング数計算グラフ（図６参照）を生成し、最大流問題を解くことで算出できる。詳細は後述する。

[処理2]
マッチング候補生成部１０４は、処理1で計算されたマッチング候補の最大数で、マッチングの利益の総和が最大となるマッチング候補の集合を算出する。マッチング候補生成部１０４は、利益最大マッチンググラフを生成し、最小費用流問題を解くことで、マッチング候補の集合を算出できる。詳細は後述する。

以下、処理1について詳細に説明する。
図６は、最大マッチング数計算グラフの例を示す。図６は、最大マッチング数計算グラフの一般的に示したものであり、図２～図５に示したリストは反映されていない。最大マッチング数計算グラフは、辺重みのない有向グラフである。最大マッチング数計算グラフは、G^M(V,E)によって表される。頂点集合Vは以下で定義される。

ソース頂点及びシンク頂点は、入口と出口に対応する頂点である。
生産者頂点集合は、生産者IDごとに生成される頂点の集合（p₁,p₂,…,p_|p|）である。
購入者頂点集合は、購入者IDごとに生成される頂点の集合（s₁, s ₂,…,s _|s|）である。
生産者補助頂点集合（p¹ ₁,p² ₁,p³ ₁,p¹ _|p|,p² _|p|）は、生産者IDに対応する補助条件ごとに生成される頂点の集合である。pの上付き文字は補助条件ID、下付き文字は生産者IDに対応する。
購入者補助頂点集合（s¹ ₂,s² ₂）は、購入者IDに対応する補助条件ごとに生成される頂点の集合である。sの上付き文字は補助条件ID、下付き文字は購入者IDに対応する。
生産者IDに対応する補助条件が存在しない場合、生産者補助頂点集合は生成されない。購入者IDに対応する補助条件が存在しない場合、購入者補助頂点集合は生成されない。図２の生産者リストの例では補助条件は存在しないため生産者補助頂点集合は生成されないが、図３の購入者リストの例では補助条件が存在するため購入者補助頂点集合は生成される。

辺の集合Eは、以下で定義される。

ただし、補助頂点（生産者補助頂点又は購入者補助頂点）がない場合は、生産者頂点又は購入者頂点を利用する。例えば生産者補助頂点がない場合は、生産者頂点から購入者補助頂点又は購入者頂点への辺を設定する。また購入者補助頂点がない場合は、生産者頂点又は生産者補助頂点から購入者頂点への辺を設定する。

生産者の売り条件と、購入者の買い条件間で条件がマッチングする（“マッチング条件が成立する”と呼ぶことがある）ためには、以下の［１］～［４］の全てが成り立つことが必要である。

［１］売却日（生産者の指定する売却可能期間内）に、輸送媒体による輸送時間を加算した日が、購入者の指定する購入可能期間に含まれる。ただし、輸送媒体が積荷を載せた状態（積荷輸送）においては、輸送媒体リストに示される速度で走行すると仮定する。輸送媒体をわざとゆっくり走行させて時間稼ぎをすることは許されないものとする。

［２］生産者の販売量（生産者の指定する範囲内）から、輸送媒体の廃棄レートによる廃棄量を引いた値が、購入者の指定する購入量の範囲内である。

［３］生産者の指定する糖度の範囲と購入者の指定する糖度の範囲とに共通部分が存在する。

［４］生産者の販売量が、輸送媒体kの積載量以下である。

以後、マッチング条件が成立する生産者補助頂点と購入者補助頂点間の辺集合のことをE^SUBと記述する。ただし、生産者補助頂点が存在しない場合は、生産者頂点と、購入者補助頂点又は購入者頂点との間の辺がE^SUBに含まれる。購入者補助頂点が存在しない場合は、生産者頂点又は生産者補助頂点と、購入者頂点との間の辺がE^SUBに含まれる。

生成されたグラフにおいて、ソース頂点から生産者頂点への全て辺、および、購入者頂点からシンク頂点への全ての辺の流量上限を１に設定し（図６参照）し、ソース頂点からシンク頂点への最大流量問題を解く。つまり、ソース頂点から他の頂点を経由してシンク頂点まで一度に送ることのできる量の最大値を算出する。この際、上述の辺の流量の上限値である１は制約条件となる。問題を解いた結果として、最大流量（ソース頂点から一度に入力可能な流量の最大値）が得られる。最大流量は、売り条件と買い条件間の実現可能な最大マッチング数、すなわち、マッチング候補の最大数（以後｜M｜と記述する）を表す。最大流量問題のアルゴリズムの詳細は、例えば非特許文献１に詳細に記載されている。

マッチング候補生成部１０４は、生成した最大マッチング数計算グラフに辺重みを設定し、利益最大マッチンググラフを生成する。利益最大マッチンググラフは、辺重み付き有向グラフとなる。

図７は、利益最大マッチンググラフ（辺重み付き有効グラフ）の例を一般的に示したものである。辺の重みは、当該の辺を利用する場合に発生する単位流量当たりのコストに相当する。辺重みは以下のように設定する。

E^SUBに含まれる辺e（辺eの両側の頂点をu^p _e, u^s _eと記述する）について、u^p _eに対応する生産者の売り条件（又は補助条件）と、u^s _eに対応する購入者の買い条件（又は補助条件）をマッチングさせることにより得られる利益をprof^eとする。このとき辺の重みは、prof^e×(-1)とする。従って、利益が大きいほど、辺eの重みは小さくなる。prof^eは、一例として以下で定義される。

ただし、購入者の購入量は、「生産者の販売量－廃棄レートによる廃棄量」となっている。

E^SUBに含まれる辺e以外の辺の重みは0とする。

生成した利益最大マッチンググラフに対して、ソース頂点からシンク頂点への流量を|M|とし、最大マッチング数計算グラフと同じ値の流量上限を設定して、最小費用流問題を解く。すなわち、流量｜M｜をソース頂点から入力し、入力された流量をシンク頂点に流す場合に、コストを最小にするフローを求める。最小費用流問題のアルゴリズムの詳細は、例えば非特許文献１に詳細に記載されている。

問題を解いた結果、E^SUBに含まれる辺eのうち、流量が0でない辺e（すなわち、求めたフローが通る辺）を特定する。特定した辺eにおいて、u^p _eに対応する生産者の売り条件（又は補助条件）と、u^s _eに対応する購入者の買い条件（補助条件）との組をマッチング候補として得る。マッチング候補に含まれる売り条件と買い条件は互いにマッチングする。マッチング候補は|M|個である。以後、輸送媒体kに対して計算されたマッチング候補の集合をU^kと表記する。このようにマッチング候補生成部１０４は、売り条件と買い条件とのマッチングにより得られる利益の総和を指標として、最小費用流問題を解くことにより、売り条件と買い条件とを含むマッチング候補を最大数又は少なくとも１つ生成する。

スケジューリング部１０５は、輸送媒体選択部１０３で選択された輸送媒体kに、U^kに含まれるマッチング候補を利益が最大となるように割り当てていく。この動作を輸送媒体のスケジューリングと呼ぶ。マッチング候補を輸送媒体kに割り当てるとは、マッチング候補に示される売り条件及び買い条件に従ってりんごを輸送するタスクを輸送媒体ｋに割り当てることを意味する。スケジューリング部１０５は、売り条件及び買い条件を含む少なくとも１つのマッチング候補に基づき、商品を輸送するタスクの割り当てと当該タスクのスケジューリングとを当該輸送媒体に対して行うスケジューリング部の一例に相当する。スケジューリング部は、前述の最大数以下の個数のマッチング候補を輸送媒体に割り当て、当該マッチング候補に応じたタスクを輸送媒体に割り当てる。この際、タスクの実行により得られる利益の総和を指標として、例えば最小費用流問題を解くことにより、輸送媒体に割り当てるタスク（あるいはタスクを割り当てるべきマッチング候補）を決定する。

スケジューリング部１０５は、輸送媒体kにマッチング候補を割り当てていく場合、下記の条件［１］及び［２］が成り立つときのみ、マッチング候補の割り当て（スケジューリング）が可能である。
［１］ 生産者の売却可能期間内に輸送媒体による輸送を開始する。
［２］ 購入者の購入可能期間内に輸送媒体による輸送が完了する。

条件［１］及び［２］の成否を判断する際、積荷した状態での輸送（積荷輸送）に要する日数、および、積荷しない状態での輸送（空荷移動）に要する日数も考慮する必要がある。空荷移動に要する日数は、例えば輸送媒体に商品（りんご）を載せずに、生産者の売り場所まで移動する日数に相当する。積荷輸送に要する日数は、生産者の売り場所から購入者の買い場所まで移動（りんごを輸送）する日数に相当する。生産者および購入者は、売り場所及び買い場所を指定しており、各場所の位置は地理ＤＢ＿１０８から特定可能であり、輸送媒体の移動速度は輸送媒体リストから特定可能である。よって、積荷輸送に要する日数及び空荷移動に要する日数を計算可能である。なお、本例では積荷輸送及び空荷移動の速度はいずれも同じとするが、積荷輸送及び空荷移動の速度が異なる場合も可能である。

ただし、積荷輸送においてはわざとゆっくり走行して、時間稼ぎをすることは許されないものとする。また空荷移動においては、出発日（又は出発時刻）より早く次の輸送開始場所（生産者の売り場所）に到着して、待機することができるものとする。

図８は、輸送媒体kに対して条件［１］、［２］を満たす例を示す。商品c₁を生産者の売り場所から、購入者の買い場所まで輸送媒体kにより輸送（積荷輸送）する。この際、商品c₁の輸送開始日が商品c₁の生産者の売却可能期間内に含まれており、商品c₁の購入者の購入日（商品c₁の輸送完了日）が、商品c₁の購入者の購入可能期間に含まれている。

輸送媒体kを空荷移動させ、商品c₂の輸送開始場所（売り場所）に移動させ、商品c₂を生産者の売り場所から、商品c₂の購入者の買い場所まで商品c₂を輸送（積荷輸送）する。この際、商品c₂の輸送開始日が、商品c₂の生産者の売却可能期間内に含まれており、商品c₂の購入者の購入日（商品c₂の輸送完了日）が、商品c₂の購入者の購入可能期間に含まれている。

スケジューリング部１０５は、最も高い利益が得られるスケジューリング（輸送媒体kに対するマッチング候補の割り当て）を行うため、スケジューリンググラフを生成し、最小費用流問題を解く。

スケジューリンググラフをG^S=(V,A)と表す。G^S=(V,A)は、辺重み付き有向グラフである。頂点集合Vは以下で定義される。U^kはマッチング候補の集合である。rはマッチング候補であり、U^kの要素である。

ソース頂点及びシンク頂点は、スケジューリンググラフの入口と出口に対応する頂点である。
輸送開始可能日頂点は、マッチング候補rの輸送開始可能期間内の個々の日に対応する頂点である。
マッチングの輸送開始可能期間とは、マッチング候補rにおける生産者の売却可能期間のうち、輸送媒体による輸送完了日がマッチング候補rにおける購入者の購入可能期間に含まれる日（範囲）のことである。
マッチング候補rに対応する輸送開始可能日頂点の集合をV_rと記述する。
V_rに含まれる輸送開始可能日頂点の中で最も早い日に対応する頂点をv^F _r、最も遅い日に対応する頂点をv^L _rと記述する。例えば、輸送開始可能日頂点集合V_rが10/1～10/5に対応する5個の頂点集合の場合、v^F _rは10/1に対応する頂点、v^L _rは10/5に対応する頂点となる。

スケジューリンググラフG^S=(V,A)の辺集合Aは、以下で定義される。

A^SUBは、輸送開始可能日頂点間の辺の集合で、個々の１つのマッチング候補r内で生成される辺の集合（A^SUB1）と、異なる２つのマッチング候補r1,r2(r1とr2は異なる)間を結ぶ辺の集合（A^SUB2）とを含む。すなわち、A^SUB＝A^SUB1∪A^SUB2である。

［A^SUB1の生成方法］
マッチング候補をrとする。また、輸送開始可能日頂点集合V_rの頂点を日付順に並べたものを[v^r ₁,…,v^r _p]とする。このとき、A^SUB1は下式で与えられる。

［A^SUB2の生成方法］
異なる任意の２つのマッチング候補をr1,r2(r1とr2は異なる)とする。
マッチング候補r1における輸送開始可能日頂点集合V_r1の頂点を日付順に並べたものを[v^r1 ₁,…,v^r1 _i,…,v^r1 _p]とする。
マッチング候補r2における輸送開始可能日頂点集合V_r2の頂点を日付順に並べたものを[v^r2 ₁,…,v^r2 _i,…,v^r2 _p]する。
頂点vに対応する日をdate(v)と表記する。
マッチング候補rにおける輸送開始場所から輸送完了場所までの輸送日数をday(r)と表記する。
マッチング候補rの輸送開始場所をpos^p _r、輸送完了場所をpos^s _rとするとき、互いに異なるマッチング候補r1,r2について、pos^p _r1からpos^p _r2まで、輸送媒体kが移動するのに必要な日数（空荷移動日数）を

と記載する。

また、同様に、１つのマッチング候補rにおける輸送開始場所から輸送完了場所まで輸送媒体kが移動するのに要する日数（積荷輸送日数）を

と記載する。
本実施形態では、荷積輸送時の速度と空荷移動時の速度は同じとするが、積荷輸送の速度と空荷移動の速度が異なる場合も可能である。

上記の前提の元、スケジューリング部１０５は、異なるマッチング候補間を結ぶ辺を、以下のように生成する。

の場合、頂点v_p ^r1から頂点v₁ ^r2への辺を生成する。

図９は、頂点v_p ^r1から頂点v₁ ^r2への辺を生成する例を示す。マッチング候補r1の輸送可能開始日頂点の末尾v_p ^r1に対応する日date(v_p ^r1)に、day(r₁)とday(r₁,r₂)とを加算する。day(r₁)はマッチング候補r1における輸送開始場所から輸送完了場所まで移動するのに要する日数である。day(r₁,r₂)は、マッチング候補r₁の買い場所からマッチング候補r₂の売り場所に移動（空荷移動）するのに要する日数である。加算後の日が、マッチング候補r2の輸送可能開始日頂点の開始v₁ ^r2に対応する日date(v₁ ^r2)以前の場合、頂点v_p ^r1から頂点v₁ ^r2への辺を生成する。生成した辺が矢印付きの太線で示される。

その他の場合、

が成り立つ任意のi,jの組合せについて、頂点

から頂点

への辺を生成する。

図１０は、頂点v_i ^r1から頂点v_j ^r2への辺を生成する例を示す。マッチング候補r1の輸送可能開始日頂点v_i ^r1に対応する日date(v_i ^r1)に、day(r₁)とday(r₁,r₂)とを加算する。day(r₁)はマッチング候補r1における輸送開始場所から輸送完了場所まで移動するのに要する日数である。day(r₁,r₂)は、マッチング候補r₁の買い場所からマッチング候補r₂の売り場所に移動（空荷移動）するのに要する日数である。加算後の日に一致する日を有する、マッチング候補r2の輸送可能開始日頂点v_j ^r2に、頂点v_i ^r1からの辺を生成する。生成した辺が矢印付きの太線（図の例では４本）で示される。

辺の重みは、辺の接続先がマッチング候補の頂点となっている辺には、以下の方法で設定する。

辺の接続先が、マッチング候補の頂点となっていない辺の重みは0とする。

辺の接続元となっているマッチング候補をr、辺の接続先のマッチング候補をmとする場合、辺の重みwは、

とする。kは輸送媒体を表す。

prof^m,kは、マッチング候補mのマッチングを実施することで得られる利益である。
pos^s _rは辺の接続元となっているマッチング候補rにおける輸送完了場所である。
pos^p _mは辺の接続先となっているマッチング候補mにおける輸送開始場所である。

は、マッチング候補rにおける輸送完了場所pos^s _rから、マッチング候補mにおける輸送開始場所pos^p _mに輸送媒体kで移動（空荷移動）するのに要するコストである。別途、輸送媒体の初期位置（q_v）を入力情報として利用可能であり、かつ辺の接続元がソース頂点である場合は、初期位置q_vから輸送開始場所までの空荷移動コストを利用することができる。

αは任意の定数である。αを十分に大きな値とすると、マッチング候補mを実施すると利益が負になる赤字マッチングでも輸送媒体にマッチング候補mを割り当てる結果が得られるようになる。つまり、利益よりも、より多くのマッチング候補を割り当てることを優先するようになる。一方、αを0に設定すると、常に利益が最大となる割り当て結果が得られる。

αを十分に大きな値にする場合、具体的には、下式を満たすαを設定すれば問題ない。

ここで、b^MAXは売り手・買い手間の空荷移動コストの最大値、Z^MINはマッチング候補による利益の最小値である。

図１１は、マッチング候補生成部１０４により生成されたマッチング候補が２つの場合に生成されたスケジューリンググラフの例である。図１１では２つのマッチング候補をそれぞれm₁,m₂としている。

マッチング候補m₁,m₂の輸送可能開始日頂点集合内の頂点に対応する時刻（日）が各種記号を用いて示されている。以下、図１２を用いて、記号を説明する。

図１２の左は、マッチング候補m₁について、t^B _p1～t^E _p1の間に生産者p₁の商品（りんご）の輸送を開始し、t^B _s1～t^E _s1の間に輸送を購入者s₁に対して完了させることを模式的に示している。図１２の右は、マッチング候補m₂について、t^B _p2～t^E _p2の間に生産者p₂の商品（りんご）の輸送を開始し、t^B _s2～t^E _s2の間に輸送を購入者s₂に対して完了させることを模式的に示している。

t^B _p1は、マッチング候補m₁の輸送可能開始日頂点のうち最初の頂点に対応する日、t^E _p1は、マッチング候補m₁の輸送可能開始日頂点のうち最後の頂点に対応する日を表す。
t^B _s1は、マッチング候補m₁の購入可能開始日頂点のうち最初の頂点に対応する日、t^E _s1は、マッチング候補m₁の輸送可能開始日頂点のうち最後の頂点に対応する日を表す。

t^B _p2は、マッチング候補m₂の輸送可能開始日頂点のうち最初の頂点に対応する日、t^E _p2は、マッチング候補m₂の輸送可能開始日頂点のうち最後の頂点に対応する日を表す。
t^B _s2は、マッチング候補m₂の購入可能開始日頂点のうち最初の頂点に対応する日、t^E _s2は、マッチング候補m₂の輸送可能開始日頂点のうち最後の頂点に対応する日を表す。

d_p1,s1は、生産者p₁の売り場所で商品（りんご）の輸送を開始してから、購入者s₁の買い場所で輸送を完了させるまでに要する時間（期間）を表す。
d_p2,s2は、生産者p₂の売り場所で商品（りんご）の輸送を開始してから、購入者s₂の買い場所で輸送を完了させるまでに要する時間（期間）を表す。
d_s1,p1は、購入者s₁における買い場所から生産者p1の売り場所に移動（空荷移動）するのに要する時間（期間）を表す。

図１１のスケジューリンググラフにおいて、Z₁は、マッチング候補m1を実行する場合の利益を表す。Z₂は、マッチング候補m2を実行する場合の利益を表す。

図１３は、利益Z₁,Z₂を具体的に説明する図である。利益Z₁は、マッチング候補m₁において生産者p₁の売り場所で商品（りんご）を購入して、購入者s₁の買い場所まで商品を輸送し、輸送したりんごを購入者s₁に販売する場合の利益（prof^m1,k）である。利益Z₂は、マッチング候補m₂において生産者p₂の売り場所で商品（りんご）を購入して、購入者s₂の買い場所まで商品を輸送し、輸送したりんごを購入者s₂に販売する場合の利益（prof^m2,k）を表す。

なお、輸送したりんごを購入者s₂に販売するとは、少なくともりんごを購入者又は代行人に渡し、あるいは購入者に指定された場所に置けばよい。売買契約自体は輸送前に行ってもよいし、りんごを購入者に渡す際に行ってもよいし、その他のタイミングで行ってもよい。同様に、生産車からりんごを購入するとは、少なくともりんごを生産者又は代行人から受け取り、あるいは生産者から指定された場所から取得すればよい。売買契約自体は輸送前に行ってもよいし、りんごを受け取る際に行ってもよいし、その他のタイミングで行ってもよい。

図１１のスケジューリンググラフにおいて、マッチング候補m₁の輸送可能開始日頂点集合内の頂点間の辺の重み（=w）は、当該辺の接続先がマッチング候補でないため、0である。同様に、マッチング候補m₂の輸送可能開始日頂点集合内の頂点間の辺の重み（=w）も、当該辺の接続先がマッチング候補でないため、0である。ソース頂点からシンク頂点への辺の重み（=w）は、接続先がマッチング候補でないため、0である。マッチング候補m₁の輸送可能開始日頂点集合における末尾の頂点からシンク頂点への辺の重み（=w）も、当該辺の接続先がマッチング候補でないため、0である。ソース頂点からマッチング候補m1の最初の頂点までの辺の重みは、－（Z₁－空荷移動コスト＋α）である。ソース頂点からマッチング候補m2の最初の頂点までの辺の重みは、－（Z₂－空荷移動コスト＋α）である。マッチング候補m1,m2間の辺の重みは、－（Z₂－空荷移動コスト＋α）である。

スケジューリング部１０５は、生成したスケジューリンググラフ（図１１参照）に対して、ソース頂点からシンク頂点へ流量１を流した時の最小費用流問題を解くことにより、輸送媒体kに関するスケジュールを決定する。スケジューリンググラフにおいて流量の上限が設定された辺は存在しないため、ソース頂点からシンク頂点へのパスは必ず１つに定まる。ソース頂点からシンク頂点までパスを順にたどり、頂点（v_r∈V_r）を通過するとき、対応するマッチング候補rを輸送媒体に割り当てていく。図１４を用いて、具体例を示す。

図１４は、最小費用流問題を解いた結果として得られたパスの例を示す。この例では、計算対象となっている輸送媒体kのスケジュールは、以下の結果となる。
初期位置（q_v）→（空荷移動）→マッチング候補m₁を実施→（空荷移動）→マッチング候補m₂を実施

各マッチング候補を開始する日は、パスが通過した頂点群（輸送可能開始日頂点集合）Vrに含まれる最初の頂点をv_i ^r1とするとき、date(v_i ^r1)によって表される。図１４の例の場合、マッチング候補m₁に対しては10/1に輸送を開始する。マッチング候補m₂に対しては、10/4に輸送を開始する。

結果出力部１０７は、スケジューリング部１０５の処理の結果として、輸送媒体kに割り当てられたマッチング候補と、輸送媒体kの輸送スケジュールとを出力する。例えば、結果出力部１０７は、マッチング候補及び輸送スケジュールを表示装置の画面に表示する。結果出力部１０７は、マッチング候補及び輸送スケジュールを外部の装置に、有線又は無線の通信により送信してもよい。また結果出力部１０７は、マッチング候補及び輸送スケジュールを内部又は外部の記憶装置に格納してもよい。記憶装置は、メモリ装置、ハードディスク装置、光ディスク装置など任意の記録媒体でよい。

後処理部１０６は、スケジューリング部１０５の処理の結果において、輸送媒体kに対して割り当てられたマッチング候補に含まれる売り条件と買い条件を、生産者リストおよび購入者リストから削除する。後処理部１０６は、輸送媒体kに対して割り当てられなかったマッチング候補が存在する場合、割り当てられなかったマッチング候補に含まれる売り条件と買い条件を、生産者リストおよび購入者リストから削除せずに残す。これにより、割り当てられなかったマッチング候補における売り条件と買い条件は、次以降に計算される輸送媒体に、新たなマッチング候補の一部として、割り当てられる可能性がある。

図１５は、本実施形態に係る輸送計画装置１００の動作の一例のフローチャートである。入力データ取得部１０１は、内部の記憶部又は外部の装置から生産者リスト、購入者リスト、輸送媒体リスト及び特定取引価格リストを取得する（ステップ１）。優先順位決定部１０２は、輸送媒体リストに基づき、輸送媒体を選択する優先順位を決定する（ステップ２）。輸送媒体選択部１０３は、優先順位に基づき輸送媒体を１つ選択する（ステップ３）。選択した輸送媒体を輸送媒体ｋとする。マッチング候補生成部１０４、生産者リストの売り条件と、売り条件にマッチする、購入者リストの買い条件とを１つずつ組み合わせたマッチング候補を、輸送媒体ｋの情報に基づき１つ以上生成する（ステップ４）。スケジューリング部１０５は、輸送媒体ｋに対するタスクスケジューリングとして、生成されたマッチング候補に応じたタスクを輸送媒体ｋに割り当てる（ステップ５）。結果出力部１０７は、スケジューリングの結果を示すデータを出力する（ステップ６）。後処理部１０６は、輸送媒体ｋに割り当てられたマッチング候補に含まれる売り条件及び買い条件を生産者リスト及び購入者リストから削除する。輸送媒体ｋに割り当てられなかったマッチング候補が存在する場合は、当該マッチング候補に含まれる売り条件及び買い条件を削除せずに残す（ステップ７）。ステップ３に戻って、以降、次の輸送媒体の選択（ステップ３）と、ステップ４～７とを実行することを繰り返す。終了条件が成立した場合は、処理を終了する。終了条件としては、選択すべき輸送媒体が存在しなくなったこと、生産者リスト又は購入者リストのうちの少なくとも一方にエントリが存在しなくなったことなどがある。

以上、本実施形態によれば、生産者リスト、購入者リスト、輸送媒体リストを少なくとも入力とし、生産者の売り条件と購入者の買い条件とをマッチングしたマッチング候補を複数生成する。複数のマッチング候補の全部又は一部を、利益を最大化するように輸送媒体に割り当てることで、配送スケジュールを生成する。これにより、生産者から商品を購入して、購入者に輸送及び販売するビジネスの利益を最大化又は最適化することが可能になる。

本実施形態によれば、ある輸送媒体で割り当てられなかったマッチング候補に含まれる売り条件及び買い条件を、新たなマッチング候補の一部として、次に選択する輸送媒体に割り当てる可能性を残すことができる。これにより、利益をより最大化できるようになる。

本実施形態によれば、生産者の売り条件および購入者の買い条件として詳細な条件（購入量、単価、購入可能期間、品質等）を設定する。これにより、より利益を最大化するマッチングが可能になる。

本実施形態によれば、選択可能な複数の売り条件を用意し（例えば、商品価格を商品の他の条件（質や量等）によって変える）、いずれかの売り条件をマッチング用に選択することにより、より利益を最大化するマッチングが可能になる。

本実施形態によれば、特定の買い手と特定の売り手間でのみ適用される売り条件として特定の売単価（特定取引価格）を設定することで、より利益を最大化するマッチングが可能になる。特定の買い手と特定の売り手間でのみ適用される買い条件として特定の買い単価（特定取引価格）を設定することで、より利益を最大化するマッチングが可能になる。

（変形例１）
本実施形態では優先順位決定部１０２は任意の１つの選択基準を用いて輸送媒体の優先順位を決定したが、輸送媒体の数が少ない場合（例えば一定個数以下）、あるいは、計算時間に余裕がある場合は、複数の選択基準を用いて、輸送スケジュールを生成してもよい。この場合、最終的に得られる利益が最も良い輸送スケジュールが得られた輸送媒体を採用すればよい。

（変形例２）
本実施形態では、生成するマッチング候補の最大数を算出し、当該最大数の制約の元、マッチングによる利益の総和が最大となるマッチング候補の集合を決定した。つまり、マッチング候補数が最大でかつ利益が最大になるマッチング候補を計算した。本変形例として、単純にマッチング候補の利益の総和が最大となるようにマッチング候補の集合を生成してもよい。すなわち、候補数が最大であることは保証しないが、単に利益の総和が最大となるマッチング候補の集合を生成してもよい。

（変形例３）
上述した実施形態では売り条件と買い条件とを組み合わせたマッチング候補（マッチング情報）を輸送媒体に割り当てたが、マッチング候補は輸送依頼と考えることができる。輸送依頼（例えば荷積場所、荷下場所、輸送依頼を実施することによる利益、利用可能な輸送媒体の集合を含む）と輸送媒体情報が与えられていて、輸送媒体に輸送依頼を割り当てていくスケジューリング問題は既知の問題として存在する。本変形例では。輸送依頼を輸送媒体に割り当てる場合に、輸送依頼に設定されている「資源」を消費するという「資源制約付きスケジューリング問題」を考える。

「資源」を消費するとは、例えば、輸送依頼r1を実施する場合は資源s1とp1を消費し、輸送依頼r2を実施する場合にはs1とp2を消費するといったことである。資源s1とp1はそれぞれ最初、１つずつ存在するとする。この場合、輸送依頼r1と輸送依頼r2の両方を輸送媒体に割り当てることは、資源s1が１つしか存在しないためできない。

この資源制約付きスケジューリング問題において、各輸送依頼に２つの利用資源s (∈S),p(∈P)が設定されている場合を考える。ただし、PおよびSはそれぞれ資源の集合で、P∩S=φ（PとSに共通の資源は存在しない）とする。このように条件が限定された問題の場合、利用資源pを商品の生産者、利用資源sを商品の購入者とすれば、図６の最大マッチング数計算グラフ、及び図７の利益最大マッチンググラフを作成できる。よって、上述の本実施形態の手法をそのまま利用して、資源制約付きスケジュール問題を解くことができる。

上述の例では各輸送依頼で消費する利用資源が２つであったが、消費する利用資源が１つ以下である輸送依頼が存在する場合も対応可能である。この場合、図６の最大マッチング数計算グラフ及び図７の利益最大マッチンググラフの流量上限１の辺の流量上限を無くし、さらに、生産者頂点と購入者頂点間の辺に流量上限１を設定すればよい。

例えば、輸送依頼rが資源s1のみを消費する場合、仮想的な生産者p_∞を想定し、ソース頂点からp_∞頂点へは流量上限の無い辺を作成する。p_∞頂点からs1頂点への辺に流量上限1を設定する。生産者頂点と購入者頂点間の辺に流量上限１を設定するのは、利用資源を消費しない輸送依頼があった場合でも、最大流量が∞にならないようにするため（各輸送依頼は１度のみスケジュールされるようにするため）である。

資源制約付きスケジューリング問題の現実的な例として、輸送する商品が精密機器であり、資源が必要な作業員や工具の場合がある。商品が精密機械の場合、専門の作業員や工具が必要になる。

図１６は、変形例３に係る情報処理装置としての輸送計画装置１００Ａのブロック図である。図１のマッチング候補生成部１０４が候補選択部（選択部）１０４Ａに置換されている。図１と同じ要素には同一の符号を付して、変更又は拡張された処理を除き、詳細な説明を省略する。以下、上述した実施形態との差分のみを記載する。

入力データ取得部１０１は、商品の輸送に使用する資源を含む少なくとも１つの輸送依頼のデータを取得する。輸送依頼に資源が複数種類に含まれていてもよい。また資源が輸送依頼に含まれない場合もあり得る。ここでは２種類の資源（第１資源及び第２資源）が輸送依頼に含まれているとする。第１資源は、商品の生産者（第１取引主体）であり、第２資源は、商品の購入者（第２取引主体）であるとする。輸送依頼は、使用する資源以外に、例えば荷積場所、荷下場所、輸送依頼を実施することによる利益、利用可能な輸送媒体などを含んでもよい。

候補選択部１０４Ａは、商品を輸送する輸送媒体の情報と、資源に関する制約とに基づき、少なくとも１つの輸送依頼を輸送依頼候補として選択する。資源に関する制約の例として、使用可能な資源の個数がある。資源が複数種類ある場合、種類ごとに制約が存在してもよい。資源に関する制約の情報及び輸送媒体の情報が入力データ取得部１０１によって取得されてもよい。候補選択部１０４Ａは、例えば図６の最大マッチング数計算グラフを作成することで、輸送依頼候補を選択してもよい。例えば第１資源を商品の生産者、第２資源を商品の購入者として、図６の最大マッチング数計算グラフを作成することができる。

スケジューリング部１０５は、輸送依頼候補に基づき商品の輸送を輸送媒体に割り当て、輸送のスケジューリングを行う。例えば、図７の利益最大マッチンググラフを作成することで、輸送依頼候補の割り当てと輸送のスケジューリングを行う。上述の実施形態のマッチング候補を輸送依頼候補と読み替えることで、上述の実施形態と同様の処理が可能である。

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

ＣＰＵ（中央演算装置）３０１は、主記憶装置３０５上で、コンピュータプログラムである輸送計画プログラムを実行する。輸送計画プログラムは、輸送計画装置１００の上述の各機能構成を実現するプログラムのことである。輸送計画プログラムは、１つのプログラムではなく、複数のプログラムやスクリプトの組み合わせにより実現されていてもよい。ＣＰＵ３０１が、輸送計画プログラムを実行することにより、各機能構成は実現される。

入力インタフェース３０２は、キーボード、マウス、及びタッチパネルなどの入力装置からの操作信号を、輸送計画装置１００に入力するための回路である。入力インタフェース３０２は入力データ取得部１０１に対応する。

表示装置３０３は、輸送計画装置１００から出力されるデータを表示する。表示装置３０３は、例えば、ＬＣＤ（液晶ディスプレイ）、有機エレクトロルミネッセンスディスプレイ、ＣＲＴ（ブラウン管）、又はＰＤＰ（プラズマディスプレイ）であるが、これに限られない。コンピュータ装置３００から出力されたデータは、この表示装置３０３に表示することができる。表示装置３０３は結果出力部１０７に対応する。

通信装置３０４は、輸送計画装置１００が外部装置と無線又は有線で通信するための回路である。データは、通信装置３０４を介して外部装置から入力することができる。外部装置から入力したデータを、主記憶装置３０５や外部記憶装置３０６に格納することができる。通信装置３０４は結果出力部１０７に対応する。

主記憶装置３０５は、輸送計画プログラム、輸送計画プログラムの実行に必要なデータ、及び輸送計画プログラムの実行により生成されたデータなどを記憶する。輸送計画プログラムは、主記憶装置３０５上で展開され、実行される。主記憶装置３０５は、例えば、ＲＡＭ、ＤＲＡＭ、ＳＲＡＭであるが、これに限られない。輸送計画装置１００の各記憶部又はデータベースは、主記憶装置３０５上に構築されてもよい。

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

なお、輸送計画プログラムは、コンピュータ装置３００にあらかじめインストールされていてもよいし、ＣＤ－ＲＯＭなどの記憶媒体に記憶されていてもよい。また、輸送計画プログラムは、インターネット上にアップロードされていてもよい。

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

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

１００ 輸送計画装置（情報処理装置）
１０１ 入力データ取得部
１０２ 優先順位決定部
１０３ 輸送媒体選択部
１０４ マッチング候補生成部（生成部）
１０４Ａ 候補選択部（選択部）
１０５ スケジューリング部
１０６ 後処理部
１０７ 結果出力部
１０８ 地理データベース（ＤＢ）
３００ コンピュータ装置
３０２ 入力インタフェース
３０３ 表示装置
３０４ 通信装置
３０５ 主記憶装置
３０６ 外部記憶装置
３０７ バス

Claims (26)

1. 第１取引主体が商品を売る売り条件と、第２取引主体が商品を買う買い条件とを、前記商品を輸送する第１輸送媒体の情報に基づき組み合わせ、組み合わせた前記売り条件と前記買い条件とを含むマッチング情報を生成し、
   前記マッチング情報に基づき、前記第１輸送媒体に前記商品の輸送を割り当て、前記輸送のスケジューリングを行う処理部を、備え、
   前記処理部は、前記第１輸送媒体の情報に基づき前記マッチング情報を生成する最大数を算出し、前記最大数のマッチング情報を生成し、前記最大数のマッチング情報に基づき、前記最大数以下の輸送を前記第１輸送媒体に割り当てる、
   情報処理装置。
2. 第１取引主体が商品を売る売り条件と、第２取引主体が商品を買う買い条件とを、前記商品を輸送する第１輸送媒体の情報に基づき組み合わせ、組み合わせた前記売り条件と前記買い条件とを含むマッチング情報を生成し、
   前記マッチング情報に基づき、前記第１輸送媒体に前記商品の輸送を割り当て、前記輸送のスケジューリングを行う処理部を、備え、
   前記処理部は、前記輸送の実行により得られる利益の総和を指標として、最小費用流問題を解くことにより前記輸送の割り当てと前記輸送のスケジューリングを行う、
   情報処理装置。
3. 第１取引主体が商品を売る売り条件と、第２取引主体が商品を買う買い条件とを、前記商品を輸送する第１輸送媒体の情報に基づき組み合わせ、組み合わせた前記売り条件と前記買い条件とを含むマッチング情報を生成し、
   前記マッチング情報に基づき、前記第１輸送媒体に前記商品の輸送を割り当て、前記輸送のスケジューリングを行う処理部を、備え、
   前記処理部は、複数の前記売り条件を含む第１リストと、複数の前記買い条件とを含む第２リストとに基づき、前記マッチング情報を生成し、
   前記第１輸送媒体に輸送がスケジュールされた前記マッチング情報に含まれる前記売り条件及び前記買い条件を、前記第１リスト及び前記第２リストから削除し、
   削除後の前記第１リストと、削除後の前記第２リストと、第２輸送媒体の情報に基づき、前記マッチング情報を生成し、
   前記マッチング情報に基づく輸送を前記第２輸送媒体に割り当て、前記輸送をスケジューリングする、
   情報処理装置。
4. 前記マッチング情報に基づく前記輸送は、前記第１取引主体の指定する場所から前記第２取引主体が指定する場所に前記商品を輸送することを含む
   請求項１～３のいずれか一項に記載の情報処理装置。
5. 前記第１輸送媒体の情報は、前記商品の積載量、移動速度、前記商品の輸送コスト及び前記商品の廃棄レートの少なくとも１つを含む
   請求項１～４のいずれか一項に記載の情報処理装置。
6. 前記売り条件は、前記商品を売る場所、前記商品の売却可能期間、前記商品の質及び前記商品の量の少なくとも１つと、前記商品の売り価格とを含み、
   前記買い条件は、前記商品を買う場所、前記商品の購買可能期間、前記商品の質及び前記商品の量の少なくとも１つと、前記商品の買い価格とを含む、
   請求項１～５のいずれか一項に記載の情報処理装置。
7. 前記第１取引主体に対して複数の前記売り条件が選択可能に設けられ、
   前記処理部は、複数の前記売り条件のうちのいずれか１つのみを前記組み合わせに用いる
   請求項１～６のいずれか一項に記載の情報処理装置。
8. 前記複数の売り条件のうちの少なくとも１つは、前記第１取引主体と特定の第２取引主体との間に適用される売り価格を含む
   請求項７に記載の情報処理装置。
9. 前記第２取引主体に対して複数の前記買い条件が選択可能に設けられ、
   前記処理部は、複数の前記買い条件のうちのいずれか１つのみを前記組み合わせに用いる
   請求項１～８のいずれか一項に記載の情報処理装置。
10. 複数の前記買い条件のうちの少なくとも１つは、前記第２取引主体と特定の第１取引主体との間に適用される買い価格を含む
    請求項９に記載の情報処理装置。
11. 前記処理部は、前記マッチング情報に基づく輸送の実行により得られる利益の総和を指標として、前記マッチング情報を生成する
    請求項１～１０のいずれか一項に記載の情報処理装置。
12. 前記処理部は、前記第１輸送媒体の情報に基づき前記マッチング情報を生成する最大数を算出し、前記最大数のマッチング情報を生成し、
    前記最大数のマッチング情報に基づき、前記最大数以下の輸送を前記第１輸送媒体に割り当てる
    請求項２、３、又は請求項２又は３を引用する請求項４～１０のいずれか一項に記載の情報処理装置。
13. 前記処理部は、最大流問題を解くことにより前記マッチング情報の最大数を算出し、前記最大数を最大流量として最小費用流問題を解くことにより、前記最大数のマッチング情報を生成する
    請求項１２に記載の情報処理装置。
14. 前記処理部は、前記輸送の実行により得られる利益の総和を指標として、前記輸送の割り当てと前記輸送のスケジューリングを行う
    請求項１、３、又は請求項１又は３を引用する請求項４～１１のいずれか一項に記載の情報処理装置。
15. 前記処理部は、最小費用流問題を解くことにより前記輸送の割り当てと前記輸送のスケジューリングを行う
    請求項１４に記載の情報処理装置。
16. 前記利益は、前記第２取引主体に対する商品の販売額から、前記第１取引主体からの商品の購入額と、前記商品の輸送コストと、前記輸送間の前記第１輸送媒体の移動コストとを減算することにより算出される
    請求項２、１４又は１５に記載の情報処理装置。
17. 前記処理部は、複数の前記売り条件を含む第１リストと、複数の前記買い条件とを含む第２リストとに基づき、前記マッチング情報を生成し、
    前記第１輸送媒体に輸送がスケジュールされた前記マッチング情報に含まれる前記売り条件及び前記買い条件を、前記第１リスト及び前記第２リストから削除し、
    削除後の前記第１リストと、削除後の前記第２リストと、第２輸送媒体の情報に基づき、前記マッチング情報を生成し、
    前記マッチング情報に基づく輸送を前記第２輸送媒体に割り当て、前記輸送をスケジューリングする
    請求項１、２、請求項１又は２を引用する請求項４～１１のいずれか一項、請求項２を引用する請求項１２、請求項２を引用する請求項１２を引用する請求項１３、請求項１を引用する請求項１４、請求項１を引用する請求項１４を引用する請求項１５、又は、請求項１６に記載の情報処理装置。
18. 複数の輸送媒体の優先順位に基づき輸送媒体を選択する輸送媒体選択部を備え、
    前記第２輸送媒体は、前記第１輸送媒体よりも低い優先順位の輸送媒体である
    請求項１７に記載の情報処理装置。
19. 前記輸送媒体選択部は、前記複数の輸送媒体の輸送条件に基づき、前記複数の輸送媒体の優先順位を決定する
    請求項１８に記載の情報処理装置。
20. 前記輸送のスケジュールを含むデータを出力する結果出力部
    を備えた請求項１～１９のいずれか一項に記載の情報処理装置。
21. コンピュータが、
    第１取引主体が商品を売る売り条件と、第２取引主体が商品を買う買い条件とを、前記商品を輸送する第１輸送媒体の情報に基づき組み合わせ、組み合わせた前記売り条件と前記買い条件とを含むマッチング情報を生成し、
    前記マッチング情報に基づき、前記第１輸送媒体に前記商品の輸送を割り当て、前記輸送のスケジューリングを行い、
    前記第１輸送媒体の情報に基づき前記マッチング情報を生成する最大数を算出し、前記最大数のマッチング情報を生成し、前記最大数のマッチング情報に基づき、前記最大数以下の輸送を前記第１輸送媒体に割り当てる、
    情報処理方法。
22. コンピュータが、
    第１取引主体が商品を売る売り条件と、第２取引主体が商品を買う買い条件とを、前記商品を輸送する第１輸送媒体の情報に基づき組み合わせ、組み合わせた前記売り条件と前記買い条件とを含むマッチング情報を生成し、
    前記マッチング情報に基づき、前記第１輸送媒体に前記商品の輸送を割り当て、前記輸送のスケジューリングを行い、
    前記輸送の実行により得られる利益の総和を指標として、最小費用流問題を解くことにより前記輸送の割り当てと前記輸送のスケジューリングを行う、
    情報処理方法。
23. コンピュータが、
    第１取引主体が商品を売る売り条件と、第２取引主体が商品を買う買い条件とを、前記商品を輸送する第１輸送媒体の情報に基づき組み合わせ、組み合わせた前記売り条件と前記買い条件とを含むマッチング情報を生成し、
    前記マッチング情報に基づき、前記第１輸送媒体に前記商品の輸送を割り当て、前記輸送のスケジューリングを行い、
    複数の前記売り条件を含む第１リストと、複数の前記買い条件とを含む第２リストとに基づき、前記マッチング情報を生成し、
    前記第１輸送媒体に輸送がスケジュールされた前記マッチング情報に含まれる前記売り条件及び前記買い条件を、前記第１リスト及び前記第２リストから削除し、
    削除後の前記第１リストと、削除後の前記第２リストと、第２輸送媒体の情報に基づき、前記マッチング情報を生成し、
    前記マッチング情報に基づく輸送を前記第２輸送媒体に割り当て、前記輸送をスケジューリングする、
    情報処理方法。
24. 第１取引主体が商品を売る売り条件と、第２取引主体が商品を買う買い条件とを、前記商品を輸送する第１輸送媒体の情報に基づき組み合わせ、組み合わせた前記売り条件と前記買い条件とを含むマッチング情報を生成するステップと、
    前記マッチング情報に基づき、前記第１輸送媒体に前記商品の輸送を割り当て、前記輸送のスケジューリングを行うステップと、
    前記第１輸送媒体の情報に基づき前記マッチング情報を生成する最大数を算出し、前記最大数のマッチング情報を生成し、前記最大数のマッチング情報に基づき、前記最大数以下の輸送を前記第１輸送媒体に割り当てるステップと、
    をコンピュータに実行させるためのコンピュータプログラム。
25. コンピュータが、
    第１取引主体が商品を売る売り条件と、第２取引主体が商品を買う買い条件とを、前記商品を輸送する第１輸送媒体の情報に基づき組み合わせ、組み合わせた前記売り条件と前記買い条件とを含むマッチング情報を生成するステップと、
    前記マッチング情報に基づき、前記第１輸送媒体に前記商品の輸送を割り当て、前記輸送のスケジューリングを行うステップと、
    前記輸送の実行により得られる利益の総和を指標として、最小費用流問題を解くことにより前記輸送の割り当てと前記輸送のスケジューリングを行うステップと、
    をコンピュータに実行させるためのコンピュータプログラム。
26. コンピュータが、
    第１取引主体が商品を売る売り条件と、第２取引主体が商品を買う買い条件とを、前記商品を輸送する第１輸送媒体の情報に基づき組み合わせ、組み合わせた前記売り条件と前記買い条件とを含むマッチング情報を生成するステップと、
    前記マッチング情報に基づき、前記第１輸送媒体に前記商品の輸送を割り当て、前記輸送のスケジューリングを行うステップと、
    複数の前記売り条件を含む第１リストと、複数の前記買い条件とを含む第２リストとに基づき、前記マッチング情報を生成するステップと、
    前記第１輸送媒体に輸送がスケジュールされた前記マッチング情報に含まれる前記売り条件及び前記買い条件を、前記第１リスト及び前記第２リストから削除するステップと、
    削除後の前記第１リストと、削除後の前記第２リストと、第２輸送媒体の情報に基づき、前記マッチング情報を生成するステップと、
    前記マッチング情報に基づく輸送を前記第２輸送媒体に割り当て、前記輸送をスケジューリングするステップと、
    をコンピュータに実行させるためのコンピュータプログラム。

Images