(57)【要約】  本発明は、経済的及び効率的な方法で、時間及び距離に関する情報を計算及び記憶するためのシステム、方法及びコンピュータプログラム製品に関する。この時間及び距離に関する情報を使用して、複数の位置からの物品を時間的及び効率的な方法で搬送及び検索するためのトラバーサブル・ネットワークを開発することができる。
2008543695.tif 000002
【特許請求の範囲】
【請求項１】
少なくともメモリ、プロセッサ及びディスプレイ装置を有するコンピュータ装置を制御し、２つ以上の配送位置の間の最短の経路情報を計算及び記憶し、記憶されたコンピュータが読取り可能なプログラムコード部分を有するコンピュータが読取り可能な記憶媒体を備えるコンピュータプログラム製品であって、前記コンピュータが読取り可能なプログラムコード部分は、
前記プロセッサ上で実行可能なグリッド分割モジュールを備える第１の実行可能な部分と、
前記プロセッサ上で実行可能な初期フレンド選択モジュールを備える第２の実行可能な部分と、
前記プロセッサ上で実行可能なスーパーマトリックス作成モジュールを備える第３の実行可能な部分と、
を備え、
前記グリッド分割モジュールが、全体的な配送領域を規定された数のグリッドの集合体に分割し、前記２つ以上の配送位置が前記規定された数の少なくとも１つの中に位置付けられ、
前記初期フレンド選択モジュールでは、前記規定された数のグリッドの１つが選択され、前記選択されたグリッド内の各特定の配送位置に対してフレンドリストが作成され、前記フレンドリストは同じ経路上に前記特定の配送位置として現れる可能性が最も高い配送位置の組を含み、
前記スーパーマトリックス作成モジュールが、選択されたグリッドに対するノード及びアークから構成するトラバーサブル・ネットワークを作り、前記選択されたグリッド内の各配送位置からトラバーサブル・ネットワーク内の全てのノードまでの時間及び／又は距離のデータを計算し、前記選択されたグリッド内の各特定の配送位置から各配送位置までの時間及び／又は距離のデータを含むスーパーマトリックスをその位置のフレンドリスト及び任意の範囲内の集積所の中に格納する、コンピュータプログラム製品。
【請求項２】
前記プロセッサ上で実行可能な地理的バランシング・モジュールを備える第４の実行可能な部分をさらに備え、
前記地理的バランシング・モジュールが、各配送位置の前記フレンドリストのバランスを保つために、各配送位置を選択し、前記選択された配送位置の周りの配送領域を４個のクワドラントに分割して前記選択された配送位置が前記４個のクワドラントに対する原点を形成し、前記選択された配送位置のフレンドリストの中の規定された数の配送位置が囲まれたほぼ円形の区域の中に位置付けられるまで、前記原点の周りに前記囲まれたほぼ円形の区域を形成するように、前記４つのクワドラントのそれぞれの中でアークを前記原点から等距離に拡大し、各クワドラントの中の前記選択された配送位置のフレンドリストの中の配送位置の数を判定し、前記選択された配送位置のフレンドリストの中の配送位置の数が任意のクワドラントにおいて（（前記選択された配送位置のフレンドリストの中の配送位置の規定された数）／４）よりも小さい場合は、そのようなクワドラントを不十分なクワドラントとしてマークし、前記選択された配送位置のフレンドリストの中で少なくとも（（前記選択された配送位置のフレンドリストの中の配送位置の規定された数）／４）の配送位置がアークとクワドラントを形成する軸とによって囲まれた区域の中に含まれるまで、又は原点からの最大距離が実現されるまで、任意の不十分なクワドラント内のアークを拡大する、
ことを特徴とする請求項１に記載のコンピュータプログラム製品。
【請求項３】
前記（（前記選択された配送位置のフレンドリストの中の配送位置の規定された数）／４）が６２５であり、前記原点からの最大距離が２５０マイルである、ことを特徴とする請求項２に記載のコンピュータプログラム。
【請求項４】
２つ以上の配送位置に対して物品を配送するシステムであって、
前記２つ以上の配送位置のそれぞれにおいて、集積所で得られる配送用の１つ以上の物品を輸送できる運搬手段と、
少なくともメモリ、プロセッサ及びディスプレイ装置を有するコンピュータ装置を制御し、前記２つ以上の配送位置の間の最短の経路情報を計算及び記憶し、記憶されたコンピュータが読取り可能なプログラムコード部分を有するコンピュータが読取り可能な記憶媒体を備えるコンピュータプログラム製品と、
を備え、前記コンピュータが読取り可能なプログラムコード部分が、
前記プロセッサ上で実行可能なグリッド分割モジュールを備える第１の実行可能な部分と、
前記プロセッサ上で実行可能な初期フレンド選択モジュールを備える第２の実行可能な部分と、
前記プロセッサ上で実行可能なスーパーマトリックス作成モジュールを備える第３の実行可能な部分と、
を備え、
前記グリッド分割モジュールが、全体的な配送領域を規定された数のグリッドの集合体に分割し、前記２つ以上の配送位置が前記規定された数のグリッドの少なくとも１つの中に位置付けられ、
前記初期フレンド選択モジュールでは、前記規定された数のグリッドの１つが選択され、前記選択されたグリッド内の各特定の配送位置に対してフレンドリストが作成され、前記フレンドリストは同じ経路上に前記特定の配送位置として現れる可能性が最も高い配送位置の組を含み、
前記スーパーマトリックス作成モジュールが、選択されたグリッドに対するノード及びアークから構成するトラバーサブル・ネットワークを作り、前記選択されたグリッド内の各配送位置からトラバーサブル・ネットワーク内の全てのノードまでの時間及び／又は距離のデータを計算し、前記選択されたグリッド内の各特定の配送位置から各配送位置までの時間及び／又は距離のデータを含むスーパーマトリックスをその位置のフレンドリスト及び任意の範囲内の集積所の中に格納し、
前記運搬手段が前記最短の経路情報を利用して、前記２つ以上の配送位置のそれぞれにおいて前記配送用の前記１つ以上の物品を得て、前記２つ以上の配送位置のそれぞれにおいて前記配送用の１つ以上の物品を各配送位置に輸送するための経路を決定する、システム。
【請求項５】
前記プロセッサ上で実行可能な地理的バランシング・モジュールを備える第４の実行可能な部分をさらに備え、
前記地理的バランシング・モジュールが、各配送位置の前記フレンドリストのバランスを保つために、各配送位置を選択し、前記選択された配送位置の周りの配送領域を４個のクワドラントに分割して前記選択された配送位置が前記４個のクワドラントに対する原点を形成し、前記選択された配送位置のフレンドリストの中の規定された数の配送位置が囲まれたほぼ円形の区域の中に位置付けられるまで、前記原点の周りに前記囲まれたほぼ円形の区域を形成するように、前記４つのクワドラントのそれぞれの中でアークを前記原点から等距離に拡大し、各クワドラントの中の前記選択された配送位置のフレンドリストの中の配送位置の数を判定し、前記選択された配送位置のフレンドリストの中の配送位置の数が任意のクワドラントにおいて（（前記選択された配送位置のフレンドリストの中の配送位置の規定された数）／４）よりも小さい場合は、そのようなクワドラントを不十分なクワドラントとしてマークし、前記選択された配送位置のフレンドリストの中で少なくとも（（前記選択された配送位置のフレンドリストの中の配送位置の規定された数）／４）の配送位置がアークとクワドラントを形成する軸とによって囲まれた区域の中に含まれるまで、又は原点からの最大距離が実現されるまで、任意の不十分なクワドラント内のアークを拡大する、
ことを特徴とする請求項４に記載のシステム。
【請求項６】
前記（（前記選択された配送位置のフレンドリストの中の配送位置の規定された数）／４）が６２５であり、前記原点からの最大距離が２５０マイルである、ことを特徴とする請求項５に記載のシステム。
【請求項７】
２つ以上の潜在的な配送位置の間の最短の経路情報を計算及び記憶するためのコンピュータシステムであって、前記コンピュータシステムが、
プロセッサを備え、前記プロセッサが、
（１）配送領域を、それぞれが１つ以上の潜在的な配送位置の第１の組を含む１つ以上の別個の地理上の区域の集合体に分割し、
（２）第１の地理上の区域を選択し、
（３）前記１つ以上の潜在的な配送位置の第１の組のそれぞれに対して、潜在的な配送位置の固有の第２の組を作り、
（４）ノード及びアークの組を備え、前記第１の地理上の区域の中に地理的に位置付けられた少なくとも潜在的な配送位置と、ステップ（３）で作られた潜在的な配送位置の任意の固有の第２の組の中に含まれた全ての潜在的な配送位置とを含む２つ以上のノードの組をさらに備えるトラバーサブル・ネットワークを作り、
（５）前記第１の地理上の区域の中に地理的に位置付けられた潜在的な配送位置のそれぞれから、前記トラバーサブル・ネットワークの中に含まれた全てのノードへの最短の経路情報を計算し、
（６）ルーティング及びスケジューリングシステムが、後の検索用に、特定の最短の経路情報を選択し、前記特定の最短の経路情報を記憶する、ように構成されるシステム。
【請求項８】
前記トラバーサブル・ネットワークが集積所に対応する少なくとも１つのノードを備える、ことを特徴とする請求項７に記載のシステム。
【請求項９】
前記第１の地理上の区域の中に地理的に位置付けられた各潜在的な配送位置に対して、潜在的な配送位置の固有の第２の組を作るステップが、
１つ以上の配送位置の前記第１の組の中の各潜在的な配送位置に対して潜在的な配送位置の前記固有の第２の組のバランスを保つステップをさらに含み、該ステップは、１つ以上の配送位置の前記第１の組の中の各潜在的な配送位置を選択し、前記選択された配送位置の周りの配送領域を４個のクワドラントに分割して前記選択された配送位置が前記４個のクワドラントに対する原点を形成し、前記選択された配送位置に対する潜在的な配送位置の規定された数の第２の組が囲まれたほぼ円形の区域の中に位置付けられるまで、前記原点の周りに前記囲まれたほぼ円形の区域を形成するように、前記４つのクワドラントのそれぞれの中でアークを前記原点から等距離に拡大し、各クワドラントの中の前記選択された配送位置の潜在的な配送位置の第２の組の中の配送位置の数を判定し、前記選択された配送位置の潜在的な配送位置の第２の組の中の配送位置の数が任意のクワドラントにおいて（（前記選択された配送位置の潜在的な配送位置の第２の組の中の配送位置の規定された数）／４）よりも小さい場合は、そのようなクワドラントを不十分なクワドラントとしてマークし、前記選択された配送位置の潜在的な配送位置の第２の組の中で少なくとも（（前記選択された配送位置の潜在的な配送位置の第２の組の中の配送位置の規定された数）／４）の配送位置がアークとクワドラントを形成する軸とによって囲まれた区域の中に含まれるまで、又は原点からの最大距離が実現されるまで、任意の不十分なクワドラント内のアークを拡大する、
ことを特徴とする請求項７に記載のシステム。
【請求項１０】
前記（（前記選択された配送位置のフレンドリストの中の配送位置の規定された数）／４）が６２５であり、前記原点からの最大距離が２５０マイルである、ことを特徴とする請求項９に記載のシステム。
【請求項１１】
２つ以上の潜在的な配送位置の間の最短の経路情報を計算及び記憶するためのコンピュータシステムであって、前記コンピュータシステムが、
プロセッサを備え、前記プロセッサが、
（１）地理上の区域の中に地理的に位置付けられた各潜在的な配送位置に対して、潜在的な配送位置の固有の組を作り、
（２）ノード及びアークの組を備え、前記地理上の区域の中に地理的に位置付けられた少なくとも潜在的な配送位置と、ステップ（１）で作られた潜在的な配送位置の固有の組の中に含まれた全ての潜在的な配送位置とを含む２つ以上のノードの組をさらに備える、前記地理上の区域と一意的に関連付けられたトラバーサブル・ネットワークを作り、
（３）地理上の区域の中に地理的に位置付けられた潜在的な配送位置のそれぞれから、トラバーサブル・ネットワークの中に含まれた全てのノードへの最短の経路情報を計算し、
（４）ルーティング及びスケジューリングシステムが、後の検索用に、特定の最短の経路情報を選択し、前記選択された特定の最短の経路情報を記憶する、ように構成されるシステム。
【請求項１２】
前記トラバーサブル・ネットワークは集積所に対応する少なくとも１つのノードを備えることを特徴とする請求項１１に記載のシステム。
【請求項１３】
２つ以上の潜在的な配送位置の間の最短の経路情報を計算及び記憶するための方法であって、
（Ａ）配送領域を、それぞれが１つ以上の潜在的な配送位置の第１の組を含む１つ以上の別個の地理上の区域の集合体に分割するステップと、
（Ｂ）第１の地理上の区域を選択するステップと、
（Ｃ）前記選択された地理上の区域の中に地理的に位置付けられた各配送位置に対して、潜在的な配送位置の対応する固有の第２の組を作るステップと、
（Ｄ）ノード及びアークの組を備え、前記選択された地理上の区域の中に地理的に位置付けられた少なくとも潜在的な配送位置と、前記選択された地理上の区域の中に地理的に位置付けられた潜在的な配送位置に対応する潜在的な配送位置の固有の第２の組の中に含まれた全ての潜在的な配送位置とを含む２つ以上のノードの組をさらに備えるトラバーサブル・ネットワークを作るステップと、
（Ｅ）前記選択された地理上の区域の中に地理的に位置付けられた配送位置から、前記トラバーサブル・ネットワークの中に含まれた全てのノードへの最短の経路情報を計算するステップと、
（Ｆ）ルーティング及びスケジューリングシステムが、後の検索用に、特定の最短の経路情報を選択し、前記特定の最短の経路情報を記憶するステップと、
（Ｇ）前記選択された地理上の区域の中に地理的に位置付けられた各潜在的な配送位置に対して、ステップ（Ｄ）からステップ（Ｆ）を繰り返すステップと、
（Ｈ）ステップ（Ａ）で作られた全ての地理上の区域に対して、ステップ（Ｂ）からステップ（Ｇ）を繰り返すステップと、
を含む方法。
【請求項１４】
前記トラバーサブル・ネットワークを作るステップが、集積所に対応する少なくとも１つのノードを含むトラバーサブル・ネットワークを作るステップを含む、ことを特徴とする請求項１３に記載の方法。
【請求項１５】
前記第１の地理上の区域の中に地理的に位置付けられた各潜在的な配送位置に対して、潜在的な配送位置の対応する固有の第２の組を作るステップが、前記第１の地理上の区域の中に地理的に位置付けられた各潜在的な配送位置に対して潜在的な配送位置の前記固有の第２の組のバランスを保つステップをさらに含み、該ステップは、１つ以上の配送位置の前記第１の組の中の各潜在的な配送位置を選択し、前記選択された配送位置の周りの配送領域を４個のクワドラントに分割して前記選択された配送位置が前記４個のクワドラントに対する原点を形成し、前記選択された配送位置に対する潜在的な配送位置の規定された数の第２の組が囲まれたほぼ円形の区域の中に位置付けられるまで、前記原点の周りに前記囲まれたほぼ円形の区域を形成するように、前記４つのクワドラントのそれぞれの中でアークを前記原点から等距離に拡大し、各クワドラントの中の前記選択された配送位置の潜在的な配送位置の第２の組の中の配送位置の数を判定し、前記選択された配送位置の潜在的な配送位置の第２の組の中の配送位置の数が任意のクワドラントにおいて（（前記選択された配送位置の潜在的な配送位置の第２の組の中の配送位置の規定された数）／４）よりも小さい場合は、そのようなクワドラントを不十分なクワドラントとしてマークし、前記選択された配送位置の潜在的な配送位置の第２の組の中で少なくとも（（前記選択された配送位置の潜在的な配送位置の第２の組の中の配送位置の規定された数）／４）の配送位置がアークとクワドラントを形成する軸とによって囲まれた区域の中に含まれるまで、又は原点からの最大距離が実現されるまで、任意の不十分なクワドラント内のアークを拡大する、ことを特徴とする請求項１３に記載の方法。
【請求項１６】
前記（（前記選択された配送位置のフレンドリストの中の配送位置の規定された数）／４）が６２５であり、前記原点からの最大距離が２５０マイルである、ことを特徴とする請求項１５に記載の方法。
【発明の詳細な説明】
【背景技術】
【０００１】
多数の配送位置の間に運搬手段のルーティングを行う場合、現在のルーティング及びスケジューリング・システムは、経路を作るために、ルーティング及びスケジューリング用アルゴリズムと併せて、記憶された時間及び距離のデータを利用することが多い。配送区域内の各位置の間の最短の道筋を計算することは、配送領域が拡大するにつれて仕事が非常に難しくなるため、高価で時間がかかる工程になることが多い。実際に、多数の配送位置の間又は拡大された領域にわたって最短の道筋の計算を行うことにより、コンピュータの処理能力及びメモリ能力を超えることが多々ある。そのように計算を実行する能力を有するコンピュータにとって、この工程はなおも時間がかかる処理を必要とする。このため、時間と距離に関するデータをより経済的で効率的な様式で計算及び記憶する改良されたロジスティック・システムが必要とされる。
【発明の開示】
【０００２】
本発明の実施形態は、時間及び距離に関する情報を経済的かつ効率的な方法で計算及び記憶するためのシステム、方法及びコンピュータプログラム製品を提供する。
【０００３】
本発明の１つの態様は、少なくともメモリ、プロセッサ及びディスプレイ装置を有するコンピュータ装置を制御するためのコンピュータプログラム製品である。このコンピュータプログラム製品は、２つ以上の配送位置の間の最短の経路情報を計算及び記憶するためのものであり、またコンピュータが読取り可能なプログラムコード部分を記憶するコンピュータが読取り可能な記憶媒体を備えている。コンピュータが読取り可能なプログラムコード部分は、全体的な配送領域を規定された数のグリッドの集合体に分割するグリッド分割モジュール（grid partitioning module）を具備している。例えば、グリッド分割モジュールは、配送領域を４の倍数である多数のグリッドに分割する４倍グリッド分割モジュールとすることができる。２つ以上の配送位置が、少なくとも１つの確定した数のグリッドの中に配置される。別のプログラムコード部分は、確定した数のグリッドの１つを選択する初期フレンド選択モジュール（initial friend selection module）であり、この選択されたグリッド内の各特定の配送位置に対して、特定の配送位置として同じ経路に現れる可能性が最も高い配送位置の組から構成されるフレンドリスト（friends list）が作られる。コンピュータプログラム製品は、スーパーマトリックス生成モジュール（super matrix creation module）も具備する。このモジュールは、選択されたグリッドに対するノード及びアーク(arc)から構成するトラバーサブル・ネットワーク（traversable network）を作り、このトラバーサブル・ネットワークの中の全てのノードに対して選択されたグリッド内の各配送位置から時間／距離のデータを計算し、またその位置のフレンドリスト及び任意の範囲内の集積所（in-range depot）の中の各配送位置に対して選択されたグリッド内の各特定の配送位置からの時間／距離のデータを含むスーパーマトリックスを格納する。
【０００４】
本発明の別の態様は、２つ以上の配送位置に対して物品を配送するシステムである。このシステムは、前記２つ以上の配送位置のそれぞれにおいて配送用の１つ以上の物品を輸送できる運搬手段から構成する。配送する物品は、集積所で得られる。このシステムは、前述したコンピュータプログラム製品をさらに具備する。運搬手段はコンピュータプログラム製品が決定した前記最短の経路情報を利用して、２つ以上の配送位置のそれぞれにおいて配送用の１つ以上の物品を得て、配送用の１つ以上の物品を各配送位置に輸送するための経路を決定する。
【０００５】
本発明のさらに別の態様は、２つ以上の潜在的な配送位置の間の最短の経路情報を計算及び記憶するためのコンピュータシステムである。このコンピュータシステムは少なくともプロセッサを具備し、このプロセッサは配送領域を１つ以上の別個の地理上の区域の集合体に分割するように構成され、各地理上の区域は１つ以上の潜在的な配送位置の第１の組を含む。プロセッサは第１の地理上の区域を選択するように構成され、第１の地理上の区域の中に地理的に位置付けられた各潜在的な配送位置に対して潜在的な配送位置の固有の第２の組を作る。プロセッサは、トラバーサブル・ネットワークを作るようにも構成される。このトラバーサブル・ネットワークはノード及びアークの組を具備し、第１の地理上の区域の中に地理的に位置付けられた少なくとも潜在的な配送位置と、上記で作られた潜在的な配送位置の任意の固有の第２の組の中に含まれた全ての潜在的な配送位置とを含む２つ以上のノードの組をさらに備える。プロセッサは、第１の地理上の区域の中に地理的に位置付けられた潜在的な配送位置のそれぞれから、トラバーサブル・ネットワークの中に含まれた全てのノードへの最短の経路情報を計算し、ルーティング及びスケジューリングシステムが後の検索用に、特定の最短の経路情報を選択し、またこの特定の最短の経路情報を記憶するように構成される。
【０００６】
本発明の別の態様は、２つ以上の潜在的な配送位置の間の最短の経路情報を計算及び記憶するためのコンピュータシステムである。このコンピュータシステムは、地理上の区域の中に地理的に位置付けられた各潜在的な配送位置に対して潜在的な配送位置の固有の組を作るように構成された少なくとも１つのプロセッサで構成される。このプロセッサはまた、地理上の区域と一意的に関連付けられたトラバーサブル・ネットワークを作るように構成される。このトラバーサブル・ネットワークはノード及びアークの組を備え、またさらに、地理上の区域の中に地理的に位置付けられた少なくとも潜在的な配送位置と、上記で作られた潜在的な配送位置の固有の組の中に含まれた全ての潜在的な配送位置とを含む２つ以上のノードの組を備える。プロセッサは、地理上の区域の中に地理的に位置付けられた潜在的な配送位置のそれぞれから、トラバーサブル・ネットワークの中に含まれた全てのノードへの最短の経路情報を計算し、ルーティング及びスケジューリングシステムが、後の検索用に、特定の最短の経路情報を選択し、またこの特定の最短の経路情報を記憶するように構成される。
【０００７】
本発明の別の態様は、２つ以上の潜在的な配送位置の間の最短の経路情報を計算及び記憶するための方法である。この方法は配送領域を１つ以上の別個の地理上の区域の集合体に分割するステップを含む。各地理上の区域は、１つ以上の潜在的な配送位置の第１の組を含む。別のステップは、選択された地理上の区域の中に地理的に位置付けられた各潜在的な配送位置に対して、第１の地理上の区域を選択し、潜在的な配送位置に対応する固有の第２の組を作ることである。次のようなトラバーサブル・ネットワークが作られる、すなわちこのトラバーサブル・ネットワークは、ノード及びアークの組を備え、またさらに、選択された地理上の区域の中に地理的に位置付けられた少なくとも潜在的な配送位置と、選択された地理上の区域の中に地理的に位置付けられた潜在的な配送位置に対応する潜在的な配送位置の固有の第２の組の中に含まれた全ての潜在的な配送位置とを含む２つ以上のノードの組を備える。選択された地理上の区域の中に地理的に位置付けられた配送位置からトラバーサブル・ネットワークの中に含まれた全てのノードへの最短の経路情報が、計算及び記憶される。上記のステップは必要な場合、選択された地理上の区域の中に地理的に位置付けられた各潜在的な配送位置に対して、また上記で作られた全ての地理上の区域に対して繰り返される。
【０００８】
本発明のこれらの及び別の態様は、本願でより十分に説明される。
【０００９】
本発明をこのようにして一般的な用語で説明してきたが、ここで添付の図面を参照する。これらの図面は、必ずしも寸法通りには描かれていない。
【発明を実施するための最良の形態】
【００１０】
本発明の全てではないが幾つかの実施形態が示されている添付の図面を参照しながら、本発明をここで説明する。実際に、本発明は多くの異なった形態で具体化することができるが、本願に記載された実施形態に限定されると解釈してはならない。むしろ、この開示内容が適切な法的必要条件を満足するように、これらの実施形態が提供される。同じ参照番号は全体を通して同じ要素を指す。
【００１１】
当業者には理解されるように、本発明は方法、データ処理システム、又はコンピュータプログラム製品として具体化することができる。このため、本発明は全体としてハードウェアの実施形態、全体としてソフトウェアの実施形態、又はソフトウェア及びハードウェアの態様を組み合わせた実施形態の形を取ることができる。さらに、本発明は、記憶媒体の中に組み込まれたコンピュータが読取り可能なプログラム命令（例えば、コンピュータのソフトウェア）を有するコンピュータが読取り可能な記録媒体上のコンピュータプログラム製品の形態を取る。より詳細には、本発明はウェブで実行されるコンピュータのソフトウェアの形態を取る。ハードディスク、ＣＤ−ＲＯＭ、光記憶装置又は磁気記憶装置を含む任意の適当なコンピュータが読取り可能な記憶媒体を利用することができる。
【００１２】
本発明を、本発明の実施形態による方法、装置（すなわち、システム）、及びコンピュータプログラム製品のブロック図及びフローチャートを参照して以下のように説明する。ブロック図及びフローチャートの各ブロック、及びブロック図及びフローチャートの中のブロックの組合せは、それぞれ、コンピュータプログラムの命令によって実行することができることは理解されよう。これらのコンピュータプログラムの命令は、汎用コンピュータ、特殊目的のコンピュータ、又は他のプログラム可能なデータ処理装置にロードされて、コンピュータ又は他のプログラム可能なデータ処理装置上で実行されるこれらの命令が、フローチャートのブロックの中で指定された機能を実行するための手段を作り出すような装置を作る。
【００１３】
コンピュータ又は他のプログラム可能なデータ処理装置を特定の方法で機能させることができるこれらのコンピュータプログラムの命令を、コンピュータが読取り可能なメモリの中に記憶して、コンピュータが読取り可能なメモリの中に記憶された命令が、フローチャートのブロックの中で指定された機能を実行するコンピュータが読取り可能な命令を含む製品を作ることもできる。コンピュータプログラムの命令をコンピュータ又は他のプログラム可能なデータ処理装置にロードし、一連の動作ステップをコンピュータ又は他のプログラム可能な装置上で実行させて、コンピュータの実行による処理を行い、コンピュータ又は他のプログラム可能な装置上で実行される命令がフローチャートのブロックの中で指定された機能を実行するステップを提供することもできる。
【００１４】
従って、ブロック図及びフローチャートのブロックは、指定された機能を実行する手段の組合せ、指定された機能を実行するステップの組合せ及び指定された機能を実行するプログラム命令の手段に対応する。ブロック図及びフローチャートの各ブロック及びブロック図及びフローチャートの中のブロックの組み合わせは、指定された機能若しくはステップ、又は特殊目的のハードウェア及びコンピュータ命令の組み合わせを実行する特殊目的のハードウェアベースのシステムによって実行されることができることも理解されよう。
【００１５】
［システム構成］
図１は、本発明の１つの実施形態によるスーパーマトリックス形コンピュータシステム１０の概略図を例示している。この図から理解できるように、この実施形態では、スーパーマトリックス形コンピュータシステム１０は、システムインターフェース又はバス９０を介してこのスーパーマトリックス形コンピュータシステム１０の中の他の構成要素と通信するプロセッサ６５を備えている。このスーパーマトリックス形コンピュータシステム１０には、データを受信及び表示するためのディスプレイ装置／入力装置７０も含まれている。例えば、このディスプレイ装置／入力装置７０は、タッチスクリーン形モニタ、キーボード、又は当業者に周知の任意の他の装置とすることができる。スーパーマトリックス形コンピュータシステム１０は、好ましくは、リードオンリーメモリ（ＲＯＭ）１４及びランダムアクセスメモリ（ＲＡＭ）１２の両方を備えるメモリ１１をさらに具備している。サーバのＲＯＭ１４は、スーパーマトリックス形コンピュータシステム１０の中の構成要素間で情報を転送するのに役に立つ基本ルーチンを含む基本入出力システム８５（ＢＩＯＳ）を記憶するのに使用される。
【００１６】
さらに、このスーパーマトリックス形コンピュータシステム１０は、ハードディスク、リムーバブル磁気ディスク、又はＣＤ−ＲＯＭディスクなどの種々のコンピュータが読取り可能な媒体に情報を記憶するためのハードディスクドライブ、フロッピー（登録商標）ディスクドライブ、ＣＤ−ＲＯＭドライブ、又は光ディスクドライブのような少なくとも１つの記憶装置１３を備える。当業者は理解するように、これらの記憶装置のそれぞれは、適当なインターフェースによってシステムバス９０に接続される。記憶装置及びそれらの関連するコンピュータが読取り可能な媒体は、パーソナルコンピュータなどのコンピュータに対して不揮発性の記憶を行う。前述のコンピュータが読取り可能な媒体は、この技術分野では周知の何らかの他の種類のコンピュータが読取り可能な媒体で置き換えることができることに注意することは重要である。そのような媒体には、例えば、磁気カセット、フラッシュメモリカード、ディジタルビデオディスク、及びベルヌーイカートリッジ（Bernoulli cartridge）が含まれる。
【００１７】
多数のプログラムモジュールは、様々な記憶装置及びＲＡＭ１２の中に記憶することができる。そのようなプログラムモジュールには、オペレーティングシステム６０、ルーティング及びスケジューリング・モジュール８００、４倍グリッド分割モジュール１００、初期フレンド選択モジュール２００、地理的バランシング・モジュール（geo-balancing module）３００、スーパーマトリックス作成モジュール５００、及びドロップオフ取扱いモジュール７００が含まれる。ルーティング及びスケジューリング・モジュール８００、４倍グリッド分割モジュール１００、初期フレンド選択モジュール２００、地理的バランシング・モジュール３００、スーパーマトリックス作成モジュール５００、及びドロップオフ取扱いモジュール７００はそれぞれ、後でより詳細に説明するように、プロセッサ６５及びオペレーティングシステム６０の支援を受けて、スーパーマトリックス形コンピュータシステム１０の動作の特定の態様を制御する。
【００１８】
スーパーマトリックス形コンピュータシステム１０の中には、コンピュータネットワーク８０の他の構成要素とインターフェースで接続する及び通信するためのネットワークインターフェース７５も配置される。さらに、１つ以上の構成要素を組み合わせることができ、また本願で説明する機能を実行する別の構成要素をスーパーマトリックス形コンピュータシステム１０の中に含むことができる。
【００１９】
［スーパーマトリックス形コンピュータシステムの例示的な流れ］
図２は、本発明の１つの実施形態によるスーパーマトリックス形コンピュータシステム１０の例示的な流れを示している。この図から分かるように、システムはステップ１５で４倍グリッド分割モジュール１００を実行することによって開始する。後でより詳細に説明するが、本発明の１つの実施形態によるこの４倍グリッド分割モジュール１００の包括的な機能は、全体的な配送領域をより小さくより管理し易いグリッドに分割することである。次に、システムはステップ２０に進み、処理するために（４倍グリッド分割モジュール１００によって作られた）第１のグリッドを選択する。グリッドが選択された後で、スーパーマトリックス形コンピュータシステム１０はステップ２５で初期フレンド選択モジュール２００を実行し、次にステップ３０で地理的バランシング・モジュール３００を実行する。本発明の種々の実施形態では、初期フレンド選択モジュール２００及び地理的バランシング・モジュール３００を実行することにより、選択されたグリッド内の各位置に対する個々のフレンドリストが作成される。「フレンドリスト」という用語は、本願で使用される場合は、特定の位置と同じ経路上に現れる可能性が最も高い位置の組を規定するために使用される。
【００２０】
次に、システムは、スーパーマトリックス作成モジュール５００が実行されるステップ５０に進む。概して、本発明の特定の実施形態では、このスーパーマトリックス作成モジュール５００は、選択されたグリッドに対してトラバーサブル・ネットワーク（「トラブネット（travnet）」）を作り、各グリッド内の位置からトラブネット内の全てのノードまでの時間／距離のデータを計算し、各グリッド内の位置からその位置のフレンド及び範囲内の集積所までの時間／距離のデータを含むスーパーマトリックスを格納する。この集積所は、配送位置に配送される物品用の保管所である。
【００２１】
次に、システムは、未処理のままのグリッドがあるかどうかを判定するステップ６０に進む。未処理のグリッドがある場合は、システムはステップ７０に進んで、次に処理するグリッドを選択する。未処理のグリッドがない場合は、システムはステップ５５に進み、処理を完了する。
【００２２】
種々のシステムモジュールの詳細な説明
図２で参照した種々のモジュールを、ここでより詳細に説明する。
【００２３】
４倍グリッド分割モジュール
図３は、本発明の１つの実施形態による４倍グリッド分割モジュール１００を示す。この図から分かるように、システムは、ユーザ（例えば、ルーティング及びスケジューリング技術者）が指定された配送領域の中で固有の配送位置の組を規定するステップ１０５から始まる。例えば、特定の日に、ユーザが１台以上の運搬手段を１００ヶ所の固有の配送位置（例えば、家庭、アパート、又は会社）に対してルーティング及びスケジューリングを行う役割を担うことがある。この状態では、ユーザは、これら１００ヶ所の固有の位置を組み込むために、ステップ１０５で固有の配送位置の組を定義する。
【００２４】
ステップ１０５を終えた後で、システムはステップ１１０に進む。このステップ１１０では、指定された固有の配送位置の全てを含む第１のグリッドが作られる。その地理的境界が配送領域内の配送位置の全ての範囲を取り囲むように、最初のグリッドがシステムによって作られる。別の実施形態では、システムがマップをユーザに示すことによって（例えば、コンピュータのディスプレイ画面を介して）、ユーザは第１のグリッドの境界を定義することができ、またこのグリッドによって囲まれた地理上の区域を選択又は定義することができる。例えば、全ての固有の配送位置がカリフォルニア州にある場合、ユーザはカリフォルニア及びそれを取り巻く州の部分を含むように第１のグリッドを設定する可能性がある。
【００２５】
次に、ステップ１２０において、システムは処理するために第１の位置を選択する。ステップ１３０で、システムは次に、この選択された位置を地理的に含むグリッドにこの選択された位置を加える。本発明の１つの実施形態では、位置をグリッドに加えること（例えば、「プロットすること」）は、位置の経度及び緯度座標に関係する位置固有データ（location-specific data）を必要とする。例えば、緯度３５°及び経度１１９°に位置した第１の位置に対して、システムは３５／１１９と入力する。１つの実施形態では、緯度／経度のデータを入力した後で、システムは選択された位置の図形表示を行う（例えば、コンピュータのディスプレイ画面を介して）。例えば、選択された位置は、オレンジ色のドット又は例えば「＋」などの他の記号で表すことができる。
【００２６】
システムが第１の位置をステップ１３０でプロットした後、システムは（ステップ１５０で）、位置を加えたグリッドが所定の「グリッド当たりの位置の最大数」というパラメータを超えるかどうかを判定する。この「グリッド当たりの位置の最大数」パラメータは、システムの中で事前に定義される。１つの実施形態では、「グリッド当たりの位置の最大数」パラメータは設定可能であり、ユーザが定義する。別の実施形態では、システムは、「グリッド当たりの位置の最大数」パラメータに対してディフォルト値を備えている。
【００２７】
ステップ１５０で、システムがある特定のグリッドにおいて「グリッド当たりの位置の最大数」パラメータが超えられたと判定すると、システムはステップ１７０に進む。このステップ１７０では、過剰な位置を有していると確認されたグリッドが、４つの等しい寸法のグリッドに分割される。例えば、グリッドがほぼ四角形である本発明の実施形態では、グリッドはほぼ四角形の４つの等しい大きさのグリッドに分割される。過剰な位置を有するグリッドを４つの等しい寸法のグリッドに分割することは、本発明による１つの実施形態であり、かつ別の実施形態では、グリッドは例えば２などの他の数の等しい大きさのグリッドに分割できることは理解されよう。例えば、グリッドがほぼ四角形の本発明の実施形態では、グリッドはほぼ四角形の４つの等しい寸法のグリッドに分割される。
【００２８】
過剰な位置を有するグリッドがステップ１７０で分割された後で、システムはステップ１６０に進み、プロットされない配送位置が固有の配送位置の組の中に残っているかどうかを判定する。
【００２９】
ステップ１５０に戻って、システムがどのグリッドも過剰な数の位置を有していないと判定すると、システムは直接ステップ１６０に進む。ステップ１６０で、システムがプロットされない配送位置が残っていないと判定すると、システムは４倍グリッド分割モジュール１００が終了するステップ１８０に進む。しかしながら、別のプロットされない配送位置が残っている場合は、システムは次の配送位置の処理を進めるステップ１４０に進む。
【００３０】
図３に示すように、この実施形態では、システムは連続的なループを実行する。このループでシステムは、各配送位置がプロットされた後で、特定のグリッドを分割する必要があるかどうかを判定する。システムはステップ１０５で定義された組の中の全ての配送位置が処理されるまで、ステップ１３０、１５０、１６０、及び／又は１７０を繰り返す。
【００３１】
例示する目的のために、図９〜図１５は、本発明の種々の実施形態の中で４倍グリッド分割モジュール１００によって実行されたステップを図を用いて説明している。より詳細に言うと、図９〜図１５は、システムが予め決められた組の２１，９３７の固有の配送位置内の様々な位置に運搬手段を経路指定及び計画する仮想の実施例を示している。図９は、２１，９３７の固有の配送位置を図式表示している。この実施形態では、大多数の配送位置はカリフォルニア州に存在する。しかしながら、位置はワシントン、アイダホ、バージニア、及びテキサスにも散発的に存在する。この実施例では、「グリッド当たりの配送位置の最大数」パラメータは５００に設定される。
【００３２】
図１０は、５０の位置をプロットした後の配送領域を例示する。（図９は全体の配送領域を示すため、２１，９７３の個々の配送位置を見分けることは困難である。）この図に示すように、全体の配送領域は、１つのグリッド７７の中に含まれる。図１１は、５０１の位置をプロットした後の配送領域を例示する。グリッド当たりの位置の最大数を５００に設定したため、グリッドは最初のグリッドの中の５０１番目の位置のプロットに続いて、４つの等しい大きさのグリッドに分割される。
【００３３】
図１２及び図１３は、１０００の位置をプロットした後の配送領域を例示する。この実施例では、最も高い密度の位置のグリッドはロサンゼルス区域で見出される（図１３を参照）。図１４は、２１，９３７の配送位置に対する完全な４倍グリッド分解を示す。最後に、図１５は、全ての２１，９３７の位置を処理した後の種々の最も高い密度の位置のグリッドの４倍グリッド分解を例示する。
【００３４】
図１６は、配送位置を処理するための順序を決定する１つの方法を例示している。この実施形態では、位置は自身の緯度及び経度座標に基づいて処理される（例えば、ステップ１２０及び１４０で選択され、ステップ１３０でプロットされる）。この実施例では、最も小さい緯度値の位置の組が最初に処理される。この緯度値は、位置の緯度座標の絶対値を取ることによって決定される。この実施形態では、緯度値が同じ位置の組は、自身のそれぞれの経度値の順序で、最も小さい経度から最も大きい経度まで処理される。このため、処理される最初の位置は、最も小さい緯度座標と最も小さい経度座標との組合せを有する位置になる。図１６は、５個の配送位置を含む特定の実施例を示す。位置１及び２は、最も小さい緯度値を有するため最初に処理される。位置１と２との間では、位置１の経度値が最小であるため、位置１が先に処理される。全ての５つの位置は、前述した規則に基づいて組の中の全ての位置がプロットされるまで、１つづつ処理される。
【００３５】
［初期フレンド選択モジュール］
４倍グリッド分割モジュール１００が配送領域全体をより小さくかつより管理しやすいグリッドに分割した後、スーパーマトリックス形コンピュータシステム１０の次の目的は、各固有の配送位置に対する個々のフレンドリストをコンパイルすることである。手短に図２に戻ると、システムはこの処理を、最初にステップ２０でグリッドを選択し、その後全てのグリッドが処理されるまで、１つのグリッドを次々と選択する（ステップ７０）ことによって実行する。
【００３６】
図４は、本発明の１つの実施形態による初期フレンド選択モジュール２００を示す。この初期フレンド選択モジュール２００は、初期フレンドリストを作成するために、最初のグリッド内の原点位置が選択されるステップ２０５から開始する。ステップ２０５で原点位置が選択されると、システムはステップ２１５に進む。このステップ２１５において、システムは選択された原点位置の予め決められた「最大フレンド半径」内の配送位置の全てのリストを作成する。１つの実施形態では、この最大フレンド半径は、設定可能なパラメータである。ステップ２１８において、最大フレンド半径内の各位置に、クワドラント(quadrant)識別子が割り当てられる。このクワドラント識別子は、例えば全体的な方向を示すことができ、隣接する位置は原点位置に対して地理的に配置される。１つの実施形態では、選択された原点位置を取り囲む区域は、４つの別個の等しいクワドラントに分割される。図１３に示すように、後でより詳細に説明するが、４つのクワドラントが、選択された原点位置を横方向及び縦方向に通過する２本の交差する線によって形成される。図４に戻ると、ステップ２２０において、システムはステップ２１５でコンパイルされたリストを、選択された原点位置に最も近い隣接位置から、選択された原点位置から最も離れた隣接位置まで分類する。
【００３７】
リストをステップ２２０で分類した後で、システムはステップ２２５に向かう。このステップ２２５で、システムは最も近い位置をフレンドリストに加える候補として選択する。候補の隣接位置を選択すると、システムはステップ２５５に進む。このステップ２５５で、システムは候補の隣接位置を原点位置のフレンドリストに加えると、「フレンドの最大数」パラメータを超えるかどうかを判定する。前述した最大フレンド半径パラメータと同様に、本発明の１つの実施形態には、設定可能な「フレンドの最大数」パラメータが含まれる。ステップ２５５において、フレンドの最大数が候補の隣接位置の加算を超えない場合は、システムはステップ２７０に進んで、隣接位置を原点位置のフレンドリストに加える。
【００３８】
隣接位置が加えられた後で、システムはステップ２２７に進む。このステップ２２７で、システムは隣接位置のクワドラント識別子を使用して、隣接位置のクワドラントに対応するカウンタをインクリメントする。この実施形態では、原点位置を取り囲む区域が４つのクワドラントに分割されるため、４つの別個のカウンタがフレンドの数を追跡するために使用される。（別個のカウンタの計算は、フレンドの最大数をステップ２５５で超過してしまったかどうかを判定する目的のために集計することができる。例えば、１つの実施形態では、ステップ２２５で選択された第１の候補が処理されるときは、カウンタの隣接位置は全体がゼロになっている。フレンドの最大数パラメータがゼロよりも大きい数に設定されていると仮定すると、第１の候補は最大値を超えることはない。）次に、ステップ２２７において、加えられた位置のクワドラントに関連したカウンタがインクリメントされる。
【００３９】
次に、システムはステップ２３０に進み、ステップ２２０でコンパイルされた分類リストに残っている位置があるかどうかを判定する。残っている場合は、システムはステップ２４５に進み、分類リスト上の次に最も近い位置を原点位置のフレンドリストに加える候補として選択する。システムは次に、（１）フレンドの最大数パラメータを超過してしまう、又は（２）ステップ２１５でコンパイルされたリストから全ての位置が処理されてしまう、のいずれかが行われるまでステップ２５５、２７０、及び２２７を繰り返す。
【００４０】
ステップ２５５において、システムが、候補の隣接位置を加えることによりフレンドの最大数パラメータを超過してしまうと判定すると、システムはステップ２６０に進み、その隣接位置をフレンドリストから除外する。次にシステムはステップ２６５に進み、選択されたグリッド内の原点位置の最大集積所半径の中の全ての集積所をフレンドリストに加える。次に、ステップ２３５において、システムは初期のフレンドリストを終了させる。初期のフレンドリストがステップ２３５で終了されると、システムはステップ２８０に進み、グリッド内の位置が選択されたグリッドの中に残っているかどうかを判定する。残っている場合は、システムはステップ２８５に進み、処理するために新しいグリッド内の位置を選択する。その後、システムはステップ２１５に進み、全てのグリッド内の位置が処理されるまで、上記のように継続する。
【００４１】
図１７は、特定の原点位置のフレンドリスト内に含まれた位置を図示している。この仮想の実施例では、「＋」１７００は、フレンドリストが計算される原点位置を示す。円１７０２の中に囲まれた区域は、初期フレンド選択モジュール２００の実行に続く原点位置のフレンドリストの中に含まれた位置を示し、また地理的バランシング・モジュールの実行に続く原点位置のフレンドリストに加えられた位置を含んでいる（後でより詳細に説明される）。円１７０２の外側のドットは、原点位置のフレンドリストの中には含まれない配送位置を示している。
【００４２】
［地理的バランシング・モジュール］
各グリッド内の位置に対して初期フレンド選択モジュール２００により初期のフレンドリストを作成した後、システムの次の目的は、フレンドリストが人口の多い区域内に配置されたフレンドで過負荷にされないようにすることである。例えば、選択された原点位置が都市の周辺部又は郊外である場合、初期フレンドリストの大多数の位置は原点位置から全体的に同じ方向に配置される（例えば、都市に向かって）。換言すると、地方のすなわち人口の希薄な地域の位置を選択された原点位置のフレンドリストの中に含むことができる前に、フレンドの最大数パラメータを超過してしまう可能性がある。
【００４３】
再度図２を参照すると、地理的バランシング・モジュール３００を実行することにより、システムはフレンドリストの中で原点位置を取り囲む全ての区域から位置を含むように試みる。図５に示すように、地理的バランシング・モジュール３００は、第１のグリッド内位置の選択を行うステップ３０５で開始する。次に、ステップ３１０で、システムは、初期フレンド選択モジュール２００のステップ２１５でコンパイルされたリストから第１の隣接位置を選択する。１つの実施形態では、ステップ３１０における選択は、隣接位置が初期フレンド選択モジュール２００のステップ２２０で分類された順序に基づく（例えば、最も近い位置から最も離れた位置）。隣接位置が選択されると、システムはステップ３１５に進み、選択された隣接位置が地理的に配置されるクワドラントを決定する。１つの実施形態では、システムは初期フレンド選択モジュール２００のステップ２１８で割り当てられたクワドラント識別子を使用して、選択された隣接位置のクワドラント識別子を決定する。
【００４４】
次に、ステップ３２０において、システムは選択された隣接位置を含むクワドラントがフレンドの最大数パラメータの１／４以上を含んでいるかどうかを判定する。例えば、フレンドの最大数パラメータが４００フレンドと設定される場合は、システムは選択されたクワドラントが１００（４００／４）以上のフレンドを含んでいるかどうかを判定する。１つの実施形態では、初期フレンド選択モジュール２００の中でフレンドの最大数パラメータを把握するために使用されるカウンタを用いて、各クワドラントが（フレンドの最大数パラメータ）／４よりも大きいか又は等しい、すなわち、ちょうど「最大数／４」のフレンドを含んでいるかどうかを判定する。選択されたクワドラントが最大数／４以上のフレンドを含んでいる場合は、システムはステップ３４０に進み、フレンドリストから隣接位置を取り除く。
【００４５】
次に、ステップ３４５において、システムは、初期フレンド選択モジュール２００からステップ２１５及び２２０でコンパイル及び分類されたリストが付加的な位置を含んでいるかどうかを判定する。含んでいる場合は、システムはステップ３５０に進み、処理のために次に最も近い隣接位置が選択され、上述したステップが繰り返される。
【００４６】
ステップ３２０において、システムは選択された隣接位置を含むクワドラントのフレンドが最大数／４よりも少ないと判定すると、システムはステップ３２５に進んで、隣接位置を原点位置のフレンドリストに加える。隣接位置をフレンドリストに加えた後で、システムはステップ３３０に進み、加えられた隣接位置が地理的に位置付けられたクワドラントに対応するカウンタをインクリメントさせる。原点位置を取り囲む区域が４つの別個のクワドラントに分割されるような実施形態では、システムは４つの異なるカウンタを利用して、各クワドラントの中のフレンドの数を追跡（又は計算）する。例えば、１つの実施形態では、クワドラント２に地理的に位置付けられた隣接位置がステップ３２５でフレンドリストに加えられる場合は、クワドラント２に対応するカウンタには１が加算される。
【００４７】
ステップ３３０の後で、システムはステップ３３３に進み、ステップ２１５及び２２０において初期フレンド選択モジュール２００からコンパイル及び分類されたリストがその他の位置を含んでいるかどうかを判定する。また、ステップ３３３において、システムはクワドラントがまだ地理的バランシングを必要とするかどうかを判定する。ステップ３３３において、システムは、（１）クワドラントが地理的バランシングを必要としない、又は（２）選択された原点位置から最大半径内の位置のリストがなくなっている、のいずれかであると判定すると、システムはステップ３５５に進み、選択されたグリッド内の位置に対するフレンドリストを完成させる。その他の場合は、システムはステップ３３５に進み、最大半径内の次に最も近い隣接位置を処理するために選択する。システムがステップ３３５で選択されたグリッド内の位置に対するフレンドリストを完成させると、システムはステップ３６０に進み、処理されないグリッド内の位置が残っているかどうかを判定する。残っている場合は、システムはステップ３７０に進み、新しいグリッド内の位置を処理するために選択する。全てのグリッド内の位置が処理されると、システムは処理を完了させるステップ３７５に進む。
【００４８】
前述のように、図１８は、最大フレンドのパラメータが２５００に設定されるという仮定の場合に、地理的バランシング・モジュール３００によって実行されるステップを図示している。垂直及び水平の線が交差する点１８００は、ステップ３０１又はステップ３７０のいずれかで選択されたグリッド内の位置を示す。この実施例では、２つの交差している線が４つの等しい大きさのクワドラントを作り出している。数値１５００、７００、２００、及び１００は、各クワドラントの中に地理的に配置され、インナーサークル１８０２によって取り囲まれた区域の中の（フレンドリストからの）位置の数を示している。このため、北東のクワドラントは１００個の位置を、南東のクワドラントは７００個の位置を、南西のクワドラントは１５００個の位置を、また北西のクワドラントは２００個の位置を含んでいる。
【００４９】
図１８に示すように、１５００及び７００のフレンドを含むクワドラントは、フレンドリストを支配する。実際に、２５００個の全フレンドの中の２２００個が、これら２つのクワドラントだけに配置されている。１つの実施形態では、地理的バランシング・モジュール３００は図１８の北西及び北東のクワドラントを、これらのクワドラントの中のアーク１８０４、１８０６を拡大して、各クワドラントが最大フレンドのパラメータの少なくとも１／４を含むまで又は最大半径内の隣接位置のリストがなくなるまでのいずれかで最初に来る方まで隣接位置を加えることによって、バランスを取ろうとする。この実施例では、北西及び北東のクワドラントの中に配置された隣接位置が、各クワドラントが少なくとも６２５個のフレンドを含むまで加えられる。最終的に、地理的バランスがフレンドリストを２５００個から、南西のクワドラントで１５００個のフレンド、南東のクワドラントで７００個の位置、北西のクワドラントで６２５個の位置、及び北東のクワドラントで６２５個の位置というように３４５０個の位置まで拡大するが、６２５個の位置が北西及び北東の各クワドラントで発見されるまでの最大区域の制限（すなわち、最大半径）は超えられることはないと仮定する。
【００５０】
図１９は原点位置のフレンドリストを図面で示したものであり、地理的バランシングによって加えられた位置を含んでいる。この仮想の実施例では、「＋」１９００は、フレンドリストが計算される原点位置を表す。第１の囲まれた区域１９０２の中に示した位置は、フレンドの最大数パラメータ又は最大半径のいずれかによって決定されたフレンドの組を表す。最大フレンドのパラメータ及び最大半径は両方とも設定可能なパラメータであり、図１９のこの仮想的な実施例では、最大フレンドのパラメータは２５００にまた最大半径は２５０マイルに設定されることは理解されよう。第２の囲まれた区域１９０４の中に示した位置は、地理的バランシング・モジュールを用いて得られたフレンドの組を表す。図１９では、第２の囲まれた区域１９０４は、中心を「プラス記号」（原点位置）に置いて形成された座標系の左上及び右上のクワドラントに加えられた位置を表す。左下及び右下には位置は加えられない、それはこれらのクワドラントはフレンドリストの中ですでに十分表されているからである（初期フレンドの選択）。地理的バランシングがない場合は、原点位置１９００に対するスーパーマトリックスは、第２の囲まれた区域１９０４内の位置の外側の密度が低い区域ではなく、原点位置１９００に近い密度が高い区域の位置に時間及び距離のみを含む可能性がある。
【００５１】
［スーパーマトリックス作成モジュール］
再度図２を参照すると、スーパーマトリックス形コンピュータシステム１０は、地理的バランシング・モジュール３００が実行した後で、スーパーマトリックス作成モジュール５００を実行する。図６に示すように、スーパーマトリックス作成モジュール５００はステップ５０５で始まり、（１）全てのグリッド内の位置、（２）グリッド内の位置の全てのフレンド、及び（３）範囲内の集積所、から得られたトラブネットを作成する。幾つかの実施形態では、「トラブネット」はアーク及びノードの組である。より具体的に言うと、この実施例では、ノードの組は、全てのグリッド内の位置、グリッド内の位置の全てのフレンド、及び任意のグリッド内の位置の最大半径の中の全ての集積所を含む「トラブネットの位置」の組を含む。トラブネットのアークは、前に列挙されたトラブネット位置を接続する全ての「必要な」ストリート部分（street segment）を含む。さらに、トラブネット位置を接続する交差するストリート部分も、ノードの組の中に含まれる。アークの組は、地方の道路、二級道路、及び州間／一級道路の組合せを含む。
【００５２】
１つの実施形態では、ストリート部分の総数（１つ以上のアークによって表すことができる）は、トラブネット位置を接続するために使用される地方道路の総数が減ることにより減少される。地方道路を減少することは、主として二級又は州間／一級道路を用いてトラブネット位置を接続することによって実現される。この実施形態では、地方道路はトラブネット位置を二級道路又は州間道路に接続する程度までだけに使用される。トラブネットに含まれる地方道路（及びストリート部分の全体）の数を減らすことにより、アーク及びノードの総数が減少される。最短経路の計算を行うために必要な処理時間は主にアーク及びノードの数に基づくために、ストリート部分の数を減少することは最終的に、トラブネット位置の間の最短経路を計算するために必要な時間を減らすことになる。トラブネットは、様々な第三者のソースから入手できる現存の地図データから得ることができる。
【００５３】
図２０は、本発明の１つの実施形態によるトラブネットを図示しており、この図面では、グリッドが３つのグリッド内の位置（位置Ａ ２００２、位置Ｂ ２００４、及び位置Ｃ ２００６）を含んでいる。各グリッド内の位置は、他の２つのグリッド内の位置のフレンドであると共に位置Ｄ ２００８である。この仮想の実施例では、フレンドの最大数は３に設定されている。このため、位置Ａ ２００２のフレンドリストは位置Ｂ ２００４、Ｃ ２００６、及びＤ ２００８を含み、位置Ｂ ２００４のフレンドリストは位置Ａ ２００２、Ｃ ２００６、及びＤ ２００８を含み、位置Ｃ ２００６のフレンドリストは位置Ａ ２００２、Ｂ ２００４、及びＤ ２００８を含む。最後に、集積所１ ２０１０は、Ａ ２００２、Ｂ ２００４、及びＣ ２００６の最大集積所半径の中にある。この実施例では、トラブネットの位置には、Ａ ２００２、Ｂ ２００４、及びＣ ２００６（グリッド内の位置）、Ｄ ２００８（グリッド内の位置のフレンド）及び集積所１ ２０１０（グリッド内の位置の最大半径の中の集積所）が含まれる。
【００５４】
これらのトラブネットの位置を用いて、各トラブネットの位置を取り巻く地方道路の接続されたアーク／ノード、取り巻く二級道路のアーク／ノード、及び最後に州間道路及び一級道路に対応するアーク／ノードを含むトラブネットが得られる。
【００５５】
図６に戻り、選択されたグリッドに対するトラブネットが作られると、システムはステップ５１０に進み、第１のグリッド内の位置を処理するために選択する。次に、ステップ５１５において、システムは選択されたグリッド内の位置からトラブネット内の全てのノードに対する最も短い時間及び距離を計算する。前述したように、幾つかの実施形態では、トラブネットのノードは、グリッド内の位置、フレンド、及び集積所だけではなく、グリッド内の位置、フレンド、及び集積所を接続する道路の交差点も含む。最短の時間及び距離を計算するために使用されるアルゴリズムは、この技術分野では周知である。
【００５６】
選択されたグリッド内の位置から全てのノードへの時間と距離が計算されると、システムはステップ５２０に進み、幾つかの時間と距離を選択的に取り出す。取り出された時間及び距離は、選択されたグリッド内の位置からその位置のフレンドまでの時間／距離を含んでいる。次に、ステップ５２５において、ステップ５２０で取り出された時間及び距離は、スーパーマトリックスの行として格納される。後でより詳細に説明されるが、図２１にスーパーマトリックスの１つの実施形態が示される。
【００５７】
選択されたグリッド内の位置からその位置のフレンドまでの時間及び距離がスーパーマトリックスの行の中に格納されると、システムはステップ５３０に進み、グリッド内の位置が処理されずに残されているかどうかを判定する。残されている場合は、システムは次のグリッド内の位置を処理するために選択する（ステップ５４５において）。図２１に示すように、各グリッド内の位置は、スーパーマトリックスの特定の行に対応する。各グリッド内の位置を表す行は、全てのグリッド内の位置が処理されるまで連続的に加えられる。全てのグリッド内の位置が処理されると、システムはステップ５７０に進み、処理を終了する。
【００５８】
図７は、スーパーマトリックス作成モジュール５００により実行される付加的なステップを例示している。グリッド内の位置とフレンドリストの中に含まれた位置との間の時間及び距離のデータを計算することに加えて、幾つかの実施形態では、スーパーマトリックス作成モジュール５００はグリッドのトラブネット内にある全ての集積所から全ての他のグリッド内で範囲内の位置及び範囲内の集積所までの最も短い経路の時間及び距離を処理するようにも設計されている。図６で説明された処理と酷似しているが、システムはステップ５５０で第１の範囲内の集積所を選択することにより開始する。次に、ステップ５５５において、選択された集積所からトラブネットの中の全てのノードまでの最短の経路の計算を（周知の最短経路のアルゴリズムを用いて）行う。ステップ５５５に続いて、システムはステップ５６０に進む。このステップ５６０で、選択された集積所から全てのグリッド内で範囲内の位置及び範囲内の集積所までの時間及び距離に対応するデータが選択され、ステップ５６５でスーパーマトリックスの中に格納される。図２１に示すように、各選択された集積所はスーパーマトリックスの中の１つの行によって表される。ステップ５７５において、システムは処理されていない集積所が（トラブネットの中に）残っているかどうかを判定する。残っている場合は、システムは次の集積所を選択し（ステップ５８０において）、ステップ５５５、５６０及び５６５を繰り返す。グリッドのトラブネットの中の全ての集積所を処理すると、システムはステップ５８５に進み、処理を完了する。
【００５９】
前述したように、図２１はスーパーマトリックスのサンプルを例示する。図２１に示されたスーパーマトリックスは、９個の位置と１個の位置／集積所のグループから導き出されている。この仮説では、フレンドの最大数パラメータは４に設定されている。しかしながら、地理的バランシングの結果として、多くの位置は４より多いフレンドを有している（例えば、位置３、５、６、７、８、及び９）。図２１に例示するように、行１には、位置１から４までの異なる位置からの時間及び距離が含まれる。図２１に示すように、各列は異なる位置を表す。この実施形態では、位置は緯度（百万分の１の度合い）及び経度（百万分の１の度合い）の座標を用いて識別される。緯度及び経度座標の後は、時間及び距離のデータである。この実施形態では、時間は秒で示され、距離は１／１００マイルで示される。このため、ここで図２の行１を参照すると、位置１から３０１８０６００，−８１５５１６００に地理的に位置付けられた位置までの時間／距離は、３０３秒（時間）及び３００マイル（距離）である。行４に例示されるように、位置４は集積所であるため、各範囲内の位置に対する時間／距離のデータを有している。この仮説では、全ての９個の位置は集積所の範囲内にあるため、行４は全ての９個の位置に対する時間／距離のデータを有している。
【００６０】
図２１に示すように、幾つかの実施形態では、スーパーマトリックスは各位置から全ての他の位置までの時間及び距離を含まない。その代わり、そのような実施形態では、スーパーマトリックスは、全ての範囲内の集積所を含む、各グリッド内の位置からその位置のフレンドまでの時間及び距離のデータのみを含む。
【００６１】
［ドロップオフ取扱いモジュール］
幾つかの実施例では、ルーティング及びスケジューリング・アルゴリズム８００の中で実行されるアルゴリズムは、互いのフレンドリストの中に含まれない２つの位置の間の時間及び距離のデータを必要とすることがある。結果として、スーパーマトリックスは時間及び距離のデータを含まない。こうした事態が起こると、システムはドロップオフ取扱いモジュール７００を実行して、時間及び距離のデータを計算することができる。
【００６２】
図８（Ａ）及び図８（Ｂ）は、本発明のいくつかの実施形態による２つの異なるドロップオフ取扱いモジュール７００を示す。ここで図８（Ａ）を参照すると、ドロップオフ取扱いモジュール７００は、システムが位置ＡとＢとの間の時間及び／又は距離のデータを要求するルーティング／スケジューリング・モジュール８００からの呼出しを受け取るステップ７０５で開始する。ステップ７１０において、システムはスーパーマトリックスがＡからＢまでの時間／距離のデータを含んでいるかどうかを判定する。含んでいる場合は、システムはステップ７１５に進み、ルーティング／スケジューリング・モジュール８００にスーパーマトリックスに含まれているデータを提供する。しかしながら、スーパーマトリックスがＡからＢまでの時間／距離のデータを含んでいない場合は、システムはステップ７２０に進み、ＸＹ距離計算法（例えば、ピタゴラスの定理）を用いてＡからＢまでの時間及び距離を計算する。ステップ７２０で時間／距離のデータが確定されると、システムはそのデータをルーティング／スケジューリング・モジュール８００に送り、処理が終了するステップ７３５に進む。
【００６３】
図８（Ｂ）に示された実施形態では、ドロップオフ取扱いモジュール７００は、図８（Ａ）で示された同じ基本的なステップを実行することによって開始する。例えば、ステップ７０５では、システムは位置ＡとＢとの間の時間及び／又は距離のデータを要求するルーティング／スケジューリング・モジュール８００からの呼出しを受け取る。ステップ７１０において、システムはスーパーマトリックスがＡからＢまでの時間／距離のデータを含んでいるかどうかを判定する。含んでいる場合は、システムはステップ７１５に進み、ルーティング／スケジューリング・モジュール８００にスーパーマトリックスに含まれているデータを提供する。しかしながら、スーパーマトリックスがＡからＢまでの時間／距離のデータを含んでいない場合は、システムはステップ７２５に進み、位置Ａ及びＢを接続する「ミニ−トラブネット」を作成する。ミニ−トラブネットを作成した後で、システムはＡとＢとの間の最短経路の時間及び距離の計算を実行する。ステップ７４０において、時間及び距離のデータは後の検索用に保存（例えば、キャッシュ）される。
【００６４】
図２２及び図２３は、１つの位置から別の位置までの時間及び距離が、図８（Ｂ）のドロップオフ取扱いモジュール７００を用いて計算されるシナリオを例示している。このシナリオは、４倍グリッド分割モジュール１００の間に、位置Ａ、Ｂ、及びＣが図２２に例示されるように１つのグリッドに配置されると仮定する。さらに、フレンドの最大数パラメータが２に設定される。初期フレンド選択モジュール２００及び地理的バランシング・モジュール３００を実行した後では、位置Ａ、Ｂ、及びＣは互いをフレンドとして含むに過ぎない。例えば、位置ＡのフレンドはＢ及びＣであり、位置ＢのフレンドはＡ及びＣであり、また位置ＣのフレンドはＡ及びＢである。この仮説には、集積所が含まれていない。この特定のグリッドに対するトラブネットが作られる場合、それは位置Ａ、Ｂ、及びＣを接続するストリート・ネットワークを含むだけである。このため、スーパーマトリックスは、Ａ、Ｂ、又はＣのいずれかから位置Ｚまでの時間及び距離のデータを備えていない。
【００６５】
スーパーマトリックスが作られた後で、ユーザが位置Ａ、Ｂ、及びＣから成る経路を作ると仮定する。スーパーマトリックスは任意の２つの位置の間の時間／距離を含んでいるため、この経路に対して、順序に関係なく、スーパーマトリックスはストリート・ネットワークに時間及び距離を提供することができる。ここで、経路の順序がＡ−Ｂ−Ｃであり、ユーザはこの時、ストップＺがストップＣの後に配置されることを希望し、経路Ａ−Ｂ−Ｃ−Ｚを作ることを決定したと仮定する。しかしながら、ここでスーパーマトリックスがＣとＺとの間の時間及び距離を提供しないという事態に至る。そのような事態が発生すると、ドロップオフ取扱いモジュール７００は、位置Ｃ及びＺを接続する図２３に例示するような「ミニ−トラブネット」を最初に作ることによって、リアルタイムで時間／距離の計算を行う。この「ミニ−トラブネット」から、システムはＣとＺとの間の最短経路の時間及び距離を計算する。（この時間及び距離は次にキャッシュされるため、システムが同じ経路指定の期間の間に再びＣとＺとの間の時間／距離を必要とする場合には、「ミニ−トラブネット」を再度作る必要はなく、また時間／距離を再度計算する必要もない。）
【００６６】
［結論］
本願に記述された本発明の多くの変形例及び他の実施形態は、前述した説明及び関連した図面の中で示した教義の利点を有する本発明が属する技術分野に精通した者には思い浮かぶであろう。このため、本発明は開示された特定の実施形態に限定されるものではなく、また変形例及び他の実施形態は添付した特許請求の範囲の中に含まれるものとすることは理解されよう。本願の中で特定の用語が使用されるが、それらの用語は一般的であり説明のためのみに使用されるものであり、本発明の範囲を限定する目的で使用されたものではない。
【図面の簡単な説明】
【００６７】
【図１】本発明の１つの実施形態によるスーパーマトリックス形コンピュータシステムの概略図である。
【図２】本発明の１つの実施形態に基づいて、スーパーマトリックス形コンピュータシステムが実行する種々のステップを示すフローチャートである。
【図３】本発明の１つの実施形態に基づいて、４倍グリッド分割モジュールが実行する種々のステップを例示するフローチャートである。
【図４】本発明の１つの実施形態に基づいて、初期フレンド選択モジュールが実行する種々のステップを例示するフローチャートである。
【図５】本発明の１つの実施形態に基づいて、地理的バランシング・モジュール（geo-balancing module）が実行する種々のステップを例示するフローチャートである。
【図６】本発明の１つの実施形態に基づいて、スーパーマトリックス作成モジュールが実行する種々のステップを例示するフローチャートである。
【図７】本発明の１つの実施形態に基づいて、各範囲内集積所から全てのグリッド内、範囲内の位置までの時間／距離を計算するためにスーパーマトリックス作成モジュールが実行する別のステップを例示するフローチャートである。
【図８Ａ】本発明の１つの実施形態に基づいて、時間及び距離がＸＹ／ピタゴラスの定理による計算を用いて作られるドロップオフ取扱いモジュールが実行する別のステップを例示するフローチャートである。
【図８Ｂ】本発明の１つの実施形態に基づいて、時間及び距離が「ミニ−トラブネット（mini-travnet）」の作成を通してコンパイルされるドロップオフ取扱いモジュールが実行する種々のステップを例示するフローチャートである。
【図９】本発明の１つの実施形態に基づいて、代表的な配送領域の中に配置され、スーパーマトリックス形コンピュータシステムの画像表示スクリーンによって表示された種々の固有の配送位置の画像表示である。
【図１０】５０個の位置をプロットした後の、図９の代表的な配送領域を例示する図である。
【図１１】５０１個の位置を処理した後の、図９の代表的な配送領域を例示する図である。
【図１２】１０００個の位置をプロットした後の、図９の代表的な配送領域を例示する図である。
【図１３】図１２に示した例示的な配送領域の拡大図を例示する図である。
【図１４】図９の種々の配送領域に対して、完全な４倍グリッド分解を例示する図である。
【図１５】全ての種々の位置が処理された後の、最も高い密度位置グリッドの４倍グリッド分解を例示する図である。
【図１６】配送位置を処理する順序を決定するための１つの方法を例示する図である。
【図１７】特定の原点位置のフレンドリストの中に含まれた位置を図示する図である。
【図１８】最大のフレンドパラメータが２５００に設定された仮定の事例で、地理的バランシング・モジュールが実行するステップを図示する図である。
【図１９】地理的バランシングを通して加えられた位置を含む原点のフレンドリストを図示する図である。
【図２０】本発明の１つの実施形態によるトラブネットを図示する図である。
【図２１】１０個の位置を含む仮定の配送領域から作られた代表的なスーパーマトリックスを例示する図である。
【図２２】１つの位置（位置Ｚ）が位置Ａ，Ｂ及びＣを含むグリッドから排除されたトラブネットを図示する図である。
【図２３】図２２の位置Ｃ及び位置Ｚの間で作られた「ミニ−トラブネット」を図示する図である。
【図１】
2008543695.tif 000003
【図２】
2008543695.tif 000004
【図３】
2008543695.tif 000005
【図４】
2008543695.tif 000006
【図５】
2008543695.tif 000007
【図６】
2008543695.tif 000008
【図７】
2008543695.tif 000009
【図８Ａ】
2008543695.tif 000010
【図８Ｂ】
2008543695.tif 000011
【図９】
2008543695.tif 000012
【図１０】
2008543695.tif 000013
【図１１】
2008543695.tif 000014
【図１２】
2008543695.tif 000015
【図１３】
2008543695.tif 000016
【図１４】
2008543695.tif 000017
【図１５】
2008543695.tif 000018
【図１６】
2008543695.tif 000019
【図１７】
2008543695.tif 000020
【図１８】
2008543695.tif 000021
【図１９】
2008543695.tif 000022
【図２０】
2008543695.tif 000023
【図２１Ａ】
2008543695.tif 000024
【図２１Ｂ】
2008543695.tif 000025
【図２２】
2008543695.tif 000026
【図２３】
2008543695.tif 000027
【国際調査報告】
2008543695.tif 000028