【手続補正書】
【提出日】令和1年11月20日(2019.11.20)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ジョブごとに、地理的な起点からそれぞれの地理的なジョブ位置までの走行に基づいて、複数のジョブのスケジューリングを行なうように構成された１つ以上のコンピュータと、
前記１つ以上のコンピュータ上で実現され、複数の動作を行なうように構成された１対多数の経路サーチャーとを備え、
前記複数の動作は、
地理的な位置に対応する複数のノードと前記地理的な位置間の走行コストによって重み付けされたノード間の複数のエッジとを含むグラフにおいて、前記地理的な起点に対応する起点ノードと前記地理的なジョブ位置に対応する複数の宛先ノードとを特定することと、
前記走行コストを用いて前記起点ノードと前記複数の宛先ノードとの間の複数の中間ノードを横断することによって、前記起点ノードから前記複数の宛先ノードまで前記グラフのエッジに沿って経路を探索することとを含み、前記横断することは、前記複数の中間ノードの少なくとも１つのサブセットの各中間ノードにおいて、前記中間ノードに対応する中間の地理的な位置と前記地理的なジョブ位置を最初に取り囲む境界との間の地理的な距離に基づいてヒューリスティックな走行コストを求めることを含み、前記複数の動作はさらに、
前記複数の宛先ノードのうちの１つの宛先ノードの発見に応じて、前記複数の宛先ノードのうちの前記１つの宛先ノードに対応する、発見された地理的な位置を除く前記地理的なジョブ位置を前記境界が取り囲むように前記境界を調節し、前記複数の宛先ノードの全てを発見するまで前記探索および前記境界の調節を継続することを含む、システム。
【請求項２】
前記複数の動作は、前記中間の地理的な位置と前記境界との間の最短の直線距離として、前記中間の地理的な位置と前記境界との間の前記地理的な距離を求めることを含む、請求項１に記載のシステム。
【請求項３】
最初に前記地理的なジョブ位置を取り囲む前記境界は矩形を含み、前記複数の動作は、探索を開始する前に、４つの基本方向の各々について前記基本方向における前記地理的な起点から最も遠い地理的なジョブ位置を有するそれぞれの境界エッジ宛先ノードを含む宛先ノードの組を求めることによって前記境界を求めることを含む、請求項１または２に記載のシステム。
【請求項４】
前記境界を調節することは、前記境界エッジ宛先ノードのうちの１つの境界エッジ宛先ノードの発見に応じてのみ、前記境界を調節することを含む、請求項３に記載のシステム。
【請求項５】
前記複数の中間ノードを横断することは、各中間ノードにおいて、前記起点ノードから前記中間ノードまで前記グラフを横断する実際の走行コストを格納することを含む、請求項１から４のいずれか１項に記載のシステム。
【請求項６】
前記複数の中間ノードを横断することは、第１の中間ノードにおいて、前記第１の中間ノードの１つ以上の隣接ノードについて、前記第１の中間ノードまでの実際の走行コストと前記第１の中間ノードについての前記ヒューリスティックな走行コストとに基づいて合計コスト推定値を求めることを含む、請求項５に記載のシステム。
【請求項７】
前記複数の中間ノードを横断することは、最も低い合計コスト推定値を有する前記１つ以上の隣接ノードから第２の中間ノードを選択し、前記第２の中間ノードまで前記グラフを横断することを含む、請求項６に記載のシステム。
【請求項８】
前記経路を探索することは、前記地理的な起点が前記境界の外側にある場合にのみ、前記複数の中間ノードを横断している間に前記ヒューリスティックな走行コストを求めることを含む、請求項１から７のいずれか１項に記載のシステム。
【請求項９】
前記グラフは道路網を表し、前記エッジは地理的な位置間の道路を表し、前記ノードは道路交差点を表し、前記走行コストは道路交差点間の道路に沿った推定走行時間を表す、請求項１から８のいずれか１項に記載のシステム。
【請求項１０】
前記１つ以上のコンピュータは、前記１対多数の経路サーチャーによって求められるような最も低い走行コストを有する第１のジョブのスケジューリングを最初に行ない、次に前記地理的な起点として前記第１のジョブの第１の地理的な位置を有する前記１対多数の経路サーチャーを用いて探索を行ない、次に前記ジョブの全てのスケジューリングが行なわれるまで前記スケジューリングを繰り返し、前記スケジューリングに基づいてユーザにスケジュールを提供することによって、前記複数のジョブのスケジューリングを行なうように構成されている、請求項１から９のいずれか１項に記載のシステム。
【請求項１１】
ジョブごとに地理的な起点からそれぞれの地理的なジョブ位置までの走行に基づいて複数のジョブのスケジューリングを行なうための方法であって、
地理的な位置に対応する複数のノードと前記地理的な位置間の走行コストによって重み付けされたノード間の複数のエッジとを含むグラフにおいて、１つ以上のコンピュータのシステムが、前記地理的な起点に対応する起点ノードと前記地理的なジョブ位置に対応する複数の宛先ノードとを特定することと、
前記１つ以上のコンピュータのシステムが、走行コストを用いて前記起点ノードと前記複数の宛先ノードとの間の複数の中間ノードを横断することによって、前記起点ノードから前記複数の宛先ノードまで前記グラフのエッジに沿って経路を探索することとを備え、前記横断することは、前記複数の中間ノードの少なくとも１つのサブセットの各中間ノードにおいて、前記中間ノードに対応する中間の地理的な位置と前記地理的なジョブ位置を最初に取り囲む境界との間の地理的な距離に基づいてヒューリスティックな走行コストを求めることを含み、前記方法はさらに、
前記複数の宛先ノードのうちの１つの宛先ノードの発見に応じて、前記１つ以上のコンピュータのシステムが、前記複数の宛先ノードのうちの前記１つの宛先ノードに対応する、発見された地理的な位置を除く前記地理的なジョブ位置を前記境界が取り囲むように前記境界を調節し、前記複数の宛先ノードの全てを発見するまで前記探索および前記境界の調節を継続することを備える、方法。
【請求項１２】
前記中間の地理的な位置と前記境界との間の最短の直線距離として、前記中間の地理的な位置と前記境界との間の前記地理的な距離を求めることを備える、請求項１１に記載の方法。
【請求項１３】
最初に前記地理的なジョブ位置を取り囲む前記境界は矩形を含み、前記方法は、探索を開始する前に、４つの基本方向の各々について前記基本方向における前記地理的な起点から最も遠い地理的なジョブ位置を有するそれぞれの境界エッジ宛先ノードを含む宛先ノードの組を求めることによって、前記境界を求めることを備える、請求項１１または１２に記載の方法。
【請求項１４】
前記境界を調節することは、境界エッジ宛先ノードのうちの１つの境界エッジ宛先ノードの発見に応じてのみ前記境界を調節することを含む、請求項１３に記載の方法。
【請求項１５】
前記複数の中間ノードを横断することは、各中間ノードにおいて、前記起点ノードから
前記中間ノードまで前記グラフを横断する実際の走行コストを格納することを含む、請求項１１から１４のいずれか１項に記載の方法。
【請求項１６】
前記複数の中間ノードを横断することは、第１の中間ノードにおいて、前記第１の中間ノードの１つ以上の隣接ノードについて、前記第１の中間ノードまでの前記実際の走行コストと前記第１の中間ノードについての前記ヒューリスティックな走行コストとに基づいて合計コスト推定値を求めることを含む、請求項１５に記載の方法。
【請求項１７】
前記複数の中間ノードを横断することは、最も低い合計コスト推定値を有する前記１つ以上の隣接ノードから第２の中間ノードを選択し、前記第２の中間ノードまで前記グラフを横断することを含む、請求項１６に記載の方法。
【請求項１８】
前記経路を探索することは、前記地理的な起点が前記境界の外側にある場合にのみ、前記複数の中間ノードを横断する間に前記ヒューリスティックな走行コストを求めることを含む、請求項１１から１７のいずれか１項に記載の方法。
【請求項１９】
前記グラフは道路網を表し、前記エッジは地理的な位置間の道路を表し、前記ノードは道路交差点を表し、前記走行コストは道路交差点間の道路に沿った推定走行時間を表す、請求項１１から１８のいずれか１項に記載の方法。
【請求項２０】
最も低い走行コストを有する第１のジョブのスケジューリングを最初に行ない、次に前記地理的な起点として前記第１のジョブの第１の地理的な位置を用いて前記探索を繰り返し、次に前記ジョブの全てのスケジューリングが行なわれるまで前記スケジューリングを繰り返し前記スケジューリングに基づいてユーザにスケジュールを提供することを備える、請求項１１から１９のいずれか１項に記載の方法。
【請求項２１】
１つ以上のコンピュータによって実行されると、請求項１１から２０のいずれか１項に記載の方法を前記１つ以上のコンピュータに実行させる１つ以上の命令を備えるプログラム。