コンピュータの処理により、経路を選択する方法であって、経路をエッジであらわし、経路の交点をノードであらわすグラフを用意するステップであって、各経路は、該経路の重みを、単調増加する区分線形の関数で近似されているステップと、出発点と目的点の組である複数のリクエストに対して、前記グラフ上で最短経路を探索して、得られた経路を、処理対象の経路の集合とするステップと、前記複数の出発点と目的点の組に対して、各々の出発点から目的点までの所要時間を最短所要時間で割った値の最大値の最小化という目的関数を解くステップと、前記目的関数を解くステップを繰り返すステップ間に、最小コストがその時点で最良解以上の経路と、前反復で追加されたが使われなかった経路を、見込みのない経路として前記処理対象の経路の集合から取り除くステップを有する、経路選択方法。前記重みが、前記経路の通過時間である、請求項1に記載の経路選択方法。前記目的関数を解くステップを繰り返すステップ間に、追加すると前記目的関数を下げる経路を前記処理対象の経路の集合に追加するステップをさらに有する、請求項2に記載の経路選択方法。実際の所要時間最短所要時間が最大で、かつ全ての候補経路の実際の所要時間が同じリクエストをbottleneckRequestとし、それらの候補経路集合に含まれるエッジをbottleneckEdgeとするとき、前記追加するステップは、現状のコストを使い、bottleneckEdgeを使わない経路を探索するステップを有する、請求項3に記載の経路選択方法。前記現状のコストを使い、bottleneckEdgeを使わない経路を探索するステップが経路をみつけられないことに応答して、bottleneckEdgeを使う経路も含めて探索するステップを有する、請求項4に記載の経路選択方法。前記bottleneckEdgeを使う経路も含めて探索するステップが経路をみつけられないことに応答して、各非bottleneckEdgeについて、その時点の解を悪くせずにフローを増加させることができる経路がない場合、現状のコストを使い、bottleneckEdgeを使わない経路を探索するステップを有する、請求項5に記載の経路選択方法。前記現状のコストを使い、bottleneckEdgeを使わない経路を探索するステップが経路をみつけられないことに応答して、bottleneckEdgeを使う経路も含めて探索するステップを有する、請求項6に記載の経路選択方法。前記目的関数は、ソルバによって解かれる、請求項1に記載の経路選択方法。前記リクエストが、出発点と目的点と需要量の組であり、前記ソルバが、該出発点から該目的点に至る複数の経路の、該需要量における使用割合を出力する、請求項8記載の経路選択方法。コンピュータの処理により、経路を選択するプログラムであって、前記コンピュータに、経路をエッジであらわし、経路の交点をノードであらわすグラフを用意するステップであって、各経路は、該経路の重みを、単調増加する区分線形の関数で近似されているステップと、出発点と目的点の組である複数のリクエストに対して、前記グラフ上で最短経路を探索して、得られた経路を、処理対象の経路の集合とするステップと、前記複数の出発点と目的点の組に対して、各々の出発点から目的点までの所要時間を最短所要時間で割った値の最大値の最小化という目的関数を解くステップと、前記目的関数を解くステップを繰り返すステップ間に、最小コストがその時点で最良解以上の経路と、前反復で追加されたが使われなかった経路を、見込みのない経路として前記処理対象の経路の集合から取り除くステップを実行させる、経路選択プログラム。前記重みが、前記経路の通過時間である、請求項10に記載の経路選択プログラム。前記目的関数を解くステップを繰り返すステップ間に、追加すると前記目的関数を下げる経路を前記処理対象の経路の集合に追加するステップをさらに有する、請求項11に記載の経路選択プログラム。実際の所要時間最短所要時間が最大で、かつ全ての候補経路の実際の所要時間が同じリクエストをbottleneckRequestとし、それらの候補経路集合に含まれるエッジをbottleneckEdgeとするとき、前記追加するステップは、現状のコストを使い、bottleneckEdgeを使わない経路を探索するステップを有する、請求項12に記載の経路選択プログラム。前記現状のコストを使い、bottleneckEdgeを使わない経路を探索するステップが経路をみつけられないことに応答して、bottleneckEdgeを使う経路も含めて探索するステップを有する、請求項13に記載の経路選択プログラム。前記目的関数は、ソルバによって解かれる、請求項10に記載の経路選択プログラム。前記リクエストが、出発点と目的点と需要量の組であり、前記ソルバが、該出発点から該目的点に至る複数の経路の、該需要量における使用割合を出力する、請求項15記載の経路選択プログラム。コンピュータの処理により、経路を選択するシステムであって、記憶手段と、前記記憶手段に記憶され、経路をエッジであらわし、経路の交点をノードであらわすグラフであって、各経路は、該経路を通過する所要時間を、単調増加する区分線形の関数で近似されているグラフと、出発点と目的点の組である複数のリクエストに対して、前記グラフ上で最短経路を探索して、得られた経路を、処理対象の経路の集合とする手段と、前記複数の出発点と目的点の組に対して、各々の出発点から目的点までの所要時間を最短所要時間で割った値の最大値の最小化という目的関数を解くソルバと、前記ソルバが、前記目的関数を解く処理を繰り返す間に、最小コストがその時点で最良解以上の経路と、前反復で追加されたが使われなかった経路を、見込みのない経路として前記処理対象の経路の集合から取り除く手段とを有する、経路選択システム。前記目的関数を解く処理を繰り返す間に、追加すると前記目的関数を下げる経路を前記処理対象の経路の集合に追加する手段をさらに有する、請求項17に記載の経路選択システム。実際の所要時間最短所要時間が最大で、かつ全ての候補経路の実際の所要時間が同じリクエストをbottleneckRequestとし、それらの候補経路集合に含まれるエッジをbottleneckEdgeとするとき、前記追加する手段は、現状のコストを使い、bottleneckEdgeを使わない経路を探索する、請求項18に記載の経路選択システム。前記現状のコストを使い、bottleneckEdgeを使わない経路を探索する手段が経路をみつけられないことに応答して、bottleneckEdgeを使う経路も含めて探索する、請求項19に記載の経路選択システム。前記リクエストが、出発点と目的点と需要量の組であり、前記ソルバが、該出発点から該目的点に至る複数の経路の、該需要量における使用割合を出力する、請求項20記載の経路選択システム。従って、この発明の目的は、多対多の経路探索処理を合理的な計算量で求める技法を提供することにある。この発明の他の目的は、複数の車両などの通行による混雑度を考慮した経路探索処理を合理的な計算量で求める技法を提供することにある。この発明においては、交通路をグラフで記述し、各エッジの所要時間を、単調増加する区分線形の関数で近似することで、交通量通行量の増加に伴う混雑の発生がモデル化される。このモデルは、図1に示す混雑度と所要時間の関係の曲線の近似になっている。そこで、出発点と目的点を指示するカーナビなどからの情報をリクエストとすると、目的関数を、全リクエストに亘る実際の所要時間を最短所要時間で割った値の最大値の最小化とすることで、全ての車両を公平に扱うことができ、全体としても合理的にルーティングになる、というのが本発明の知見である。これは、整数値を取る変数と実数値を取る変数の両方を用いる混合整数計画問題MIPとして記述することができ、所定のソルバで解くことができる。但し、MIPでの記述は、あらゆる経路を陽に列挙する必要があり、候補となる経路は、グラフのサイズに関して、一般に指数個存在するので、NP困難問題となって、現実的に解くことが困難である。本発明の1つの特徴によれば、候補経路は指数個存在するが、初期状態から、見込みのある経路を徐々に追加して反復してMIPを解くことで、候補経路数の爆発が抑えられる。本発明の別の特徴によれば、ある反復終了時点での実際の経路を使って新たな経路を探索することで、迂回路として利用価値の高い経路を優先して探索することができる。このとき、本発明の1つの側面によれば、最小コストがその時点で最良解以上の経路と、前反復で追加されたが使われなかった経路が、見込みのない経路として取り除かれる。本発明のさらに別の特徴によれば、MIPの計算の結果、出発地から目的地への複数の経路とその利用割合が得られ、その結果を用いて、混雑を緩和するような最適なルーティングが可能となる。本発明の更に別の特徴によれば、経路候補の更新の際には、前反復で使用された経路は必ず残すようにすることで、MIPにおいて前反復の解を初期値として利用することが可能となり、計算時間を大幅に短縮することが可能となる。この発明によれば、混合整数計画問題を用いつつ、見込みのない経路は取り除き、前反復で使用された経路は必ず残すようにして有望な値から反復計算を開始することで、合理的な計算量で多対多の経路を計算することができる。さらに、この発明によれば、各エッジの所要時間を、単調増加する区分線形の関数で近似することで、妥当な計算量で、混雑を緩和する望ましいルーティングが得られる。以下、図面に基づき、この発明の実施例を説明する。特に断わらない限り、同一の参照番号は、図面を通して、同一の対象を指すものとする。尚、以下で説明するのは、本発明の一実施形態であり、この発明を、この実施例で説明する内容に限定する意図はないことを理解されたい。図4を参照すると、本発明の一実施例に係るシステム構成及び処理を実現するためのコンピュータハードウェアのブロック図が示されている。図1において、システムパス402には、CPU404と、主記憶RAM406と、ハードディスクドライブHDD408と、キーボード410と、マウス412と、ディスプレイ414が接続されている。CPU404は、好適には、32ビットまたは64ビットのアーキテクチャに基づくものであり、例えば、インテル社のPentium商標4、Core商標2Duo、Xeon商標、AMD社のAthlon商標などを使用することができる。主記憶406は、好適には、4GB以上の容量をもつものである。ハードディスクドライブ408は、大量の交通路グラフデータを格納できるように、例えば、500GB以上の容量をもつものであることが望ましい。このようなハードウェア構成の好適な例の1つとして、IBMSystemXシリーズがあるが、これには限定されず、通常のパーソナルコンピュータでも、本発明を実施可能である。ハードディスクドライブ408には、個々に図示しないが、オペレーティングシステムが、予め格納されている。オペレーティングシステムは、Linux商標、マイクロソフト社のWindowsXP商標、Windows商標2000、Windows商標2008サーバ、アップルコンピュータのMacOS商標などの、CPU404に適合する任意のものでよい。ハードディスクドライブ408にはさらに、後述する、処理のメインルーチン502、交通路グラフデータ504、リクエストデータ506、ソルバ508、経路探索モジュール510、及び経路更新モジュール512が格納されている。メインルーチン502、ソルバ508、経路探索モジュール510、及び経路更新モジュール512は、C、C、C、Java商標などの既存のプログラミング言語処理系で作成され、システムの起動時、あるいは、必要に応じてオペレーティングシステムの働きで、メモリ406にロードされて実行される。ディスプレイ414は、好適には、液晶ディスプレイであり、例えば、XGA4024×768の解像度、またはUXGA1600×1200の解像度などの任意の解像度のものを使用することができる。ディスプレイ414は、図示しないが、本発明の処理プログラムを起動したり、停止したりするための操作画面を表示したり、交通路データや、交通路上の経路を表示したりするために使用される。次に、図5の機能ブロック図を参照して、本発明を実施するための論理的機能構成について説明する。図5において、メインルーチン502は、全体の処理を統括するプログラムであり、操作画面図示しないをディスプレイ414に表示し、ユーザのキーボード410やマウス412の操作に応じて、処理を開始したり、停止したりする機能を有する。交通路グラフデータ504は、交差点をノード、道路をエッジとするように交通路をグラフで記述し、各エッジの所要時間を、単調増加する区分線形の関数で近似することで、交通量通行量の増加に伴う混雑の発生をモデル化した重み付きグラフデータである。グラフをコンピュータ可読且つ、ハードディスクなどの媒体に保存可能な形式に表現するには、典型的には行列表現と、リスト表現があるが、この発明の目的のためには、どちらの形式でもよい。図6に、エッジの所要時間の区分線形性を示す。ここでxは、1時間あたりの車の通過台数のような交通量である。これは、図1に示すグラフの区分線形近似になっている。図示されているように、00である。ここでは3つだけの区間が図示されているが、これは一実施例に過ぎず、必要に応じて、任意の数と幅の区間をとることができる。このような区分線形の関数は、これには限定されないが、例えば、各エッジから指し示される、メモリ上のテーブルを参照する線形関数として実装することができる。すなわち、0と計算される。リクエストデータ506は、出発地、目的地、需要量の集合として与えられる。このようなリクエストデータは例えば、プローブカーデータを利用することにより、収集することができる。プローブカーデータを利用した交通データ収集技法は公知であり、例えば、特開2004-110458号公報、特開2004-156982号公報、特開2007-193705号公報、特開2004-241987号公報などを参照されたい。これらの技法によれば、所定の期間に、出発地、目的地の対毎に、その間を走った車両の台数が分かるので、その台数を需要量とし、出発地、目的地、需要量を需要量で降順ソートし、上位から所定の数の組をハードディスクドライブ408に保存するなどして、リクエストデータ506を用意することができる。ソルバ508は、全リクエストに亘る、実際の所要時間/最短所要時間の最大値の最小化を目的関数とする、混合整数計画問題MIPとして定式化された式を解くことにより、各リクエストに対して、複数のルートとその使用割合実数を出力として与える。好適なソルバは、これには限定されないが、IBMILOGCPLEXである。このMIPの定式化については、後でより詳細に説明する。経路探索モジュール510は、ダイクストラ法、A法など従来周知のアルゴリズムにより、重み付きグラフの経路探索を行う。あるいは、A法の改良版である、本出願に係る特開2008-157698号公報に記述されているアルゴリズムを使ってもよい。経路更新モジュール512は、計算量を減らすために適宜経路を除去し、あるいは有利な経路を追加する処理を行う。経路更新モジュール512が実行する処理については、図8のフローチャートを参照して、後で詳細に説明する。次に、図7及び図8のフローチャートを参照して、本発明の経路選択処理について説明する。図7では、メインルーチン502は、ステップ702で、経路探索モジュール510を呼び出して、最小コスト経路、すなわち、各エッジで、所要時間tmaxiaixbiの式でx0と置いた場合の、リクエストデータ506における出発地、目的地の対における、出発地から目的地までの最短経路を探索する。ステップ704では、メインルーチン502は、ソルバ508を呼び出して、その時点での候補経路の下で、混合整数計画問題MIPを解く。なお、ステップ704、ステップ706及びステップ708からなるループで、2回目以降は、前回の解を初期値とすることで、計算時間の短縮が可能である。次に、MIPの定式化について説明する。この定式化は、全リクエストに亘る、実際の所要時間/最短所要時間の最大値の最小化を目的関数とすることを意図している。交通路グラフデータ504のノードの集合をV、エッジの集合をEとすると、グラフGであらわされる。そこで、図6の区分線形近似を参照すると、エッジe∈Eの移動にかかる所要時間は、交通量をxであらわしたとき、次の式であらわされる。temaxiただし、aei0一方、リクエストiは、以下の属性をもつ。出発地点のノードsi∈V目的地点のノードgi∈V需要量di∈Rdi0また、ノードsiからノードgiへのサイクルを含まない全ての経路の集合をPiとする。すると、p∈Piは、以下のように、連結する辺の順列として表される。pここで、pは、pをつなぐ辺の数である。そこで、交通量xが0の場合の、ノードsiからノードgiへの最小所要時間をTiとする。すなわちTiは、次式であらわされる。このとき、Tiは、Piの全要素を陽に列挙しないでも、各辺e∈Eのコストをteとし、例えば、経路探索モジュール510を呼び出して、最短経路探索アルゴリズムなどを実行することで求めることができる。また、リクエストiの候補経路集合Piの要素に適当に順番を付け、Piのj番目の経路をpijであらわすことにする。また、Lを十分大きな正の定数とし、yijを、リクエストiの候補経路jを使用するかどうかをあらわす、01の整数変数である。以上の定義を用いて、混合整数計画問題は、以下のように定式化される。ここで、st以下が、制約式をあらわしている。この混合整数計画問題を解いた結果得られるxijは、リクエストiにおけるj番目の経路の交通量をあらわす。すなわち、xijdiが、リクエストiにおけるj番目の経路の使用割合となる。この使用割合は、例えば、図9で、出発地1から、目的地1への複数の経路それぞれに関連付けられたパーセンテージとして示すものである。次にステップ706では、メインルーチン502は、終了条件を満足したかどうかを判断する。ここで終了条件とは例えば、計算時間が事前に設定した時間を超えた、あるいは、反復回数が、所定回数を超えた、などである。メインルーチン502は、終了条件を満足したと判断すると、処理を終了する。その時点で、リクエスト毎の出発地から目的地への複数の経路と、その経路毎の使用割合が得られる。メインルーチン502が、ステップ706で、終了条件を満足していないと判断すると、処理は、ステップ708に進み、そこで、メインルーチン502は、経路更新モジュール512を呼び出して、候補経路の更新処理を行う。候補経路の更新処理とは、使われなかった経路や有望でない経路を削除し、有望とみなされる経路を追加する処理であり、図8のフローチャートを参照して、後で詳細に説明する。ステップ708で候補経路が更新された後、ステップ704では、その更新された候補経路に基づき、ソルバ508によって、再びMIPが解かれることになる。次に、図8のフローチャートを参照して、経路更新モジュール512の処理を説明する。すなわち、ステップ802で、経路更新モジュール512は、各リクエストについて、以下のような経路を、見込みがない経路として取り除く。最小コストが、その時点で、最良解以上の経路。ここで最小コストとは、交通量x0とした場合のコストである。前反復で追加されたが、使われなかった経路。ここで、使われなかった経路というのは、ステップ704におけるソルバ508での計算結果における、変数yijの値が0であることによって判別される。このように経路を取り除く処理によって、候補経路数の爆発を抑えることができる。ステップ804では、経路更新モジュール512は、実際の所要時間最短所要時間が最大で、かつ全ての候補経路の実際の所要時間が同じリクエストをbottleneckRequestとし、それらの候補経路集合に含まれるエッジをbottleneckEdgeとする。すなわち、経路更新モジュール512は、各反復の結果から、ボトルネックとなっているリクエスト、及びbottleneckEdgeの集合を特定する。すなわち、目的関数値を決定しているリクエストをbottleneckRequestと定義し、そのリクエストの候補経路に含まれるエッジをbottleneckEdgeと定義している。ステップ806では、経路更新モジュール512は、各bottleneckRequestについて、以下の条件を満たす、コストが現状の最良解未満の経路を探索する。現状のコストを使い、bottleneckEdgeを使わない経路を探索する。見つからなければ、現状のコストを使い、bottleneckEdgeを使う経路も含めて探索する。こうして見つかった経路は、新たに追加される。すなわち、追加すると目的関数値が下がる経路、あるいは、下がる可能性が高い経路を効率的に追加することが可能となる。ステップ808では、経路更新モジュール512は、ステップ806で、候補経路が見つかったかどうかを判断する。もし見つかったのなら、図8で示すサブルーチンを抜けて、図7のステップ704に戻る。ステップ808で、経路更新モジュール512が、候補経路が見つからなかったと判断すると、ステップ810で、経路更新モジュール512は、各非bottleneckRequestについて、その時点の解を悪くせずにフロー、すなわち交通量を増加させることができる経路がない場合、以下の条件の経路を探索する。現状のコストを使い、bottleneckEdgeを使わない経路を探索する。見つからなければ、bottleneckEdgeを使う経路も含めて探索する。こうして見つかった経路は、新たに追加される。その後、図8で示すサブルーチンを抜けて、図7のステップ704に戻る。ステップ810のような処理を行うのは、ボトルネックとなっていないリクエストについても、候補経路を追加することで目的関数値が向上することもあるからである。このとき、以下の条件を満たす候補経路を持つリクエストについては、いかなる経路を追加しても目的関数値の向上は図れないことが分かる。その候補経路のいかなるエッジもbottleneckEdgeではなく、かつ、その経路自体が現在の目的関数値を決定している経路ではない。なお、この条件は、エッジのコスト関数として狭義に単調増加するコスト関数を使うことが前提となっている。すなわち、所要時間の関数のaxbに関して、a0ではなくa0としてある。図7のフローチャートに戻って、ステップ704でのMIPの計算の後、ステップ706で終了条件を満足したと判定されると、各リクエスト毎の複数の経路と、その個々の経路の使用割合が返される。こうして得られた多対多の出発地と目的地の間の望ましい経路と、望ましい経路の使用割合が得られると、車両の交通路においては、通勤時間帯などの恒常的定常的な渋滞の緩和、恒常的に渋滞が発生する施設周辺のルーティング、などの応用が考えられる。また、群集の誘導として、イベント会場などでの効率のよい群衆の誘導経路の立案、ビル火災時などにおける効率的な避難経路の立案などの応用もありえる。なお、特定の実施例に従い本発明を説明してきたが、例示されているハードウェア構成は一例であって、マルチプロセッサ環境、ネットワーク接続のクラウドコンピューティング環境など、任意のハードウェア環境で使用可能である。