JP2024535459A - 車両スケジューリング装置、制御方法およびプログラム - Google Patents

Abstract

車両スケジューリング装置（２０００）は、対象車両が割り当てられた対象者に割り当てられたタスクを示すタスクリスト情報（１０）を取得する。車両スケジューリング装置（２０００）は、地点の各ペアについて最小コストを示すコスト行列を使用して対象車両のタスクの実行順序を決定し、各タスクについて移動経路を選択し、スケジュール情報（２０）を生成し、対象車両と一時的な障害物との間の競合を検出する。競合が検出されると、車両スケジューリング装置（２０００）は、検出が検出されなくなるまで、地点のペアの最小コストを更新するようにコスト行列を更新し、スケジュール情報（２０）を繰り返し生成する。【選択図】図１

Description

本開示は、全体として、車両について、タスクの実行順序およびタスクを実行するために車両が移動する経路を決定する技術に関する。

タスクを実行するために車両が使用される状況がある。例えば、物流会社は、倉庫内の荷物を受け取って配送するために無人搬送車（AGV: automatic guided vehicle）を使用しうる。各車両は、作業空間、例えば倉庫内を移動しながら、順番に割り当てられた複数のタスクを実行する。

これらの車両を管理するためには、各車両についてタスクの実行順序および移動ルートを予め決めておく必要がある。非特許文献１には、複数の車両のそれぞれについて同時にタスクの実行順序および移動ルートを決定する技術が開示されている。

Ayoub Insa Correa、Andre Langevin、及び Louis-Martin Rousseau、「Scheduling and routing of automated guided vehicles: A hybrid approach」、Computers & Operations Research、Volume 34、Issue 6、1688-1707ページ、２００７年６月 Chryssi Malandraki 及び Mark S. Daskin、「Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms」、Transportation Science、Volume 26、Issue 3、185-200ページ、１９９２年８月 Guni Sharon、Roni Stern、Ariel Felner、及び Nathan Sturtevant、「Conflict-Based Search for Optimal Multi-Agent Path Finding」、26th AAAI Conference on Artificial Intelligence、２０１２年７月２２日

非特許文献１では、複数の車両について同時にタスクの実行順序および移動ルートが決定される。したがって、新たな車両が追加された場合には、新たに追加された車両だけでなく、全ての車両についてタスクの実行順序および移動ルートを再度決定する必要がある。本開示の目的は、タスクの実行順序およびタスクを実行する車両の移動ルートを決定するための新たな技術を提供することである。

本開示の車両スケジューリング装置は、少なくとも１つのプロセッサと、命令を記憶するメモリとを備える。前記少なくとも１つのプロセッサは、前記命令を実行して、少なくとも１台の対象車両が割り当てられた対象者に割り当てられたタスクを示すタスクリスト情報を取得し、前記対象車両は、前記タスクに対応するタスク地点において割り当てられた各タスクを実行し、作業空間内の地点の各ペアの最小コストが示されるコスト行列を使用して車両ルーティング問題を解くことによって、各対象車両に対する前記タスクの実行順序を決定し、各タスクについて、前記決定されたタスクの実行順序に基づいて、前記タスクの前記タスク地点まで移動するコストが最小となる経路であるタスク経路を選択し、
各対象車両について、前記対象車両に割り当てられた前記タスクの前記実行順序および各タスクの前記タスク経路を示す前記対象車両のスケジュール情報を生成し、前記対象車両と、その位置が経時的に変化する一時的な障害物との間の競合である外部競合を検出し、かつ、１つ以上の外部競合が検出された場合に、さらに、前記競合が検出された地点の前記ペアの前記最小コストを更新するように前記コスト行列を更新することと、前記対象車両と前記一時的な障害物との検出が検出されなくなるまで、前記タスクの前記実行順序の前記決定、各タスクの前記タスク経路の前記選択、前記スケジュール情報の前記生成、前記競合の前記検出、および前記コスト行列の前記更新を繰り返し行うこととを行う、ように構成される。

本開示の制御方法は、コンピュータによって行われる。当該制御方法は、少なくとも１台の対象車両が割り当てられた対象者に割り当てられたタスクを示すタスクリスト情報を取得することを含み、前記対象車両は、前記タスクに対応するタスク地点において割り当てられた各タスクを実行し、作業空間内の地点の各ペアの最小コストが示されるコスト行列を使用して車両ルーティング問題を解くことによって、各対象車両に対する前記タスクの実行順序を決定することと、各タスクについて、前記タスクの前記決定された実行順序に基づいて、前記タスクの前記タスク地点まで移動するコストが最小となる経路であるタスク経路を選択することと、各対象車両について、前記対象車両に割り当てられた前記タスクの前記実行順序および各タスクの前記タスク経路を示す前記対象車両のスケジュール情報を生成することと、前記対象車両と、その位置が経時的に変化する一時的な障害物との間の競合である外部競合を検出することとを含み、１つ以上の外部競合が検出された場合に、前記競合が検出された地点の前記ペアの前記最小コストを更新するように前記コスト行列を更新すること、ならびに、前記対象車両と前記一時的な障害物との検出が検出されなくなるまで、前記タスクの前記実行順序の前記決定、各タスクの前記タスク経路の前記選択、前記スケジュール情報の前記生成、前記競合の前記検出、および前記コスト行列の前記更新を繰り返し行うことをさらに行うことを含む。

本開示の非一時的なコンピュータ可読記憶媒体は、前述した本開示の制御方法をコンピュータに実行させるプログラムを格納する。

本開示によれば、タスクの実行順序およびタスクを実行する車両の移動ルートを決定する新たな技術が提供される。

実施形態１の装置の概要を示す図である。 タスクの実行スケジュールの例を示す図である。 車両スケジューリング装置の機能構成の一例を示すブロック図である。 車両スケジューリング装置を実現するコンピュータのハードウェア構成の一例を示すブロック図である。 実施形態１の車両スケジューリング装置が行う処理の一例を示すフローチャートである。 タスクリスト情報をテーブル形式で示す図である。 時間依存コスト行列を示す図である。 時間依存経路行列を示す図である。 マップ情報が示すグリッドマップの一部を示す図である。 スケジュール情報をテーブル形式で示す図である。 予約テーブルの例を示す図である。 対象者に複数の対象車両が割り当てられた場合の、実施形態１の車両スケジューリング装置が行う処理の一例を示すフローチャートである。 実施形態２の車両スケジューリング装置の概要を示す図である。 実施形態２の車両スケジューリング装置２０００が行う処理の一例を示すフローチャートである。 時間非依存コスト行列を示す図である。 時間非依存経路行列を示す図である。 時間非依存グリッドマップを示す図である。 対象者に複数の対象車両が割り当てられた場合の、実施形態２の車両スケジューリング装置が行う処理の一例を示すフローチャートである。

以下、本開示の実施の形態について、図面を参照しながら説明する。各図において同一の要素には同一の符号を付し、必要に応じて重複する説明を省略する。さらに、記憶部は、１つ以上の記憶装置で構成される。

実施形態１
＜概要＞
図１は、実施形態１の車両スケジューリング装置２０００の概要を示す。ここで、図１に示す概要は、車両スケジューリング装置２０００を理解しやすくするために車両スケジューリング装置２０００の動作の一例を示したものであり、車両スケジューリング装置２０００の可能な動作の範囲を限定したり狭めたりするものではない。

車両スケジューリング装置２０００は、タスクリスト情報１０を取得し、タスクリスト情報１０からスケジュール情報２０を生成する。タスクリスト情報１０は、車両の操作者などの対象者に割り当てられたタスクを示す。対象者は、車両スケジューリング装置２０００がスケジュール情報２０を生成する対象の人物である。以下、対象者に割り当てられた車両を対象車両と呼ぶ。スケジュール情報２０は、タスクの実行スケジュールを示す（より詳細な説明は後述する）。

対象車両は、無人搬送車（AGV）やドローンなど、任意の種類の自律型車両であってもよい。ただし、対象車両は、必ずしも自律型車両である必要はなく、対象者が手動で運転する任意の種類の車両であってもよい。

対象車両は、割り当てられたタスクを実行するために作業空間を動き回るように構成される。作業空間は、対象車両がタスクを実行するために動き回ることができる任意の場所である。例えば、作業空間は、倉庫や空港などである。作業空間は、対象車両がタスクを実行することができる複数の地点を含む。以下、タスクが実行される地点を、そのタスクのタスク地点と呼ぶ。

対象車両によって実行される様々な種類のタスクが存在し得る。例えば、タスクは、配送される荷物の受け取り、荷物の配送、機器の検査、機器の修理などであってもよい。各タスクは、指定された地点（すなわち、そのタスク地点）で実行されなければならないため、対象車両は、タスクを実行するためにタスク地点まで移動する必要がある。なお、タスクは、必ずしも対象車両のみで実行される必要はなく、作業者などと連携して実行されてもよい。例えば、対象車両がタスク地点に荷物を配送し、作業者が対象車両から荷物を降ろす。

上述したように、スケジュール情報２０は、タスクの実行スケジュールを示す。タスクは倉庫４０内を移動して実行されるため、タスクの実行スケジュールは、タスクの実行順序と、各タスク地点まで移動するための経路（以下、タスク経路と呼ぶ）とで表される。地点間に１つ以上の経路が存在してもよい。或るタスクのタスク経路は、対象車両が移動することがスケジュールされた経路であって、前回のタスクのタスク地点からそのタスクのタスク地点までの取り得る経路のうちのコストが最小となる経路である。

図２は、タスクの実行スケジュールの例を示す。この例では、対象車両３０は、最初に地点Ｓ１に位置し、最後に地点Ｓ４に位置しなければならない。実行されるべきタスクは、地点Ｓ２、Ｓ３、Ｓ５、Ｓ６でそれぞれ実行されるタスクＸａ、Ｘｂ、Ｘｃ、Ｘｄの４つである。車両スケジューリング装置２０００は、タスクの実行順序として「Ｘａ→Ｘｃ→Ｘｄ→Ｘｂ」を決定する。したがって、対象車両３０が訪問する地点の順序として、「Ｓ１→Ｓ２→Ｓ５→Ｓ６→Ｓ３→Ｓ４」が決定される。次いで、車両スケジューリング装置２０００は、タスクＸａ、Ｘｃ、Ｘｄ、Ｘｂのタスク経路として、それぞれＰ２、Ｐ４、Ｐ６、Ｐ１０を選択する。さらに、地点Ｓ３から地点Ｓ４までの移動には、経路Ｐ１１が選択される。結果として、１）地点Ｓ１から経路Ｐ２を通って地点Ｓ２まで移動してタスクＸａを実行し、２）地点Ｓ２から経路Ｐ４を通って地点Ｓ５まで移動してタスクＸｃを実行し、３）地点Ｓ５から経路Ｐ６を通って地点Ｓ６まで移動してタスクＸｄを実行し、４）地点Ｓ６から経路Ｐ１０を通って地点Ｓ３まで移動してタスクＸｂを実行し、そして、５）地点Ｓ３から地点Ｓ４へ移動するという実行スケジュールを表すスケジュール情報２０が生成される。

スケジュール情報２０を生成するために、車両スケジューリング装置２０００は、対象車両３０のタスクの実行順序を決定し、各タスクについてタスク経路を選択する。タスクの実行順序は、コスト行列を使用して車両ルーティング問題（VRP: vehicle routing problem）を解くことによって決定される。ここで、VRP は、複数の車両を扱うことができる巡回セールスマン問題（TSP: travelling salesman problem）の一般化である。したがって、車両の台数が１台の場合、タスクの実行順序を決定するために解かれる問題を TSPと呼ぶこともできる。

この実施の形態では、スケジュール情報２０を生成するために時間依存 VRP（TDVRP: time-dependent VRP）が採用される。時間依存 VRPは時間依存コストを扱うことができ、地点の各ペアの移動コストは経時的に変化する。したがって、この実施形態では、コスト行列は時間依存コスト行列１００と呼ばれ、地点の各ペアおよび各時点の移動コストを示す。時間依存コスト行列１００内の地点のペアに対応付けられたコストは、そのペアが取り得る経路のうちのコストが最小となる経路のコストである。ここで、「時間依存コスト行列１００」および「コスト行列１００」という用語は、この実施形態では互いに交換可能に使用される。

タスクの実行順序を決定した後、車両スケジューリング装置２０００は、各タスクが取り得る経路の中からタスク経路を選択する。各タスクについて、コストが最小となる経路がタスク経路として選択される。車両スケジューリング装置２０００は、タスクの実行順序の決定結果と各タスクのタスク経路とを使用してスケジュール情報を生成する。

対象車両３０のスケジュール情報２０を確定する前に、車両スケジューリング装置２０００は、対象車両３０と一時的な障害物との間の競合をさらに考慮に入れる。一時的な障害物は、一定の期間の間、作業空間の一定の領域を占める障害物である。例えば、対象車両３０以外の車両が一時的な障害物となる可能性がある。別の例では、人が作業空間内でいくつかの作業を行うことも一時的な障害物になる可能性がある。

対象車両３０のスケジュール情報２０は、対象車両３０が一時的な障害物と競合するタスクの実行スケジュールを示す可能性がある。したがって、車両スケジューリング装置２０００は、スケジュール情報２０が競合のないスケジュールを示すまで、競合を考慮してスケジュール情報２０を繰り返し生成する。

具体的には、車両スケジューリング装置２０００は、スケジュール情報２０を生成した後、対象車両３０が一時的な障害物と競合しているか否かを確認する。競合が検出された場合、車両スケジューリング装置２０００は、検出された競合を考慮してスケジュール情報２０を再度生成する。競合が検出されない場合、車両スケジューリング装置２０００は、スケジュール情報２０の生成を終了する（すなわち、対象車両３０のスケジュール情報は確定される）。

検出された競合に基づいて時間依存コスト行列１００を更新することによって、競合の影響が考慮される。具体的には、時間依存コスト行列１００によって示される経路のコストは、競合のために最小にならない可能性がある。したがって、時間依存コスト行列１００は、検出された競合に基づいて、地点の各ペアのコストが最小となる経路を示すように更新される。

車両スケジューリング装置２０００は、更新されたコスト行列１００を使用して TDVRP を再び解き、対象車両３０に対するタスクの実行順序を決定する。検出された競合はコスト行列１００に反映されるので、TDVRPの解は、対象車両３０が検出された競合の発生を回避することができるタスクの実行順序を示す。

＜効果の例＞
車両スケジューリング装置２０００によれば、対象車両３０のタスクの実行スケジュールは、対象車両が他の車両などの一時的な障害物と競合しなくなるまで繰り返し更新される。このように、既に確定している他車両のタスクの実行スケジュールを考慮して対象車両３０のタスクの実行スケジュールが決定されるため、他車両のタスクの実行スケジュールを再生成する必要がない。言い換えると、各車両のタスクの実行スケジュールは、先着順で生成することができる。したがって、各車両のタスクの実行スケジュールを効率的に生成することができる。さらに、実施形態１の車両スケジューリング装置２０００は、TDVRP が実施形態２の車両スケジューリング装置２０００で採用されている時間非依存コストを用いた VRP よりも費用効率の高い解を提供する可能性が高いので、対象車両３０が実施形態２のものよりも費用効率よく作業することができるスケジュール情報２０を生成する可能性が高い。

以下、車両スケジューリング装置２０００のより詳細な説明について説明する。

＜機能構成例＞
図３は、車両スケジューリング装置２０００の機能構成の一例を示す。車両スケジューリング装置２０００は、取得部２０２０と、生成部２０４０と、競合検出部２０６０と、更新部２０８０とを含む。取得部２０２０は、タスクリスト情報１０を取得する。生成部２０４０は、時間依存コスト行列１００を用いて TDVRP を解くことによってタスクの実行順序を決定し、各タスクのタスク経路を選択することで、スケジュール情報２０を生成する。競合検出部２０６０は、対象車両３０および一時的な障害物との競合を検出する。競合が検出された場合、更新部２０８０は、検出された競合に基づいて時間依存コスト行列１００を更新する。スケジュール情報２０の生成、競合検出、およびコスト行列１００の更新は、競合が検出されなくなるまで繰り返し行われる。

＜ハードウエア構成の例＞
車両スケジューリング装置２０００は、１つ以上のコンピュータで実現されうる。それら１つ以上のコンピュータのそれぞれは、車両スケジューリング装置２０００を実現するために作成された専用のコンピュータであってもよいし、パーソナルコンピュータ（PC: Personal Computer）、サーバマシン又はモバイルデバイスなどの汎用のコンピュータであってもよい。

車両スケジューリング装置２０００は、コンピュータにアプリケーションをインストールすることで実現されうる。そのアプリケーションは、コンピュータを車両スケジューリング装置２０００として機能させるプログラムで実現される。言い換えれば、そのプログラムは、車両スケジューリング装置２０００の機能構成部を実装したものである。

図４は、車両スケジューリング装置２０００を実現するコンピュータ１０００のハードウエア構成の例を示すブロック図である。図４において、コンピュータ１０００は、バス１０２０、プロセッサ１０４０、メモリ１０６０、ストレージデバイス１０８０、入出力インタフェース１１００、及びネットワークインタフェース１１２０を有する。

バス１０２０は、プロセッサ１０４０、メモリ１０６０、ストレージデバイス１０８０、入出力インタフェース１１００、及びネットワークインタフェース１１２０が相互にデータの送信及び受信をするためのデータ通信路である。プロセッサ１０４０は、CPU（Central Processing Unit）、GPU（Graphics Processing Unit）、又は FPGA（Field-Programmable Gate Array）などといったプロセッサである。メモリ１０６０は、RAM（Random Access Memory）又は ROM（Read Only Memory）などの主記憶要素である。ストレージデバイス１０８０は、ハードディスク、SSD（Solid State Drive）、又はメモリカードなどの補助記憶要素である。入出力インタフェース１１００は、コンピュータ１０００と周辺デバイス（キーボード、マウス、又はディスプレイ装置など）との間のインタフェースである。ネットワークインタフェース１１２０は、コンピュータ１０００とネットワークとの間のインタフェースである。ネットワークは、LAN（Local Area Network）でもよいし、WAN（Wide Area Network）でもよい。

ストレージデバイス１０８０は、前述したプログラムを格納しうる。CPU１０４０は、車両スケジューリング装置２０００の各機能構成部を実現するためにそのプログラムを実行する。

コンピュータ１０００は、図４に示される構成に限定されない。例えば、前述したように、車両スケジューリング装置２０００は複数のコンピュータで実現されうる。この場合、それらのコンピュータは、ネットワークを介して互いに接続されうる。

＜処理の流れ＞
図５は、車両スケジューリング装置２０００が行う処理の一例を示すフローチャートである。取得部２０２０は、タスクリスト情報１０を取得する（Ｓ１０２）。生成部２０４０は、時間依存コスト行列１００を初期化する（Ｓ１０４）。生成部２０４０は、時間依存コスト行列１００を使用してタスクの実行順序を決定する（Ｓ１０６）。生成部２０４０は、各タスクのタスク経路を選択する（Ｓ１０８）。生成部２０４０は、スケジュール情報２０を生成する（Ｓ１１０）。競合検出部２０６０は、スケジュール情報２０を使用して競合検出を行う（Ｓ１１２）。競合が検出されない場合（Ｓ１１２：いいえ）、車両スケジューリング装置２０００は、スケジュール情報２０を出力する（Ｓ１１６）。

一方、競合が検出された場合（Ｓ１１２：はい）、更新部２０８０は、検出された競合に基づいて時間依存コスト行列１００を更新する（Ｓ１１４）。

時間依存コスト行列１００の更新後、車両スケジューリング装置２０００の処理はステップＳ１０６に戻る。これにより、ステップＳ１１２で競合が検出されなくなるまで（言い換えれば、対象車両３０のスケジュール情報２０が競合のないスケジュールを示すまで）、スケジュール情報２０の生成（Ｓ１０６～Ｓ１１０）、競合検出（Ｓ１１２）、およびコスト行列１００の更新（Ｓ１１４）が繰り返し行われる。

＜タスクリスト情報の取得：Ｓ１０２＞
取得部２０２０は、タスクリスト情報１０を取得する（Ｓ１０２）。タスクリスト情報１０は、対象車両３０の対象者に割り当てられているタスクを示す。ここでは、対象者には、自身のタスクを実行するための単一の対象車両３０が割り当てられていると仮定する。したがって、対象者のタスクリスト情報１０が示すタスクの全てが、単一の対象車両３０に割り当てられる。対象者に複数の車両が割り当てられている場合については後述する。

タスクリスト情報１０は、各対象者に予め用意されていてもよい。具体的には、各タスクリスト情報１０は、対応する対象者の識別子と対応付けて用意される。したがって、取得部２０２０は、対象車両３０の対象者の識別子に対応付けられたタスクリスト情報１０を取得する。

図６は、タスクリスト情報１０をテーブル形式で示す。タスクリスト情報１０には、対象者の識別子である作業者識別子１２が対応付けられている。タスクリスト情報１０は、タスク識別子１４と、タスク地点１６と、所要時間１８と、所要容量１９とを含む。

タスク識別子１４は、タスクの識別子を示す。タスク地点１６は、タスクのタスク地点を示す。タスクが荷物の受け取りである場合、タスク地点１６は、対象車両３０が荷物を受け取るために移動する地点を示す。所要時間１８は、タスクを実行するために対象車両３０がタスク地点に滞在しなければならないと推定される時間の長さを示す。タスクが荷物の受け取りである場合、所要時間１８は、対象車両３０がタスク地点で荷物を受け取るのに必要な時間を示しうる。所要容量１９は、対象車両３０がタスクを行うために必要な容量を示す。例えば、タスクが荷物の受け取りである場合、所要容量１９は、配送される荷物の量を示しうる。ここで、対象車両３０が１台である場合、対象車両３０の容量は、タスクリスト情報１０が示す所要容量１９の最大値よりも大きい必要がある。なお、対象車両３０の容量を考慮する必要がない場合（例えば、対象車両３０の容量が配送されるべき荷物の量よりもはるかに大きいことが事前に確実である場合）、タスクリスト情報１０は、所要容量１９を示す必要はない。

取得部２０２０がタスクリスト情報１０を取得する方法は様々ありうる。例えば、タスクリスト情報１０は、車両スケジューリング装置２０００がアクセス可能な記憶部に、対象者の識別子と対応付けて予め記憶されている。この場合、取得部２０２０は、記憶部から、対象車両３０の対象者の識別子に対応付けられたタスクリスト情報１０を取得する。なお、取得部２０２０は、対象車両３０の対象者の識別子を指定するユーザ入力を受信するなど、任意の方法で対象車両３０の対象者の識別子を取得する。

別の例では、取得部２０２０は、対象車両３０の対象者が操作するモバイルデバイスやＰＣなどの他のコンピュータから送信されてくるタスクリスト情報１０を受信することによって、タスクリスト情報１０を取得してもよい。

＜時間依存コスト行列１００の初期化：Ｓ１０４＞
生成部２０４０は、時間依存コスト行列１００を初期化する（Ｓ１０４）。時間依存コスト行列１００は、地点の各ペアおよび各時点についての最小の移動コストを示す。図７は、時間依存コスト行列１００を示す。時間依存コスト行列１００は、三次元行列であってもよく、それぞれ、セルの第１のインデックス（ｘ座標）は移動の開始地点を表し、セルの第２のインデックス（ｙ座標）は移動の終了地点を表し、セルの第３のインデックス（ｚ座標）は時点を表す。

コスト行列１００のセル（Ｓｉ，Ｓｊ，Ｔｋ）は、移動開始時刻をＴｋとして、地点Ｓｉから地点Ｓｊまでの最小の移動コストを示してもよい。例えば、図７に示す斜線で塗りつぶしたセルの座標は（Ｓ５，Ｓ７，Ｔ４）である。したがって、このセルが示す値は、移動開始時刻Ｔ４での地点Ｓ５からＳ７までの最小の移動コストを示す。

時間依存コスト行列１００を初期化するためには、地点の各ペアおよび各時点についてコストが最小となる経路を求める必要がある。そのために、生成部２０４０は、最初に、地点の各ペアおよび各時点についてコストが最小となる経路を示す時間依存経路行列を初期化しうる。

図８は、時間依存経路行列１１０を示す。なお、以下、「時間依存経路行列１１０」および「経路行列１１０」という用語は、相互に交換可能に使用される。経路行列１１０は、三次元行列であってもよく、それぞれ、セルの第１のインデックス（ｘ座標）は移動の開始地点を表し、セルの第２のインデックス（ｙ座標）は移動の終了地点を表し、セルの第３のインデックス（ｚ座標）は時点を表す。

時間依存経路行列１１０のセル（Ｓｉ，Ｓｊ，Ｔｋ）は、移動開始時刻をＴｋとして、地点Ｓｉから地点Ｓｊまでの移動コストが最小となる経路を示しうる。例えば、図８に示す斜線で塗りつぶしたセルの座標は（Ｓ５，Ｓ７，Ｔ４）である。したがって、このセルが示す値は、移動開始時刻Ｔ４での地点Ｓ５からＳ７までの移動コストが最小となる経路を示す。

経路行列１１０を初期化するとき、各経路のコストは経時的に一定であると仮定することができる。したがって、生成部２０４０は、開始地点と終了地点の各ペアについて、各経路のコストが一定であるマップ情報を使用して最短経路問題を解くことによって、そのペアが取り得る経路の中からコストが最小となる経路を決定する。マップ情報は、作業空間のグリッドマップを格納しうる。対象車両４０が作業空間を二次元的に移動する場合（例えば、対象車両３０が自動車である場合）、グリッド情報は、作業空間の床面の二次元グリッドマップを示す。対象車両３０が作業空間を三次元的に移動する場合（例えば、対象車両３０がドローンである場合）、グリッド情報は、作業空間の三次元グリッドマップを示す。グリッドマップはまた、各地点の位置、および壁、棚、または机などの恒久的な障害物も示す。

図９は、マップ情報が示すグリッドマップの一部を示す。図９のグリッドマップは、地点Ｓ１およびＳ２の位置を示している。さらに、恒久的な障害物の位置を斜線で示している。地点Ｓ１からＳ２までの各経路は、対象車両３０が移動することができる一連の位置（グリッド）によって表すことができる。

各経路のコストは経時的に一定であると仮定されるので、最短経路問題を解くための任意のアルゴリズム、例えばダイクストラアルゴリズム、Ａ＊探索アルゴリズム、または空間時間Ａ＊（space time A*）アルゴリズムを使用して、地点の各ペアの最短経路を見つけることができる。なお、以下で詳述するように、コストが経時的に変動する場合には、空間時間Ａ＊アルゴリズムのような時間依存コストを扱うことができるアルゴリズムを使用して最短経路問題が解かれる。

時間依存経路行列１１０が初期化された後、生成部２０４０は、時間依存経路行列１１０に基づいて時間依存コスト行列１００を初期化する。具体的には、時間依存コスト行列１００の各セルは、時間依存経路行列の対応するセルによって示される経路のコストを示すべきである。したがって、生成部２０４０は、ｉ、ｊ、ｋの各ペアについて、時間依存経路行列１００のセル（Ｓｉ，Ｓｊ，Ｔｋ）が示すコストを、時間依存コスト行列１００のセル（Ｓｉ，Ｓｊ，Ｔｋ）に設定する。

＜スケジュール情報の生成：Ｓ１０６～Ｓ１１０＞
生成部２０４０は、タスクの実行順序を決定し（Ｓ１０６）、各タスクにタスク経路を選択すること（Ｓ１０８）により、スケジュール情報２０を生成する（Ｓ１１０）。図１０は、スケジュール情報２０をテーブル形式で示す。スケジュール情報２０は、各タスクについて、タスク識別子２２、タスク地点２４、タスク経路２６、および開始時刻２８の４種類のデータを含む。

タスク識別子２２は、タスクの識別子を示す。対象地点２４は、対象車両３０がそのタスクを実行する地点を示す。タスク経路２６は、対象車両３０がタスク地点まで移動するタスク経路を示す。開始時刻２８は、タスクがタスク地点までの移動を開始する時刻を示す。スケジュール情報２０では、タスクの実行順序を分かりやすくするために、開始時刻の昇順にタスクがソートされることが好ましい。

生成部２０４０は、TDVRP を時間依存コスト行列１００を用いて解くことにより、対象車両３０に割り当てられたタスクの実行順序を決定する。TDVRP を解くためには、出発地、目的地、実行されるべきタスクのリスト、対象車両３０の容量、および時間依存コスト関数を、TDVRP を解くアルゴリズムに与える必要がある。出発地は、対象車両３０の初期位置である。目的地は、全ての作業が終了したときに対象車両３０が移動する位置である。例えば、作業空間内の車両の保管場所を出発地および目的地として設定してもよい。

生成部２０４０は、実行されるべきタスクのリストとして、タスクリスト情報１０を使用する。さらに、生成部２０４０は、時間依存コスト関数として、時間依存コスト行列１００を使用する。対象車両３０の出発地、目的地、および容量については、対象車両３０に対応付けて予め定義されていてもよい。したがって、生成部２０４０は、例えば、予め情報が記憶されている記憶部部から、対象車両３０の出発地、目的地、および容量を示す情報（以下、車両情報と呼ぶ）を取得してもよい。

生成部２０４０は、TDVRP の解として、対象車両３０に実行させるタスクの実行順序を得る。ここで、TDVRP を解くアルゴリズムには様々なものがありうる。例の１つは、混合整数線形計画法（MILP: Mixed Integer Linear Programming）である。別の例では、Tabu 探索アルゴリズムまたは反復局所探索アルゴリズムなどのメタヒューリスティックアルゴリズムも採用することもできる。生成部２０４０は、これらのアルゴリズムのいずれを使用してもよい。

生成部２０４０は、タスクの実行順序を決定した後、各タスクのタスク経路を選択する。例えば、生成部２０４０は、時間依存経路行列１１０を使用する。具体的には、生成部２０４０は、各タスクについて、時間依存経路行列１１０から、タスクの開始地点、タスク地点および開始時刻に対応するセルが示す経路を抽出し、抽出した経路をそのタスクのタスク経路として設定する。ここで、タスクの開始地点は、前回のタスクのタスク地点である。

（ｎ－１）番目のタスクが、時刻Ｔｎ－１に地点Ｓｎ－１まで移動して荷物を受け取ることを含み、ｎ番目のタスクが、時刻Ｔｎに地点Ｓｎまで移動して荷物を降ろすことを含むとする。この場合、経路行列１１０のセル（Ｓｎ－１，Ｓｎ，Ｔｎ）が示す経路が、ｎ番目のタスクのタスク経路として使用される。

タスクの開始時刻は、最初のタスクから前回のタスクまでの移動時間と所要時間（例えば、荷物を受け取るのに必要な時間）との和として計算することができる。タスクの移動時間は、タスク経路のコストおよび対象車両３０の速度を使用して計算することができる。タスクの開始時刻の計算は、以下のように定式化することができる：

式中、ＳＴｎは第ｎのタスクの開始時刻であり、Ｃａは、ａ番目のタスクのタスク経路のコストであり、ｖは、対象車両３０の速度であり、ｆ（）は、経路のコストと対象車両３０の速度とに基づいて、経路を移動するための移動時間を計算する関数であり、そして、Ｒａはａ番目のタスクの所要時間である。

生成部２０４０は、各タスクのタスク経路を選択した後、上記のように決定されたタスクの実行順序および各経路のタスク経路を示すスケジュール情報２０を生成する。

＜競合検出：Ｓ１１２＞
競合検出部２０６０は、対象車両３０に対して競合検出を行う（Ｓ１１２）。競合として扱うことができる状況には２つの種類があり得る。第１の種類の競合は、対象車両３０と一時的な障害物とが互いに同じ時点で同じ位置を占有するようにスケジュールされる頂点競合（vertex conflict）と呼ばれている。

一時的な障害物は、恒久的ではなく一時的に作業空間の特定の領域を占有する種類の障害物である。例えば、一時的な障害物は、対象車両３０以外の対象者に割り当てられた、既にスケジュール情報２０が生成されている車両でありうる。別の例では、一時的な障害物は、機器を操作するなど、何かを行うために作業空間の特定の領域を占有することがスケジュールされた人であってもよい。

時刻Ｔ２～Ｔ４の間、対象車両Ｖ１が地点Ｓ１で作業を行うことがスケジュールされているとする。さらに、別の車両Ｖ２は、時刻Ｔ１～Ｔ３（Ｔ１＜Ｔ２＜Ｔ３＜Ｔ４）の間、地点Ｓ１で作業を行うことがスケジュールされている。この場合、車両Ｖ１およびＶ２は、時刻Ｔ２～Ｔ３の間に同じ位置Ｓ１を占有するため、時刻Ｔ２～Ｔ３の間に頂点競合を有する。

第２の種類の競合は、２台の車両が互いに交差するようにスケジュールされるエッジ競合と呼ばれている。時刻Ｔ１～Ｔ２の間に、対象車両Ｖ１が位置ＡからＢへ移動するとする。同時に、時刻Ｔ１～Ｔ２の間に、別の車両Ｖ２が位置ＢからＡに移動する。この場合、車両Ｖ１およびＶ２は同じ時点で同じ位置を占有しないが、それでもなお互いに交差する間に競合する（クロスオーバー競合としても知られる）。

競合検出部２０６０は、一時的な障害物ごとに、作業空間の一定の領域を占有するイベントのスケジュールを示すイベント情報を得る。具体的には、イベント情報は、各時点における一時的な障害物の位置を示しうる。いくつかのイベント情報は、例えば、車両スケジューリング装置２０００がアクセス可能な記憶部に予め記憶されている。ここで、一時的な障害物が車両である場合、競合検出部２０６０は、その一時的な障害物のスケジュール情報２０をイベント情報として使用する。

競合検出部２０６０は、一時的な障害物ごとに、対象車両３０のスケジュール情報２０と一時的な障害物のイベント情報とを使用して、対象車両の位置と一時的な障害物の位置とを各時点で比較することにより、対象車両３０が一時的な障害物と互いに競合するか否か（言い換えれば、同じ時刻に同じ場所に位置することがスケジュールされているか否か）を決定する。競合検出部２０６０は、対象車両３０が一時的な障害物と互いに競合していると決定した場合、検出された競合に関する情報を競合情報に追加する。競合情報は、競合の位置および期間を示す。ここで、競合情報は、競合検出を開始する前に空に初期化される。

＜コスト行列１００の更新：Ｓ１１４＞
対象車両３０について１つ以上の競合が検出された場合（Ｓ１１２：はい）、更新部２０８０は、競合情報に基づいて時間依存コスト行列１１０を更新する。更新部２０８０は、時間依存経路行列１１０を使用して時間依存コスト行列１００を更新することができる。この場合、更新部２０８０は、最初に、空間時間Ａ＊アルゴリズムなどの時間依存コストを扱うことができるアルゴリズムで最短経路問題を解くことによって時間依存経路行列１１０を更新しうる。

空間時間Ａ＊アルゴリズムは、各時点について各障害物の位置を示す時間依存グリッドマップである、予約テーブルと呼ばれるデータ構造を扱う。マップ情報によって示される恒久的な障害物は、予約テーブルにおいて、各時点において１つ以上のグリッドを占有する障害物として扱われる。一方、競合情報によって示される競合は、予約テーブルにおいて、その位置で競合が発生している間にのみ１つ以上のグリッドを占有する障害物として扱われる。

更新部２０８０は、マップ情報と競合情報とを使用して予約テーブルを生成する。具体的には、マップ情報が示す恒久的な障害物ごとに、更新部２０８０は、各時点でのマップ情報における恒久的な障害物の位置に対応する予約テーブルの位置に、恒久的な障害物を設置する。さらに、競合情報によって示される競合ごとに、更新部２０８０は、競合情報によって示される期間中の競合情報の競合の位置に対応する予約テーブル内の位置に、障害物として各競合を設置する。

図１１は、予約テーブルの例を示す。この例では、予約テーブルは、時刻Ｔ０からＴｎまでの時間依存グリッドマップ１２０を示す。マップ情報には、（１，１）および（２，４）の位置に恒久的な障害物が示されている。競合情報は、時刻Ｔａ～Ｔｂに位置（３，２）で発生する競合Ａと、時刻Ｔｃ～Ｔｄに位置（４，３）で発生する競合Ｂとを示している（Ｔ０＜Ｔａ＜Ｔｂ＜Ｔｃ＜Ｔｄ＜Ｔｎ）。

この場合、時刻Ｔ０からＴａまでの間、位置（１，１）および（２，４）にある恒久的な障害物が予約テーブルに示されている。時刻ＴａからＴｂまで、予約テーブルは、位置（３，２）にある競合Ａをさらに示す。時刻ＴｂからＴｃまで、予約テーブルは再び２つの恒久的な障害物のみを示す。次いで、時刻ＴｃからＴｄまで、予約テーブルは、位置（４，３）にある競合Ｂをさらに示す。時刻Ｔｄの後、予約テーブルは再び２つの恒久的な障害物のみを示す。

予約テーブルは、地点の各ペアについて生成される。次いで、更新部２０８０は、地点の各ペアについて予約テーブルを使用して最短経路問題を解く。これにより、更新部２０８０は、地点の各ペアおよび各時点についてコストが最小となる経路を求めることで、時間依存経路行列１１０を更新する。ここで、地点のペアの経路上で競合が検出されない場合には、そのペアの経路を更新する必要はない。

時間依存経路行列１１０を更新した後、更新部２０８０は、更新された経路行列１１０に基づいて時間依存コスト行列１１０を更新する。ここで、時間依存経路行列１１０に基づく時間依存コスト行列１００の更新は、上述した時間依存経路行列１１０に基づく時間依存コスト行列１００の初期化と同様に行うことができる。

＜スケジュール情報２０の出力：Ｓ１１６＞
競合検出部２０６０により競合が検出されなかった場合（Ｓ１１２：いいえ）、車両スケジューリング装置２０００は、スケジュール情報２０を出力する。スケジュール情報２０は、様々な方法で出力が可能である。例えば、車両スケジューリング装置２０００は、スケジュール情報２０を記憶部に格納しうる。別の例では、車両スケジューリング装置２０００は、ディスプレイ装置にスケジュール情報２０を表示させるように、スケジュール情報２０をディスプレイ装置に出力しうる。別の例では、車両スケジューリング装置２０００は、対象者によって操作されるモバイルデバイスまたはＰＣなどの別のコンピュータにスケジュール情報２０を送信しうる。ここで、スケジュール情報２０は、対象車両３０の識別子と対応付けて出力されることが好ましい。

＜複数の対象車両３０の扱い方＞
対象者には、２台以上の対象車両３０が割り当てられてもよい。この場合は、対象者に単一の対象車両３０が割り当てられている場合とは異なり、対象車両３０が互いに競合する可能性がある。以下、複数の対象車両３０の扱い方が記述される。

図１２は、複数の対象車両３０が対象者に割り当てられている場合の、車両スケジューリング装置２０００が行う処理の一例を示すフローチャートである。取得部２０２０は、タスクリスト情報１０を取得する（Ｓ２０２）。次いで、生成部２０４０は、時間依存コスト行列１００および時間依存経路行列を初期化する（Ｓ２０４）。これらの処理は、対象者に単一の対象車両３０が割り当てられている場合と同様に行われる。

生成部２０４０は、各対象車両３０についてタスクの実行順序を決定する（Ｓ２０６）。各対象車両３０についてタスクの実行順序を決定するためには、各対象車両３０に対するタスクの割り当てを決定する必要がある。この点に関して、TDVRP を解くことにより、各対象車両３０に対するタスクの割り当てと、各対象車両３０に対するタスクの実行順序の決定とを同時に行うことができる。具体的には、TDVRP を解くアルゴリズムは、さらに、車両の台数および各車両の容量を入力とし、各車両に対するタスクの実行順序を出力する。したがって、生成部２０４０は、TDVRP を解いた結果、各対象車両３０についてタスクの実行順序を得ることができる。ここで、対象車両３０の台数および各車両の容量は、上述した車両情報に含まれうる。

生成部２０４０は、各対象車両３０に対するタスクの実行順序を決定した後、各タスクのタスク経路を選択する（Ｓ２０８）。タスク経路の選択は、対象者に単一の対象車両３０が割り当てられている場合と同様に、時間依存経路行列１１０を使用して行われる。各タスクにタスク経路が選択された結果、生成部２０４０は、各対象車両３０についてスケジュール情報２０を生成する（Ｓ２１０）。

検出部２０６０は、競合検出を行う。対象者に複数の対象車両３０が割り当てられている場合、内部競合および外部競合の２つの種類の競合が発生する可能性がある。内部競合は、対象車両３０間の競合である。一方で、外部競合は、対象車両３０と一時的な障害物との間の競合であり、これについては既に上述されている。

検出部２０６０は、最初に、内部競合の検出を行いうる（Ｓ２１２）。検出部２０６０は、対象車両３０の各ペアについて、それらのスケジュール情報２０を比較することにより、それらの内部競合を検出する。具体的には、２台の対象車両３０が同じ場所に同時に位置するようにスケジュールされている場合、それらは互いに競合する。

内部競合が検出された場合（Ｓ２１２：はい）、更新部２０８０は、検出された内部競合に基づいてコスト行列１００および経路行列１１０を更新する（Ｓ２１４）。検出された内部競合に基づいて経路行列１１０を更新するために、更新部２０８０は、内部競合の解消を行い、それにより、内部競合が検出された地点のペアについてコストが最小となる新しい経路を計算する。検出部２０６０は、非特許文献３によって開示されている競合ベースの探索アルゴリズムなど、任意の内部競合解消アルゴリズムを使用することができる。

内部競合の解消の結果、内部競合が検出された地点のペアについて、コストが最小となる経路が更新される。したがって、更新部２０８０は、内部競合の解消の結果に基づいて時間依存経路行列１１０を更新する。更新部２０８０はまた、更新された経路行列１１０に基づいて時間依存コスト行列１００を更新する。更新された経路行列１１０に基づいてコスト行列１００を更新する方法は、初期化された経路行列１１０に基づいてコスト行列１００を初期化する方法と同じである。

内部競合が検出されない場合（Ｓ２１２：いいえ）、競合検出部２０６０は、外部競合の検出を行う（Ｓ２１６）。外部競合（すなわち、対象車両３０と一時的な障害物との間の競合）を検出する方法は、既に上述されている。対象車両３０は複数存在するため、外部競合の検出は各対象車両３０について行われることに留意されたい。

外部競合が検出されない場合（Ｓ２１６：いいえ）、車両スケジューリング装置２０００は、この場合は競合が検出されないので、スケジュール情報２０を出力する（Ｓ２２０）。一方で、外部競合が検出された場合（Ｓ２１６：はい）、更新部２０８０は、検出された外部競合に基づいて、時間依存コスト行列１００および時間依存経路行列１１０を更新する（Ｓ２１８）。この処理は、対象者に単一の対象車両３０が割り当てられている場合と同様に行うことができる。

時間依存コスト行列１００および時間依存経路行列１１０が更新された後（Ｓ２１４またはＳ２１８）、装置２０００は、タスクの実行順序を決定し、各タスクのタスク経路を選択し、スケジュール情報２０を再度生成する（Ｓ２０６、Ｓ２０８、およびＳ２１０）。次いで、再度、内部競合および外部競合の検出を行う（Ｓ２１２およびＳ２１６）。これらの処理の繰り返し実行は、競合が検出されなくなる（Ｓ２１６：いいえ）まで継続される。

＜他車両のスケジュール情報の修正＞
上記の説明では、競合を回避するために更新されるのは対象車両３０のスケジュール情報２０である。しかしながら、対象車両３０が対象車両３０以外の車両（以下、障害車両と呼ぶ）と競合する場合には、対象車両３０のスケジュール情報２０に代えて障害車両のスケジュール情報２０を更新することで競合を回避してもよい。

対象車両３０が、スケジュール情報２０が確定されて記憶部に記憶されている車両Ｖ１と競合していることが検出されたとする。この場合、車両Ｖ１のスケジュール情報２０を更新し、その一方で対象車両３０のスケジュール情報２０を確定することで、競合を回避することができる。

更新部２０８０は、対象車両３０と障害車両との間で外部競合が検出された場合、障害車両のスケジュール情報２０の更新が承認されたか否かを確認してもよい。承認された場合、上述した対象車両３０のスケジュール情報２０の繰り返し更新と同様にして、競合が検出されなくなるまで、障害車両のスケジュール情報２０を繰り返し更新する。この場合、車両スケジューリング装置２０００は、競合に基づいて対象車両３０のスケジュール情報２０を更新することなく、スケジュール情報２０を出力する。さらに、車両スケジューリング装置２０００は、競合が検出されなくなるまで障害車両のスケジュール情報２０を更新した後、スケジュール情報２０を出力する。障害車両のスケジュール情報２０の更新が承認されない場合、車両スケジューリング装置２０００は、競合が検出されなくなるまで、対象車両３０のスケジュール情報２０を繰り返し生成する。

車両スケジューリング装置２０００が障害車両のスケジュール情報２０の更新の承認を確認する方法は様々である。例えば、車両スケジューリング装置２０００は、障害車両に予め対応付けられたアドレス、例えば障害車両の操作者のメールアドレスに、スケジュール情報２０の更新の承認要求を送信する。この場合、車両スケジューリング装置２０００は、要求に対する応答を受信し、その応答が障害車両のスケジュール情報２０の更新を承認することを示すか否かを確認する。車両スケジューリング装置２０００は、応答が障害車両のスケジュール情報２０の更新を承認することを示す場合、障害車両のスケジュール情報２０の繰り返し更新を行う。

別の例では、スケジュール情報２０は、その更新が承認されるか否かを示す承認フラグを有してもよい。この場合、車両スケジューリング装置２０００は、その更新が承認されること示す、障害車両のスケジュール情報２０の承認フラグがあるか否かを確認する。障害車両のスケジュール情報２０の承認フラグがその更新を承認することを示す場合、車両スケジューリング装置２０００は、障害車両のスケジュール情報２０の繰り返し更新を行う。承認フラグの値は、障害車両の操作者によって予め設定されてもよい。

実施形態２
＜概要＞
図１３は、実施形態２の車両スケジューリング装置２０００の概要を示す。ここで、図１３に示す概要は、車両スケジューリング装置２０００を理解しやすくするために車両スケジューリング装置２０００の動作の一例を示したものであり、車両スケジューリング装置２０００の可能な動作の範囲を限定したり狭めたりするものではない。

実施形態２の車両スケジューリング装置２０００は、地点の各ペアの移動コストが経時的に一定であると仮定する点で、実施形態１とは異なる。したがって、この実施形態の車両スケジューリング装置２０００は、時間依存コスト行列１００の代わりに、対象車両３０がいつ移動を開始するかにかかわらず一定である、地点の各ペアの移動コストを示す時間非依存コスト行列２００を採用する。

コストは経時的に一定であると仮定されるので、時間非依存コストを扱う任意の VRP を解くことによって、対象車両３０に割り当てられたタスクの実行順序を決定することができる。例えば、車両の容量を考慮する場合、容量性 VRP（capacitated VRP）が採用される。この場合、対象車両３０に割り当てられたタスクの実行順序は、 CVRP の解として得られる。

競合が検出されると、車両スケジューリング装置２０００は、競合に基づいて時間非依存コスト行列２００を更新する。時間非依存コスト行列２００は時間ベースのコストを扱わないので、時間非依存コスト行列２００は、一時的な障害物を恒久的な障害物と同様に扱う。具体的には、競合が検出された位置は、競合がいつ発生したかにかかわらず、障害物によって占有されていると見なされる。

＜作用効果の例＞
実施形態１の車両スケジューリング装置２０００と同様に、実施形態２の車両スケジューリング装置２０００は、対象車両３０が一時的な障害物と競合しなくなるまで、対象車両３０のタスクの実行スケジュールを繰り返し更新する。したがって、実施形態２の車両スケジューリング装置２０００は、実施形態２の車両スケジューリング装置２０００と同様の理由により、各車両のタスクの実行スケジュールを効率的に生成することができる。さらに、実施形態２の車両スケジューリング装置２０００は、時間非依存コストを用いて VRDP を解く方が TDVRP を解くよりも時間がかからない可能性が高いので、スケジュール情報２０を確定するために実施形態１よりも時間がかからない可能性が高い。

以下、車両スケジューリング装置２０００のより詳細な説明について説明する。

＜機能構成の例＞
実施形態２の車両スケジューリング装置２０００は、実施形態１の車両スケジューリング装置２０００と同様の機能構成を有してもよい。したがって、車両スケジューリング装置２０００の機能構成の一例も図３に示すことができる。

実施形態２の生成部２０４０は、タスクの実行順序を決定するために、TDVRP ではなく時間非依存コストを用いて VRP を解く点において、実施形態１と異なる。さらに、時間依存コスト行列１００ではなく、時間非依存コスト行列２００を使用する。実施形態２の更新部２０８０は、検出された競合に基づいて、時間依存コスト行列１００ではなく、時間非依存コスト行列２００を更新する点で、実施形態１と異なる。

＜ハードウェア構成の例＞
実施形態２の車両スケジューリング装置２０００は、実施形態２の車両スケジューリング装置２０００を実現するものと同様の１つ以上のコンピュータによって実現されてもよい。したがって、そのハードウェア構成も図４に示すことができる。

＜処理の流れ＞
図１４は、実施形態２の車両スケジューリング装置２０００が行う処理の一例を示すフローチャートである。図１４において、境界が太線の処理（ステップＳ３０４、Ｓ３０６、Ｓ３０８、およびＳ３１４）は、図５に示す実施形態１の対応する処理とは異なる。

取得部２０２０は、タスクリスト情報１０を取得する（Ｓ３０２）。生成部２０４０は、時間非依存コスト行列２００を初期化する（Ｓ３０４）。生成部２０４０は、時間非依存コスト行列２００を使用してタスクの実行順序を決定する（Ｓ３０６）。生成部２０４０は、各タスクのタスク経路を選択する（Ｓ３０８）。生成部２０４０は、スケジュール情報２０を生成する（Ｓ３１０）。競合検出部２０６０は、スケジュール情報２０を使用して競合検出を行う（Ｓ３１２）。競合が検出されない場合（Ｓ３１２：いいえ）、車両スケジューリング装置２０００は、スケジュール情報２０を出力する（Ｓ３１６）。一方、競合が検出された場合（Ｓ３１２：はい）、更新部２０８０は、検出された競合に基づいて時間非依存コスト行列２００を更新する（Ｓ３１４）。

時間非依存コスト行列２００の更新後、車両スケジューリング装置２０００の処理はステップＳ３０６に戻る。これにより、ステップＳ３１２で競合が検出されなくなるまで、スケジュール情報２０の生成（Ｓ３０６～Ｓ３１０）、競合検出（Ｓ３１２）、および時間非依存コスト行列２００の更新（Ｓ３１４）が繰り返し行われる。

＜タスクリスト情報の取得：Ｓ３０２＞
取得部２０２０は、実施形態１と同様にして、タスクリスト情報１０を取得する。

＜時間非依存コスト行列２００の初期化：Ｓ３０４＞
生成部２０４０は、時間非依存コスト行列２００を初期化する（Ｓ３０４）。時間非依存コスト行列２００は、各々が経時的に一定である地点の各ペアについての最小の移動コストを示す。図１５は、時間非依存コスト行列２００を示す。時間非依存コスト行列２００は、二次元行列であってもよく、それぞれ、セルの第１のインデックス（ｘ座標）は移動の開始地点を表し、セルの第２のインデックス（ｙ座標）は移動の終了地点を表す。

コスト行列２００のセル（Ｓｉ，Ｓｊ）は、地点Ｓｉから地点Ｓｊまでの最小の移動コストを示すことができる。例えば、図１５に示す斜線で塗りつぶしたセルの座標は（Ｓ５，Ｓ７）である。したがって、このセルが示す値は、地点Ｓ５からＳ７までの最小の移動コストを示す。

時間非依存コスト行列２００を初期化するために、実施形態２の生成部２０４０は、実施形態１の生成部２０４０が時間依存経路行列１１０を使用するのと同様に、時間非依存経路行列を使用してもよい。時間非依存経路行列は、経時的に一定である、地点の各ペアのコストが最小となる経路を示す。

図１６は、時間非依存経路行列２１０を示す。ここで、以下、「時間非依存経路行列２１０」および「経路行列２１０」という用語は、互いに交換可能に使用される。経路行列２１０は、二次元行列であってもよく、それぞれ、セルの第１のインデックス（ｘ座標）は移動の開始地点を表し、セルの第２のインデックス（ｙ座標）は移動の終了地点を表す。

時間非依存経路行列２１０のセル（Ｓｉ，Ｓｊ）は、地点Ｓｉから地点Ｓｊまでの移動コストが最小となる経路を示すことができる。例えば、図１６に示す斜線で塗りつぶしたセルの座標は（Ｓ５，Ｓ７）である。したがって、このセルが示す値は、地点Ｓ５からＳ７までの移動コストが最小となる経路を示す。

開始地点と終了地点の各ペアについて、生成部２０４０は、上述したマップ情報を使用して最短経路問題を解くことによって、そのペアが取り得る経路の中からコストが最小となる経路を決定する。各経路のコストは経時的に一定であると仮定されるので、最短経路問題を解くための任意のアルゴリズム、例えばダイクストラアルゴリズム、Ａ＊探索アルゴリズム、または空間時間Ａ＊アルゴリズムを使用して、地点の各ペアの最短経路を見つけることができる。

時間非依存経路行列２１０が初期化された後、生成部２０４０は、時間依存経路行列１１０に基づいて時間依存コスト行列１００を初期化するのと同様の方法で、時間非依存経路行列２１０に基づいて時間非依存コスト行列２００を初期化する。具体的には、時間非依存コスト行列２００の各セルは、時間非依存経路行列２１０の対応するセルによって示される経路のコストを示すはずである。したがって、生成部２０４０は、ｉおよびｊの各ペアについて、時間非依存経路行列２１０のセル（Ｓｉ，Ｓｊ）が示すコストを、時間非依存コスト行列２００のセル（Ｓｉ，Ｓｊ）に設定する。

＜スケジュール情報の生成：Ｓ３０６～Ｓ３１０＞
生成部２０４０は、タスクの実行順序を決定し（Ｓ３０６）、各タスクのタスク経路を選択すること（Ｓ３０８）により、スケジュール情報２０を生成する（Ｓ３１０）。生成部２０４０は、VRP を時間非依存コスト行列２００を用いて解くことにより、対象車両３０に割り当てられたタスクの実行順序を決定する。時間非依存コストを用いて VRP を解くためには、出発地、目的地、実行されるべきタスクのリスト、および時間非依存コスト関数を、VRP を解くためのアルゴリズムに与える必要がある。なお、CVRP を採用する場合、対象車両３０の容量もアルゴリズムに与えられる。出発地、目的地、および実行されるべきタスクのリストの説明については、実施形態１で説明した通りである。生成部２０４０は、時間非依存コスト関数として、時間非依存コスト行列２００を使用する。

生成部２０４０は、VRP の解として、対象車両３０に実行させるタスクの実行順序を得る。ここで、VRP を解くアルゴリズムには様々なものがある。例えば、VRP を解くために、MILP や、Tabu探索アルゴリズムまたは反復局所探索アルゴリズムなどのメタヒューリスティックアルゴリズムを採用することができる。

生成部２０４０は、タスクの実行順序を決定した後、各タスクのタスク経路を選択する。この実施形態では、生成部２０４０は、時間非依存経路行列２１０を使用することができる。具体的には、生成部２０４０は、各タスクについて、時間非依存経路行列２１０から、タスクの開始地点およびタスク地点に対応するセルが示す経路を抽出し、抽出した経路をそのタスクのタスク経路として設定する。

（ｎ－１）番目のタスクが、地点Ｓｎ－１まで移動して荷物を受け取ることを含み、ｎ番目のタスクが、地点Ｓｎまで移動して荷物を降ろすことを含むとする。この場合、経路行列２１０のセル（Ｓｎ－１，Ｓｎ）が示す経路が、ｎ番目のタスクのタスク経路として使用される。

実施形態２の生成部２０４０は、各タスクにタスク経路を選択した後、の実施形態１と同様にスケジュール情報２０を生成する。

＜競合検出：Ｓ３１２＞
競合検出部２０６０は、対象車両３０に対して競合検出を行う（Ｓ３１２）。実施形態２の競合検出部２０６０は、実施形態１と同様に競合を検出する。

＜コスト行列２００の更新：Ｓ３１４＞
対象車両３０について１つ以上の競合が検出された場合（Ｓ３１２：はい）、更新部２０８０は、競合情報に基づいて時間非依存コスト行列２００を更新する。更新部２０８０は、時間非依存経路行列２１０を使用して時間非依存コスト行列２００を更新することができる。この場合、更新部２０８０は、最初に、最短経路問題を任意のアルゴリズムを用いて解くことにより、時間非依存経路行列２１０を更新してもよい。

検出された競合を最短経路問題の解に反映させるために、更新部２０８０は、マップ情報と競合情報とに基づいて時間非依存グリッドマップを生成し、これを最短経路問題を解くアルゴリズムに入力する。この時間非依存グリッドマップは、競合が検出された位置に対応するグリッドに障害物があることを除いて、マップ情報によって示されるグリッドマップと同じである。

図１７は、時間非依存グリッドマップ２２０を示す。この例では、マップ情報には、位置（１，１）、（２，４）に恒久的な障害物が示されているものと仮定する。さらに、競合情報は、時刻Ｔａ～Ｔｂに位置（３，２）で発生する競合Ａと、時刻Ｔｃ～Ｔｄに位置（４，３）で発生する競合Ｂとを示している（Ｔ０＜Ｔａ＜Ｔｂ＜Ｔｃ＜Ｔｄ＜Ｔｎ）。

この場合、時間非依存グリッドマップ２２０には、マップ情報が示す（１，１）および（２，４）の位置にある障害物が示されている。さらに、競合Ａに対応する（３，２）の障害物、および競合Ｂに対応する（４，３）の障害物も示されている。

時間非依存グリッドマップ２２０は、地点の各ペアについて生成される。次いで、更新部２０８０は、地点の各ペアについて、時間非依存グリッドマップ２２０を使用して最短経路問題を解く。これにより、更新部２０８０は、地点の各ペアについてコストが最小となる経路を求めることで、時間非依存経路行列２１０を更新する。

時間非依存経路行列２１０を更新した後、更新部２０８０は、更新された経路行列２１０に基づいて時間非依存コスト行列２００を更新する。ここで、時間非依存経路行列２１０に基づく時間非依存コスト行列２００の更新は、上述した時間非依存経路行列２１０に基づく時間非依存コスト行列２００の初期化と同様に行うことができる。

＜スケジュール情報２０の出力：Ｓ３１６＞
競合検出部２０６０により競合が検出されなかった場合（Ｓ３１２：いいえ）、車両スケジューリング装置２０００は、スケジュール情報２０を出力する（Ｓ３１６）。実施形態２のスケジュール情報２０は、実施形態１と同様に出力される。

＜複数の対象車両３０の扱い方＞
実施形態２の車両スケジューリング装置２０００は、地点間の移動コストが経時的に一定であると仮定されることを除いて、実施形態１と同様に複数の対象車両３０を扱う。図１８は、対象者に複数の対象車両３０が割り当てられた場合の、実施形態２の車両スケジューリング装置２０００が行う処理の一例を示すフローチャートである。図１８において、境界が太線の処理（ステップＳ４０４、Ｓ４０６、Ｓ４０８、Ｓ４１４、およびＳ４１８）は、図１２に示す実施形態１と異なる。

取得部２０２０は、タスクリスト情報１０を取得する（Ｓ４０２）。次いで、生成部２０４０は、時間非依存コスト行列２００および時間非依存経路行列２１０を初期化する（Ｓ４０４）。これらの処理は、対象者に単一の対象車両３０が割り当てられている場合と同様に行われる。

生成部２０４０は、各対象車両３０に対するタスクの実行順序を決定する（Ｓ４０６）。生成部２０４０は、実施形態１と同様に、VRP を解くことにより、各対象車両３０に対するタスクの割り当てと、各対象車両３０に対するタスクの実行順序の決定とを同時に行うことができる。具体的には、VRP を解くアルゴリズムは、さらに、車両の台数を入力とし、各車両に対するタスクの実行順序を出力する。したがって、生成部２０４０は、VRP を解いた結果、各対象車両３０についてタスクの実行順序を得ることができる。ここで、CVRP を採用する場合、CVRP を解くアルゴリズムに各車両の容量も与えられる。

生成部２０４０は、各対象車両３０に対するタスクの実行順序を決定した後、各タスクに対するタスク経路を選択する（Ｓ４０８）。タスク経路の選択は、対象者に単一の対象車両３０が割り当てられている場合と同様に、時間非依存経路行列２１０を使用して行われる。各タスクのタスク経路が選択された結果、生成部２０４０は、各対象車両３０についてスケジュール情報２０を生成する（Ｓ４１０）。

次いで、検出部２０６０は、内部競合の検出を行いうる（Ｓ４１２）。内部競合が検出された場合（Ｓ４１２：はい）、更新部２０８０は、検出された内部競合に基づいてコスト行列２００および経路行列２１０を更新する（Ｓ４１４）。実施形態２の更新部２０８０は、実施形態１と同様に、内部競合の解消を行うことにより、内部競合が検出された地点のペアについて、コストが最小となる新たな経路を計算する。更新部２０８０は、内部競合の解消の結果に基づいて時間非依存経路行列２１０を更新する。更新部２０８０はまた、更新された経路行列２１０に基づいて時間非依存コスト行列２００を更新する。

内部競合が検出されない場合（Ｓ４１２：いいえ）、競合検出部２０６０は、実施形態１と同様に、外部競合の検出を行う（Ｓ４１６）。

外部競合が検出されない場合（Ｓ４１６：いいえ）、車両スケジューリング装置２０００は、この場合は競合が検出されないので、スケジュール情報２０を出力する（Ｓ４２０）。一方で、外部競合が検出された場合（Ｓ４１６：はい）、更新部２０８０は、検出された外部競合に基づいて、時間非依存コスト行列２００および時間非依存経路行列２１０を更新する（Ｓ４１８）。この処理は、対象者に単一の対象車両３０が割り当てられている場合と同様に行うことができる。

時間非依存コスト行列２００および時間非依存経路行列２１０が更新された後（Ｓ４１４またはＳ４１８）、装置２０００は、タスクの実行順序を決定し、各タスクのタスク経路を選択し、スケジュール情報２０を再度生成する（Ｓ４０６、Ｓ４０８、およびＳ４１０）。次いで、再度、内部競合および外部競合の検出を行う（Ｓ４１２、Ｓ４１６）。これらの処理の繰り返し実行は、競合が検出されなくなる（Ｓ４１６：いいえ）まで継続される。

＜他車両のスケジュール情報の修正＞
実施形態１の車両スケジューリング装置２０００と同様に、実施形態２の車両スケジューリング装置２０００は、対象車両と競合する障害車両のスケジュール情報２０を、その更新が承認される場合に繰り返し更新してもよい。

以上、実施の形態を参照して本開示を説明したが、本開示は上記の実施の形態に限定されるものではない。本開示の構成および詳細には、本発明の範囲内で当業者が理解し得る様々な変更を行うことができる。

本開示で言及されるプログラムは、コンピュータに読み込まれた場合に、実施形態で説明された１又はそれ以上の機能をコンピュータに行わせるための命令群（又はソフトウェアコード）を含む。プログラムは、非一時的なコンピュータ可読媒体又は実体のある記憶媒体に格納されてもよい。限定ではなく例として、コンピュータ可読媒体又は実体のある記憶媒体は、random-access memory（RAM）、read-only memory（ROM）、フラッシュメモリ、solid-state drive（SSD）又はその他のメモリ技術、CD-ROM、digital versatile disc（DVD）、Blu-ray（登録商標）ディスク又はその他の光ディスクストレージ、磁気カセット、磁気テープ、磁気ディスクストレージ又はその他の磁気ストレージデバイスを含む。プログラムは、一時的なコンピュータ可読媒体又は通信媒体上で送信されてもよい。限定ではなく例として、一時的なコンピュータ可読媒体又は通信媒体は、電気的、光学的、音響的、またはその他の形式の伝搬信号を含む。

上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
＜付記＞
（付記１）
少なくとも１つのプロセッサと、
命令を記憶するメモリと
を備える車両スケジューリング装置であって、前記少なくとも１つのプロセッサが、前記命令を実行して、
少なくとも１台の対象車両が割り当てられた対象者に割り当てられたタスクを示すタスクリスト情報を取得し、前記対象車両は、前記タスクに対応するタスク地点において割り当てられた各タスクを実行し、
作業空間内の地点の各ペアの最小コストが示されるコスト行列を使用して車両ルーティング問題を解くことによって、各対象車両に対する前記タスクの実行順序を決定し、
各タスクについて、前記決定されたタスクの実行順序に基づいて、前記タスクの前記タスク地点まで移動するコストが最小となる経路であるタスク経路を選択し、
各対象車両について、前記対象車両に割り当てられた前記タスクの前記実行順序および各タスクの前記タスク経路を示す前記対象車両のスケジュール情報を生成し、
前記対象車両と、その位置が経時的に変化する一時的な障害物との間の競合である外部競合を検出し、かつ
１つ以上の外部競合が検出された場合に、さらに、
前記競合が検出された地点の前記ペアの前記最小コストを更新するように前記コスト行列を更新することと、
前記対象車両と前記一時的な障害物との検出が検出されなくなるまで、前記タスクの前記実行順序の前記決定、各タスクの前記タスク経路の前記選択、前記スケジュール情報の前記生成、前記競合の前記検出、および前記コスト行列の前記更新を繰り返し行うこととを行う、
ように構成される車両スケジューリング装置。
（付記２）
前記外部競合の前記検出は、
一時的な障害物ごとに、各時点における前記一時的な障害物の位置を示すイベント情報を取得することと、
前記対象車両の前記スケジュール情報と各一時的な障害物の前記イベント情報とを比較して、前記対象車両および前記一時的な障害物が互いに同じ時刻に同じ場所に位置することがスケジュールされている場合に、前記対象車両が前記一時的な障害物と競合していると決定することとを含む、
付記１に記載の車両スケジューリング装置。
（付記３）
各対象車両に対する前記タスクの前記実行順序が、時間依存車両ルーティング問題を解くことによって決定され、
前記コスト行列が時間依存コストを示すように構成され、かつ
前記コスト行列の前記初期化は、
前記作業空間のマップ情報を使用して最短経路問題を解くことによって経路行列を初期化することを含み、前記経路行列は、地点の各ペアおよび各時点について、前記地点間の１つ以上の取り得る経路のうちのコストが最小となる経路を示し、前記マップ情報は、各地点の位置、およびその位置が経時的に変化しない恒久的な障害物の位置を示し、
地点の各ペアおよび各時点について、前記経路行列のセルによって示される前記経路のコストを、前記コスト行列の対応するセルに設定することを含む、
付記１または２に記載の車両スケジューリング装置。
（付記４）
前記コスト行列の前記更新は、
前記マップ情報および前記外部競合の前記検出の結果に基づいて、各時点について、各地点の位置、恒久的な障害物の位置、および前記外部競合の位置を示す予約テーブルを生成することと、
前記予約テーブルを使用して最短経路問題を解くことによって前記経路行列を更新することと、
地点の各ペアおよび各時点について、前記経路行列のセルによって示される前記経路のコストを、前記コスト行列の対応するセルに設定することとを含む、
付記３に記載の車両スケジューリング装置。
（付記５）
前記コスト行列が時間非依存コストを示すように構成され、かつ
前記コスト行列の前記初期化は、
前記作業空間のマップ情報を使用して最短経路問題を解くことによって経路行列を初期化することを含み、前記経路行列は、地点の各ペアについて、前記地点間の１つ以上の取り得る経路のうちのコストが最小となる経路を示し、前記マップ情報は、各地点の位置、およびその位置が経時的に変化しない恒久的な障害物の位置を示し、
地点の各ペアについて、前記経路行列のセルによって示される前記経路のコストを、前記コスト行列の対応するセルに設定することを含む、
付記１または２に記載の車両スケジューリング装置。
（付記６）
前記コスト行列の前記更新は、
前記マップ情報および前記外部競合の前記検出の結果に基づいて、各地点の位置、恒久的な障害物の位置、および前記外部競合の位置を示すグリッドマップを生成することと、
前記グリッドマップを使用して最短経路問題を解くことによって前記経路行列を更新することと、
地点の各ペアについて、前記経路行列のセルによって示される前記経路のコストを、前記コスト行列の対応するセルに設定することとを含む、
付記５に記載の車両スケジューリング装置。
（付記７）
前記少なくとも１つのプロセッサが、前記命令を実行して、
２台以上の対象車両が前記対象者に割り当てられている場合、前記外部競合を検出する前に、前記対象車両間の競合である内部競合を検出することと、
１つ以上の内部競合が検出された場合に、
前記内部競合が検出された地点の前記ペアについて、コストが最小となる前記経路を更新するために内部競合の解消を行うことによって前記経路行列を更新することと、
各タスクに対する前記タスク経路の前記選択、前記スケジュール情報の前記生成、前記内部競合の前記検出、および前記経路行列の前記更新を、内部競合が検出されなくなるまで繰り返し行うこととをさらに行うようにさらに構成される、
付記４または６に記載の車両スケジューリング装置。
（付記８）
前記少なくとも１つのプロセッサが、前記命令を実行して、
１つ以上の外部競合が検出され、かつ前記一時的な障害物が前記対象車両以外の車両である場合に、
前記一時的な障害物の前記スケジュール情報の更新が承認されるか否かを確認することと、
前記一時的な障害物の前記スケジュール情報が承認される場合には、前記対象車両の前記スケジュール情報を繰り返し生成することに代えて、外部競合が検出されなくなるまで、前記一時的な障害物の前記スケジュール情報を繰り返し更新することとをさらに行うようにさらに構成される、
付記１から７のいずれか一項に記載の車両スケジューリング装置。
（付記９）
コンピュータによって行われる制御方法であって、
少なくとも１台の対象車両が割り当てられた対象者に割り当てられたタスクを示すタスクリスト情報を取得することを含み、前記対象車両は、前記タスクに対応するタスク地点において割り当てられた各タスクを実行し、
作業空間内の地点の各ペアの最小コストが示されるコスト行列を使用して車両ルーティング問題を解くことによって、各対象車両に対する前記タスクの実行順序を決定することと、
各タスクについて、前記タスクの前記決定された実行順序に基づいて、前記タスクの前記タスク地点まで移動するコストが最小となる経路であるタスク経路を選択することと、
各対象車両について、前記対象車両に割り当てられた前記タスクの前記実行順序および各タスクの前記タスク経路を示す前記対象車両のスケジュール情報を生成することと、
前記対象車両と、その位置が経時的に変化する一時的な障害物との間の競合である外部競合を検出することとを含み、
１つ以上の外部競合が検出された場合に、
前記競合が検出された地点の前記ペアの前記最小コストを更新するように前記コスト行列を更新すること、ならびに
前記対象車両と前記一時的な障害物との検出が検出されなくなるまで、前記タスクの前記実行順序の前記決定、各タスクの前記タスク経路の前記選択、前記スケジュール情報の前記生成、前記競合の前記検出、および前記コスト行列の前記更新を繰り返し行うことをさらに行うことを含む、制御方法。
（付記１０）
前記外部競合の前記検出は、
一時的な障害物ごとに、各時点における前記一時的な障害物の位置を示すイベント情報を取得することと、
前記対象車両の前記スケジュール情報と各一時的な障害物の前記イベント情報とを比較して、前記対象車両および前記一時的な障害物が互いに同じ時刻に同じ場所に位置することがスケジュールされている場合に、前記対象車両が前記一時的な障害物と競合していると決定することとを含む、
付記９に記載の制御方法。
（付記１１）
各対象車両に対する前記タスクの前記実行順序が、時間依存車両ルーティング問題を解くことによって決定され、
前記コスト行列が時間依存コストを示すように構成され、かつ
前記コスト行列の前記初期化は、
前記作業空間のマップ情報を使用して最短経路問題を解くことによって経路行列を初期化することを含み、前記経路行列は、地点の各ペアおよび各時点について、前記地点間の１つ以上の取り得る経路のうちのコストが最小となる経路を示し、前記マップ情報は、各地点の位置、およびその位置が経時的に変化しない恒久的な障害物の位置を示し、
地点の各ペアおよび各時点について、前記経路行列のセルによって示される前記経路のコストを、前記コスト行列の対応するセルに設定することを含む、
付記９または１０に記載の制御方法。
（付記１２）
前記コスト行列の前記更新は、
前記マップ情報および前記外部競合の前記検出の結果に基づいて、各時点について、各地点の位置、恒久的な障害物の位置、および前記外部競合の位置を示す予約テーブルを生成することと、
前記予約テーブルを使用して最短経路問題を解くことによって前記経路行列を更新することと、
地点の各ペアおよび各時点について、前記経路行列のセルによって示される前記経路のコストを、前記コスト行列の対応するセルに設定することとを含む、
付記１１に記載の制御方法。
（付記１３）
前記コスト行列が時間非依存コストを示すように構成され、かつ
前記コスト行列の前記初期化は、
前記作業空間のマップ情報を使用して最短経路問題を解くことによって経路行列を初期化することを含み、前記経路行列が、地点の各ペアについて、前記地点間の１つ以上の取り得る経路のうちのコストが最小となる経路を示し、前記マップ情報が、各地点の位置、およびその位置が経時的に変化しない恒久的な障害物の位置を示し、
地点の各ペアについて、前記経路行列のセルによって示される前記経路のコストを、前記コスト行列の対応するセルに設定することを含む、
付記９または１０に記載の制御方法。
（付記１４）
前記コスト行列の前記更新は、
前記マップ情報および前記外部競合の前記検出の結果に基づいて、各地点の位置、恒久的な障害物の位置、および前記外部競合の位置を示すグリッドマップを生成することと、
前記グリッドマップを使用して最短経路問題を解くことによって前記経路行列を更新することと、
地点の各ペアについて、前記経路行列のセルによって示される前記経路のコストを、前記コスト行列の対応するセルに設定することとを含む、
付記１３に記載の制御方法。
（付記１５）
２台以上の対象車両が前記対象者に割り当てられている場合、前記外部競合を検出する前に、前記対象車両間の競合である内部競合を検出することと、
１つ以上の内部競合が検出された場合に、
前記内部競合が検出された地点の前記ペアについて、コストが最小となる前記経路を更新するために内部競合解消を行うことによって前記経路行列を更新することと、
各タスクに対する前記タスク経路の前記選択、前記スケジュール情報の前記生成、前記内部競合の前記検出、および前記経路行列の前記更新を、内部競合が検出されなくなるまで繰り返し行うこととをさらに行うこととをさらに含む、
付記１２または１４に記載の制御方法。
（付記１６）
１つ以上の外部競合が検出され、かつ前記一時的な障害物が前記対象車両以外の車両である場合に、
前記一時的な障害物の前記スケジュール情報の更新が承認されるか否かを確認すること、
前記一時的な障害物の前記スケジュール情報が承認される場合には、前記対象車両の前記スケジュール情報を繰り返し生成することに代えて、外部競合が検出されなくなるまで、前記一時的な障害物の前記スケジュール情報を繰り返し更新することとをさらに行うことをさらに含む、
付記９から１５のいずれか一項に記載の制御方法。
（付記１７）
コンピュータに、
少なくとも１台の対象車両が割り当てられた対象者に割り当てられたタスクを示すタスクリスト情報を取得することを実行させ、前記対象車両は、前記タスクに対応するタスク地点において割り当てられた各タスクを実行し、
作業空間内の地点の各ペアの最小コストが示されるコスト行列を使用して車両ルーティング問題を解くことによって、各対象車両に対する前記タスクの実行順序を決定することと、
各タスクについて、前記タスクの前記決定された実行順序に基づいて、前記タスクの前記タスク地点まで移動するコストが最小となる経路であるタスク経路を選択することと、
各対象車両について、前記対象車両に割り当てられた前記タスクの前記実行順序および各タスクの前記タスク経路を示す前記対象車両のスケジュール情報を生成することと、
前記対象車両と、その位置が経時的に変化する一時的な障害物との間の競合である外部競合を検出することとを実行させ、
１つ以上の外部競合が検出された場合に、
前記競合が検出された地点の前記ペアの前記最小コストを更新するように前記コスト行列を更新すること、ならびに
前記対象車両と前記一時的な障害物との検出が検出されなくなるまで、前記タスクの前記実行順序の前記決定、各タスクの前記タスク経路の前記選択、前記スケジュール情報の前記生成、前記競合の前記検出、および前記コスト行列の前記更新を繰り返し行うことをさらに行うこととを実行させるプログラムを記憶する非一時的コンピュータ可読記憶媒体。
（付記１８）
前記外部競合の前記検出は、
一時的な障害物ごとに、各時点における前記一時的な障害物の位置を示すイベント情報を取得することと、
前記対象車両の前記スケジュール情報と各一時的な障害物の前記イベント情報とを比較して、前記対象車両および前記一時的な障害物が互いに同じ時刻に同じ場所に位置することがスケジュールされている場合に、前記対象車両が前記一時的な障害物と競合していると決定することとを含む、
付記１７に記載の記憶媒体。
（付記１９）
各対象車両に対する前記タスクの前記実行順序が、時間依存車両ルーティング問題を解くことによって決定され、
前記コスト行列が時間依存コストを示すように構成され、かつ
前記コスト行列の前記初期化は、
前記作業空間のマップ情報を使用して最短経路問題を解くことによって経路行列を初期化することを含み、前記経路行列が、地点の各ペアおよび各時点について、前記地点間の１つ以上の取り得る経路のうちのコストが最小となる経路を示し、前記マップ情報が、各地点の位置、およびその位置が経時的に変化しない恒久的な障害物の位置を示し
地点の各ペアおよび各時点について、前記経路行列のセルによって示される前記経路のコストを、前記コスト行列の対応するセルに設定することとを含む、
付記１７または１８に記載の記憶媒体。
（付記２０）
前記コスト行列の前記更新は、
前記マップ情報および前記外部競合の前記検出の結果に基づいて、各時点について、各地点の位置、恒久的な障害物の位置、および前記外部競合の位置を示す予約テーブルを生成することと、
前記予約テーブルを使用して最短経路問題を解くことによって前記経路行列を更新することと、
地点の各ペアおよび各時点について、前記経路行列のセルによって示される前記経路のコストを、前記コスト行列の対応するセルに設定することとを含む、
付記１９に記載の記憶媒体。
（付記２１）
前記コスト行列が時間非依存コストを示すように構成され、かつ
前記コスト行列の前記初期化は、
前記作業空間のマップ情報を使用して最短経路問題を解くことによって経路行列を初期化することを含み、前記経路行列が、地点の各ペアについて、前記地点間の１つ以上の取り得る経路のうちのコストが最小となる経路を示し、前記マップ情報が、各地点の位置、およびその位置が経時的に変化しない恒久的な障害物の位置を示し、
地点の各ペアについて、前記経路行列のセルによって示される前記経路のコストを、前記コスト行列の対応するセルに設定することとを含む、
付記１７または１８に記載の記憶媒体。
（付記２２）
前記コスト行列の前記更新は、
前記マップ情報および前記外部競合の前記検出の結果に基づいて、各地点の位置、恒久的な障害物の位置、および前記外部競合の位置を示すグリッドマップを生成することと、
前記グリッドマップを使用して最短経路問題を解くことによって前記経路行列を更新することと、
地点の各ペアについて、前記経路行列のセルによって示される前記経路のコストを、前記コスト行列の対応するセルに設定することとを含む、
付記２１に記載の記憶媒体。
（付記２３）
前記プログラムが、前記コンピュータに、
２台以上の対象車両が前記対象者に割り当てられている場合、前記外部競合を検出する前に、前記対象車両間の競合である内部競合を検出することと、
１つ以上の内部競合が検出された場合に、
前記内部競合が検出された地点の前記ペアについて、コストが最小となる前記経路を更新するために内部競合解消を行うことによって前記経路行列を更新すること、
各タスクに対する前記タスク経路の前記選択、前記スケジュール情報の前記生成、前記内部競合の前記検出、および前記経路行列の前記更新を、内部競合が検出されなくなるまで繰り返し行うことをさらに行うこととをさらに実行させる、
付記２０または２２に記載の記憶媒体。
（付記２４）
前記プログラムが、前記コンピュータに、
１つ以上の外部競合が検出され、かつ前記一時的な障害物が前記対象車両以外の車両である場合に、
前記一時的な障害物の前記スケジュール情報の更新が承認されるか否かを確認すること、
前記一時的な障害物の前記スケジュール情報が承認される場合には、前記対象車両の前記スケジュール情報を繰り返し生成することに代えて、外部競合が検出されなくなるまで、前記一時的な障害物の前記スケジュール情報を繰り返し更新することをさらに行うことをさらに実行させる、
付記１７から２３のいずれか一項に記載の記憶媒体。

本出願は、２０２１年１０月７日に出願された日本特許出願特願２０２１－１６５３５１号を基礎とする優先権を主張し、その開示は参照によりその全体が本明細書に組み込まれる。

１０ タスクリスト情報
２０ スケジュール情報
３０ 対象車両
１００ 時間依存コスト行列
１１０ 時間依存経路行列
１２０ グリッドマップ
１０００ コンピュータ
１０２０ バス
１０４０ プロセッサ
１０６０ メモリ
１０８０ ストレージデバイス
１１００ 入出力インタフェース
１１２０ ネットワークインタフェース
２０００ 車両スケジューリング装置
２０２０ 取得部
２０４０ 生成部
２０６０ 競合検出部
２０８０ 更新部

ストレージデバイス１０８０は、前述したプログラムを格納しうる。プロセッサ１０４０は、車両スケジューリング装置２０００の各機能構成部を実現するためにそのプログラムを実行する。

経路行列１１０を初期化するとき、各経路のコストは経時的に一定であると仮定することができる。したがって、生成部２０４０は、開始地点と終了地点の各ペアについて、各経路のコストが一定であるマップ情報を使用して最短経路問題を解くことによって、そのペアが取り得る経路の中からコストが最小となる経路を決定する。マップ情報は、作業空間のグリッドマップを格納しうる。対象車両３０が作業空間を二次元的に移動する場合（例えば、対象車両３０が自動車である場合）、グリッド情報は、作業空間の床面の二次元グリッドマップを示す。対象車両３０が作業空間を三次元的に移動する場合（例えば、対象車両３０がドローンである場合）、グリッド情報は、作業空間の三次元グリッドマップを示す。グリッドマップはまた、各地点の位置、および壁、棚、または机などの恒久的な障害物も示す。

時間依存経路行列１１０が初期化された後、生成部２０４０は、時間依存経路行列１１０に基づいて時間依存コスト行列１００を初期化する。具体的には、時間依存コスト行列１００の各セルは、時間依存経路行列の対応するセルによって示される経路のコストを示すべきである。したがって、生成部２０４０は、ｉ、ｊ、ｋの各ペアについて、時間依存経路行列１１０のセル（Ｓｉ，Ｓｊ，Ｔｋ）が示すコストを、時間依存コスト行列１００のセル（Ｓｉ，Ｓｊ，Ｔｋ）に設定する。

＜コスト行列１００の更新：Ｓ１１４＞
対象車両３０について１つ以上の競合が検出された場合（Ｓ１１２：はい）、更新部２０８０は、競合情報に基づいて時間依存コスト行列１００を更新する。更新部２０８０は、時間依存経路行列１１０を使用して時間依存コスト行列１００を更新することができる。この場合、更新部２０８０は、最初に、空間時間Ａ＊アルゴリズムなどの時間依存コストを扱うことができるアルゴリズムで最短経路問題を解くことによって時間依存経路行列１１０を更新しうる。

競合検出部２０６０は、競合検出を行う。対象者に複数の対象車両３０が割り当てられている場合、内部競合および外部競合の２つの種類の競合が発生する可能性がある。内部競合は、対象車両３０間の競合である。一方で、外部競合は、対象車両３０と一時的な障害物との間の競合であり、これについては既に上述されている。

競合検出部２０６０は、最初に、内部競合の検出を行いうる（Ｓ２１２）。競合検出部２０６０は、対象車両３０の各ペアについて、それらのスケジュール情報２０を比較することにより、それらの内部競合を検出する。具体的には、２台の対象車両３０が同じ場所に同時に位置するようにスケジュールされている場合、それらは互いに競合する。

内部競合が検出された場合（Ｓ２１２：はい）、更新部２０８０は、検出された内部競合に基づいてコスト行列１００および経路行列１１０を更新する（Ｓ２１４）。検出された内部競合に基づいて経路行列１１０を更新するために、更新部２０８０は、内部競合の解消を行い、それにより、内部競合が検出された地点のペアについてコストが最小となる新しい経路を計算する。競合検出部２０６０は、非特許文献３によって開示されている競合ベースの探索アルゴリズムなど、任意の内部競合解消アルゴリズムを使用することができる。

時間依存コスト行列１００および時間依存経路行列１１０が更新された後（Ｓ２１４またはＳ２１８）、車両スケジューリング装置２０００は、タスクの実行順序を決定し、各タスクのタスク経路を選択し、スケジュール情報２０を再度生成する（Ｓ２０６、Ｓ２０８、およびＳ２１０）。次いで、再度、内部競合および外部競合の検出を行う（Ｓ２１２およびＳ２１６）。これらの処理の繰り返し実行は、競合が検出されなくなる（Ｓ２１６：いいえ）まで継続される。

Claims (24)

1. 少なくとも１つのプロセッサと、
   命令を記憶するメモリと
   を備える車両スケジューリング装置であって、前記少なくとも１つのプロセッサが、前記命令を実行して、
   少なくとも１台の対象車両が割り当てられた対象者に割り当てられたタスクを示すタスクリスト情報を取得し、前記対象車両は、前記タスクに対応するタスク地点において割り当てられた各タスクを実行し、
   作業空間内の地点の各ペアの最小コストが示されるコスト行列を使用して車両ルーティング問題を解くことによって、各対象車両に対する前記タスクの実行順序を決定し、
   各タスクについて、前記決定されたタスクの実行順序に基づいて、前記タスクの前記タスク地点まで移動するコストが最小となる経路であるタスク経路を選択し、
   各対象車両について、前記対象車両に割り当てられた前記タスクの前記実行順序および各タスクの前記タスク経路を示す前記対象車両のスケジュール情報を生成し、
   前記対象車両と、その位置が経時的に変化する一時的な障害物との間の競合である外部競合を検出し、かつ
   １つ以上の外部競合が検出された場合に、さらに、
   前記競合が検出された地点の前記ペアの前記最小コストを更新するように前記コスト行列を更新することと、
   前記対象車両と前記一時的な障害物との検出が検出されなくなるまで、前記タスクの前記実行順序の前記決定、各タスクの前記タスク経路の前記選択、前記スケジュール情報の前記生成、前記競合の前記検出、および前記コスト行列の前記更新を繰り返し行うこととを行う、
   ように構成される車両スケジューリング装置。
2. 前記外部競合の前記検出は、
   一時的な障害物ごとに、各時点における前記一時的な障害物の位置を示すイベント情報を取得することと、
   前記対象車両の前記スケジュール情報と各一時的な障害物の前記イベント情報とを比較して、前記対象車両および前記一時的な障害物が互いに同じ時刻に同じ場所に位置することがスケジュールされている場合に、前記対象車両が前記一時的な障害物と競合していると決定することとを含む、
   請求項１に記載の車両スケジューリング装置。
3. 各対象車両に対する前記タスクの前記実行順序が、時間依存車両ルーティング問題を解くことによって決定され、
   前記コスト行列が時間依存コストを示すように構成され、かつ
   前記コスト行列の前記初期化は、
   前記作業空間のマップ情報を使用して最短経路問題を解くことによって経路行列を初期化することを含み、前記経路行列は、地点の各ペアおよび各時点について、前記地点間の１つ以上の取り得る経路のうちのコストが最小となる経路を示し、前記マップ情報は、各地点の位置、およびその位置が経時的に変化しない恒久的な障害物の位置を示し、
   地点の各ペアおよび各時点について、前記経路行列のセルによって示される前記経路のコストを、前記コスト行列の対応するセルに設定することを含む、
   請求項１または２に記載の車両スケジューリング装置。
4. 前記コスト行列の前記更新は、
   前記マップ情報および前記外部競合の前記検出の結果に基づいて、各時点について、各地点の位置、恒久的な障害物の位置、および前記外部競合の位置を示す予約テーブルを生成することと、
   前記予約テーブルを使用して最短経路問題を解くことによって前記経路行列を更新することと、
   地点の各ペアおよび各時点について、前記経路行列のセルによって示される前記経路のコストを、前記コスト行列の対応するセルに設定することとを含む、
   請求項３に記載の車両スケジューリング装置。
5. 前記コスト行列が時間非依存コストを示すように構成され、かつ
   前記コスト行列の前記初期化は、
   前記作業空間のマップ情報を使用して最短経路問題を解くことによって経路行列を初期化することを含み、前記経路行列は、地点の各ペアについて、前記地点間の１つ以上の取り得る経路のうちのコストが最小となる経路を示し、前記マップ情報は、各地点の位置、およびその位置が経時的に変化しない恒久的な障害物の位置を示し、
   地点の各ペアについて、前記経路行列のセルによって示される前記経路のコストを、前記コスト行列の対応するセルに設定することを含む、
   請求項１または２に記載の車両スケジューリング装置。
6. 前記コスト行列の前記更新は、
   前記マップ情報および前記外部競合の前記検出の結果に基づいて、各地点の位置、恒久的な障害物の位置、および前記外部競合の位置を示すグリッドマップを生成することと、
   前記グリッドマップを使用して最短経路問題を解くことによって前記経路行列を更新することと、
   地点の各ペアについて、前記経路行列のセルによって示される前記経路のコストを、前記コスト行列の対応するセルに設定することとを含む、
   請求項５に記載の車両スケジューリング装置。
7. 前記少なくとも１つのプロセッサが、前記命令を実行して、
   ２台以上の対象車両が前記対象者に割り当てられている場合、前記外部競合を検出する前に、前記対象車両間の競合である内部競合を検出することと、
   １つ以上の内部競合が検出された場合に、
   前記内部競合が検出された地点の前記ペアについて、コストが最小となる前記経路を更新するために内部競合の解消を行うことによって前記経路行列を更新することと、
   各タスクに対する前記タスク経路の前記選択、前記スケジュール情報の前記生成、前記内部競合の前記検出、および前記経路行列の前記更新を、内部競合が検出されなくなるまで繰り返し行うこととをさらに行うようにさらに構成される、
   請求項４または６に記載の車両スケジューリング装置。
8. 前記少なくとも１つのプロセッサが、前記命令を実行して、
   １つ以上の外部競合が検出され、かつ前記一時的な障害物が前記対象車両以外の車両である場合に、
   前記一時的な障害物の前記スケジュール情報の更新が承認されるか否かを確認することと、
   前記一時的な障害物の前記スケジュール情報が承認される場合には、前記対象車両の前記スケジュール情報を繰り返し生成することに代えて、外部競合が検出されなくなるまで、前記一時的な障害物の前記スケジュール情報を繰り返し更新することとをさらに行うようにさらに構成される、
   請求項１から７のいずれか一項に記載の車両スケジューリング装置。
9. コンピュータによって行われる制御方法であって、
   少なくとも１台の対象車両が割り当てられた対象者に割り当てられたタスクを示すタスクリスト情報を取得することを含み、前記対象車両は、前記タスクに対応するタスク地点において割り当てられた各タスクを実行し、
   作業空間内の地点の各ペアの最小コストが示されるコスト行列を使用して車両ルーティング問題を解くことによって、各対象車両に対する前記タスクの実行順序を決定することと、
   各タスクについて、前記タスクの前記決定された実行順序に基づいて、前記タスクの前記タスク地点まで移動するコストが最小となる経路であるタスク経路を選択することと、
   各対象車両について、前記対象車両に割り当てられた前記タスクの前記実行順序および各タスクの前記タスク経路を示す前記対象車両のスケジュール情報を生成することと、
   前記対象車両と、その位置が経時的に変化する一時的な障害物との間の競合である外部競合を検出することとを含み、
   １つ以上の外部競合が検出された場合に、
   前記競合が検出された地点の前記ペアの前記最小コストを更新するように前記コスト行列を更新すること、ならびに
   前記対象車両と前記一時的な障害物との検出が検出されなくなるまで、前記タスクの前記実行順序の前記決定、各タスクの前記タスク経路の前記選択、前記スケジュール情報の前記生成、前記競合の前記検出、および前記コスト行列の前記更新を繰り返し行うことをさらに行うことを含む、制御方法。
10. 前記外部競合の前記検出は、
    一時的な障害物ごとに、各時点における前記一時的な障害物の位置を示すイベント情報を取得することと、
    前記対象車両の前記スケジュール情報と各一時的な障害物の前記イベント情報とを比較して、前記対象車両および前記一時的な障害物が互いに同じ時刻に同じ場所に位置することがスケジュールされている場合に、前記対象車両が前記一時的な障害物と競合していると決定することとを含む、
    請求項９に記載の制御方法。
11. 各対象車両に対する前記タスクの前記実行順序が、時間依存車両ルーティング問題を解くことによって決定され、
    前記コスト行列が時間依存コストを示すように構成され、かつ
    前記コスト行列の前記初期化は、
    前記作業空間のマップ情報を使用して最短経路問題を解くことによって経路行列を初期化することを含み、前記経路行列は、地点の各ペアおよび各時点について、前記地点間の１つ以上の取り得る経路のうちのコストが最小となる経路を示し、前記マップ情報は、各地点の位置、およびその位置が経時的に変化しない恒久的な障害物の位置を示し、
    地点の各ペアおよび各時点について、前記経路行列のセルによって示される前記経路のコストを、前記コスト行列の対応するセルに設定することを含む、
    請求項９または１０に記載の制御方法。
12. 前記コスト行列の前記更新は、
    前記マップ情報および前記外部競合の前記検出の結果に基づいて、各時点について、各地点の位置、恒久的な障害物の位置、および前記外部競合の位置を示す予約テーブルを生成することと、
    前記予約テーブルを使用して最短経路問題を解くことによって前記経路行列を更新することと、
    地点の各ペアおよび各時点について、前記経路行列のセルによって示される前記経路のコストを、前記コスト行列の対応するセルに設定することとを含む、
    請求項１１に記載の制御方法。
13. 前記コスト行列が時間非依存コストを示すように構成され、かつ
    前記コスト行列の前記初期化は、
    前記作業空間のマップ情報を使用して最短経路問題を解くことによって経路行列を初期化することを含み、前記経路行列が、地点の各ペアについて、前記地点間の１つ以上の取り得る経路のうちのコストが最小となる経路を示し、前記マップ情報が、各地点の位置、およびその位置が経時的に変化しない恒久的な障害物の位置を示し、
    地点の各ペアについて、前記経路行列のセルによって示される前記経路のコストを、前記コスト行列の対応するセルに設定することを含む、
    請求項９または１０に記載の制御方法。
14. 前記コスト行列の前記更新は、
    前記マップ情報および前記外部競合の前記検出の結果に基づいて、各地点の位置、恒久的な障害物の位置、および前記外部競合の位置を示すグリッドマップを生成することと、
    前記グリッドマップを使用して最短経路問題を解くことによって前記経路行列を更新することと、
    地点の各ペアについて、前記経路行列のセルによって示される前記経路のコストを、前記コスト行列の対応するセルに設定することとを含む、
    請求項１３に記載の制御方法。
15. ２台以上の対象車両が前記対象者に割り当てられている場合、前記外部競合を検出する前に、前記対象車両間の競合である内部競合を検出することと、
    １つ以上の内部競合が検出された場合に、
    前記内部競合が検出された地点の前記ペアについて、コストが最小となる前記経路を更新するために内部競合解消を行うことによって前記経路行列を更新することと、
    各タスクに対する前記タスク経路の前記選択、前記スケジュール情報の前記生成、前記内部競合の前記検出、および前記経路行列の前記更新を、内部競合が検出されなくなるまで繰り返し行うこととをさらに行うこととをさらに含む、
    請求項１２または１４に記載の制御方法。
16. １つ以上の外部競合が検出され、かつ前記一時的な障害物が前記対象車両以外の車両である場合に、
    前記一時的な障害物の前記スケジュール情報の更新が承認されるか否かを確認すること、
    前記一時的な障害物の前記スケジュール情報が承認される場合には、前記対象車両の前記スケジュール情報を繰り返し生成することに代えて、外部競合が検出されなくなるまで、前記一時的な障害物の前記スケジュール情報を繰り返し更新することとをさらに行うことをさらに含む、
    請求項９から１５のいずれか一項に記載の制御方法。
17. コンピュータに、
    少なくとも１台の対象車両が割り当てられた対象者に割り当てられたタスクを示すタスクリスト情報を取得することを実行させ、前記対象車両は、前記タスクに対応するタスク地点において割り当てられた各タスクを実行し、
    作業空間内の地点の各ペアの最小コストが示されるコスト行列を使用して車両ルーティング問題を解くことによって、各対象車両に対する前記タスクの実行順序を決定することと、
    各タスクについて、前記タスクの前記決定された実行順序に基づいて、前記タスクの前記タスク地点まで移動するコストが最小となる経路であるタスク経路を選択することと、
    各対象車両について、前記対象車両に割り当てられた前記タスクの前記実行順序および各タスクの前記タスク経路を示す前記対象車両のスケジュール情報を生成することと、
    前記対象車両と、その位置が経時的に変化する一時的な障害物との間の競合である外部競合を検出することとを実行させ、
    １つ以上の外部競合が検出された場合に、
    前記競合が検出された地点の前記ペアの前記最小コストを更新するように前記コスト行列を更新すること、ならびに
    前記対象車両と前記一時的な障害物との検出が検出されなくなるまで、前記タスクの前記実行順序の前記決定、各タスクの前記タスク経路の前記選択、前記スケジュール情報の前記生成、前記競合の前記検出、および前記コスト行列の前記更新を繰り返し行うことをさらに行うこととを実行させるプログラムを記憶する非一時的コンピュータ可読記憶媒体。
18. 前記外部競合の前記検出は、
    一時的な障害物ごとに、各時点における前記一時的な障害物の位置を示すイベント情報を取得することと、
    前記対象車両の前記スケジュール情報と各一時的な障害物の前記イベント情報とを比較して、前記対象車両および前記一時的な障害物が互いに同じ時刻に同じ場所に位置することがスケジュールされている場合に、前記対象車両が前記一時的な障害物と競合していると決定することとを含む、
    請求項１７に記載の記憶媒体。
19. 各対象車両に対する前記タスクの前記実行順序が、時間依存車両ルーティング問題を解くことによって決定され、
    前記コスト行列が時間依存コストを示すように構成され、かつ
    前記コスト行列の前記初期化は、
    前記作業空間のマップ情報を使用して最短経路問題を解くことによって経路行列を初期化することを含み、前記経路行列が、地点の各ペアおよび各時点について、前記地点間の１つ以上の取り得る経路のうちのコストが最小となる経路を示し、前記マップ情報が、各地点の位置、およびその位置が経時的に変化しない恒久的な障害物の位置を示し
    地点の各ペアおよび各時点について、前記経路行列のセルによって示される前記経路のコストを、前記コスト行列の対応するセルに設定することとを含む、
    請求項１７または１８に記載の記憶媒体。
20. 前記コスト行列の前記更新は、
    前記マップ情報および前記外部競合の前記検出の結果に基づいて、各時点について、各地点の位置、恒久的な障害物の位置、および前記外部競合の位置を示す予約テーブルを生成することと、
    前記予約テーブルを使用して最短経路問題を解くことによって前記経路行列を更新することと、
    地点の各ペアおよび各時点について、前記経路行列のセルによって示される前記経路のコストを、前記コスト行列の対応するセルに設定することとを含む、
    請求項１９に記載の記憶媒体。
21. 前記コスト行列が時間非依存コストを示すように構成され、かつ
    前記コスト行列の前記初期化は、
    前記作業空間のマップ情報を使用して最短経路問題を解くことによって経路行列を初期化することを含み、前記経路行列が、地点の各ペアについて、前記地点間の１つ以上の取り得る経路のうちのコストが最小となる経路を示し、前記マップ情報が、各地点の位置、およびその位置が経時的に変化しない恒久的な障害物の位置を示し、
    地点の各ペアについて、前記経路行列のセルによって示される前記経路のコストを、前記コスト行列の対応するセルに設定することとを含む、
    請求項１７または１８に記載の記憶媒体。
22. 前記コスト行列の前記更新は、
    前記マップ情報および前記外部競合の前記検出の結果に基づいて、各地点の位置、恒久的な障害物の位置、および前記外部競合の位置を示すグリッドマップを生成することと、
    前記グリッドマップを使用して最短経路問題を解くことによって前記経路行列を更新することと、
    地点の各ペアについて、前記経路行列のセルによって示される前記経路のコストを、前記コスト行列の対応するセルに設定することとを含む、
    請求項２１に記載の記憶媒体。
23. 前記プログラムが、前記コンピュータに、
    ２台以上の対象車両が前記対象者に割り当てられている場合、前記外部競合を検出する前に、前記対象車両間の競合である内部競合を検出することと、
    １つ以上の内部競合が検出された場合に、
    前記内部競合が検出された地点の前記ペアについて、コストが最小となる前記経路を更新するために内部競合解消を行うことによって前記経路行列を更新すること、
    各タスクに対する前記タスク経路の前記選択、前記スケジュール情報の前記生成、前記内部競合の前記検出、および前記経路行列の前記更新を、内部競合が検出されなくなるまで繰り返し行うことをさらに行うこととをさらに実行させる、
    請求項２０または２２に記載の記憶媒体。
24. 前記プログラムが、前記コンピュータに、
    １つ以上の外部競合が検出され、かつ前記一時的な障害物が前記対象車両以外の車両である場合に、
    前記一時的な障害物の前記スケジュール情報の更新が承認されるか否かを確認すること、
    前記一時的な障害物の前記スケジュール情報が承認される場合には、前記対象車両の前記スケジュール情報を繰り返し生成することに代えて、外部競合が検出されなくなるまで、前記一時的な障害物の前記スケジュール情報を繰り返し更新することをさらに行うことをさらに実行させる、
    請求項１７から２３のいずれか一項に記載の記憶媒体。

Images