(57)【要約】      （修正有）【課題】出発位置と到着位置の各組合せの移動情報（移動距離及び／又は移動時間）を短時間で算出すること。【解決手段】サーバは、出発位置から到着位置までの移動情報を算出する移動情報算出処理を実行することが可能である。サーバは、出発位置と到着位置の組合せ群を含むマトリクスデータを２回に亘ってランダムに並び替えることによって、第１マトリクスデータ１１０及び第２マトリクスデータ１２０を作成する。サーバＰＣ５０の一方のＣＰＵは、第１マトリクスデータ１１０に含まれる各組合せの配置順序に従って第１の移動情報算出処理を実行する。サーバの他方のＣＰＵは、第２マトリクスデータ１１０に含まれる各組合せの配置順序に従って第２の移動情報算出処理を第１の移動情報算出処理と並行して実行する。【選択図】図９
2008287304.tif 000002
【特許請求の範囲】
【請求項１】
出発位置から到着位置までの移動距離及び／又は移動時間に関する移動情報を算出する移動情報算出装置であり、
出発位置と到着位置の組合せ群を含む位置情報データを入力する入力装置と、入力装置に入力された位置情報データを記憶するデータ記憶装置と、データ記憶装置に記憶されている位置情報データに含まれる各組合せについて移動情報を算出する移動情報算出処理を実行する制御装置と、制御装置によって算出された各組合せの移動情報を記憶する移動情報記憶装置とを備え、
制御装置は、位置情報データに含まれる各組合せについて、
（１）当該組合せの移動情報が移動情報記憶装置に記憶されているのか否かを判断し、
（２）当該組合せの移動情報が移動情報記憶装置に記憶されている場合は、当該組合せの移動情報を算出せず、
（３）当該組合せの移動情報が移動情報記憶装置に記憶されていない場合は、当該組合せの移動情報を算出して移動情報記憶装置に記憶する
ことによって移動情報算出処理を実行し、
制御装置は、位置情報データに含まれる各組合せについて少なくとも２パターンの処理順序を決定し、一方のパターンの処理順序に従って第１の前記移動情報算出処理を実行するとともに、他方のパターンの処理順序に従って第２の前記移動情報算出処理を第１の前記移動情報算出処理と並行して実行する
ことを特徴とする移動情報算出装置。
【請求項２】
制御装置は、位置情報データに含まれる各組合せの並び順を少なくとも２回に亘ってランダムに並び替えることによって、位置情報データに含まれる各組合せについて少なくとも２パターンの処理順序を決定する
ことを特徴とする請求項１の移動情報算出装置。
【請求項３】
位置情報データは、複数の出発位置が第１方向に並んでいるとともに、複数の到着位置が第２方向に並んでいるマトリクスデータを含んでおり、
制御装置は、
マトリクスデータに含まれる複数の出発位置及び／又は複数の到着位置をランダムに並び替えて第１マトリクスデータを作成し、その第１マトリクスデータにおける各組合せの配置順序に従って第１の前記移動情報算出処理を実行するとともに、
マトリクスデータに含まれる複数の出発位置及び／又は複数の到着位置をランダムに並び替えて第２マトリクスデータを作成し、その第２マトリクスデータにおける各組合せの配置順序に従って第２の前記移動情報算出処理を実行する
ことを特徴とする請求項２の移動情報算出装置。
【請求項４】
制御装置は、
マトリクスデータに含まれる出発位置数Ｍ１より小さい正の整数であってＭ１と公約数を持たない全ての値を算出し、算出された各値の中からランダムに１つの値を選択し、選択された値を差分値として複数の出発位置を並び替えるとともに、
マトリクスデータに含まれる到着位置数Ｎ１より小さい正の整数であってＮ１と公約数を持たない全ての値を算出し、算出された各値の中からランダムに１つの値を選択し、選択された値を差分値として複数の到着位置を並び替える
という並び替え処理を２回に亘って実行することによって、前記第１マトリクスデータ及び前記第２マトリクスデータを作成する
ことを特徴とする請求項３の移動情報算出装置。
【請求項５】
制御装置は、
マトリクスデータに含まれる出発位置数Ｍ２より小さくてＭ２の約数ではない全ての素数を算出し、算出された各値の中からランダムに１つの値を選択し、選択された値を差分値として複数の出発位置を並び替えるとともに、
マトリクスデータに含まれる到着位置数Ｎ２より小さくてＮ２の約数ではない全ての素数を算出し、算出された各値の中からランダムに１つの値を選択し、選択された値を差分値として複数の到着位置を並び替える
という並び替え処理を２回に亘って実行することによって、前記第１マトリクスデータ及び前記第２マトリクスデータを作成する
ことを特徴とする請求項３の移動情報算出装置。
【請求項６】
制御装置は、位置情報データに含まれる各組合せについて第１パターンの処理順序を決定するとともに第１パターンと異なる第２パターンの処理順序を決定することによって、
位置情報データに含まれる各組合せについて少なくとも２パターンの処理順序を決定する
ことを特徴とする請求項１の移動情報算出装置。
【請求項７】
出発位置から到着位置までの移動距離及び／又は移動時間に関する移動情報をコンピュータを利用して算出する移動情報算出方法であり、
そのコンピュータが、出発位置と到着位置の組合せ群を含む位置情報データを入力する入力工程と、入力工程で入力された位置情報データを第１記憶装置に記憶するデータ記憶工程と、第１記憶装置に記憶されている位置情報データに含まれる各組合せについて移動情報を算出する移動情報算出処理を実行する算出工程とを実行し、
算出工程では、位置情報データに含まれる各組合せについて、
（１）当該組合せの移動情報が第２記憶装置に記憶されているのか否かを判断し、
（２）当該組合せの移動情報が第２記憶装置に記憶されている場合は、当該組合せの移動情報を算出せず、
（３）当該組合せの移動情報が第２記憶装置に記憶されていない場合は、当該組合せの移動情報を算出して第２記憶装置に記憶する
ことによって移動情報算出処理を実行し、
算出工程では、位置情報データに含まれる各組合せについて少なくとも２パターンの処理順序を決定し、一方のパターンの処理順序に従って第１の前記移動情報算出処理を実行するとともに、他方のパターンの処理順序に従って第２の前記移動情報算出処理を第１の前記移動情報算出処理と並行して実行する
ことを特徴とする移動情報算出方法。
【請求項８】
出発位置から到着位置までの移動距離及び／又は移動時間に関する移動情報をコンピュータに算出させるコンピュータプログラムであり、
そのコンピュータプログラムは、出発位置と到着位置の組合せ群を含む位置情報データを入力する入力工程と、入力工程で入力された位置情報データを第１記憶装置に記憶するデータ記憶工程と、第１記憶装置に記憶されている位置情報データに含まれる各組合せについて移動情報を算出する移動情報算出処理を実行する算出工程とをコンピュータに実行させ、
算出工程では、位置情報データに含まれる各組合せについて、
（１）当該組合せの移動情報が第２記憶装置に記憶されているのか否かを判断し、
（２）当該組合せの移動情報が第２記憶装置に記憶されている場合は、当該組合せの移動情報を算出せず、
（３）当該組合せの移動情報が第２記憶装置に記憶されていない場合は、当該組合せの移動情報を算出して第２記憶装置に記憶する
ことによって移動情報算出処理を実行し、
算出工程では、位置情報データに含まれる各組合せについて少なくとも２パターンの処理順序を決定し、一方のパターンの処理順序に従って第１の前記移動情報算出処理を実行するとともに、他方のパターンの処理順序に従って第２の前記移動情報算出処理を第１の前記移動情報算出処理と並行して実行する
ことを特徴とするコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、出発位置から到着位置までの移動距離及び／又は移動時間に関する移動情報を算出する技術に関する。
【背景技術】
【０００２】
本発明の背景となる事項を以下に列挙する。
（１）道路ネットワーク情報等に基づいて出発位置から到着位置までの移動情報（移動距離及び／又は移動時間）を算出する技術が知られている。例えば、下記の特許文献１には、移動情報を算出する装置が開示されている。
（２）複数の出発位置と複数の到着位置とが存在する場合に、出発位置と到着位置の組合せ群のそれぞれについて移動情報を算出しなければならない状況がある。例えば、複数の部品仕入先と複数の部品納入先とが存在し、部品搬送車両の効率的な走行経路をコンピュータによって立案するためには、最初に、部品仕入先と部品納入先の各組合せについて移動情報を算出しなければならない。コンピュータは、算出された各組合せの移動情報と最適化条件（例えば時間優先や距離優先）とに基づいて走行経路を立案することができる。
【０００３】
【特許文献１】特開２００４−２２００９５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
例えば、自動車のように部品点数が多い製品を製造する場合、多数の部品仕入先や部品納入先が存在する。この場合、部品仕入先と部品納入先の組合せ数が多くなり、各組合せの移動情報をコンピュータが算出するのに膨大な時間が必要になる。複数の出発位置と複数の到着位置（上記の例では部品仕入先と部品納入先）とが存在する場合に、それらの各組合せの移動情報をコンピュータによって効率的に算出するための方法論は確立されていない。
【０００５】
本発明は、上記した実情に鑑みてなされたものであり、出発位置と到着位置の各組合せの移動情報を短時間で算出することを可能とする技術を提供する。
【課題を解決するための手段】
【０００６】
本明細書によって開示される一つの技術は、出発位置から到着位置までの移動距離及び／又は移動時間に関する移動情報を算出する移動情報算出装置である。この移動情報算出装置は、入力装置とデータ記憶装置と制御装置と移動情報記憶装置とを備える。入力装置は、出発位置と到着位置の組合せ群を含む位置情報データを入力する。例えば、出発位置（到着位置）は、その出発位置（到着位置）を特定するＩＤによって表現されてもよいし、その出発位置（到着位置）の緯度及び経度（もしくは住所）によって表現されてもよい。データ記憶装置は、入力装置に入力された位置情報データを記憶する。制御装置は、データ記憶装置に記憶されている位置情報データに含まれる各組合せについて移動情報を算出する移動情報算出処理を実行する。移動情報記憶装置は、制御装置によって算出された各組合せの移動情報を記憶する。
【０００７】
制御装置は、位置情報データに含まれる各組合せについて、
（１）当該組合せの移動情報が移動情報記憶装置に記憶されているのか否かを判断し、
（２）当該組合せの移動情報が移動情報記憶装置に記憶されている場合は、当該組合せの移動情報を算出せず、
（３）当該組合せの移動情報が移動情報記憶装置に記憶されていない場合は、当該組合せの移動情報を算出して移動情報記憶装置に記憶する
ことによって移動情報算出処理を実行する。
なお、制御装置は、出発位置から到着位置までの移動距離のみを算出してもよいし、移動時間のみを算出してもよいし、移動距離と移動時間の両方を算出してもよい。また、出発位置（到着位置）の緯度及び経度は、上記の位置情報データに含まれていてもよいし、そうでなくてもよい。後者の場合、例えば、以下の（１）又は（２）を採用して移動情報を算出してもよい。（１）移動情報算出装置は、出発位置（到着位置）のＩＤとその出発位置（到着位置）の緯度及び経度を対応づけて記憶しているＩＤ−絶対位置記憶装置を有していてもよい。位置情報データに出発位置（到着位置）のＩＤが含まれる場合、そのＩＤをキーとしてＩＤ−絶対位置記憶装置を検索することによって緯度及び経度を特定することができ、その緯度及び経度から移動情報を算出することができる。（２）移動情報算出装置は、地図データを記憶している。位置情報データに出発位置（到着位置）の住所が含まれる場合、その住所と地図データから緯度及び経度を特定することができ、その緯度及び経度から移動情報を算出することができる。
【０００８】
上記の制御装置は、位置情報データに含まれる各組合せについて少なくとも２パターンの処理順序を決定し、一方のパターンの処理順序に従って第１の移動情報算出処理を実行するとともに、他方のパターンの処理順序に従って第２の移動情報算出処理を第１の移動情報算出処理と並行して実行する。
上記の「位置情報データに含まれる各組合せについて少なくとも２パターンの処理順序を決定する」とは、一方のパターンの処理順序と他方のパターンの処理順序とが必ず異なるように両パターンの処理順序を決定することに限定されない。例えば、後述するように、位置情報データに含まれる各組合せの並び順をランダムに並び替えることによって一方のパターンの処理順序を決定し、各組合せの並び順を再びランダムに並び替えることによって他方のパターンの処理順序を決定してもよい。この場合、一方のパターンの処理順序と他方のパターンの処理順序とが一致する可能性がある。この場合も、「各組合せについて少なくとも２パターンの処理順序を決定する」ことに等しい。即ち、「各組合せについて少なくとも２パターンの処理順序を決定する」とは、一方のパターンの処理順序と他方のパターンの処理順序とが必ず異なるようになる手法を利用して両パターンの処理順序を決定することを含むとともに、一方のパターンの処理順序と他方のパターンの処理順序とが異なるようになる可能性がある手法（一致する可能性もある手法）を利用して両パターンの処理順序を決定することを含む。
【０００９】
上記の技術では、第１及び第２の移動情報算出処理が並行して実行される。第１の移動情報算出処理を実行するための処理順序と第２の移動情報算出処理を実行するための処理順序とが異なる（もしくは異なる可能性がある）。２つの処理順序が異なる場合、第１の移動情報算出処理で先に移動情報が算出される組合せ（例えば出発位置Ｘ１と到着位置Ｘ２の組合せ）が存在する一方で、第２の移動情報算出処理で先に移動情報が算出される組合せ（例えば出発位置Ｘ３と到着位置Ｘ４の組合せ）が存在することになる。上記の例の場合、出発位置Ｘ１と到着位置Ｘ２の組合せの移動情報が第１の移動情報算出処理で算出されて移動情報記憶装置に記憶されているために、第２の移動情報算出処理では、その組合せの移動情報を算出する必要がない。また、出発位置Ｘ３と到着位置Ｘ４の組合せの移動情報が第２の移動情報算出処理で算出されて移動情報記憶装置に記憶されているために、第１の移動情報算出処理では、その組合せの移動情報を算出する必要がない。この結果、各組合せの移動情報を短時間で算出することができる。この技術では、異なるパターンの処理順序に従って複数の移動情報算出処理を並行して実行し得るために、各組合せの移動情報を短時間で算出することができる。
【００１０】
制御装置は、位置情報データに含まれる各組合せの並び順を少なくとも２回に亘ってランダムに並び替えることによって、位置情報データに含まれる各組合せについて少なくとも２パターンの処理順序を決定してもよい。
一方において、制御装置は、位置情報データに含まれる各組合せについて第１パターンの処理順序を決定するとともに第１パターンと異なる第２パターンの処理順序を決定することによって、位置情報データに含まれる各組合せについて少なくとも２パターンの処理順序を決定してもよい。この技術によると、第１の移動情報算出処理を実行するための処理順序と第２の移動情報算出処理を実行するための処理順序とが異なるパターンになることが保証される。このために、各組合せの移動情報を算出するための時間を確実に短縮化することができる。
【００１１】
上記の位置情報データは、複数の出発位置が第１方向に並んでいるとともに、複数の到着位置が第２方向に並んでいるマトリクスデータを含んでいてもよい。なお、この「マトリクスデータ」という用語は、最も広義に解釈されるべきものであり、マトリクス形式になっている必要は必ずしもなく、マトリクス形式に変換することができるデータも含む概念である。
制御装置は、マトリクスデータに含まれる複数の出発位置及び／又は複数の到着位置をランダムに並び替えて第１マトリクスデータを作成し、その第１マトリクスデータにおける各組合せの配置順序に従って第１の移動情報算出処理を実行してもよい。また、制御装置は、マトリクスデータに含まれる複数の出発位置及び／又は複数の到着位置をランダムに並び替えて第２マトリクスデータを作成し、その第２マトリクスデータにおける各組合せの配置順序に従って第２の移動情報算出処理を実行してもよい。
【００１２】
上記の技術によると、マトリクスデータをランダムに並び替えることによって、各組合せの処理順序をランダムに決定することができる。マトリクスデータをランダムに並び替えるための具体的な手法として、以下の（１）又は（２）を採用してもよい。
【００１３】
（１）制御装置は、
（１−１）マトリクスデータに含まれる出発位置数Ｍ１より小さい正の整数であってＭ１と公約数を持たない全ての値（ここではＣ１とする）を算出し、算出された各値の中からランダムに１つの値を選択し、選択された値を差分値として複数の出発位置を並び替えるとともに、
（１−２）マトリクスデータに含まれる到着位置数Ｎ１より小さい正の整数であってＮ１と公約数を持たない全ての値（ここではＣ２とする）を算出し、算出された各値の中からランダムに１つの値を選択し、選択された値を差分値として複数の到着位置を並び替える
という並び替え処理を２回に亘って実行することによって、上記の第１マトリクスデータ及び第２マトリクスデータを作成してもよい。
なお、上記の「選択された値を差分値として複数の出発位置（到着位置）を並び替える」とは、マトリクスデータにおける複数の出発位置（到着位置）の並び順を差分値ずつずらして配置することを意味する。
【００１４】
上記の手法を利用すると、マトリクスデータをランダムに並び替えて第１マトリクスデータ及び第２マトリクスデータを作成することができる。
なお、本発明者の研究によって、差分値として１を利用しても並び替え処理を実行することができることがわかっている。このために、上記の（１−１）では、Ｃ１のみの中からランダムに１つの値が選択されてもよいし、Ｃ１と１を含む各値の中からランダムに１つの値が選択されてもよい。前者の場合も後者の場合も、「算出された各値の中からランダムに１つの値を選択する」ことに等しい。また、上記の（１−２）では、Ｃ２のみの中からランダムに１つの値が選択されてもよいし、Ｃ２と１を含む各値の中からランダムに１つの値が選択されてもよい。前者の場合も後者の場合も、「算出された各値の中からランダムに１つの値を選択する」ことに等しい。
なお、マトリクスデータに含まれる出発位置数Ｍ１と到着位置数Ｎ１が同じ場合がある。この場合、制御装置は、上記の（１−１）においてＣ１が算出されている場合は、上記の（１−２）においてＣ２を算出することを省略してもよい。また、制御装置は、上記の（１−２）においてＣ２が算出されている場合は、上記の（１−１）においてＣ１を算出することを省略してもよい。このようにしても、上記の並び替え処理を実行することに等しい。
また、マトリクスデータに含まれる出発位置数Ｍ１と到着位置数Ｎ１が同じ場合、制御装置は、上記の（１−１）と（１−２）のいずれかのみで差分値を選択するようにしてもよい。例えば、制御装置は、上記の（１−１）において差分値Ｄ１が選択された場合、上記の（１−２）においても差分値Ｄ１を利用して複数の到着位置を並び替えてもよい。このようにしても、上記の並び替え処理を実行することに等しい。一方において、制御装置は、上記の（１−１）と（１−２）のそれぞれにおいて差分値を選択するようにしてもよい。
なお、１回目の並び替え処理と２回目の並び替え処理は並行して（同時的に）実行されてもよいし、１回目の並び替え処理を終えてから２回目の並び替え処理を実行してもよい。後者の場合、２回目の並び替え処理では上記のＣ１やＣ２を算出することを省略してもよい。１回目の並び替え処理と同じ結果が得られるからである。この場合も、２回に亘って並び替え処理を実行することに等しい。
【００１５】
（２）制御装置は、
（２−１）マトリクスデータに含まれる出発位置数Ｍ２より小さくてＭ２の約数ではない全ての素数（ここではＥ１とする）を算出し、算出された各値の中からランダムに１つの値を選択し、選択された値を差分値として複数の出発位置を並び替えるとともに、
（２−２）マトリクスデータに含まれる到着位置数Ｎ２より小さくてＮ２の約数ではない全ての素数（ここではＥ２とする）を算出し、算出された各値の中からランダムに１つの値を選択し、選択された値を差分値として複数の到着位置を並び替える
という並び替え処理を２回に亘って実行することによって、上記の第１マトリクスデータ及び第２マトリクスデータを作成してもよい。
【００１６】
この手法を利用しても、マトリクスデータをランダムに並び替えて第１マトリクスデータ及び第２マトリクスデータを作成することができる。
なお、上記の（２−１）では、Ｅ１のみの中からランダムに１つの値が選択されてもよいし、Ｅ１と１を含む各値の中からランダムに１つの値が選択されてもよい。また、上記の（２−２）では、Ｅ２のみの中からランダムに１つの値が選択されてもよいし、Ｅ２と１を含む各値の中からランダムに１つの値が選択されてもよい。
また、マトリクスデータに含まれる出発位置数Ｍ２と到着位置数Ｎ２が同じ場合、制御装置は、上記の（２−１）においてＥ１が算出されている場合は、上記の（２−２）においてＥ２を算出することを省略してもよい。また、制御装置は、上記の（２−２）においてＥ２が算出されている場合は、上記の（２−１）においてＥ１を算出することを省略してもよい。
また、マトリクスデータに含まれる出発位置数Ｍ２と到着位置数Ｎ２が同じ場合、制御装置は、上記の（２−１）と（２−２）のいずれかのみで差分値を選択するようにしてもよい。一方において、制御装置は、上記の（２−１）と（２−２）のそれぞれにおいて差分値を選択するようにしてもよい。
なお、１回目の並び替え処理を終えてから２回目の並び替え処理を実行する場合、２回目の並び替え処理では上記のＣ１やＣ２を算出することを省略してもよい。
【００１７】
また、本発明の技術は、出発位置から到着位置までの移動距離及び／又は移動時間に関する移動情報をコンピュータを利用して算出する移動情報算出方法として表現することもできる。この方法では、コンピュータが入力工程とデータ記憶工程と算出工程とを実行する。入力工程では、出発位置と到着位置の組合せ群を含む位置情報データを入力する。データ記憶工程では、入力工程で入力された位置情報データを第１記憶装置に記憶する。算出工程では、第１記憶装置に記憶されている位置情報データに含まれる各組合せについて移動情報を算出する移動情報算出処理を実行する。
【００１８】
上記の算出工程では、位置情報データに含まれる各組合せについて、
（１）当該組合せの移動情報が第２の記憶装置に記憶されているのか否かを判断し、
（２）当該組合せの移動情報が第２の記憶装置に記憶されている場合は、当該組合せの移動情報を算出せず、
（３）当該組合せの移動情報が第２の記憶装置に記憶されていない場合は、当該組合せの移動情報を算出して第２の記憶装置に記憶する
ことによって移動情報算出処理を実行する。
【００１９】
また、算出工程では、位置情報データに含まれる各組合せについて少なくとも２パターンの処理順序を決定し、一方のパターンの処理順序に従って第１の移動情報算出処理を実行するとともに、他方のパターンの処理順序に従って第２の移動情報算出処理を第１の移動情報算出処理と並行して実行する。
この方法によると、各組合せの移動情報を短時間で算出することが可能になる。
【００２０】
また、上記の方法をコンピュータに実行させるコンピュータプログラムも有用である。このコンピュータプログラムを利用すると、上記の方法を実行するコンピュータを実現することができる。
【発明を実施するための最良の形態】
【００２１】
ここでは、以下の実施例に記載されている特徴を列記しておく。
（形態１）移動情報算出装置は、複数の処理を並行して実行することができる複数のＣＰＵを有している。
（形態２）移動情報算出装置は、サーバＰＣである。サーバＰＣは、クライアントＰＣから位置情報データ（マトリクスデータ）を取得する。サーバＰＣは、位置情報データに含まれる各組合せについて移動情報を算出する。サーバＰＣは、算出された各組合せの移動情報をクライアントＰＣに出力する。
【実施例】
【００２２】
（第１実施例）
図面を参照して本発明の実施例を説明する。図１は、各地に存在している複数の拠点の一例を示す。本実施例では、複数の仕入先１０と複数の中継地１２と複数の工場１４が存在する。各拠点１０，１２，１４には、固有のＩＤが存在する。本実施例では、１２の拠点が存在するために、「００１」から「０１２」までのＩＤが存在する。本実施例では、各仕入先１０から各工場１４に部品を搬送するための部品搬送車両の走行経路をコンピュータによって立案する。仕入先１０から中継地１２を経て工場１４に部品が搬送されることもあれば、仕入先１０から工場１４にダイレクトに部品が搬送されることもある。走行経路を立案するための様々な最適化条件を設定することができる。最適化条件が変われば、走行経路も変わる。例えば、移動時間を短縮化することを優先すれば、ＩＤ「００１」の仕入先１０からＩＤ「００８」の工場１４に部品を搬送するという走行経路が立案されるのに対し、移動距離を最短化することを優先すれば、上記の走行経路が立案されないことがある。
【００２３】
図２は、走行経路立案システムの構成を示す。走行経路立案システム２０は、クライアントＰＣ３０とサーバＰＣ５０を備える。クライアントＰＣ３０は、ＣＰＵ３２とハードディスク３４と操作部４２と表示部４４とネットワークインターフェイス４６等を有する。ＣＰＵ３２は、ハードディスク３４に記憶されている各種のプログラムに従って処理を実行する。ハードディスク３４は、走行経路立案プログラム記憶部３６と依頼データファイル記憶部３８とその他の記憶部４０等を有する。走行経路立案プログラム記憶部３６は、ユーザによって設定された最適化条件に従って走行経路を立案するためのプログラムを記憶している。なお、最適な走行経路を立案するためのプログラムは公知であるために、その詳しい内容の説明は省略する。
【００２４】
依頼データファイル記憶部３８は、サーバＰＣ５０に処理を実行させる依頼データを記憶している。図３は、依頼データファイル記憶部３８の記憶内容の一例を示す。依頼データファイル記憶部３８は、２つの依頼データファイル８０，９０を記憶している。
依頼データファイル８０は、マトリクスデータ８２と最適化条件データ８４を含んでいる。マトリクスデータ８２は、複数の出発位置ＩＤがＸ方向（横方向）に並んでいて複数の到着位置ＩＤがＹ方向（縦方向）に並んでいるマトリクス形式のデータである。本実施例では、図１に示される全ての拠点が、出発位置と到着位置の両方として採用されている。即ち、１２の出発位置と１２の到着位置が存在し、出発位置と到着位置の組合せが１４４組存在する。なお、図示省略しているが、各拠点のＩＤには、その拠点の緯度及び経度が対応づけられている。マトリクスデータ８２は、各拠点の緯度及び経度を含んでいるデータであると言える。後で詳しく説明するが、このマトリクスデータ８２がサーバＰＣ５０に送られる。これにより、サーバＰＣ５０が、マトリクスデータ８２に含まれる各組合せの移動時間及び移動距離（以下では「移動情報」と呼ぶことがある）を算出することになる。最適化条件データ８４は、走行経路立案プログラム（図２の符号３６参照）に従って走行経路を立案する際に利用される最適化条件を記憶している。この最適化条件データ８４は、サーバＰＣ５０に送られるものではなく、クライアントＰＣ３０内のみで利用される。
依頼データファイル９０は、マトリクスデータ９２と最適化条件データ９４を有する。マトリクスデータ９２は、上記のマトリクスデータ８２と同じものである。即ち、マトリクスデータ９２は、マトリクスデータ８２と同じ順序で出発位置及び到着位置が並んでいる。このマトリクスデータ９２もサーバＰＣ５０に送られる。最適化条件データ９４は、上記の最適化条件データ８４と異なる最適化条件を含んでいる。
【００２５】
図２に示される記憶部４０は、ＣＰＵ３２が様々な処理を実行する過程で生成される情報を記憶することができる。操作部４２は、キーボードやマウスによって構成される。ユーザは、操作部４２を操作することによって、上記の依頼データ８０，９０（図３参照）を作成することができる。表示部４４は、様々な情報を表示することができる。ネットワークインターフェイス４６は、サーバＰＣ５０に接続されている。クライアントＰＣ３０は、ネットワークインターフェイス４６を介して様々な情報をサーバＰＣ５０と通信することができる。
【００２６】
サーバＰＣ５０は、複数のＣＰＵ５２，５４とハードディスク５６とネットワークインターフェイス６８等を有する。ＣＰＵ５２，５４は、ハードディスク５６に記憶されている各種のプログラムに従って処理を実行する。ＣＰＵ５２，５４は、様々な処理を並行して（同時的に）実行することが可能である。ハードディスク５６は、時間距離計算プログラム記憶部５８とマトリクスデータ記憶部６０と計算結果キャッシュ６２と道路ネットワーク情報記憶部６４とその他の記憶部６６等を有する。
時間距離計算プログラム記憶部５８は、後述する道路ネットワーク情報に基づいて出発位置から到着位置までの移動情報（移動時間及び移動距離）を算出するためのプログラムを記憶している。このプログラムに従ってＣＰＵ５２，５４が処理を実行することによって、マトリクスデータ８２，９２（図３参照）に含まれる複数の組合せのそれぞれについて移動情報が算出される。この点については後で詳しく説明する。マトリクスデータ記憶部６０は、クライアントＰＣ３０から送られてくるマトリクスデータ８２，９２（図３参照）を記憶する。また、マトリクスデータ記憶部６０は、マトリクスデータ８２，９２の各出発位置と各到着位置をランダムに並び替えることによって得られるマトリクスデータを記憶する。この点については後で詳しく説明する。
【００２７】
計算結果キャッシュ６２は、時間距離計算プログラムに従って算出された計算結果を記憶する。図４は、計算結果キャッシュ６２の記憶内容の一例を示す。計算結果キャッシュ６２は、出発位置ＩＤと、到着位置ＩＤと、出発位置から到着位置までの移動距離と、出発位置から到着位置までの移動時間とが対応づけられたテーブル１００を記憶することが可能である。計算結果キャッシュ６２にどのようにしてデータが記憶されるのかについては、後で詳しく説明する。
【００２８】
図２に示される道路ネットワーク情報記憶部６４は、図１に示される各拠点を含む道路ネットワーク情報を記憶している。道路ネットワーク情報記憶部６４は、時間距離計算プログラムに従って出発位置から到着位置までの移動情報を算出する際に利用される。なお、道路ネットワーク情報に基づいて出発位置から到着位置までの移動情報を算出する手法は公知であるために、その詳しい説明は省略する。記憶部６６は、ＣＰＵ５２，５４が様々な処理を実行する過程で生成される情報を記憶することができる。ネットワークインターフェイス６８は、クライアントＰＣ３０に接続されている。サーバＰＣ５０は、ネットワークインターフェイス６８を介して様々な情報をクライアントＰＣ３０と通信することができる。
【００２９】
続いて、クライアントＰＣ３０の動作について説明する。ユーザは、操作部４２を操作することによって、依頼データファイル８０，９０（図３参照）を作成することができる。ユーザは、操作部４２を操作することによって、走行経路立案プログラムを起動することができる。この場合、各依頼データファイル８０，９０に含まれるマトリクスデータ８２，９２がサーバＰＣ５０に送られる。これにより、マトリクスデータ８２，９２に含まれる出発位置と到着位置の各組合せの移動情報がサーバＰＣ５０によって計算されることになる。クライアントＰＣ３０は、サーバＰＣ５０から各組合せの移動情報を取得する。次いで、クライアントＰＣ３０は、各組合せの移動情報と依頼データファイル８０の最適化条件データ８４（図３参照）とに従って走行経路を算出（立案）する。なお、各組合せの移動情報と最適化条件とに従って走行経路を算出する手法は公知であるために、その詳しい説明は省略する。また、クライアントＰＣ３０は、各組合せの移動情報と依頼データファイル９０の最適化条件データ９４（図３参照）とに従って走行経路を算出（立案）する。これにより、２種類の走行経路が立案されることになる。ユーザは、立案された各走行経路を参考にしながら走行経路を決定することができる。
【００３０】
次いで、サーバＰＣ５０の動作について説明する。図５は、サーバＰＣ５０のＣＰＵ５２，５４が実行する処理のフローチャートを示す。クライアントＰＣ３０から出力されたマトリクスデータ８２，９２は、サーバＰＣ５０に入力される（Ｓ１０）。ＣＰＵ５２，５４は、Ｓ１０で入力されたマトリクスデータ８２，９２をマトリクスデータ記憶部６０に記憶する（Ｓ１２）。次いで、ＣＰＵ５２，５４は、マトリクスデータ８２，９２の並び替え処理を実行し、後述する第１マトリクスデータ及び第２マトリクスデータを作成する（Ｓ１４）。
【００３１】
図６は、並び替え処理のフローチャートを示す。なお、本実施例では、マトリクスデータ８２，９２が同じデータである。このために、１つのマトリクスデータ８２から第１マトリクスデータ及び第２マトリクスデータを作成する例を説明する。しかしながら、マトリクスデータ８２から第１マトリクスデータを作成し、マトリクスデータ９２から第２マトリクスデータを作成してもよい。この場合、ＣＰＵ５２が第１マトリクスデータを作成し、それと並行してＣＰＵ５４が第２マトリクスデータを作成してもよい。
ＣＰＵ５２，５４は、マトリクスデータ８２に含まれる出発位置数を特定する。本実施例の場合、１２が特定される。次いで、ＣＰＵ５２，５４は、１２より小さい正の整数であって１２と公約数を持たない各値を算出する（Ｓ３０）。本実施例の場合、この条件を満たすのは５，７，１１の３つの値である。ＣＰＵ５２，５４は、Ｓ３０で算出された各値（５，７，１１）及び１の４つの値（１，５，７，１１）の中から１つの値をランダムに選択する（Ｓ３２）。続いて、ＣＰＵ５２，５４は、Ｓ３２で選択された値を差分値としてマトリクスデータ８２の各出発位置を並び替える（Ｓ３４）。この処理の内容を次に詳しく説明する。
【００３２】
図８を参照しながら、Ｓ３４の内容を詳しく説明する。図８は、マトリクスデータ８２を示す。１２の出発位置（ＩＤ「００１」から「０１２」）がＸ方向に並んでおり、１２の到着位置（ＩＤ「００１」から「０１２」）がＹ方向に並んでいる。
例えば、Ｓ３２で選択された差分値が１である場合、左から１番目の列にＩＤ「００１」が配置される。さらに、左から２番目の列にＩＤ「００２」が配置され、左から３番目の列にＩＤ「００３」が配置される。即ち、差分値が１である場合、各ＩＤが１列ずつ右方にずれるようにして順に配置される。同様に、他のＩＤ「００４」から「０１２」も順に配置される。即ち、Ｓ３２で選択された差分値が１である場合、各出発位置を並び替える必要がない。なお、本実施例では、左から１番目の列にＩＤ「００１」を配置しているが、どの列にＩＤ「００１」が配置されてもよい。
また、例えば、Ｓ３２で選択された差分値が５である場合、左から５番目の列にＩＤ「００１」が配置される。さらに、左から１０番目の列にＩＤ「００２」が配置され、左から３番目の列にＩＤ「００３」が配置される。即ち、差分値が５である場合、各ＩＤが５列ずつ右方にずれるようにして順に配置される。同様に、他のＩＤ「００４」から「０１２」も順に配置される。なお、本実施例では、左から５番目の列にＩＤ「００１」を配置しているが、どの列にＩＤ「００１」が配置されてもよい。
また、Ｓ３２で選択された差分値が７や１１である場合も、上記と同様の規則に従って各ＩＤが配置される。即ち、差分値が７である場合、左から７番目の列にＩＤ「００１」が配置され、各ＩＤが７列ずつ右方にずれるようにして順に配置される。また、差分値が１１である場合、左から１１番目の列にＩＤ「００１」が配置され、各ＩＤが１１列ずつ右方にずれるようにして順に配置される。なお、Ｓ３２で作成された出発位置の並び順は、記憶部６６（図２参照）に一時的に記憶される。
【００３３】
続いて、ＣＰＵ５２，５４は、上記のＳ３２と同じ処理を実行する（Ｓ３６）。即ち、ＣＰＵ５２，５４は、４つの値（１，５，７，１１）の中から１つの値をランダムに選択する。なお、本実施例では、マトリクスデータ８２に含まれる出発位置数と到着位置数が同じである。このために、到着位置を並び替える際にＳ３０に相当する処理を実行しない。しかしながら、出発位置数と到着位置数が異なる場合には、到着位置を並び替える際にもＳ３０に相当する処理を実行してもよい。例えば、到着位置数が２０である場合、２０より小さい正の整数であって２０と公約数を持たない各値（３，７，９，１３，１７）が算出される。この場合、Ｓ３６では、１，３，７，９，１３，１７の６つの値の中から１つの値がランダムに選択される。
【００３４】
次いで、ＣＰＵ５２，５４は、選択された値を差分値としてマトリクスデータ８２の各到着位置を並び替える（Ｓ３８）。この処理は、上記したＳ３４と同様の手法を利用して実行される。例えば、差分値が１である場合、上から１番目の行にＩＤ「００１」が配置され、各ＩＤが１行ずつ下方にずれるようにして順に配置される。また、例えば、差分値が５である場合、上から５番目の行にＩＤ「００１」が配置され、各ＩＤが５行ずつ下方にずれるようにして順に配置される。なお、ＩＤ「００１」が配置される行は、特に限定されない。ＩＤ「００１」は、どの行に配置されてもよい。Ｓ３８で作成された到着位置の並び順は、記憶部６６（図２参照）に一時的に記憶される。ＣＰＵ５２，５４は、Ｓ３４で作成された出発位置の並び順とＳ３８で作成された到着位置の並び順とに基づいて第１マトリクスデータを作成し、その第１マトリクスデータをマトリクスデータ記憶部６０（図２参照）に記憶する（Ｓ４０）。なお、図９には、差分値１が採用された出発位置の並び順と差分値５が採用された到着位置の並び順とを有する第１マトリクスデータ１１０が例示されている。
【００３５】
ＣＰＵ５２，５４は、上記のＳ３２からＳ３８と同様の処理を再び実行する（Ｓ４２）。これによって得られた出発位置の並び順と到着位置の並び順とに基づいて第２マトリクスデータを作成することができる。ＣＰＵ５２，５４は、第２マトリクスデータをマトリクスデータ記憶部６０（図２参照）に記憶する（Ｓ４４）。なお、図９には、差分値７が採用された出発位置の並び順と差分値１１が採用された到着位置の並び順とを有する第２マトリクスデータ１２０が例示されている。
【００３６】
本実施例では、マトリクスデータ８２とマトリクスデータ９２（図３参照）が同じものであるために、１つのマトリクスデータ８２から第１マトリクスデータ及び第２マトリクスデータを作成している。しかしながら、マトリクスデータ８２から第１マトリクスデータを作成し、マトリクスデータ９２から第２マトリクスデータを作成してもよい。この場合、マトリクスデータ８２から第１マトリクスデータを作成するためにＳ３０からＳ４０の処理を実行し、マトリクスデータ９２から第２マトリクスデータを作成するためにＳ３０からＳ４０の処理を実行してもよい。この手法は、マトリクスデータ８２とマトリクスデータ９２が異なるパターンに配列されている場合（例えば出発位置や到着位置の並び順が異なる場合）に有効である。
【００３７】
図５に示されるように、ＣＰＵ５２，５４は、第１マトリクスデータ１１０と第２マトリクスデータ１２０を作成すると、移動情報算出処理を実行する（Ｓ１６）。図７は、移動情報算出処理のフローチャートを示す。図７では、２つのフローチャートが並列的に示されている。左側のフローチャートは、一方のＣＰＵ５２によって実行される。右側のフローチャートは、他方のＣＰＵ５４によって実行される。左側のフローチャートと右側のフローチャートは、２つのＣＰＵ５２，５４によって並行して（同時的に）実行される。
【００３８】
まず、図７の左側のフローチャートの内容について説明する。ＣＰＵ５２は、第１マトリクスデータ１１０から出発位置と到着位置の１つの組合せを特定する（Ｓ５０）。本実施例では、図９の第１マトリクスデータ１１０に示されるように、上から１番目かつ左から１番目に存在する組合せ（出発位置ＩＤ「００１」と到着位置ＩＤ「００５」の組合せ）が特定される。次いで、ＣＰＵ５２は、計算結果キャッシュ６２（図２参照）を検索し（Ｓ５２）、Ｓ５０で特定された組合せの移動情報が計算結果キャッシュ６２に記憶されているのか否かを判断する（Ｓ５４）。ここでＹＥＳの場合、Ｓ５６とＳ５８をスキップしてＳ６０に進む。一方において、Ｓ５４でＮＯの場合、ＣＰＵ５２は、Ｓ５０で特定された組合せの移動情報を算出する（Ｓ５６）。上述したように、出発位置ＩＤや到着位置ＩＤには、そのＩＤを持つ拠点の緯度及び経度が対応づけられている。ＣＰＵ５２は、出発位置ＩＤを持つ拠点の緯度及び経度と、到着位置ＩＤを持つ拠点の緯度及び経度と、道路ネットワーク情報記憶部６４（図２参照）に記憶されている道路ネットワーク情報とに基づいて、その出発位置からその到着位置までの移動情報を算出する。道路ネットワーク情報を利用して二点間の移動情報を算出する手法は公知であるために、その詳しい内容の説明は省略する。ＣＰＵ５２は、算出された移動情報を計算結果キャッシュ６２に記憶する（Ｓ５８）。
【００３９】
ＣＰＵ５２は、第１マトリクスデータ１１０に含まれる全ての組合せについてＳ５０からＳ５８の処理を実行したのか否かを判断する（Ｓ６０）。ここでＮＯの場合、ＣＰＵ５２は、Ｓ５０に戻って次の組合せを特定する。本実施例では、図９の第１マトリクスデータ１１０の破線の矢印で示すように、上から１番目かつ左から１番目に存在する組合せから右に順に処理が実行される。従って、上から１番目かつ左から１番目に存在する組合せについてＳ５８の処理が終了した場合、次のＳ５０の処理では、上から１番目かつ左から２番目に存在する組合せ（出発位置ＩＤ「００２」と到着位置ＩＤ「００５」の組合せ）が特定される。また、上から１番目の行に存在する全ての組合せについて処理が終了すると、次の行（上から２番目の行）について処理が実行される。即ち、上から１番目かつ左から１２番目に存在する組合せ（出発位置ＩＤ「０１２」と到着位置ＩＤ「００５」の組合せ）についてＳ５８の処理が終了した場合、次のＳ５０の処理では、上から２番目かつ左から１番目に存在する組合せ（出発位置ＩＤ「００１」と到着位置ＩＤ「０１０」の組合せ）が特定される。このような規則に従って各組合せが順に特定され、各組合せについてＳ５０からＳ５８の処理が実行される。
【００４０】
第１マトリクスデータ１１０に含まれる全ての組合せについてＳ５０からＳ５８の処理を実行された場合、ＣＰＵ５２は、Ｓ６０でＹＥＳと判断する。これにより、ＣＰＵ５２によって実行される移動情報算出処理が終了する。なお、出発位置ＩＤと到着位置ＩＤが同じである各組合せ（図９の第１マトリクスデータ１１０においてハッチングで示した各組合せ）については、ＣＰＵ５２は、Ｓ５０からＳ５８の処理を実行する必要がない。移動距離と移動時間がともにゼロになるという結果がわかっているからである。従って、ＣＰＵ５２は、Ｓ５０で組合せを特定する際に、出発位置ＩＤと到着位置ＩＤが同じである各組合せをスキップして次の組合せを特定してもよい。
【００４１】
次いで、図７の右側のフローチャートの内容について説明する。ＣＰＵ５４は、第２マトリクスデータ１２０から出発位置と到着位置の１つの組合せを特定する（Ｓ７０）。本実施例では、上述したＳ５０の場合と同様に、第２マトリクスデータ１１０における上から１番目かつ左から１番目に存在する組合せ（出発位置ＩＤ「００７」と到着位置ＩＤ「０１１」の組合せ）が特定される。次いで、ＣＰＵ５４は、計算結果キャッシュ６２（図２参照）を検索し（Ｓ７２）、Ｓ７０で特定された組合せの移動情報が計算結果キャッシュ６２に記憶されているのか否かを判断する（Ｓ７４）。ここでＮＯの場合、ＣＰＵ５４は、Ｓ７０で特定された組合せの移動情報を算出し（Ｓ７６）、算出された移動情報を計算結果キャッシュ６２に記憶する（Ｓ７８）。
【００４２】
ＣＰＵ５４は、第２マトリクスデータ１２０に含まれる全ての組合せについてＳ７０からＳ７８の処理を実行していない場合（Ｓ８０でＮＯの場合）、Ｓ７０に戻って次の組合せを特定する。本実施例では、第２マトリクスデータ１２０の破線の矢印で示すように、上から１番目かつ左から１番目に存在する組合せから右に順に処理が実行される。また、上から１番目の行に存在する全ての組合せについて処理が終了すると、次の行（上から２番目の行）について処理が実行される。即ち、第１マトリクスデータ１１０の場合と同様の規則に従って各組合せが順に特定され、各組合せについてＳ７０からＳ７８の処理が実行される。
【００４３】
第２マトリクスデータ１２０に含まれる全ての組合せについてＳ７０からＳ７８の処理を実行された場合、ＣＰＵ５４は、Ｓ８０でＹＥＳと判断する。これにより、ＣＰＵ５４によって実行される移動情報算出処理が終了する。なお、第１マトリクスデータ１１０の場合と同様に、ＣＰＵ５４は、Ｓ７０で組合せを特定する際に、出発位置ＩＤと到着位置ＩＤが同じである各組合せ（第２マトリクスデータ１２０においてハッチングで示した各組合せ）をスキップして次の組合せを特定してもよい。
【００４４】
図５に示されるように、ＣＰＵ５２，５４は、移動情報算出処理を実行すると、計算結果キャッシュ６２に記憶されている計算結果（各組合せの移動情報）をクライアントＰＣ３０に出力する（Ｓ１８）。これにより、クライアントＰＣ３０は、各組合せの移動情報と依頼データファイル８０の最適化条件データ８４（図３参照）とに従って走行経路を立案することができる。また、クライアントＰＣ３０は、各組合せの移動情報と依頼データファイル９０の最適化条件データ９４（図３参照）とに従って走行経路を立案することができる。
【００４５】
第１実施例の技術では、マトリクスデータ８２をランダムに並び替えることによって第１マトリクスデータ１１０が作成され、マトリクスデータ８２を再びランダムに並び替えることによって第２マトリクスデータ１２０が作成される。ＣＰＵ５２は、第１マトリクスデータ１１０の配置順序に従って各組合せについて移動情報算出処理を実行する。また、ＣＰＵ５４は、第２マトリクスデータ１２０の配置順序に従って各組合せについて移動情報算出処理を実行する。第１マトリクスデータ１１０と第２マトリクスデータ１２０はランダムに作成されるために、ＣＰＵ５２が実行する処理順序とＣＰＵ５４が実行する処理順序が異なるパターンになる可能性が高い。２つの処理順序が異なる場合、ＣＰＵ５２の移動情報算出処理で先に移動情報が算出される組合せが存在する一方で、ＣＰＵ５４の移動情報算出処理で先に移動情報が算出される組合せが存在することになる。例えば、図９の例の場合、出発位置ＩＤ「００１」と到着位置ＩＤ「００５」の組合せ（以下では「第１組合せ」と呼ぶ）の移動情報は、ＣＰＵ５４より先にＣＰＵ５２によって算出される。この場合、図７のＳ７０において第１組合せが特定された段階では、第１組合せの移動情報が計算結果キャッシュ６２に記憶されている。このために、ＣＰＵ５４は、第１組合せの移動情報を算出する必要がない。また、例えば、出発位置ＩＤ「００７」と到着位置ＩＤ「０１１」の組合せ（以下では「第２組合せ」と呼ぶ）の移動情報は、ＣＰＵ５２より先にＣＰＵ５４によって算出される。この場合、図７のＳ５０において第２組合せが特定された段階では、第２組合せの移動情報が計算結果キャッシュ６２に記憶されている。このために、ＣＰＵ５２は、第２組合せの移動情報を算出する必要がない。本実施例によると、２つのＣＰＵ５２，５４が共同して（手分けして）各組合せの移動情報を算出することができる。この結果、各組合せの移動情報を短時間で算出することができる。
【００４６】
（第２実施例）
続いて、本発明の第２実施例を説明する。本実施例では、並び替え処理の内容が第１実施例と異なる。図１０は、本実施例の並び替え処理のフローチャートを示す。なお、本実施例でも、１つのマトリクスデータ８２から第１マトリクスデータ及び第２マトリクスデータが作成される場合を例として、並び替え処理の内容を説明する。図１０のＳ１００及び１０２は、図６のＳ３０及びＳ３２と同様である。このために、Ｓ１００及び１０２の説明を省略する。ＣＰＵ５２，５４は、Ｓ１０２で選択された値を記憶部６６に記憶する（Ｓ１０４）。ここで記憶された値は、後工程で利用される。次いで、ＣＰＵ５２，５４は、Ｓ１０２で選択された値を差分値としてマトリクスデータ８２の各出発位置を並び替えるとともに、Ｓ１０２で選択された値を差分値としてマトリクスデータ８２の各到着位置を並び替える（Ｓ１０６）。これにより、第１マトリクスデータが作成されることになる。本実施例では、出発位置を並び替えるための差分値と到着位置を並び替えるための差分値とが同じである。この点が第１実施例と異なる。ＣＰＵ５２，５４が第１マトリクスデータを記憶する点（Ｓ１０８）は、第１実施例と同様である（図６のＳ４０参照）。
【００４７】
続いて、ＣＰＵ５２，５４は、１，５，７，１１の４つの値からＳ１０４で記憶部６６に記憶された値（第１マトリクスデータを作成するための差分値）を除外する。例えば、Ｓ１０４で記憶部６６に記憶された値が１である場合、ＣＰＵ５２，５４は、５，７，１１の３つの値から１つの値をランダムに選択する（Ｓ１１０）。次いで、ＣＰＵ５２，５４は、Ｓ１１０で選択された値を差分値としてマトリクスデータ８２の各出発位置を並び替えるとともに、Ｓ１０２で選択された値を差分値としてマトリクスデータ８２の各到着位置を並び替える（Ｓ１１２）。これにより、第２マトリクスデータが作成されることになる。ＣＰＵ５２，５４が第２マトリクスデータを記憶する点（Ｓ１１４）は、第１実施例と同様である（図６のＳ４４参照）。
【００４８】
本実施例では、第１マトリクスデータを作成するための差分値と第２マトリクスデータを作成するための差分値とが一致することがない。このために、第１マトリクスデータと第２マトリクスデータが異なるパターンになることが保証される。
【００４９】
（第２実施例の変形例）
第２実施例では、出発位置を並び替えるための差分値と到着位置を並び替えるための差分値とが同じである。しかしながら、第１実施例の場合と同様に、出発位置を並び替えるための差分値と到着位置を並び替えるための差分値のそれぞれをランダムに選択するようにしてもよい。この場合、第１マトリクスデータを作成する際には、出発位置を並び替えるための差分値Ｓ１と到着位置を並び替えるための差分値Ｓ２とのそれぞれを記憶部６６に記憶させることが好ましい。第２マトリクスデータを作成する際には、差分値Ｓ１を除外した各値の中から出発位置を並び替えるための差分値を選択し、差分値Ｓ２を除外した各値の中から到着位置を並び替えるための差分値を選択することが好ましい。このようにしても、第１マトリクスデータと第２マトリクスデータが異なるパターンになることが保証される。
【００５０】
（第３実施例）
続いて、本発明の第３実施例を説明する。本実施例では、並び替え処理の内容が第１実施例や第２実施例と異なる。図１１は、本実施例の並び替え処理のフローチャートを示す。第１実施例では、図６のＳ３０に示されるように、マトリクスデータ８２に含まれる出発位置数１２（到着位置数も同じである）より小さくて１２と公約数を持たない各値が算出される。これに対し、本実施例では、マトリクスデータ８２に含まれる出発位置数１２（到着位置数も同じである）より小さくて１２の約数ではない素数（５，７，１１）が算出される（Ｓ１２０）。出発位置数が１２である場合は、第１実施例の場合も第３実施例の場合も結果（５，７，１１）が同じになる。しかしながら、出発位置数が変わると、結果が異なってくる。なお、図１１のＳ１２２からＳ１３４は、図６のＳ３２からＳ４４と同様である。このために、Ｓ１２２からＳ１３４の説明を省略する。
【００５１】
本実施例によっても、並び替え処理を実行して第１マトリクスデータ及び第２マトリクスデータを作成することができる。
【００５２】
以上、本発明の具体例を詳細に説明したが、これらは例示に過ぎず、特許請求の範囲を限定するものではない。特許請求の範囲に記載の技術には、以上に例示した具体例を様々に変形、変更したものが含まれる。上記の実施例の変形例を以下に列挙する。
【００５３】
（１）上記の実施例では、マトリクスデータ８２，９２（図３参照）の各拠点（各ＩＤ）に緯度及び経度が対応づけられている。サーバＰＣ５０は、クライアントＰＣ３０からマトリクスデータ８２，９２を取得することによって各拠点の緯度及び経度を知ることができる。しかしながら、サーバＰＣ５０は、各拠点のＩＤと緯度及び経度が対応づけられているデータを予め記憶していてもよい。この場合、クライアントＰＣ３０で作成されるマトリクスデータ８２，９２は、緯度及び経度を含む必要はなく、各拠点のＩＤのみを含んでいてもよい。
【００５４】
（２）上記の実施例では、サーバＰＣ５０が２つのＣＰＵ５２，５４を有する。しかしながら、サーバＰＣ５０は、３つ以上のＣＰＵを有していてもよい。この場合、マトリクスデータ８２をランダムに並び替えることによって、上記の第１及び第２マトリクスデータに加えて第３マトリクスデータを作成してもよい。第１、第２、及び第３マトリクスデータのそれぞれについて各ＣＰＵが移動情報算出処理を並行して実行してもよい。
【００５５】
また、本明細書または図面に説明した技術要素は、単独であるいは各種の組合せによって技術的有用性を発揮するものであり、出願時請求項記載の組合せに限定されるものではない。また、本明細書または図面に例示した技術は複数目的を同時に達成し得るものであり、そのうちの一つの目的を達成すること自体で技術的有用性を持つものである。
【図面の簡単な説明】
【００５６】
【図１】各地に存在している複数の拠点の一例を示す。
【図２】走行経路立案システムの構成を示す。
【図３】依頼データファイル記憶部の記憶内容の一例を示す。
【図４】計算結果キャッシュの記憶内容の一例を示す。
【図５】サーバＰＣが実行するメイン処理のフローチャートを示す。
【図６】サーバＰＣが実行する並び替え処理のフローチャートを示す。
【図７】サーバＰＣが実行する移動情報算出処理のフローチャートを示す。
【図８】マトリクスデータの複数の出発位置を並び替える様子を説明するための図を示す。
【図９】第１及び第２マトリクスデータの一例を示す。
【図１０】第２実施例の並び替え処理のフローチャートを示す。
【図１１】第３実施例の並び替え処理のフローチャートを示す。
【符号の説明】
【００５７】
１０：仕入先
１２：中継地
１４：工場
２０：走行経路立案システム
３０：クライアントＰＣ
３２：ＣＰＵ
３６：走行経路立案プログラム記憶部
３８：依頼データファイル記憶部
５０：クライアントＰＣ
５２，５４：ＣＰＵ
５８：時間距離計算プログラム記憶部
６０：マトリクスデータ記憶部
６２：計算結果キャッシュ
６４：道路ネットワーク情報記憶部
８２，９２：マトリクスデータ
１１０：第１マトリクスデータ
１２０：第２マトリクスデータ
【図１】
2008287304.tif 000003
【図２】
2008287304.tif 000004
【図３】
2008287304.tif 000005
【図４】
2008287304.tif 000006
【図５】
2008287304.tif 000007
【図６】
2008287304.tif 000008
【図７】
2008287304.tif 000009
【図８】
2008287304.tif 000010
【図９】
2008287304.tif 000011
【図１０】
2008287304.tif 000012
【図１１】
2008287304.tif 000013