(57)【要約】      （修正有）【課題】拡張可能なマルチ車両タスク割り当てのためのシステムおよび方法を提供する。【解決手段】１つ以上の車両に割り当てられる複数のタスクを表す複数のノードの数、前記ノード間の距離、前記複数のノードのそれぞれに関連付けられた需要および前記１つ以上の車両のそれぞれの最大積載能力を含む複数の入力パラメーターを取得し、複数のクラスターのそれぞれが、関連付けられた車両用の実現可能なルートを形成するよう、最近傍ベースクラスタリングおよびルーティング（ｎＣＡＲ）アプローチに基づいて、前記複数のノードの複数のクラスターを判別する。ノードの数は、１つの注文の波において、数百から数千の範囲とすることができる。【選択図】図３
2019125341.tif 000002
【特許請求の範囲】
【請求項１】
2019125341.tif 000013
【請求項３】
前記複数のクラスターは、クラスターがスタートおよび終了するノードを表すデポノードを除く前記複数のノードの互いに接続されていない複数のセットを含む請求項１に記載のプロセッサー実施方法。
【請求項４】
前記複数のクラスターを含む前記クラスターの数は、全ての前記タスクを完了させるために必要とされる車両の数を決定する請求項１に記載のプロセッサー実施方法。
【請求項５】
システム（１００）であって、
１つ以上のハードウェアプロセッサー（１０４）に動作可能に接続され、前記１つ以上のハードウェアプロセッサーによって実行されるよう構成された命令を保存するよう構成されている１つ以上のデータストレージデバイス（１０２）を含み、
前記命令は、前記１つ以上のハードウェアプロセッサーによって実行されることにより、
１つ以上の車両に割り当てられる複数のタスクを表す複数のノードの数、前記ノード間の距離、前記複数のノードのそれぞれに関連付けられた需要、および前記１つ以上の車両のそれぞれの最大積載能力を含む複数の入力パラメーターを取得し、
複数のクラスターのそれぞれが、関連付けられた車両用の実現可能なルートを形成するよう、最近傍ベースクラスタリングおよびルーティング（ｎＣＡＲ）アプローチに基づいて、前記複数のノードの前記複数のクラスターを判別するよう構成されており、
前記複数のクラスターのそれぞれに関連付けられた総需要は、前記関連付けられた車両の前記最大積載能力内に収まり、
前記複数のクラスターは、最も低い総コストに繋がり、
前記総コストは、全ての前記タスクを完了させるために前記１つ以上の車両によって巡回される合計長さを表しており、
さらに、前記命令は、前記１つ以上のハードウェアプロセッサーによって実行されることにより、
巡回セールスマン問題アプローチ（ＴＳＰ）を用いて、前記複数のクラスターのそれぞれの最適なルートを判別するよう構成されていることを特徴とするシステム。
【請求項６】
前記１つ以上のハードウェアプロセッサーは、
（ｉ）最初は如何なるクラスターにも割り当てられていないｎ個の前記ノードのｎ個の潜在的クラスターを生成する工程であって、
ｉ番目の潜在的クラスターの需要を、ｉ番目のノードの前記需要で初期化する工程と、
前記ｉ番目のノードを、現在のノードとして特定する工程と、
前記現在のノードとのユークリッド距離に基づいて、前記現在のノードの最近傍のノードを繰り返し判別する工程と、
積載能力制約が満たされる場合に、前記最近傍のノードを、クラスターメンバーとして選択し、さらに、前記最近傍のノードを、新たな現在のノードとして特定する工程であって、
前記実現可能なルートを形成するために、前記総需要を表す前記最近傍のノードの前記需要および前記ｉ番目の潜在的クラスターの前記需要の合計は、前記関連付けられた車両の前記最大積載能力内に収まっている、前記最近傍のノードを、前記クラスターメンバーとして選択する前記工程と、を各ノードのために繰り返して実行する工程を含む前記ｎ個のノードの前記ｎ個の潜在的クラスターを生成する前記工程と、
（ｉｉ）前記ｎ個の潜在的クラスターからベストクラスターを選択する工程であって、
前記ｎ個の潜在的クラスターの複数のノードに関連付けられたシングルノードサイクルコストおよびオイラーサイクルコストを算出する工程と、
それらの合計を、前記ｎ個の潜在的クラスターのそれぞれの総コストとして割り当て
2019125341.tif 000014
2019125341.tif 000015
【発明の詳細な説明】
【優先権主張】
【０００１】
本出願は、２０１８年１月１１日付けで出願されたインド国特許出願第２０１８２１００１２９５号に基づく優先権を主張する。該出願の開示内容の全てが、参照によりここに援用される。
【技術分野】
【０００２】
本発明は、一般的に、積載能力制約付き車両ルーティングプログラム（ＣＶＲＰ：Capacity-constrained Vehicle Routing Program）に関し、より具体的には、拡張可能なマルチ車両タスク割り当て（scalable multi-vehicle task allocation）のためのシステムおよび方法に関する。
【背景技術】
【０００３】
最新の倉庫においては、一般的に、人間が実行するには生産性が低く、危険なタスクを実行するために、人間と共に複数のロボットが採用されている。例えば、そのようなタスクは、ロボットに、出荷する対象物を各々のストレージラックから持って来させることや、出荷する対象物をパッケージングドックに持って行かせることを含む。これには、全てのタスクを完了させるために全てのロボットによって巡回される総経路（コスト）が最小化されるような、ルート計画および注意深いタスク割り当て（task allocation）が必要とされる。シングルラン（同じルートの一部）において実行可能なタスクの数は、ロボットの最大積載能力（maximum capacity）およびルート上での複数の対象物の組み合わせ重量に依存する。このタスク割り当て問題は、積載能力制約付き車両ルーティングプログラム（ＣＶＲＰ：Capacity-constrained Vehicle Routing Program）にマッピングされ、これは、非決定性多項式時間（ＮＰ：Nondeterministic Polynomial time）困難問題である。ＣＶＲＰインスタンス（CVRP instance）に対する準最適解を提供する多数の方法が存在するが、これらは、ノード（タスク）の数に応じて、適切に規模を変更しない。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明の実施形態は、本発明者らによって認識されている従来のシステムにおける１つ以上の上述の技術的課題に対する解決としての技術的改善を提供する。
【０００５】
１つの態様において、プロセッサー実施方法が提供される。該プロセッサー実施方法は、１つ以上の車両に割り当てられる複数のタスクを表す複数のノードの数、前記ノード間の距離、前記複数のノードのそれぞれに関連付けられた需要、および前記１つ以上の車両のそれぞれの最大積載能力を含む複数の入力パラメーターを取得する工程と、複数のクラスターのそれぞれが、関連付けられた車両用の実現可能なルートを形成するよう、最近傍ベースクラスタリングおよびルーティング（ｎＣＡＲ：nearest neighbor based Clustering and Routing）アプローチに基づいて、前記複数のノードの前記複数のクラスターを判別する工程であって、前記複数のクラスターのそれぞれに関連付けられた総需要（total demand）は、前記関連付けられた車両の前記最大積載能力内に収まり、前記複数のクラスターは、最も低い総コストに繋がり、前記総コストは、全ての前記タスクを完了させるために前記１つ以上の車両によって巡回される合計長さ（total length）を表している、前記複数のノードの前記複数のクラスターを判別する前記工程と、巡回セールスマン問題（ＴＳＰ：Traveling Salesman Problem）アプローチを用いて、前記複数のクラスターのそれぞれの最適なルートを判別する工程と、を含む。
【０００６】
異なる態様において、システムが提供される。該システムは、１つ以上のプロセッサーに動作可能に接続され、命令を保存するよう構成された１つ以上のデータストレージデバイスと、を含む。前記命令は、前記１つ以上のプロセッサーによって実行されることにより、１つ以上の車両に割り当てられる複数のタスクを表す複数のノードの数、前記ノード間の距離、前記複数のノードのそれぞれに関連付けられた需要、および前記１つ以上の車両のそれぞれの最大積載能力を含む複数の入力パラメーターを取得し、複数のクラスターのそれぞれが、関連付けられた車両用の実現可能なルートを形成するよう、最近傍ベースクラスタリングおよびルーティング（ｎＣＡＲ）アプローチに基づいて、前記複数のノードの前記複数のクラスターを判別するよう構成されている。ここで、前記複数のクラスターのそれぞれに関連付けられた総需要は、前記関連付けられた車両の前記最大積載能力内に収まり、前記複数のクラスターは、最も低い総コストに繋がり、前記総コストは、全ての前記タスクを完了させるために前記１つ以上の車両によって巡回される合計長さを表している。さらに、前記命令は、前記１つ以上のプロセッサーによって実行されることにより、巡回セールスマン問題アプローチ（ＴＳＰ）を用いて、前記複数のクラスターのそれぞれの最適なルートを判別する。
【０００７】
さらに異なる態様において、内部において具体化された（embodied）コンピューター可読プログラムを有する非一時的コンピューター可読媒体（non-transitory computer readable medium）を含むコンピュータープログラム製品が提供される。前記コンピューター可読プログラムは、演算デバイスにおいて実行されたときに、前記演算デバイスに、１つ以上の車両に割り当てられる複数のタスクを表す複数のノードの数、前記ノード間の距離、前記複数のノードのそれぞれに関連付けられた需要、および前記１つ以上の車両のそれぞれの最大積載能力を含む複数の入力パラメーターを取得させ、複数のクラスターのそれぞれが、関連付けられた車両用の実現可能なルートを形成するよう、最近傍ベースクラスタリングおよびルーティング（ｎＣＡＲ）アプローチに基づいて、前記複数のノードの前記複数のクラスターを判別させる。ここで、前記複数のクラスターのそれぞれに関連付けられた総需要は、前記関連付けられた車両の前記最大積載能力内に収まり、前記複数のクラスターは、最も低い総コストに繋がり、前記総コストは、全ての前記タスクを完了させるために前記１つ以上の車両によって巡回される合計長さを表している。さらに、前記コンピューター可読プログラムは、前記演算デバイスにおいて実行されたときに、前記演算デバイスに、巡回セールスマン問題アプローチ（ＴＳＰ）を用いて、前記複数のクラスターのそれぞれの最適なルートを判別させる。
【０００８】
本発明の１つの実施形態において、前記１つ以上のハードウェアプロセッサーは、（ｉ）最初は如何なるクラスターにも割り当てられていないｎ個の前記ノードのｎ個の潜在的クラスターを生成する工程であって、ｉ番目の潜在的クラスターの需要を、ｉ番目のノードの前記需要で初期化する工程と、前記ｉ番目のノードを、現在のノードとして特定する工程と、前記現在のノードと、前記現在のノードとのユークリッド距離に基づいて、前記現在のノードの最近傍のノードを繰り返し判別する工程と、積載能力制約が満たされる場合に、前記最近傍のノードを、クラスターメンバーとして選択し、さらに、前記最近傍のノードを、新たな現在のノードとして特定する工程であって、前記実現可能なルートを形成するために、前記総需要を表す前記最近傍のノードの前記需要および前記ｉ番目の潜在的クラスターの前記需要の合計は、前記関連付けられた車両の前記最大積載能力内に収まっている、前記最近傍のノードを、前記クラスターメンバーとして選択する前記工程と、を各ノードのために繰り返して実行する工程を含む前記ｎ個の前記ノードのｎ個の前記潜在的クラスターを生成する前記工程と、（ｉｉ）前記ｎ個の潜在的クラスターからベストクラスターを選択する工程であって、前記ｎ個の潜在的クラスターの複数のノードに関連付けられたシングルノードサイクルコストおよびオイラーサイクルコストを算出する工程と、それらの合計を、前記ｎ個の潜在的クラスターのそれぞれの総コストとして割り当てる工程と、最も低い総コストに関連付けられた前記潜在的クラスターを、ベストクラスターとして選択する工程と、前記ベストクラスターの前記複数のノードを、グループＴに割り当て、さらに、前記ｎ個のノードの残りのノードを、グループに割り当てる工程と、によって、前記ｎ個の潜在的クラスターから前記ベストクラスターを選択する工程と、（ｉｉｉ）前記グループが空になるまで、前記工程（ｉ）および前記工程（ｉｉ）を繰り返す工程と、によって、前記ｎＣＡＲアプローチ基づいて、前記複数のノードの前記複数のクラスターを判別するようさらに構成されており、各繰り返しでの前記ベストクラスターは、前記関連付けられた車両の前記実現可能なルートを形成する前記複数のクラスターを構成する。
【０００９】
本発明の１つの実施形態において、前記複数のクラスターは、クラスターがスタートおよび終了するノードを表すデポノード（depot node）を除く前記複数のノードの互いに接続されていない複数のセット（disjoint set）を含む。
【００１０】
本発明の１つの実施形態において、前記複数のクラスターを含む前記クラスターの数は、全ての前記タスクを完了させるために必要とされる車両の数を決定する。
【００１１】
以上の一般的な説明および以下の詳細な説明の双方は例示および例示のためのものであり、特許請求の範囲のように本発明の実施形態の限定を構成するものではないことは理解されるべきである。
【図面の簡単な説明】
【００１２】
本開示の一部として組み入られ、本開示の一部を構成する添付の図面は、例示的な実施形態を示しており、詳細な説明と共に、開示の原理を説明するよう機能する。
【００１３】
【図１】図１は、本分野において既知のシングルランにおけるシングルタスク完了（ＳＴ−ＳＲ）ｖｓシングルランにおける１つを超えるタスク完了（ＭＴ−ＳＲ）の概念的表示を示している。
【００１４】
【図２】図２は、本発明の実施形態に係る、拡張可能なマルチ車両タスク割り当てのためのシステムの例示的なブロック図を示している。
【００１５】
【図３】図３は、本発明の例示的な実施形態に係る、拡張可能なマルチ車両割り当てのためのコンピューター実施方法を示す例示的なフロー図である。
【００１６】
【図４】図４は、積載能力制約付き車両ルーティング問題ライブラリ（ＣＶＲＰＬＩＢ：Capacitated Vehicle Routing Problem Library）のＰデータセットを用いた本発明の方法と、グーグル（商標）最適化ツール（ＯＲ−Ｔｏｏｌｓ）とのコスト比の画像表現を提供している。
【００１７】
【図５】図５は、積載能力制約付き車両ルーティング問題ライブラリ（ＣＶＲＰＬＩＢ）のＰデータセットを用いた本発明の方法およびグーグル（商標）最適化ツール（ＯＲ−Ｔｏｏｌｓ）の実行時間の画像表現を提供している。
【００１８】
【図６】図６は、Ｕｃｈｏａ等によって提供されたＸデータセットを用いた本発明の方法およびグーグル（商標）最適化ツール（ＯＲ−Ｔｏｏｌｓ）の実行時間の画像表現を提供している。
【００１９】
【図７】図７は、膨大な数のノードに対する本発明の方法とグーグル（商標）最適化ツール（ＯＲ−Ｔｏｏｌｓ）との間のコスト比較を提供している。
【００２０】
【図８】図８は、膨大な数のノードに対する本発明の方法とグーグル（商標）最適化ツール（ＯＲ−Ｔｏｏｌｓ）との間の実行時間に関する性能比較を提供している。
【００２１】
【図９】図９は、膨大な数のノードに対する本発明の方法とグーグル（商標）最適化ツール（ＯＲ−Ｔｏｏｌｓ）との間のルートの数に関する性能比較を提供している。
【００２２】
本分野における当業者であれば、本発明の原理を具体化するシステムを示す概念的な概要を表す本明細書の任意のブロック図を適切に理解できるであろう。同様に、コンピューター可読媒体内において実質的に表され、明示または明示しない演算デバイスまたはプロセッサーによって実行される様々な処理を表す任意のフローチャート、フロー図、状態遷移図、疑似コード等が、適切に理解されるであろう。
【発明を実施するための形態】
【００２３】
例示的な実施形態が、添付の図面を参照して記述される。各図において、参照番号の左端の桁は、その参照番号が最初に現れる図面の番号を示している。利便性のため、各図を通して、同様または同等の部分を参照するために同じ参照番号が用いられている。開示の原理の実施例および特徴が本明細書に記述される一方、変形、応用、および他の実施が、開示の実施形態の原理および範囲から逸脱することなく、実現可能である。以下の詳細な説明は、以下の特許請求の範囲によって明示される真の範囲および原理に対する例示のためのものである。
【００２４】
詳細な説明を述べる前に、以下の議論の全ては、記述される特定の実施に関わらず、本質的に、限定というよりは、例示である。
【００２５】
一般的に、複数の可動性ロボット（mobile robots）のグループを用いた自動化は、２つの主たる工程、すなわち、タスク割り当て（task allocation）とタスク実行（task execution）から構成されている。タスク割り当ての目的は、全てのタスクを実行するための全体のコストを最小化することを保証することであるが、冗長な複数のロボットリソースはタスクを完了させるために割り当てられない。一方、タスク実行は、割り当てに従って、複数のタスクが正確かつ安全に実行されることを保証する。本発明は、タスク割り当てに焦点を当てる。
【００２６】
倉庫での状況では、ロボットのタスクは、特定の対象物の位置まで移動する作業、ストレージラックから対象物を持って来る作業、および元々の位置（パッケージングドック）へ戻る作業として定義されている。大部分において、ロボットは、ラックから複数の対象物を同時に持って来ることはないものの、ロボットは、ドックに戻る前に、シングルラン（single run）において１つを超える対象物を持って来ることもできる。これにより、シングルランにおいて１つの対象物を持って来る場合と比較して、全体の巡回時間を減少させることができる。図１は、本分野において既知のシングルランにおけるシングルタスク完了（ＳＴ−ＳＲ：Single Task completion on a Single Run）およびシングルランにおける１つを超えるタスク（複数タスク）完了（ＭＴ−ＳＲ：Multiple Tasks completion on a Single Run）の概念的表示を示している。明らかに、近くにある複数の対象物をシングルランにおいて持って来る場合、要求されている対象物の全てを持って来るために要する合計時間は、ＭＴ−ＳＲの場合の方が少ない。ＳＴ−ＳＲは、ＭＴ−ＳＲ問題の特殊な制約付きバージョンである。ＭＴ−ＳＲのケースに関連する課題は、複数のロボットのそれぞれが特定（固定）の運搬能力（carrying capacity）を有している場合に、ロボットに対して与えられる複数のタスクを最適にグループ化することである。
【００２７】
本発明は、積載能力制約付き車両ルーティング（ＣＶＲＰ：Capacity constrained Vehicle Routing）問題に要約されるマルチロボットタスク割り当て問題に関するものである。ここで、各ロボットは、自身の最大重量運搬能力（maximum weight carrying capacity）によって制約を受けている。本発明の目的は、複数の品物をパッケージングドックへ持って行くための全体時間を最小化することができるように、複数のタスクを、複数のロボットに割り当てることである。ＣＶＲＰは、既知の非決定性多項式時間（ＮＰ：Nondeterministic Polynomial time）困難問題であるため、従来のＣＶＲＰのための厳密な発見的方法は、複数のノード（タスク）の数に応じて、適切に規模を変更しない。倉庫での状況のような応用においては、典型的なＣＶＲＰインスタンスにおけるより少ないノードの数（一般的には、最大１００個）とは対照的に、ノードの数が大規模になり得、さらに、大幅に変化し得る（数百から数千に変化し得る）。そのため、現在普及している方法は、実行困難である。
【００２８】
本明細書の文脈において、表現「車両（vehicle）」および「ロボット（robot）」は、同じ意味で使用可能である。本明細書の更なる記述は倉庫での状況に関するものであるが、記述される応用はこれに限定されず、本発明のシステムおよび方法は、任意の領域において適用可能であり、特に、本発明のシステムおよび方法は、ＣＶＲＰインスタンスは、宅配サービス、相乗りサービス、製品輸送サービス等のような、割り当てられるべき膨大な数のタスク（ノード）を含む任意の領域に応用可能である。
【００２９】
倉庫内では、顧客が品物を発注したときに品物が発送されるよう予定されている。通常、倉庫は、非常に広い範囲にわたって広がっており、複数の品物もまた、広大な領域に渡って存在するラック内に保管されている。ロボットのタスクは、ストレージラックから品物を取り出し、パッケージングドックへ持って行くことである。本開示において、複数のロボットは同種・同質のものであり、ロボットのそれぞれは、固定された最大重量運搬能力を有している。また、複数のタスクは本質的に同質であるが、品物の保管場所および重量の面で互いに異なる。一般的に、複数のタスクは、波（wave）として扱われ、ここで、波は、数百から数千のタスクを含む。複数のタスクを完了させると、前の波を実行している間に溜まった次の波が、実行のために取り出される。
【００３０】
本開示は、注文された品物の全てを取ってくる作業のコストを最小化する発見的方法（heuristic method）を提供する。本開示の文脈において、コストは、全てのタスクを完了させるために全てのロボットによって巡回される総経路長（total path length）を指す。ロボットは、常に、倉庫のパッケージドックからスタートし、倉庫のパッケージドックに戻ってくる。シングルランにおいて、ロボットは、複数の品物を持って来ることができる。すなわち、ロボットは、複数のタスクを完了させ、提供された全てのタスクの総需要（重量）がロボットの積載能力内に収まる。よって、これは、マルチタスクロボットおよびシングルロボットタスク（ＭＴ−ＳＲ： Multi-Task robot and Single Robot task）割り当て問題として分類することができる。ここで、１つのロボットは、同時に複数のタスクを実行し、タスクを完了させるために１つのロボットが必要とされる。
【００３１】
この問題は、多数の車両が、デポ（発着所）において自身の行程をスタートおよび終了させる古典的なＣＶＲＰ問題に要約することができる。多数の車両の行程において、多数の車両は、多数の顧客にサービスを提供する。ここで、単一の行程における全ての顧客の総需要は、複数のロボットの積載能力限界内に収まっていなければならない。目的は、複数のロボットの集団によって実行される全ての行程の総コストが最小化され、全ての顧客が、１つのロボットから、正確にサービスを受けられるよう、複数のロボットのそれぞれの最適なルートを発見することである。ＣＶＲＰはＮＰ困難（NP hard）として知られているため、ＭＴ−ＳＲ割り当て問題もまた、ＮＰ困難問題である。
【００３２】
この技術的問題の数学的定式化（mathematical formulation）は、以下のように表すことができる。Ｇ＝（Ｖ，Ｅ）は、方向付けのない、一式のグラフであるとする。グラフ内の交点の数は、｜Ｖ｜＝ｎ＋１である。交点は、Ｖ＝｛ｖ０，ｖ１，．．．，ｖｎ｝で表され、交点ｖ０はデポ（発着所）に対応し、他の交点Ｖ’＝Ｖ＼｛ｖ０｝は、ｎ個のサイト（ｎ個の地点）に対応する。Ｖｉ＝｛ｖｉ，０≦ｉ≦ｎ｝を考える。交点の数がＥで表され、各ｅ∈Ｅがコストｃｅ＞０を有している。これは、エッジｅを巡回するためのコストである。各交点ｖｉ∈Ｖ’用に、満たされなければならない関連付けられた需要ｄｉ＞０が存在する。ｋが、デポにおいて利用可能なロボットの数であり、Ｃが各ロボットの積載能力であるとする。一般性を失うことなく、任意の交点の最大需要が、最大でも各ロボットの積載能力である、すなわち、全てのｖｉ∈Ｖ’において、ｄｉ＜Ｃであるものとする。
【００３３】
本発明の目的は、複数のサイクルの総コストが最小化され、各サイクルでの全ての交点の総需要が任意のロボットの積載能力を超えないような、交点−非接続サイクル（vertex-disjoint cycle）（デポでの接続を除く）のセットを発見することである。数学的には、この目的は、以下の条件のｔ個のサイクルＣｙｃｌｅ１，．．．，Ｃｙｃｌｅｔを見つけることである。
2019125341.tif 000003
サイクルＣｙｃｌｅのコストは、ｃ（Ｃｙｃｌｅ）＝Σｖ∈Ｃｃ（ｖ）である。
【００３４】
車両（Ｃ）の最大積載能力および複数のノードのセット（Ｎ）が、それぞれの位置と特定の需要と共に与えられると、本発明に係る、発見的最近傍ベースクラスタリングおよびルーティング（ｎＣＡＲ）方法は、全てのノード（ｖｃｏｕｎｔ）を訪れることが必要な車両の数を提供する。さらに、該方法は、全てのルートを巡回するための総コスト（Ｃｔｏｔａｌ）と、複数のノードのシーケンス（Ｒｌｉｓｔ）として、各車両のルートを提供する。複数のノードは、割り当てられる複数のタスクを表し、需要は、複数のタスクに関連付けられた重量／分量／数を表し、最大積載能力は、車両の重量運搬能力を表す。本開示に係るｎＣＡＲ方法の対象は、複数のルートのリストを発見するのと同時に、総経路コストを最小化することである。ここで、全てのルートは、全ての車両の積載能力制約を満たし、そのため、複数の車両に割り当て可能である。発見的ｎＣＡＲは、全てのノード（タスク）を、多数のクラスターに分割する。ここで、複数のクラスターは、デポを除く複数のノードの非接続セット（disjoint set）を含む。そして、ルートを巡回セールスマン問題（ＴＳＰ：Traveling Salesman Problem）にマッピングすることにより、複数のクラスターのそれぞれのためのルートが構築される。複数のノードのセットＴが与えられると、ＴＳＰ（Ｔ）は、ハミルトニアンサイクル（ルート）Ｒおよびそのコストｃを返す。１つの実施形態において、ｎＣＡＲは、近似比（approximation ratio）が１．５のＣｈｒｉｓｔｏｆｉｄｅｓによるＴＳＰのための方法を用いる。クラスターを生成するための基準は、２つの要素から構成される。最初に、クラスター内の複数のノードは、実現可能なルートを形成しなくてはならない。すなわち、全てのクラスターメンバーの総需要は、複数の車両の積載能力制約（Ｃ）内に収まる。さらに、複数のクラスターは、個々のクラスターの経路コストがより低い総経路コストに繋がるように、形成されなければならない。
【００３５】
図面、より具体的には、図２〜９を参照すると、各図を通して、対応する特徴を参照するために同じ参照番号が一貫して用いられている。好適な実施形態が示され、これら実施形態が、以下の例示的なシステムおよび方法の文脈において記述される。
【００３６】
図２は、本発明の実施形態に係る、拡張可能なマルチ車両タスク割り当てのためのシステム１００の例示的なブロック図を示している。１つの実施形態において、システム１００は、１つ以上のプロセッサー１０４と、通信インターフェースデバイスまたは入力／出力（Ｉ／Ｏ）インターフェース１０６と、１つ以上のプロセッサー１０４に動作可能に接続された１つ以上のデータストレージデバイスまたはメモリー１０２と、を備えている。１つ以上のプロセッサー１０４は、１つ以上のマイクロプロセッサー、マイクロコンピューター、マイクロコントローラー、デジタル信号プロセッサー、中央処理ユニット（ＣＰＵ）、状態機械、グラフィックコントローラー、論理回路、および／または、動作命令に基づいて信号を操作する任意のデバイスとして実施可能なハードウェアプロセッサーである。機能の中でも特に、プロセッサーは、メモリー内に保存されているコンピューター可読命令をフェッチおよび実行するよう構成されている。１つの実施形態において、システム１００は、ラップトップコンピューター、デスクトップコンピューター、ノートパソコン、ワークステーション、メインフレームコンピューター、サーバー、ネットワーククラウド等のような様々な演算システム内において実施することができる。
【００３７】
Ｉ／Ｏインターフェースデバイス１０６は、例えば、ウェブインターフェース、グラフィカルユーザーインターフェース等の様々なソフトウェアおよびハードウェアインターフェースを含み得、さらに、有線ネットワーク（例えば、ＬＡＮ、ケーブル等）および無線ネットワーク（ＷＬＡＮ、セルラー、衛星等）を含む広範な種類のネットワークＮ／Ｗおよびプロトコルタイプにおける相互通信を容易にすることができる。１つの実施形態において、Ｉ／Ｏインターフェースデバイス１０６は、多数のデバイスを互いに接続、または、他のサーバーに接続するための１つ以上のポートを含み得る。
【００３８】
メモリー１０２は、例えば、揮発性メモリー（静的ランダムアクセスメモリー（ＳＲＡＭ）および動的ランダムアクセスメモリー（ＤＲＡＭ）等）および／または非揮発性メモリー（リードオンリーメモリー（ＲＯＭ）、消去可能プログラム可能ＲＯＭ、フラッシュメモリー、ハードディスク、光学ディスク、磁気テープ等）のような本分野において既知の任意のコンピューター可読媒体を含む。１つの実施形態において、システム１００の１つ以上のモジュール（図示せず）が、メモリー１０２内に保存されている。
【００３９】
実施形態の１つにおいて、システム１００は、１つ以上のプロセッサー１０４に動作可能に接続された１つ以上のデータデバイスまたはメモリー１０２を備えている。１つ以上のデータデバイスまたはメモリー１０２は、１つ以上のプロセッサー１０４によって、方法２００の工程を実行するよう構成された命令を保存するよう構成されている。
【００４０】
図３は、本発明の実施形態に係る、拡張可能なマルチ車両タスク割り当てのためのコンピューター実施方法を示す例示的なフロー図である。方法２００の工程が、図２のシステム１００の複数のコンポーネントを参照して、詳細に説明される。プロセスの工程、方法の工程、技術等は、一連の順番で記述することができ、そのようなプロセス、方法、および技術は、異なる順番で動作するよう構成することもできる。換言すれば、記述される工程の任意のシーケンスまたは順番は、必ずしも、その順番で工程を実行しなければならないという要件を示すものではない。本明細書において記述されるプロセスの工程は、実行可能な任意の順番で実行されてもよい。さらに、いくつかの工程が、同時に実行されてもよい。
【００４１】
したがって、本発明の１つの実施形態において、１つ以上のプロセッサー１０４は、工程２０２において、１つ以上の車両に割り当てられる複数のタスクを表す複数のノードの数、ノード間の距離、複数のノードのそれぞれに関連付けられた需要、および１つ以上の
2019125341.tif 000004
2019125341.tif 000005
2019125341.tif 000006
2019125341.tif 000007
2019125341.tif 000008
2019125341.tif 000009
2019125341.tif 000010
2019125341.tif 000011
2019125341.tif 000012
【図１】
2019125341.tif 000016
【図２】
2019125341.tif 000017
【図３】
2019125341.tif 000018
【図４】
2019125341.tif 000019
【図５】
2019125341.tif 000020
【図６】
2019125341.tif 000021
【図７】
2019125341.tif 000022
【図８】
2019125341.tif 000023
【図９】
2019125341.tif 000024
【手続補正書】
【提出日】平成30年12月17日(2018.12.17)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
プロセッサー実施方法（２００）であって、
１つ以上の車両に割り当てられる複数のタスクを表す複数のノードの数、前記ノード間の距離、前記複数のノードのそれぞれに関連付けられた需要、および前記１つ以上の車両のそれぞれの最大積載能力を含む複数の入力パラメーターを取得する工程（２０２）と、
複数のクラスターのそれぞれが、関連付けられた車両用の実現可能なルートを形成するよう、最近傍ベースクラスタリングおよびルーティング（ｎＣＡＲ）アプローチに基づいて、前記複数のノードの前記複数のクラスターを判別する工程（２０４）であって、
前記複数のクラスターのそれぞれに関連付けられた総需要は、前記関連付けられた車両の前記最大積載能力内に収まり、
前記複数のクラスターは、最も低い総コストに繋がり、
前記総コストは、全ての前記タスクを完了させるために前記１つ以上の車両によって巡回される合計長さを表している、前記複数のノードの前記複数のクラスターを判別する前記工程（２０４）と、
巡回セールスマン問題（ＴＳＰ）アプローチを用いて、前記複数のクラスターのそれぞれの最適なルートを判別する工程（２０６）と、を含むことを特徴とするプロセッサー実施方法。
【請求項２】
2019125341.tif 000025
【請求項３】
前記複数のクラスターは、クラスターがスタートおよび終了するノードを表すデポノードを除く前記複数のノードの互いに接続されていない複数のセットを含む請求項１に記載のプロセッサー実施方法。
【請求項４】
前記複数のクラスターを含む前記クラスターの数は、全ての前記タスクを完了させるために必要とされる車両の数を決定する請求項１に記載のプロセッサー実施方法。
【請求項５】
システム（１００）であって、
１つ以上のハードウェアプロセッサー（１０４）に動作可能に接続され、前記１つ以上のハードウェアプロセッサーによって実行されるよう構成された命令を保存するよう構成されている１つ以上のデータストレージデバイス（１０２）を含み、
前記命令は、前記１つ以上のハードウェアプロセッサーによって実行されることにより、
１つ以上の車両に割り当てられる複数のタスクを表す複数のノードの数、前記ノード間の距離、前記複数のノードのそれぞれに関連付けられた需要、および前記１つ以上の車両のそれぞれの最大積載能力を含む複数の入力パラメーターを取得し、
複数のクラスターのそれぞれが、関連付けられた車両用の実現可能なルートを形成するよう、最近傍ベースクラスタリングおよびルーティング（ｎＣＡＲ）アプローチに基づいて、前記複数のノードの前記複数のクラスターを判別するよう構成されており、
前記複数のクラスターのそれぞれに関連付けられた総需要は、前記関連付けられた車両の前記最大積載能力内に収まり、
前記複数のクラスターは、最も低い総コストに繋がり、
前記総コストは、全ての前記タスクを完了させるために前記１つ以上の車両によって巡回される合計長さを表しており、
さらに、前記命令は、前記１つ以上のハードウェアプロセッサーによって実行されることにより、
巡回セールスマン問題アプローチ（ＴＳＰ）を用いて、前記複数のクラスターのそれぞれの最適なルートを判別するよう構成されていることを特徴とするシステム。
【請求項６】
前記１つ以上のハードウェアプロセッサーは、
（ｉ）最初は如何なるクラスターにも割り当てられていないｎ個の前記ノードのｎ個の潜在的クラスターを生成する工程であって、
ｉ番目の潜在的クラスターの需要を、ｉ番目のノードの前記需要で初期化する工程と、
前記ｉ番目のノードを、現在のノードとして特定する工程と、
前記現在のノードとのユークリッド距離に基づいて、前記現在のノードの最近傍のノードを繰り返し判別する工程と、
積載能力制約が満たされる場合に、前記最近傍のノードを、クラスターメンバーとして選択し、さらに、前記最近傍のノードを、新たな現在のノードとして特定する工程であって、
前記実現可能なルートを形成するために、前記総需要を表す前記最近傍のノードの前記需要および前記ｉ番目の潜在的クラスターの前記需要の合計は、前記関連付けられた車両の前記最大積載能力内に収まっている、前記最近傍のノードを、前記クラスターメンバーとして選択する前記工程と、を各ノードのために繰り返して実行する工程を含む前記ｎ個のノードの前記ｎ個の潜在的クラスターを生成する前記工程と、
（ｉｉ）前記ｎ個の潜在的クラスターからベストクラスターを選択する工程であって、
前記ｎ個の潜在的クラスターの複数のノードに関連付けられたシングルノードサイクルコストおよびオイラーサイクルコストを算出する工程と、
それらの合計を、前記ｎ個の潜在的クラスターのそれぞれの総コストとして割り当て
2019125341.tif 000026
【請求項７】
前記複数のクラスターは、クラスターがスタートおよび終了するノードを表すデポノードを除く前記複数のノードの互いに接続されていない複数のセットを含む請求項５に記載のシステム。
【請求項８】
前記複数のクラスターを含む前記クラスターの数は、全ての前記タスクを完了させるために必要とされる車両の数を決定する請求項５に記載のシステム。
【請求項９】
内部において具体化されたコンピューター可読プログラムを有する非一時的コンピューター可読媒体を含むコンピュータープログラム製品であって、
前記コンピューター可読プログラムは、演算デバイスにおいて実行されたときに、前記演算デバイスに、
１つ以上の車両に割り当てられる複数のタスクを表す複数のノードの数、前記ノード間の距離、前記複数のノードのそれぞれに関連付けられた需要、および前記１つ以上の車両のそれぞれの最大積載能力を含む複数の入力パラメーターを取得し、
複数のクラスターのそれぞれが、関連付けられた車両用の実現可能なルートを形成するよう、最近傍ベースクラスタリングおよびルーティング（ｎＣＡＲ）アプローチに基づいて、前記複数のノードの前記複数のクラスターを判別させるよう構成されており、
前記複数のクラスターのそれぞれに関連付けられた総需要は、前記関連付けられた車両の前記最大積載能力内に収まり、
前記複数のクラスターは、最も低い総コストに繋がり、前記総コストは、全ての前記タスクを完了させるために前記１つ以上の車両によって巡回される合計長さを表しており、
さらに、前記コンピューター可読プログラムは、前記演算デバイスにおいて実行されたときに、前記演算デバイスに、
巡回セールスマン問題アプローチ（ＴＳＰ）を用いて、前記複数のクラスターのそれぞれの最適なルートを判別させるよう構成されていることを特徴とするコンピュータープログラム製品。
【請求項１０】
2019125341.tif 000027
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【優先権主張】
【０００１】
本出願は、２０１８年１月１１日付けで出願されたインド国特許出願第２０１８２１００１２９５号に基づく優先権を主張する。該出願の開示内容の全てが、参照によりここに援用される。
【技術分野】
【０００２】
本発明は、一般的に、積載能力制約付き車両ルーティングプログラム（ＣＶＲＰ：Capacity-constrained Vehicle Routing Program）に関し、より具体的には、拡張可能なマルチ車両タスク割り当て（scalable multi-vehicle task allocation）のためのシステムおよび方法に関する。
【背景技術】
【０００３】
最新の倉庫においては、一般的に、人間が実行するには生産性が低く、危険なタスクを実行するために、人間と共に複数のロボットが採用されている。例えば、そのようなタスクは、ロボットに、出荷する対象物を各々のストレージラックから持って来させることや、出荷する対象物をパッケージングドックに持って行かせることを含む。これには、全てのタスクを完了させるために全てのロボットによって巡回される総経路（コスト）が最小化されるような、ルート計画および注意深いタスク割り当て（task allocation）が必要とされる。シングルラン（同じルートの一部）において実行可能なタスクの数は、ロボットの最大積載能力（maximum capacity）およびルート上での複数の対象物の組み合わせ重量に依存する。このタスク割り当て問題は、積載能力制約付き車両ルーティングプログラム（ＣＶＲＰ：Capacity-constrained Vehicle Routing Program）にマッピングされ、これは、非決定性多項式時間（ＮＰ：Nondeterministic Polynomial time）困難問題である。ＣＶＲＰインスタンス（CVRP instance）に対する準最適解を提供する多数の方法が存在するが、これらは、ノード（タスク）の数に応じて、適切に規模を変更しない。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明の実施形態は、本発明者らによって認識されている従来のシステムにおける１つ以上の上述の技術的課題に対する解決としての技術的改善を提供する。
【０００５】
１つの態様において、プロセッサー実施方法が提供される。該プロセッサー実施方法は、１つ以上の車両に割り当てられる複数のタスクを表す複数のノードの数、前記ノード間の距離、前記複数のノードのそれぞれに関連付けられた需要、および前記１つ以上の車両のそれぞれの最大積載能力を含む複数の入力パラメーターを取得する工程と、複数のクラスターのそれぞれが、関連付けられた車両用の実現可能なルートを形成するよう、最近傍ベースクラスタリングおよびルーティング（ｎＣＡＲ：nearest neighbor based Clustering and Routing）アプローチに基づいて、前記複数のノードの前記複数のクラスターを判別する工程であって、前記複数のクラスターのそれぞれに関連付けられた総需要（total demand）は、前記関連付けられた車両の前記最大積載能力内に収まり、前記複数のクラスターは、最も低い総コストに繋がり、前記総コストは、全ての前記タスクを完了させるために前記１つ以上の車両によって巡回される合計長さ（total length）を表している、前記複数のノードの前記複数のクラスターを判別する前記工程と、巡回セールスマン問題（ＴＳＰ：Traveling Salesman Problem）アプローチを用いて、前記複数のクラスターのそれぞれの最適なルートを判別する工程と、を含む。
【０００６】
異なる態様において、システムが提供される。該システムは、１つ以上のプロセッサーに動作可能に接続され、命令を保存するよう構成された１つ以上のデータストレージデバイスと、を含む。前記命令は、前記１つ以上のプロセッサーによって実行されることにより、１つ以上の車両に割り当てられる複数のタスクを表す複数のノードの数、前記ノード間の距離、前記複数のノードのそれぞれに関連付けられた需要、および前記１つ以上の車両のそれぞれの最大積載能力を含む複数の入力パラメーターを取得し、複数のクラスターのそれぞれが、関連付けられた車両用の実現可能なルートを形成するよう、最近傍ベースクラスタリングおよびルーティング（ｎＣＡＲ）アプローチに基づいて、前記複数のノードの前記複数のクラスターを判別するよう構成されている。ここで、前記複数のクラスターのそれぞれに関連付けられた総需要は、前記関連付けられた車両の前記最大積載能力内に収まり、前記複数のクラスターは、最も低い総コストに繋がり、前記総コストは、全ての前記タスクを完了させるために前記１つ以上の車両によって巡回される合計長さを表している。さらに、前記命令は、前記１つ以上のプロセッサーによって実行されることにより、巡回セールスマン問題アプローチ（ＴＳＰ）を用いて、前記複数のクラスターのそれぞれの最適なルートを判別する。
【０００７】
さらに異なる態様において、内部において具体化された（embodied）コンピューター可読プログラムを有する非一時的コンピューター可読媒体（non-transitory computer readable medium）を含むコンピュータープログラム製品が提供される。前記コンピューター可読プログラムは、演算デバイスにおいて実行されたときに、前記演算デバイスに、１つ以上の車両に割り当てられる複数のタスクを表す複数のノードの数、前記ノード間の距離、前記複数のノードのそれぞれに関連付けられた需要、および前記１つ以上の車両のそれぞれの最大積載能力を含む複数の入力パラメーターを取得させ、複数のクラスターのそれぞれが、関連付けられた車両用の実現可能なルートを形成するよう、最近傍ベースクラスタリングおよびルーティング（ｎＣＡＲ）アプローチに基づいて、前記複数のノードの前記複数のクラスターを判別させる。ここで、前記複数のクラスターのそれぞれに関連付けられた総需要は、前記関連付けられた車両の前記最大積載能力内に収まり、前記複数のクラスターは、最も低い総コストに繋がり、前記総コストは、全ての前記タスクを完了させるために前記１つ以上の車両によって巡回される合計長さを表している。さらに、前記コンピューター可読プログラムは、前記演算デバイスにおいて実行されたときに、前記演算デバイスに、巡回セールスマン問題アプローチ（ＴＳＰ）を用いて、前記複数のクラスターのそれぞれの最適なルートを判別させる。
【０００８】
2019125341.tif 000028
【０００９】
本発明の１つの実施形態において、前記複数のクラスターは、クラスターがスタートおよび終了するノードを表すデポノード（depot node）を除く前記複数のノードの互いに接続されていない複数のセット（disjoint set）を含む。
【００１０】
本発明の１つの実施形態において、前記複数のクラスターを含む前記クラスターの数は、全ての前記タスクを完了させるために必要とされる車両の数を決定する。
【００１１】
以上の一般的な説明および以下の詳細な説明の双方は例示および例示のためのものであり、特許請求の範囲のように本発明の実施形態の限定を構成するものではないことは理解されるべきである。
【図面の簡単な説明】
【００１２】
本開示の一部として組み入られ、本開示の一部を構成する添付の図面は、例示的な実施形態を示しており、詳細な説明と共に、開示の原理を説明するよう機能する。
【００１３】
【図１】図１は、本分野において既知のシングルランにおけるシングルタスク完了（ＳＴ−ＳＲ）ｖｓシングルランにおける１つを超えるタスク完了（ＭＴ−ＳＲ）の概念的表示を示している。
【００１４】
【図２】図２は、本発明の実施形態に係る、拡張可能なマルチ車両タスク割り当てのためのシステムの例示的なブロック図を示している。
【００１５】
【図３】図３は、本発明の例示的な実施形態に係る、拡張可能なマルチ車両割り当てのためのコンピューター実施方法を示す例示的なフロー図である。
【００１６】
【図４】図４は、積載能力制約付き車両ルーティング問題ライブラリ（ＣＶＲＰＬＩＢ：Capacitated Vehicle Routing Problem Library）のＰデータセットを用いた本発明の方法と、グーグル（商標）最適化ツール（ＯＲ−Ｔｏｏｌｓ）とのコスト比の画像表現を提供している。
【００１７】
【図５】図５は、積載能力制約付き車両ルーティング問題ライブラリ（ＣＶＲＰＬＩＢ）のＰデータセットを用いた本発明の方法およびグーグル（商標）最適化ツール（ＯＲ−Ｔｏｏｌｓ）の実行時間の画像表現を提供している。
【００１８】
【図６】図６は、Ｕｃｈｏａ等によって提供されたＸデータセットを用いた本発明の方法およびグーグル（商標）最適化ツール（ＯＲ−Ｔｏｏｌｓ）の実行時間の画像表現を提供している。
【００１９】
【図７】図７は、膨大な数のノードに対する本発明の方法とグーグル（商標）最適化ツール（ＯＲ−Ｔｏｏｌｓ）との間のコスト比較を提供している。
【００２０】
【図８】図８は、膨大な数のノードに対する本発明の方法とグーグル（商標）最適化ツール（ＯＲ−Ｔｏｏｌｓ）との間の実行時間に関する性能比較を提供している。
【００２１】
【図９】図９は、膨大な数のノードに対する本発明の方法とグーグル（商標）最適化ツール（ＯＲ−Ｔｏｏｌｓ）との間のルートの数に関する性能比較を提供している。
【００２２】
本分野における当業者であれば、本発明の原理を具体化するシステムを示す概念的な概要を表す本明細書の任意のブロック図を適切に理解できるであろう。同様に、コンピューター可読媒体内において実質的に表され、明示または明示しない演算デバイスまたはプロセッサーによって実行される様々な処理を表す任意のフローチャート、フロー図、状態遷移図、疑似コード等が、適切に理解されるであろう。
【発明を実施するための形態】
【００２３】
例示的な実施形態が、添付の図面を参照して記述される。各図において、参照番号の左端の桁は、その参照番号が最初に現れる図面の番号を示している。利便性のため、各図を通して、同様または同等の部分を参照するために同じ参照番号が用いられている。開示の原理の実施例および特徴が本明細書に記述される一方、変形、応用、および他の実施が、開示の実施形態の原理および範囲から逸脱することなく、実現可能である。以下の詳細な説明は、以下の特許請求の範囲によって明示される真の範囲および原理に対する例示のためのものである。
【００２４】
詳細な説明を述べる前に、以下の議論の全ては、記述される特定の実施に関わらず、本質的に、限定というよりは、例示である。
【００２５】
一般的に、複数の可動性ロボット（mobile robots）のグループを用いた自動化は、２つの主たる工程、すなわち、タスク割り当て（task allocation）とタスク実行（task execution）から構成されている。タスク割り当ての目的は、全てのタスクを実行するための全体のコストを最小化することを保証することであるが、冗長な複数のロボットリソースはタスクを完了させるために割り当てられない。一方、タスク実行は、割り当てに従って、複数のタスクが正確かつ安全に実行されることを保証する。本発明は、タスク割り当てに焦点を当てる。
【００２６】
倉庫での状況では、ロボットのタスクは、特定の対象物の位置まで移動する作業、ストレージラックから対象物を持って来る作業、および元々の位置（パッケージングドック）へ戻る作業として定義されている。大部分において、ロボットは、ラックから複数の対象物を同時に持って来ることはないものの、ロボットは、ドックに戻る前に、シングルラン（single run）において１つを超える対象物を持って来ることもできる。これにより、シングルランにおいて１つの対象物を持って来る場合と比較して、全体の巡回時間を減少させることができる。図１は、本分野において既知のシングルランにおけるシングルタスク完了（ＳＴ−ＳＲ：Single Task completion on a Single Run）およびシングルランにおける１つを超えるタスク（複数タスク）完了（ＭＴ−ＳＲ：Multiple Tasks completion on a Single Run）の概念的表示を示している。明らかに、近くにある複数の対象物をシングルランにおいて持って来る場合、要求されている対象物の全てを持って来るために要する合計時間は、ＭＴ−ＳＲの場合の方が少ない。ＳＴ−ＳＲは、ＭＴ−ＳＲ問題の特殊な制約付きバージョンである。ＭＴ−ＳＲのケースに関連する課題は、複数のロボットのそれぞれが特定（固定）の運搬能力（carrying capacity）を有している場合に、ロボットに対して与えられる複数のタスクを最適にグループ化することである。
【００２７】
本発明は、積載能力制約付き車両ルーティング（ＣＶＲＰ：Capacity constrained Vehicle Routing）問題に要約されるマルチロボットタスク割り当て問題に関するものである。ここで、各ロボットは、自身の最大重量運搬能力（maximum weight carrying capacity）によって制約を受けている。本発明の目的は、複数の品物をパッケージングドックへ持って行くための全体時間を最小化することができるように、複数のタスクを、複数のロボットに割り当てることである。ＣＶＲＰは、既知の非決定性多項式時間（ＮＰ：Nondeterministic Polynomial time）困難問題であるため、従来のＣＶＲＰのための厳密な発見的方法は、複数のノード（タスク）の数に応じて、適切に規模を変更しない。倉庫での状況のような応用においては、典型的なＣＶＲＰインスタンスにおけるより少ないノードの数（一般的には、最大１００個）とは対照的に、ノードの数が大規模になり得、さらに、大幅に変化し得る（数百から数千に変化し得る）。そのため、現在普及している方法は、実行困難である。
【００２８】
本明細書の文脈において、表現「車両（vehicle）」および「ロボット（robot）」は、同じ意味で使用可能である。本明細書の更なる記述は倉庫での状況に関するものであるが、記述される応用はこれに限定されず、本発明のシステムおよび方法は、任意の領域において適用可能であり、特に、本発明のシステムおよび方法は、ＣＶＲＰインスタンスは、宅配サービス、相乗りサービス、製品輸送サービス等のような、割り当てられるべき膨大な数のタスク（ノード）を含む任意の領域に応用可能である。
【００２９】
倉庫内では、顧客が品物を発注したときに品物が発送されるよう予定されている。通常、倉庫は、非常に広い範囲にわたって広がっており、複数の品物もまた、広大な領域に渡って存在するラック内に保管されている。ロボットのタスクは、ストレージラックから品物を取り出し、パッケージングドックへ持って行くことである。本開示において、複数のロボットは同種・同質のものであり、ロボットのそれぞれは、固定された最大重量運搬能力を有している。また、複数のタスクは本質的に同質であるが、品物の保管場所および重量の面で互いに異なる。一般的に、複数のタスクは、波（wave）として扱われ、ここで、波は、数百から数千のタスクを含む。複数のタスクを完了させると、前の波を実行している間に溜まった次の波が、実行のために取り出される。
【００３０】
本開示は、注文された品物の全てを取ってくる作業のコストを最小化する発見的方法（heuristic method）を提供する。本開示の文脈において、コストは、全てのタスクを完了させるために全てのロボットによって巡回される総経路長（total path length）を指す。ロボットは、常に、倉庫のパッケージドックからスタートし、倉庫のパッケージドックに戻ってくる。シングルランにおいて、ロボットは、複数の品物を持って来ることができる。すなわち、ロボットは、複数のタスクを完了させ、提供された全てのタスクの総需要（重量）がロボットの積載能力内に収まる。よって、これは、マルチタスクロボットおよびシングルロボットタスク（ＭＴ−ＳＲ： Multi-Task robot and Single Robot task）割り当て問題として分類することができる。ここで、１つのロボットは、同時に複数のタスクを実行し、タスクを完了させるために１つのロボットが必要とされる。
【００３１】
この問題は、多数の車両が、デポ（発着所）において自身の行程をスタートおよび終了させる古典的なＣＶＲＰ問題に要約することができる。多数の車両の行程において、多数の車両は、多数の顧客にサービスを提供する。ここで、単一の行程における全ての顧客の総需要は、複数のロボットの積載能力限界内に収まっていなければならない。目的は、複数のロボットの集団によって実行される全ての行程の総コストが最小化され、全ての顧客が、１つのロボットから、正確にサービスを受けられるよう、複数のロボットのそれぞれの最適なルートを発見することである。ＣＶＲＰはＮＰ困難（NP hard）として知られているため、ＭＴ−ＳＲ割り当て問題もまた、ＮＰ困難問題である。
【００３２】
この技術的問題の数学的定式化（mathematical formulation）は、以下のように表すことができる。Ｇ＝（Ｖ，Ｅ）は、方向付けのない、一式のグラフであるとする。グラフ内の交点の数は、｜Ｖ｜＝ｎ＋１である。交点は、Ｖ＝｛ｖ０，ｖ１，．．．，ｖｎ｝で表され、交点ｖ０はデポ（発着所）に対応し、他の交点Ｖ’＝Ｖ＼｛ｖ０｝は、ｎ個のサイト（ｎ個の地点）に対応する。Ｖｉ＝｛ｖｉ，０≦ｉ≦ｎ｝を考える。交点の数がＥで表され、各ｅ∈Ｅがコストｃｅ＞０を有している。これは、エッジｅを巡回するためのコストである。各交点ｖｉ∈Ｖ’用に、満たされなければならない関連付けられた需要ｄｉ＞０が存在する。ｋが、デポにおいて利用可能なロボットの数であり、Ｃが各ロボットの積載能力であるとする。一般性を失うことなく、任意の交点の最大需要が、最大でも各ロボットの積載能力である、すなわち、全てのｖｉ∈Ｖ’において、ｄｉ＜Ｃであるものとする。
【００３３】
本発明の目的は、複数のサイクルの総コストが最小化され、各サイクルでの全ての交点の総需要が任意のロボットの積載能力を超えないような、交点−非接続サイクル（vertex-disjoint cycle）（デポでの接続を除く）のセットを発見することである。数学的には、この目的は、以下の条件のｔ個のサイクルＣｙｃｌｅ１，．．．，Ｃｙｃｌｅｔを見つけることである。
2019125341.tif 000029
サイクルＣｙｃｌｅのコストは、ｃ（Ｃｙｃｌｅ）＝Σｖ∈Ｃｃ（ｖ）である。
【００３４】
車両（Ｃ）の最大積載能力および複数のノードのセット（Ｎ）が、それぞれの位置と特定の需要と共に与えられると、本発明に係る、発見的最近傍ベースクラスタリングおよびルーティング（ｎＣＡＲ）方法は、全てのノード（ｖｃｏｕｎｔ）を訪れることが必要な車両の数を提供する。さらに、該方法は、全てのルートを巡回するための総コスト（Ｃｔｏｔａｌ）と、複数のノードのシーケンス（Ｒｌｉｓｔ）として、各車両のルートを提供する。複数のノードは、割り当てられる複数のタスクを表し、需要は、複数のタスクに関連付けられた重量／分量／数を表し、最大積載能力は、車両の重量運搬能力を表す。本開示に係るｎＣＡＲ方法の対象は、複数のルートのリストを発見するのと同時に、総経路コストを最小化することである。ここで、全てのルートは、全ての車両の積載能力制約を満たし、そのため、複数の車両に割り当て可能である。発見的ｎＣＡＲは、全てのノード（タスク）を、多数のクラスターに分割する。ここで、複数のクラスターは、デポを除く複数のノードの非接続セット（disjoint set）を含む。そして、ルートを巡回セールスマン問題（ＴＳＰ：Traveling Salesman Problem）にマッピングすることにより、複数のクラスターのそれぞれのためのルートが構築される。複数のノードのセットＴが与えられると、ＴＳＰ（Ｔ）は、ハミルトニアンサイクル（ルート）Ｒおよびそのコストｃを返す。１つの実施形態において、ｎＣＡＲは、近似比（approximation ratio）が１．５のＣｈｒｉｓｔｏｆｉｄｅｓによるＴＳＰのための方法を用いる。クラスターを生成するための基準は、２つの要素から構成される。最初に、クラスター内の複数のノードは、実現可能なルートを形成しなくてはならない。すなわち、全てのクラスターメンバーの総需要は、複数の車両の積載能力制約（Ｃ）内に収まる。さらに、複数のクラスターは、個々のクラスターの経路コストがより低い総経路コストに繋がるように、形成されなければならない。
【００３５】
図面、より具体的には、図２〜９を参照すると、各図を通して、対応する特徴を参照するために同じ参照番号が一貫して用いられている。好適な実施形態が示され、これら実施形態が、以下の例示的なシステムおよび方法の文脈において記述される。
【００３６】
図２は、本発明の実施形態に係る、拡張可能なマルチ車両タスク割り当てのためのシステム１００の例示的なブロック図を示している。１つの実施形態において、システム１００は、１つ以上のプロセッサー１０４と、通信インターフェースデバイスまたは入力／出力（Ｉ／Ｏ）インターフェース１０６と、１つ以上のプロセッサー１０４に動作可能に接続された１つ以上のデータストレージデバイスまたはメモリー１０２と、を備えている。１つ以上のプロセッサー１０４は、１つ以上のマイクロプロセッサー、マイクロコンピューター、マイクロコントローラー、デジタル信号プロセッサー、中央処理ユニット（ＣＰＵ）、状態機械、グラフィックコントローラー、論理回路、および／または、動作命令に基づいて信号を操作する任意のデバイスとして実施可能なハードウェアプロセッサーである。機能の中でも特に、プロセッサーは、メモリー内に保存されているコンピューター可読命令をフェッチおよび実行するよう構成されている。１つの実施形態において、システム１００は、ラップトップコンピューター、デスクトップコンピューター、ノートパソコン、ワークステーション、メインフレームコンピューター、サーバー、ネットワーククラウド等のような様々な演算システム内において実施することができる。
【００３７】
Ｉ／Ｏインターフェースデバイス１０６は、例えば、ウェブインターフェース、グラフィカルユーザーインターフェース等の様々なソフトウェアおよびハードウェアインターフェースを含み得、さらに、有線ネットワーク（例えば、ＬＡＮ、ケーブル等）および無線ネットワーク（ＷＬＡＮ、セルラー、衛星等）を含む広範な種類のネットワークＮ／Ｗおよびプロトコルタイプにおける相互通信を容易にすることができる。１つの実施形態において、Ｉ／Ｏインターフェースデバイス１０６は、多数のデバイスを互いに接続、または、他のサーバーに接続するための１つ以上のポートを含み得る。
【００３８】
メモリー１０２は、例えば、揮発性メモリー（静的ランダムアクセスメモリー（ＳＲＡＭ）および動的ランダムアクセスメモリー（ＤＲＡＭ）等）および／または非揮発性メモリー（リードオンリーメモリー（ＲＯＭ）、消去可能プログラム可能ＲＯＭ、フラッシュメモリー、ハードディスク、光学ディスク、磁気テープ等）のような本分野において既知の任意のコンピューター可読媒体を含む。１つの実施形態において、システム１００の１つ以上のモジュール（図示せず）が、メモリー１０２内に保存されている。
【００３９】
実施形態の１つにおいて、システム１００は、１つ以上のプロセッサー１０４に動作可能に接続された１つ以上のデータデバイスまたはメモリー１０２を備えている。１つ以上のデータデバイスまたはメモリー１０２は、１つ以上のプロセッサー１０４によって、方法２００の工程を実行するよう構成された命令を保存するよう構成されている。
【００４０】
図３は、本発明の実施形態に係る、拡張可能なマルチ車両タスク割り当てのためのコンピューター実施方法を示す例示的なフロー図である。方法２００の工程が、図２のシステム１００の複数のコンポーネントを参照して、詳細に説明される。プロセスの工程、方法の工程、技術等は、一連の順番で記述することができ、そのようなプロセス、方法、および技術は、異なる順番で動作するよう構成することもできる。換言すれば、記述される工程の任意のシーケンスまたは順番は、必ずしも、その順番で工程を実行しなければならないという要件を示すものではない。本明細書において記述されるプロセスの工程は、実行可能な任意の順番で実行されてもよい。さらに、いくつかの工程が、同時に実行されてもよい。
【００４１】
したがって、本発明の１つの実施形態において、１つ以上のプロセッサー１０４は、工程２０２において、１つ以上の車両に割り当てられる複数のタスクを表す複数のノードの数、ノード間の距離、複数のノードのそれぞれに関連付けられた需要、および１つ以上の
車両のそれぞれの最大積載能力を含む複数の入力パラメーターを取得するよう構成されている。１つの実施形態において、複数の入力パラメーターは、複数のノードの位置を含み、１つ以上のプロセッサー１０４は、ノード間の距離を算出するよう構成されている。本開示の文脈において、「距離」は、三角不等式（triangle inequality）を満足するメートル（metric）である。
【００４２】
2019125341.tif 000030
【００４３】
2019125341.tif 000031
2019125341.tif 000032
【００４４】
本発明の１つの実施形態において、ｎＣＡＲ方法は、最初に、ｎ個のノードのｎ個の潜在的クラスターを生成する。ここで、最初の段階では、ｎ個のノードは、如何なるクラスターにも割り当てられていない。ＣＶＲＰの最適解を発見するための通常のアプローチは、全ての可能性のあるクラスターの組み合わせを探索し、さらに、最も低い（全体）コストを提供する組み合わせを選択することである。しかし、このアプローチは、指数関数的に組み合わせが多い場合には、実行可能な方法ではない。ｎＣＡＲは、低いコストの解を提供する可能性が最も高い可能性のあるクラスターの組み合わせのサブセットを生成する制約された最近傍アプローチである。サブセットは、クラスターがスタートおよび終了するノードを表すデポを除いた複数のノードの複数の非接続セットの複数のクラスターを含む。全ての可能性のあるクラスターの組み合わせが探索されるわけではないので、ｎＣＡＲ方法は、より拡張可能な方法である。本発明によれば、ｎ個のクラスターの生成は、最初に、ｉ番目の潜在的クラスターの需要を、ｉ番目のノードの需要で初期化することを含む。その後、ｉ番目のノードが、現在のノードとして特定される。現在検討中の最近傍のノードと、現在のノードとの間のユークリッド距離に基づいて、現在のノードの最近傍のノードが、繰り返し判別される。積載能力制約が満たされるのであれば、検討中の最近傍のノードが、クラスターメンバーとして選択される。ｉ番目の潜在的クラスターの需要と最近傍のノードの需要との合計が、総需要を表す。総需要が、関連付けられた車両の最大積載能力内に収まっている場合、それは、積載能力制約が満たされていることを示しており、さらに、検討中の最近傍のノードが、実現可能なルートを形成するためのクラスターメンバーとして選択されることを示している。その後、検討中の最近傍のノードは、現在のノードとして特定される。
【００４５】
2019125341.tif 000033
【００４６】
本開示の１つの実施形態において、１つ以上のプロセッサー１０４は、工程２０６において、巡回セールスマン問題（ＴＳＰ）アプローチを用いて、複数のクラスターのそれぞれにおける最適なルートを判別するよう構成されている。
【００４７】
2019125341.tif 000034
【００４８】
本発明によれば、複数のクラスターを含むクラスターの数は、全てのタスクを完了させるために必要とされる車両の数を決定する。
【００４９】
2019125341.tif 000035
【００５０】
プロシージャーｅｕｌｅｒＣｙｃｌｅは、Ｖ内における複数のノードの線形時間深さ優先探索（ＤＦＳ：linear-time Depth-First Search）に基づく。そのため、実行時間は、Ｏ（ｎ）となる。プロシージャーｅｕｌｅｒＣｙｃｌｅへのコールおよび８行目のｗｈｉｌｅループの双方は、３行目のｆｏｒループ内に含まれている。このｆｏｒループの外側は、｜Ｎ｜によって境界付けられており、そのため、このループの計算のコスト（complexity）は、Ｏ（ｎ）である。よって、関数ｆｅａｓｉｂｌｅＲｏｕｔｅの計算のコストは、全体として、Ｏ（ｎ×（Ｏ（ｎ）＋Ｏ（ｎ）））＝Ｏ（ｎ２）となる。
【００５１】
メイン関数ｎＣＡＲについて検討する。メイン関数ｎＣＡＲでは、関数ｆｅａｓｉｂｌｅＲｏｕｔｅが、各呼び出しにおいて、すなわち、Ｔ≠０の間、１つの空ではないルート（non-empty route）を返す。セットＮが、Ｖとして初期化され、ｗｈｉｌｅループ（６行目）の各繰り返しの１２行目において、ＴがＮから取り除かれる。よって、セットＮのサイズは、単調減少する。これは、６行目のｗｈｉｌｅループが最大｜Ｖ｜回（これは、Ｏ（ｎ）である）実行されることを示している。ｆｅａｓｉｂｌｅＲｏｕｔｅは、Ｏ（ｎ２）なので、ｎＣＡＲの実行時間は、Ｏ（ｎ×ｎ２）＝Ｏ（ｎ３）である。
【００５２】
評価：本発明のｎＣＡＲの性能は、以下の３つの面、すなわち、（ｉ）解のコスト、（ｉｉ）解におけるルートの数、および（ｉｉｉ）方法の実行時間から評価される。解のコストは、全てのノードを訪問するために、全ての車両によって巡回される総距離として測定される。単一の車両は、（積載能力制約によって）、１回の巡回で、全てのノードを訪問することはできないであろうから、解は、多数のルートを含み、１つのルートは、複数のノードのシーケンスを含む。解の中のルートの数と同じ数の利用可能な車両が存在する場合、全てのルートは、複数の異なる車両によって並行して巡回可能である。しかしながら、車両の数が、ルートの数よりも少ない場合、割り当ては、長時間を要するものとなり、車両は、以前に割り当てられたルートを完了させた後に、新たなルートをスタートすることになる。各ルートが、異なる車両または複数のルートを通過する１つの車両によって通過されるか否かによっては、解のコストは変化しない。また、複数のルートを巡回するシーケンスは、解のコストに如何なる影響も与えない。第３の性能メトリックは、標準コンピューター（デュアルコアおよび４ＧＢのインテル（商標）第５世代プロセッサー）上での方法の絶対実行時間（ミリ秒）である。
【００５３】
ｎＣＡＲと最適解との比較：ｎＣＡＲの性能は、最適解が既知のＣＶＲＰ（ベンチマーク）のいくつかの良く知られたインスタンスで評価される。最初に、Ａｕｇｅｒａｔｅｔ  ａｌ．によって提供される制約付き車両ルーティング問題ライブラリ（ＣＶＲＰＬＩＢ：Capacitated Vehicle Routing Problem Library）のＰデータセットの結果が提供される。以下の表Ｉは、最適に解かれたこれらＣＶＲＰインスタンス、グーグル（商標）最適化ツール（ＯＲ−Ｔｏｏｌｓ）、および本発明のｎＣＡＲ方法のコストとルートの数を示している。
表Ｉ：ＣＶＲＰＬＩＢのＰデータセットに基づく、最適解、グーグル（商標）ＯＲ−Ｔｏｏｌｓ、およびｎＣＡＲ方法間の性能比較
2019125341.tif 000036
表Ｉから明らかなように、ＯＲ−ＴｏｏｌｓおよびｎＣＡＲの双方によって提供される解は、最適解に近い。図４は、制約付き車両ルーティング問題ライブラリ（ＣＶＲＰＬＩＢ）のＰデータセットを用いた、グーグル（商標）最適化ツール（ＯＲ−Ｔｏｏｌｓ）と本発明の方法とのコスト比の画像表現を提供している。ここで、コスト比は、以下のように定義される。
2019125341.tif 000037
いくつかの例外的なケースが、表Ｉにおいてハイライトされている。すなわち、Ｐ−ｎ２２−ｋ８およびＰ−ｎ５５−ｋ８であり、ＯＲ−Ｔｏｏｌｓのコスト比が１より小さくなっている。ＯＲ−Ｔｏｏｌｓは、理論的には不可能であるが、最適解よりも少ないコストの解（太字部）を生成しており、最適解は、より多くのルートを有している（下線部）。これらの矛盾は、主として、ユークリッド距離の浮動小数点の丸め（四捨五入）によるものである。しかしながら、Ｐ−ｎ２２−ｋ８のインスタンスに関し、ＯＲ−Ｔｏｏｌｓは、常に、低いコストの解を提供する。最適解は、より少ないルートを要求するが、解のコストはより高く、必要とされるルートの数に関して如何なる制約も受けない唯の最適化目標（only optimization goal）である。これは、この特定のインスタンスの最適解を無効とする。
【００５４】
３つの方法の全てにおいて必要とされる車両の数は、大部分のインスタンスに関してほぼ同じであるが、最適解が、より少ない数のルートを含むことがよくある。しかしながら、最適解が、他の２つの方法と比較してより多くのルートを含む１つのインスタンス（Ｐ−ｎ５５−ｋ８）が存在する。本方法の目標は総コストを最小化することなので、この解は、最適解のコストが他の２つよりも低いので、間違いなく、実現可能なものである。ＯＲ−ＴｏｏｌｓがｎＣＡＲと比較して大幅に少ないコスト比を有することがよくあるとしても、これは、制約付き車両ルーティング問題ライブラリ（ＣＶＲＰＬＩＢ）のＰデータセットを用いたグーグル（商標）最適化ツール（ＯＲ−Ｔｏｏｌｓ）および本発明の方法の実行時間の画像表現を提供する図５から明らかなように、大幅に多い計算時間を必要とするものである。これは、データセット全体に対して当てはまる。例えば、同様の結果が、１００から１０００個のノードから構成されるＵｃｈｏａ  ｅｔ  ａｌ．によって提供されるＸデータセットを用いたグーグル（商標）最適化ツール（ＯＲ−Ｔｏｏｌｓ）および本発明の方法の実行時間の画像表現を提供する図６に示されている。
【００５５】
膨大な数のノードに対するｎＣＡＲの性能：比較的膨大な数のノード（数百から数千の単位）が存在する場合に解く必要があるＭＴ−ＳＲ割り当て問題（倉庫での状況）では、ｎＣＡＲの性能は、そのような大規模なインスタンス用に分析される。そのようなインスタンス用の最適解は、合理的な時間では生成することができないので、ｎＣＡＲは、ＯＲ−Ｔｏｏｌｓによって生成された解のみと比較される。ＯＲ−Ｔｏｏｌｓは、少ない数のノードのＣＶＲＰインスタンスの大多数において、ｎＣＡＲと比較して低いコストの解を提供するが、ｎＣＡＲは、膨大な数のノードのＣＶＲＰインスタンスが用いられる場合に、上述の３つのパラメーターの全てにおいて、ＯＲ−Ｔｏｏｌｓを上回る。よって、ＣＶＲＰインスタンスが膨大な数のノードを含む倉庫での状況において、ｎＣＡＲは、より好ましい選択肢である。
【００５６】
図５、図６、および図７は、それぞれ、解のコスト、解を発見するための実行時間、および解におけるルートの数に関し、ｎＣＡＲとＯＲ−Ｔｏｏｌｓとを比較している。ＣＶＲＰインスタンスは、３つの異なる数のノード、すなわち、５００、１０００、２０００個のノードを含んでいる。これらノードセットのそれぞれのために、各車両の需要および各車両の積載能力に基づいて、ルートの最小数（理論値）が変化する。よって、９つのＣＶＲＰインスタンスの合計が存在する。
【００５７】
図７は、膨大な数のノードに対する本発明の方法とグーグル（商標）最適化ツール（ＯＲ−Ｔｏｏｌｓ）との間のコスト比較を提供している。図７から明らかなように、ｎＣＡＲは、ノードの数が増加するにつれて、低いコストの解を提供している。さらに、ＯＲ−Ｔｏｏｌｓは、解を発見するために非常に長い実行時間を要求している。図８は、膨大な数のノードに対する本発明の方法とグーグル（商標）最適化ツール（ＯＲ−Ｔｏｏｌｓ）との間の実行時間に関する性能比較を提供している。図８から明らかなように、ＣＶＲＰインスタンスにおけるノードの数とともに、実行時間が何倍にも増加している。ｎＣＡＲの効果は、解のコストが、全てのタスクを完了させるための期間の面において測定されるのであれば、さらに効果的なものとなる。解の中にｒ個のルートおよびｒ個の車両がある場合、全ての車両は、それぞれ１つのルートに割り当て可能である。解のコストは、最大ルート長の面において測定可能である。明らかに、ノードの数がより多い場合、解は、非常に膨大な数のルートを含む。車両の限定された数によって、全てのルートを並行に訪問することはできない。その結果、割り当ては、長時間を要するものとなり、車両は、以前のルートを完了させた後に、新たなルートに取り掛かることになる。この場合、解のコストは、全ての車両間の時間の最大量となる。よって、より少ない数のルートは、より良い結果をもたらす。図９は、膨大な数のノードに対する本発明の方法とグーグル（商標）最適化ツール（ＯＲ−Ｔｏｏｌｓ）との間のルートの数についての性能比較を提供している。
【００５８】
マルチロボットタスク割り当て（ＭＲＴＡ：Multi-Robot Task Allocation）方法が、特に、倉庫での状況を参照して、上で説明された。ここで、タスクは、対象物を、それぞれのストレージラックからピックアップすることとして規定されている。ロボットは、シングルランにおいて、複数の対象物を取り出すことができるが、対象物の数は、ロボットの積載能力によって制約を受ける。この問題は、ＣＶＲＰ問題に要約することができる。ＣＶＲＰは、ＮＰ困難として知られており、この問題もＮＰ困難である。最新の整数プログラミングベース最適化方法（integer programming based optimal methods）は、最大１００個のノードのＣＶＲＰインスタンスを解く。しかしながら、倉庫での状況では、ノードの数は、注文の波において、数百から数千の範囲となり得る。よって、本発明のシステムおよび方法は、膨大な数のノードが存在したとしても、合理的な良好な結果を提供することができるｎＣＡＲと呼ばれるＯ（ｎ３）の発見的アプローチを提供する。実験結果は、本発明が、より少ないインスタンスにおいて最適解に近い解を提供することを示している（最大でコスト比が１．６）。最適解が利用できない膨大な数のノードのＣＶＲＰのために、ｎＣＡＲは、グーグル（商標）最適化ツール（ＯＲ−Ｔｏｏｌｓ）によって提供される最新の近似方法と比較される。評価は、ｎＣＡＲが、解のコスト、ルートの数、およびアルゴリズムの実際の実行時間の面において、ＯＲ−Ｔｏｏｌｓと比較してより良い結果を実現している。
【００５９】
上述の記載は、本分野における当業者が、本実施形態を製造および使用することができるように、本発明を記述する。本発明の実施形態の範囲は、特許請求の範囲によって規定され、本分野における当業者であればなし得る他の変形例もこれに含まれる。そのような他の変形例は、特許請求の範囲の要素と文言上異ならない同様の要素を有していても、本発明の範囲内であるし、それらが、特許請求の範囲の要素と文言上非実質的に異なる均等な要素を含んでいたとしても本発明の範囲内である。
【００６０】
本明細書において規定される本発明の実施形態の範囲は、本分野における当業者がなし得る他の変形例を含む。そのような他の実施形態は、特許請求の範囲の要素と文言上異ならない同様の要素を有していても、本発明の範囲内であるし、それらが、特許請求の範囲の要素と文言上非実質的に異なる均等な要素を含んでいたとしても本発明の範囲内である。
【００６１】
保護の範囲は、内部にメッセージを有するコンピューター可読手段に加えて、プログラムにまで及ぶことは理解されるべきである。そのようなコンピューター可読保存手段は、プログラムが、サーバー、携帯デバイス、または任意の好適なプログラム可能デバイス上で実行されたときに、本方法の１つ以上の工程を実行するためのプログラムコード手段を含む。ハードウェアデバイスは、例えば、サーバー、パーソナルコンピューターのような任意の種類のコンピューター、および、これらの任意の組み合わせを含む任意の好適なプログラム可能デバイスである。また、デバイスは、ハードウェア手段（例えば、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ））、ハードウェア手段とソフトウェア手段の組み合わせ（例えば、ＡＳＩＣとＦＰＧＡ）、少なくとも１つのマイクロプロセッサー、内部にソフトウェアモジュールを有する少なくとも１つのメモリーを含む手段であってもよい。よって、手段は、ハードウェア手段とソフトウェア手段の双方を含む。本明細書において記述された方法の実施形態は、ハードウェアおよびソフトウェアにおいて実施することができる。また、デバイスは、ソフトウェア手段を含む。代替的に、本発明は、例えば、複数のＣＰＵを用いて、複数の異なるハードウェアデバイス上において実施されていてもよい。
【００６２】
ここで記述された実施形態は、ハードウェア要素とソフトウェア要素を含み得る。ソフトウェアにおいて実施される実施形態は、これに限定されるものではないが、ファームウェア、常駐ソフトウェア、マイクロコード等を含む。本明細書で記述され、本発明のシステムを含む様々なモジュールによって実行される機能は、他のモジュールまたは他のモジュールの組み合わせにおいて実施されてもよい。記述の目的のため、コンピューター使用可能またはコンピューター可読媒体は、使用のために、命令実行システム、装置、またはデバイスと共に用いられ、または、接続され、プログラムを、含有、保存、通信、伝搬、または送信することができる任意の装置であってもよい。ここで記述された様々なモジュールは、ソフトウェアおよび／またはハードウェアモジュールとして実施されてもよく、任意の非一時的コンピューター可読媒体または他の記憶デバイスの任意の種類のものに保存されてもよい。非一時的コンピューター可読媒体の非限定的な例としては、ＣＤ、ＤＶＤ、ブルーレイディスク、フラッシュメモリー、ハードディスクドライブ等が挙げられる。
【００６３】
さらに、プロセスの工程、方法の工程、技術等が一連の順番で記述されるが、そのようなプロセス、方法、および技術は、代替的な順番で動作するよう構成されていてもよい。換言すれば、記述された工程の任意の手順または順番は、各工程がその順番で実行されなければならないという要件を必ずしも示すものではない。ここに開示されたプロセスの工程は、任意の順番の実施で実行されてもよい。さらに、いくつかの工程は、同時に実行されてもよい。
【００６４】
示された工程は、例示的な実施形態を説明するために提供され、現在も進む技術発展が、特定の機能が実行される様態を変化させ得るであろうことは予期されるべきである。これらの例は、説明の目的のために提示されるものであって、限定のためのものではない。さらに、機能構成ブロックの境界は、既述の利便性のために適宜規定されたものである。特定の機能およびそれらの関係が適切に実行される限り、代替的な境界を規定することができる。代替物（本明細書に記述されたものの均等物、拡張物、変形物、逸脱物等）は、関連分野における当業者であれば、そこに含まれる技術に基づいて適切に理解可能であろう。そのような代替物もまた、開示された本発明の実施形態の範囲および原理の範囲内である。また、用語「含む（comprising）」、「有する（having）」、「含む／含有する（containing）」、「備える（including）」、およびこれらの他の形式は、同等の意味を表すものであり、これらの任意の１つの用語に続く１つまたは複数の項目が含まれるオープンエンドなリストを意味し、これらの１つまたは複数の項目の排他的なリストを意味するものではなく、リストされた１つまたは複数の項目にのみ限定されるという意味ではない。本明細書および添付の特許請求の範囲において用いられる単数形「ａ」、「ａｎ」、および「ｔｈｅ」は、文脈が明示的に示していない限り、複数への参照を含むことに留意すべきである。
【００６５】
本開示および例は、例示としてのみ解されるよう意図されており、本発明の実施形態の真の範囲および原理は、特許請求の範囲によって示されている。
【外国語明細書】
2019125341.tif 000038
2019125341.tif 000039
2019125341.tif 000040
2019125341.tif 000041
2019125341.tif 000042
2019125341.tif 000043
2019125341.tif 000044
2019125341.tif 000045
2019125341.tif 000046
2019125341.tif 000047
2019125341.tif 000048
2019125341.tif 000049
2019125341.tif 000050
2019125341.tif 000051
2019125341.tif 000052
2019125341.tif 000053
2019125341.tif 000054
2019125341.tif 000055
2019125341.tif 000056
2019125341.tif 000057
2019125341.tif 000058
2019125341.tif 000059
2019125341.tif 000060
2019125341.tif 000061
2019125341.tif 000062
2019125341.tif 000063
2019125341.tif 000064
2019125341.tif 000065
2019125341.tif 000066
2019125341.tif 000067
2019125341.tif 000068
2019125341.tif 000069
2019125341.tif 000070
2019125341.tif 000071
2019125341.tif 000072
2019125341.tif 000073
2019125341.tif 000074
2019125341.tif 000075
2019125341.tif 000076