(57)【要約】  本開示は、カープールサービスのための最適化されたルートを決定するためのシステムおよび方法に関する。方法は、複数の第1の候補経路を生成するために複数のノードをつなぎ合わせるステップを含んでもよい。方法はまた、複数のノードのうちのいずれか2つの間の地理的距離に基づいて、複数の第1の候補経路の各々の地理的長さを決定するステップを含んでもよい。方法はまた、複数の第1の候補経路の各々の地理的長さに基づいて、複数の第1の候補経路の中から1つまたは複数の第2の候補経路を決定するステップを含んでもよい。方法はまた、1つまたは複数の第2の候補経路の各々のナビゲーション長を決定するステップを含んでもよい。方法はまた、ナビゲーション長に基づいて、1つまたは複数の第2の候補経路の中からターゲット経路を決定するステップを含んでもよい。
2021512291.tif 000002
【特許請求の範囲】
【請求項１】
命令のセットを含む少なくとも1つの非一時的コンピュータ可読記憶媒体と、
前記少なくとも1つの非一時的コンピュータ可読記憶媒体と通信する少なくとも1つのプロセッサであって、前記命令を実行するとき、前記少なくとも1つのプロセッサは、
複数の第1の候補経路を生成するために複数のノードをつなぎ合わせ、前記複数のノードは1つまたは複数の要求に基づいて決定され、前記複数の第1の候補経路は前記複数のノードに関する第1の条件を満たし、
前記複数のノードのうちのいずれか2つの間の地理的距離に基づいて、前記複数の第1の候補経路の各々の地理的長さを決定し、
前記複数の第1の候補経路の各々の前記地理的長さに基づいて、前記複数の第1の候補経路の中から1つまたは複数の第2の候補経路を決定し、
前記1つまたは複数の第2の候補経路の各々の前記ナビゲーション長を決定し、
前記ナビゲーション長に基づいて、前記1つまたは複数の第2の候補経路の中からターゲット経路を決定し、前記ターゲット経路の前記ナビゲーション長は、前記1つまたは複数の第2の候補経路のうちで最短である、ように指示される、少なくとも1つのプロセッサと、
を含む、システム。
【請求項２】
1つまたは複数の第2の候補経路を生成するために、前記少なくとも1つのプロセッサは、
前記複数の第1の候補経路の中から基準経路を決定し、前記基準経路の前記地理的長さは、前記複数の第1の候補経路のうちで最短であり、
前記基準経路内の隣接ノード間のナビゲーション長に基づいて、前記基準経路のナビゲーション長を決定し、
前記1つまたは複数の第2の候補経路を決定し、第2の候補経路の前記地理的長さは、前記基準経路の前記ナビゲーション長よりも短い、ようにさらに指示される、請求項1に記載のシステム。
【請求項３】
各要求は出発ノードおよび行先ノードを含み、前記第1の条件は、第1の候補経路における出発ノードの優先順位が、前記第1の候補経路における前記行先ノードの優先順位よりも高いことである、請求項1または2に記載のシステム。
【請求項４】
複数の第1の候補経路を生成するために、前記少なくとも1つのプロセッサは、
前記複数のノードに基づいて初期閉路を決定し、前記初期閉路は第1のノードシーケンスを有するオイラー閉路であり、
前記第1のノードシーケンスおよび前記複数のノードに関する前記第1の条件に基づいて、複数の第2のノードシーケンスを決定し、
前記複数の第2のノードシーケンスに基づいて、前記複数の前記第1の候補経路を決定する、ようにさらに指示される、請求項1から3のいずれか一項に記載のシステム。
【請求項５】
前記オイラー閉路は、クリストフィードのアルゴリズムに基づいて決定される、請求項4に記載のシステム。
【請求項６】
前記複数の第2のノードシーケンスは、2最適化アルゴリズムに基づいて決定される、請求項4または5に記載のシステム。
【請求項７】
前記複数の第1の候補経路の中から前記1つまたは複数の第2の候補経路を決定するために、前記少なくとも1つのプロセッサは、
前記基準経路の前記地理的長さと前記複数の第1の候補経路の各々の地理的長さとの間の複数の第1の差を決定し、
前記基準経路の前記ナビゲーション長と前記基準経路の前記地理的長さとの間の差に基づいて第1のパラメータを決定し、
対応する第1の候補経路の第1の差が前記第1のパラメータより小さいならば、前記対応する第1の候補経路を第2の候補経路として割り当てる、ようにさらに指示される、請求項2に記載のシステム。
【請求項８】
前記第2の候補経路の各々は、1つまたは複数のセクションを含み、各セクションは、前記第2の候補経路の2つの隣接ノードを接続し、
前記基準経路のナビゲーション長を決定するために、前記少なくとも1つのプロセッサは、
前記基準経路の複数のセクションを含む基準セクションセットを取得し、
前記基準経路の前記ナビゲーション長を決定するために、前記基準セクションセットの各セクションの前記ナビゲーション長を決定する、ようにさらに指示される、請求項2または7に記載のシステム。
【請求項９】
前記1つまたは複数の第2の候補経路の各々の前記ナビゲーション長を決定するために、前記少なくとも1つのプロセッサは、
前記基準経路と前記第2の候補経路との間の1つまたは複数の異なるセクションを決定し、
前記1つまたは複数の異なるセクションを前記基準セクションセットに追加し、
前記基準セクションセットに基づいて、前記第2の候補経路の前記ナビゲーション長を決定する、ようにさらに指示される、請求項8に記載のシステム。
【請求項１０】
前記第2の候補経路のセクションの前記ノードシーケンスが前記基準経路のセクションのノードシーケンスと反対であり、かつ、
前記セクションの前記ナビゲーション長と前記地理的長さとの差がしきい値を超えない場合には、
前記第2の候補経路の前記セクションは異なるセクションではない、請求項9に記載のシステム。
【請求項１１】
各々が少なくとも1つのプロセッサおよび記憶媒体を有する少なくとも1つのデバイス上で実施される方法であって、前記方法は、
複数の第1の候補経路を生成するために複数のノードをつなぎ合わせるステップであって、前記複数のノードは1つまたは複数の要求に基づいて決定され、前記複数の第1の候補経路は前記複数のノードに関する第1の条件を満たす、ステップと、
前記複数のノードのいずれか2つの間の地理的距離に基づいて、前記複数の第1の候補経路の各々の地理的長さを決定するステップと、
前記複数の第1の候補経路の各々の前記地理的長さに基づいて、前記複数の第1の候補経路の中から1つまたは複数の第2の候補経路を決定するステップと、
前記1つまたは複数の第2の候補経路の各々の前記ナビゲーション長を決定するステップと、
前記ナビゲーション長に基づいて、前記1つまたは複数の第2の候補経路の中からターゲット経路を決定するステップであって、前記ターゲット経路の前記ナビゲーション長は、前記1つまたは複数の第2の候補経路のうちで最短である、ステップと、
を含む、方法。
【請求項１２】
1つまたは複数の第2の候補経路を生成するために、前記方法は、
前記複数の第1の候補経路の中から基準経路を決定するステップであって、前記基準経路の前記地理的長さは、前記複数の第1の候補経路のうちで最短である、ステップと、
前記基準経路内の隣接ノード間のナビゲーション長に基づいて、前記基準経路のナビゲーション長を決定するステップと、
前記1つまたは複数の第2の候補経路を決定するステップであって、第2の候補経路の前記地理的長さは、前記基準経路の前記ナビゲーション長よりも短い、ステップと、
をさらに含む、請求項11に記載の方法。
【請求項１３】
各要求は出発ノードおよび行先ノードを含み、前記第1の条件は、第1の候補経路における出発ノードの優先順位が、前記第1の候補経路における前記行先ノードの優先順位よりも高いことである、請求項11または12に記載の方法。
【請求項１４】
複数の第1の候補経路を生成するために、前記方法は、
前記複数のノードに基づいて初期閉路を決定するステップであって、前記初期閉路は第1のノードシーケンスを有するオイラー閉路である、ステップと、
前記第1のノードシーケンスおよび前記複数のノードに関する前記第1の条件に基づいて、複数の第2のノードシーケンスを決定するステップと、
前記複数の第2のノードシーケンスに基づいて、前記複数の前記第1の候補経路を決定するステップと、
をさらに含む、請求項11から13のいずれか一項に記載の方法。
【請求項１５】
前記オイラー閉路は、クリストフィードのアルゴリズムに基づいて決定される、請求項14に記載の方法。
【請求項１６】
前記複数の第2のノードシーケンスは、2最適化アルゴリズムに基づいて決定される、請求項14または15に記載の方法。
【請求項１７】
前記複数の第1の候補経路の中から前記1つまたは複数の第2の候補経路を決定するために、前記方法は、
前記基準経路の前記地理的長さと前記複数の第1の候補経路の各々の地理的長さとの間の複数の第1の差を決定するステップと、
前記基準経路の前記ナビゲーション長と前記基準経路の前記地理的長さとの間の差に基づいて第1のパラメータを決定するステップと、
対応する第1の候補経路の第1の差が前記第1のパラメータより小さいならば、前記対応する第1の候補経路を第2の候補経路として割り当てるステップと、
をさらに含む、請求項12に記載の方法。
【請求項１８】
前記第2の候補経路の各々は、1つまたは複数のセクションを含み、各セクションは、前記第2の候補経路の2つの隣接ノードを接続し、
前記基準経路の前記ナビゲーション長を決定するために、前記方法は、
前記基準経路の複数のセクションを含む基準セクションセットを取得するステップと、
前記基準経路の前記ナビゲーション長を決定するために、前記基準セクションセットの各セクションのナビゲーション長を決定するステップと、
をさらに含む、請求項12または17に記載の方法。
【請求項１９】
前記1つまたは複数の第2の候補経路の各々の前記ナビゲーション長を決定するために、前記方法は、
前記基準経路と前記第2の候補経路との間の1つまたは複数の異なるセクションを決定するステップと、
前記1つまたは複数の異なるセクションを前記基準セクションセットに追加するステップと、
前記基準セクションセットに基づいて、前記第2の候補経路の前記ナビゲーション長を決定するステップと、
をさらに含む、請求項18に記載の方法。
【請求項２０】
前記第2の候補経路のセクションの前記ノードシーケンスが前記基準経路のセクションのノードシーケンスと反対であり、かつ、
前記セクションの前記ナビゲーション長と前記地理的長さとの差がしきい値を超えない場合には、
前記第2の候補経路の前記セクションは異なるセクションではない、請求項19に記載の方法。
【請求項２１】
コンピュータプログラム製品を具体化する非一時的コンピュータ可読媒体であって、前記コンピュータプログラム製品は、コンピューティングデバイスに対して、
複数の第1の候補経路を生成するために複数のノードをつなぎ合わせ、前記複数のノードは1つまたは複数の要求に基づいて決定され、前記複数の第1の候補経路は前記複数のノードに関する第1の条件を満たし、
前記複数のノードのうちのいずれか2つの間の地理的距離に基づいて、前記複数の第1の候補経路の各々の地理的長さを決定し、
前記複数の第1の候補経路の各々の前記地理的長さに基づいて、前記複数の第1の候補経路の中から1つまたは複数の第2の候補経路を決定し、
前記1つまたは複数の第2の候補経路の各々の前記ナビゲーション長を決定し、
前記ナビゲーション長に基づいて、前記1つまたは複数の第2の候補経路の中からターゲット経路を決定し、前記ターゲット経路の前記ナビゲーション長は、前記1つまたは複数の第2の候補経路のうちで最短である、
ことをさせるように構成された命令を含む、非一時的コンピュータ可読媒体。
【請求項２２】
各要求は出発ノードおよび行先ノードを含み、前記第1の条件は、第1の候補経路における出発ノードの優先順位が、前記第1の候補経路における前記行先ノードの優先順位よりも高いことである、請求項21に記載の非一時的コンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、概して、オンラインからオフラインのサービスプラットフォームに関し、特に、カープールサービスの最適化されたルートを決定するためのシステムおよび方法に関する。
【背景技術】
【０００２】
インターネット技術の発達により、オンラインタクシーを呼ぶサービスや配車サービスなどのオンラインからオフラインへのサービスは、人々の日常生活においてますます重要な役割を果たしている。定期カープーリングサービスの場合、ドライバーは、ドライバーの始点、各乗客の始点と終点を通過し、最終的に最後の乗客の終点に到達する必要がある。これは典型的な配車計画（VRP）の問題であり、最短の移動距離を実現するには、配車の順序を考慮する必要がある。この問題を解決する過程では、ナビゲーション距離計算サービスを頻繁に要求して、走行経路上の任意の2点間の距離を計算する必要がしばしばある。そのようなリソースは有益であり、場合によってはコストがかかる。したがって、サービスの注文に対するサーバの応答速度を改善し、コンピューティングリソースを節約するための効果的なシステムと方法を開発することが望ましい。
【発明の概要】
【課題を解決するための手段】
【０００３】
本開示の一態様によれば、システムは、命令のセットを格納する少なくとも1つの非一時的コンピュータ可読記憶媒体と、少なくとも1つの非一時的コンピュータ可読記憶媒体と通信する少なくとも1つのプロセッサと、を含んでもよい。命令のセットを実行するとき、少なくとも1つのプロセッサは、システムに対して、複数の第1の候補経路を生成させるために、複数のノードをつなぎ合わせさせてもよい。複数のノードは1つまたは複数の要求に基づいて決定されてもよく、複数の第1の候補経路は複数のノードに関する第1の条件を満たしてもよい。少なくとも1つのプロセッサはまた、システムに対して、複数の第1の候補経路の各々の地理的長さに基づいて、複数の第1の候補経路の中から1つまたは複数の第2の候補経路を決定させてもよい。少なくとも1つのプロセッサはまた、システムに対して、1つまたは複数の第2の候補経路の各々のナビゲーション長を決定させてもよい。少なくとも1つのプロセッサはまた、システムに対して、ナビゲーション長に基づいて、1つまたは複数の第2の候補経路の中からターゲット経路を決定させてもよい。ターゲット経路のナビゲーション長は、1つまたは複数の第2の候補経路のうちで最短であってもよい。
【０００４】
いくつかの実施形態では、1つまたは複数の第2の候補経路を生成するために、少なくとも1つのプロセッサはまた、システムに対して、複数の第1の候補経路の中から基準経路を決定させてもよい。基準経路の地理的長さは、複数の第1の候補経路のうちで最短であってもよい。少なくとも1つのプロセッサはまた、システムに対して、基準経路内の隣接ノード間のナビゲーション長に基づいて、基準経路のナビゲーション長を決定させてもよい。少なくとも1つのプロセッサはまた、システムに対して、1つまたは複数の第2の候補経路を決定させてもよい。第2の候補経路の地理的長さは、基準経路のナビゲーション長よりも短くてもよい。
【０００５】
いくつかの実施形態では、各要求は出発ノードおよび行先ノードを含んでもよく、第1の条件は、第1の候補経路における出発ノードの優先順位が、第1の候補経路における行先ノードの優先順位よりも高いことであってもよい。
【０００６】
いくつかの実施形態では、複数の第1の候補経路を生成するために、少なくとも1つのプロセッサはまた、システムに対して、複数のノードに基づいて初期閉路を決定させてもよい。初期閉路は、第1のノードシーケンスを有するオイラー閉路であってもよい。少なくとも1つのプロセッサはまた、システムに対して、第1のノードシーケンスおよび複数のノードに関する第1の条件に基づいて、複数の第2のノードシーケンスを決定させてもよい。少なくとも1つのプロセッサはまた、システムに対して、複数の第2のノードシーケンスに基づいて、複数の第1の候補経路を決定させてもよい。
【０００７】
いくつかの実施形態では、オイラー閉路は、クリストフィードのアルゴリズムに基づいて決定されてもよい。
【０００８】
いくつかの実施形態では、複数の第2のノードシーケンスは、2最適化アルゴリズムに基づいて決定されてもよい。
【０００９】
いくつかの実施形態では、複数の第1の候補経路の中から1つまたは複数の第2の候補経路を決定するために、少なくとも1つのプロセッサはまた、システムに対して、基準経路の地理的長さと複数の第1の候補経路の各々の地理的長さとの間の複数の第1の差を決定させてもよい。少なくとも1つのプロセッサはまた、システムに対して、基準経路のナビゲーション長と基準経路の地理的長さとの間の差に基づいて第1のパラメータを決定させてもよい。少なくとも1つのプロセッサはまた、システムに対して、対応する第1の候補経路の第1の差が第1のパラメータより小さいならば、対応する第1の候補経路を第2の候補経路として割り当てさせてもよい。
【００１０】
いくつかの実施形態では、第2の候補経路の各々は、1つまたは複数のセクションを含んでもよい。各セクションは、第2の候補経路の2つの隣接ノードに接続されてもよい。基準経路のナビゲーション長を決定するために、少なくとも1つのプロセッサは、システムに対して、基準経路の複数のセクションを含む基準セクションセットを取得させてもよい。少なくとも1つのプロセッサはまた、システムに対して、基準経路のナビゲーション長を決定するために、基準セクションセット内の各セクションのナビゲーション長を決定させてもよい。
【００１１】
いくつかの実施形態では、1つまたは複数の第2の候補経路の各々のナビゲーション長を決定するために、少なくとも1つのプロセッサはまた、システムに対して、基準経路と第2の候補経路との間の1つまたは複数の異なるセクションを決定させてもよい。少なくとも1つのプロセッサはまた、システムに対して、1つまたは複数の異なるセクションを基準セクションセットに追加させてもよい。少なくとも1つのプロセッサはまた、システムに対して、基準セクションセットに基づいて第2の候補経路のナビゲーション長を決定させてもよい。
【００１２】
いくつかの実施形態では、第2の候補経路のセクションのノードシーケンスが基準経路のセクションのノードシーケンスと反対であり、かつ、セクションのナビゲーション長と地理的長さとの差がしきい値を超えないならば、第2の候補経路のセクションは異なるセクションではなくてもよい。
【００１３】
本開示の別の態様によれば、コンピュータにより実施される方法は、少なくとも1つのプロセッサによって実行される以下の動作のうちの1つまたは複数を含んでもよい。方法は、複数の第1の候補経路を生成するために複数のノードをつなぎ合わせるステップを含んでもよい。複数のノードは1つまたは複数の要求に基づいて決定されてもよく、複数の第1の候補経路は複数のノードに関する第1の条件を満たしてもよい。方法はまた、複数のノードのいずれか2つの間の地理的距離に基づいて、複数の第1の候補経路の各々の地理的長さを決定するステップを含んでもよい。方法はまた、複数の第1の候補経路の各々の地理的長さに基づいて、複数の第1の候補経路の中から1つまたは複数の第2の候補経路を決定するステップを含んでもよい。方法はまた、1つまたは複数の第2の候補経路の各々のナビゲーション長を決定するステップを含んでもよい。方法はまた、ナビゲーション長に基づいて、1つまたは複数の第2の候補経路の中からターゲット経路を決定するステップを含んでもよい。ターゲット経路のナビゲーション長は、1つまたは複数の第2の候補経路のうちで最短であってもよい。
【００１４】
本開示のさらに別の態様によれば、システムの少なくとも1つのプロセッサによって実行された場合に、システムに対して方法を実行させる命令を格納する非一時的機械可読記憶媒体。方法は、複数の第1の候補経路を生成するために複数のノードをつなぎ合わせるステップを含んでもよい。複数のノードは1つまたは複数の要求に基づいて決定されてもよく、複数の第1の候補経路は複数のノードに関する第1の条件を満たしてもよい。方法はまた、複数のノードのいずれか2つの間の地理的距離に基づいて、複数の第1の候補経路の各々の地理的長さを決定するステップを含んでもよい。方法はまた、複数の第1の候補経路の各々の地理的長さに基づいて、複数の第1の候補経路の中から1つまたは複数の第2の候補経路を決定するステップを含んでもよい。方法はまた、1つまたは複数の第2の候補経路の各々のナビゲーション長を決定するステップを含んでもよい。方法はまた、ナビゲーション長に基づいて、1つまたは複数の第2の候補経路の中からターゲット経路を決定するステップを含んでもよい。ターゲット経路のナビゲーション長は、1つまたは複数の第2の候補経路のうちで最短であってもよい。
【００１５】
本開示は、例示的な実施形態に関してさらに説明される。これらの例示的な実施形態は、図面を参照して詳細に説明される。これらの実施形態は、非限定的な例示的な実施形態であり、図面のいくつかの図全体を通して、同様の符号は同様の構造を表す。
【図面の簡単な説明】
【００１６】
【図１】本開示のいくつかの実施形態による例示的なオンラインからオフラインへのサービスシステムを示すブロック図である。
【図２】本開示のいくつかの実施形態による例示的なコンピューティングデバイスの例示的なハードウェアおよびソフトウェア構成要素を示す概略図である。
【図３】本開示のいくつかの実施形態による、使用端末が実装され得る例示的なモバイルデバイスの例示的なハードウェアおよび／またはソフトウェア構成要素を示す概略図である。
【図４】本開示のいくつかの実施形態による例示的な処理エンジンを示すブロック図である。
【図５】本開示のいくつかの実施形態による、ターゲット経路を決定するための例示的なプロセスを示すフローチャートである。
【図６】本開示のいくつかの実施形態による、複数の第1の候補経路を決定するための例示的なプロセスを示すフローチャートである。
【図７】本開示のいくつかの実施形態による、第2の候補経路を決定するための例示的なプロセスを示すフローチャートである。
【図８】本開示のいくつかの実施形態による、基準経路のナビゲーション長を決定するための例示的なプロセスを示すフローチャートである。
【図９】本開示のいくつかの実施形態による、1つまたは複数の第2の候補経路の各々のナビゲーション長を決定するための例示的なプロセスを示すフローチャートである。
【発明を実施するための形態】
【００１７】
以下の説明は、当業者が本開示を製造および使用できるようにするために提示され、特定の用途およびその要件の文脈で提供される。開示された実施形態に対する様々な修正は、当業者には容易に明らかであり、本明細書で定義された一般原理は、本開示の趣旨および範囲から逸脱することなく、他の実施形態および用途に適用され得る。したがって、本開示は、示された実施形態に限定されず、特許請求の範囲と矛盾しない最も広い範囲が与えられるべきである。
【００１８】
本明細書で使用される用語は、特定の例示的な実施形態を説明するためだけであり、限定することを意図するものではない。本明細書で使用される単数形「a」、「an」、および「the」は、文脈がそうでないことを明確に示さない限り、複数形も含むことを意図することができる。本明細書で使用される場合、「備える」、「備える」、および／または「備える」、「含む」、「含む」、および／または「含む」という用語は、述べられた特徴、整数、ステップ、動作、要素、および/または構成要素の存在を指定するが、1つまたは複数の他の特徴、整数、ステップ、動作、要素、構成要素、および／またはそれらのグループの存在または追加を排除するものではないことがさらに理解されよう。
【００１９】
本開示のこれらのおよび他の特徴、ならびに特性、ならびに動作の方法および構造の関連する要素の機能ならびに部品の組み合わせおよび製造の経済性は、添付の図面を参照して以下の説明を検討すると、より明確になり得るが、これらの図面はすべて本開示の一部を形成する。しかし、図面は例示および説明のみを目的としており、本開示の範囲を限定することを意図していないことを明確に理解されたい。図面は縮尺通りではないことが理解される。
【００２０】
本開示で使用されるフローチャートは、本開示のいくつかの実施形態に従ってシステムが実施する動作を示す。明確に理解されるべきことであるが、フローチャートの動作は、順不同で実施されてもよい。逆に、動作は逆の順序で、または同時に実施することができる。さらに、フローチャートに1つまたは複数の他の動作を追加することができる。フローチャートから1つまたは複数の動作を削除することができる。
【００２１】
さらに、本開示のシステムおよび方法は、主に輸送サービスの要求を配信することに関して説明されているが、本開示が限定を意図するものではないことも理解されたい。本開示のシステムまたは方法は、任意の他の種類のオンラインからオフラインへのサービスに適用され得る。例えば、本開示のシステムまたは方法は、陸上、海洋、航空宇宙など、またはそれらの任意の組み合わせを含む異なる環境の輸送システムに適用され得る。輸送システムの車両は、タクシー、自家用車、ヒッチ、バス、電車、新幹線、高速鉄道、地下鉄、船舶、航空機、宇宙船、熱気球、無人車両など、またはそれらの任意の組み合わせを含んでもよい。輸送システムはまた、管理および／または配布のための任意の輸送システム、例えば、至急便を送付および／または受け取るためのシステムを含んでもよい。本開示のシステムまたは方法の用途は、ユーザーデバイス上で実施されてもよく、ウェブページ、ブラウザのプラグイン、クライアント端末、カスタムシステム、内部解析システム、人工知能ロボットなど、またはそれらの任意の組み合わせを含んでもよい。
【００２２】
本開示における「乗客」、「要求者」、「サービス要求者」、および「顧客」という用語は、サービスを要求または発注することができる個人、エンティティ、またはツールを指すために交換可能に使用される。また、本開示における「ドライバー」、「提供者」、および「サービス提供者」という用語は、サービスを提供するか、またはサービスの提供を容易にすることができる個人、エンティティ、またはツールを指すために交換可能に使用される。
【００２３】
本開示における「サービス要求」、「サービスの要求」、「要求」、および「発注」という用語は、同義的に使用され、乗客、サービス要求者、顧客、ドライバー、提供者、サービス提供者など、またはそれらの任意の組み合わせによって開始され得る要求を指す。サービス要求は、乗客、サービス要求者、顧客、ドライバー、提供者、またはサービス提供者のいずれかによって受け入れられ得る。サービス要求は有料または無料であってもよい。
【００２４】
本開示における「サービス提供者端末」および「ドライバー端末」という用語は、サービスを提供するか、またはサービスの提供を容易にするためにサービス提供者によって使用されるモバイル端末を指すために交換可能に使用される。本開示における「サービス要求者端末」および「乗客端末」という用語は、サービスを要求または発注するためにサービス要求者によって使用されるモバイル端末を指すために交換可能に使用される。
【００２５】
本開示で使用される測位技術は、全地球測位システム（GPS）、全地球航法衛星システム（GLONASS）、コンパス航法システム（COMPASS）、ガリレオ測位システム、準天頂衛星システム（QZSS）、ワイヤレスフィデリティ（Wi−Fi）測位技術など、またはそれらの任意の組み合わせに基づくことができる。上記の測位システムのうちの1つまたは複数は、本開示において交換可能に使用されてもよい。
【００２６】
本開示の一態様は、オンラインからオフラインへのサービスのターゲット経路を決定するためのシステムおよび方法に関する。システムは、1つまたは複数の要求に基づいて複数のノードを取得することができる。システムは、複数の第1の候補経路を生成するために複数のノードをつなぎ合わせてもよい。複数の第1の候補経路は、複数のノードに関する第1の条件を満たす。システムは、複数のノードのいずれか2つの間の地理的距離に基づいて、複数の第1の候補経路の各々の地理的長さを決定することができる。システムは、複数の第1の候補経路の中から基準経路を決定することができる。基準経路の地理的長さは、複数の第1の候補経路のうちで最短であってもよい。システムは、基準経路内の隣接ノード間のナビゲーション長に基づいて、基準経路のナビゲーション長を決定することができる。システムは、複数の第1の候補経路の中から1つまたは複数の第2の候補経路を決定することができる。第2の候補経路の地理的長さは、基準経路のナビゲーション長よりも短い。システムは、1つまたは複数の第2の候補経路の各々のナビゲーション長を決定することができる。システムは、ナビゲーション長に基づいて、1つまたは複数の第2の候補経路の中からターゲット経路を決定することができる。ターゲット経路のナビゲーション長は、1つまたは複数の第2の候補経路のうちで最短であってもよい。
【００２７】
オンラインタクシーを呼ぶなどのオンラインからオフラインへのサービスは、ポストインターネット時代にのみ根ざした新しい形式のサービスであることに留意されたい。それはポストインターネットの時代にだけ立ち上げることができる技術的な解決策をユーザーとサービス提供者に提供する。インターネット以前の時代では、ユーザーが路上でタクシーを呼ぶと、タクシーの要求と受け入れは、乗客とその乗客を見る1人のタクシードライバーとの間でのみ行われる。乗客が電話でタクシーを呼ぶ場合には、サービス提供者によるサービス要求とサービスの受け入れは、乗客とサービス提供者（例えば、タクシー会社または代理店）との間でのみ発生し得る。しかし、オンラインタクシーは、サービスのユーザーがサービスを予約し、ユーザーから離れた膨大な数の個々のサービス提供者（例えば、タクシードライバー）に予約サービス要求を自動的に分配することを可能にする。また、複数のサービス提供者がサービス要求に同時にリアルタイムで応答することもできる。したがって、インターネットを通じて、オンラインからオフラインへのサービスシステムは、従来のインターネット以前の輸送サービスシステムでは決して経験することができない、はるかに効率的なトランザクションプラットフォームをユーザーとサービス提供者に提供することができる。予約注文を割り当てると、要求者とサービス提供者の両方に効率的にサービスを提供することができる。
【００２８】
図1は、本開示のいくつかの実施形態による例示的なオンラインからオフラインへのサービスシステム100を示すブロック図である。例えば、オンラインからオフラインへのサービスシステム100は、輸送サービスのためのオンラインからオフラインへのサービスプラットフォームであってもよい。オンラインからオフラインへのサービスシステム100は、サーバ110、ネットワーク120、サービス要求者端末130、サービス提供者端末140、車両150、記憶装置160、および航法システム170を含んでもよい。
【００２９】
オンラインからオフラインへのサービスシステム100は、複数のサービスを提供することができる。例示的なサービスは、タクシーを呼ぶサービス、ドライバーサービス、エクスプレスカーサービス、カープールサービス、バスサービス、ドライバーハイヤーサービス、およびシャトルサービスを含んでもよい。いくつかの実施形態では、オンラインからオフラインへのサービスは、食事の予約、ショッピングなどの任意のオンラインサービス、またはそれらの任意の組み合わせであってもよい。
【００３０】
いくつかの実施形態では、サーバ110は、単一のサーバまたはサーバグループであってもよい。サーバグループは、集中型または分散型であってもよい（例えば、サーバ110は分散型システムであってもよい）。いくつかの実施形態では、サーバ110はローカルまたはリモートであってもよい。例えば、サーバ110は、ネットワーク120を介して、サービス要求者端末130、サービス提供者端末140、および／または記憶装置160に格納された情報および／またはデータにアクセスすることができる。別の例として、サーバ110は、サービス要求者端末130、サービス提供者端末140、および／または記憶装置160に直接接続されて、記憶された情報および／またはデータにアクセスすることができる。いくつかの実施形態では、サーバ110は、クラウドプラットフォーム上に実装されてもよい。単なる例として、クラウドプラットフォームは、プライベートクラウド、パブリッククラウド、ハイブリッドクラウド、コミュニティクラウド、分散クラウド、インタークラウド、マルチクラウドなど、またはそれらの任意の組み合わせを含んでもよい。いくつかの実施形態では、サーバ110は、本開示の図2に示す1つまたは複数の構成要素を有するコンピューティングデバイス200上に実装されてもよい。
【００３１】
いくつかの実施形態では、サーバ110は、処理エンジン112を含んでもよい。処理エンジン112は、本開示で説明される1つまたは複数の機能を実行するために、サービス要求に関する情報および／またはデータを処理することができる。例えば、処理エンジン112は、サービス要求者端末130から受信されたサービス要求のターゲット経路を決定することができる。いくつかの実施形態では、処理エンジン112は、1つまたは複数の処理エンジン（例えば、シングルコア処理エンジンまたはマルチコアプロセッサ）を含んでもよい。単なる例として、処理エンジン112は、中央処理装置（CPU）、特定用途向け集積回路（ASIC）、特定用途向け命令セットプロセッサ（ASIP）、グラフィック処理装置（GPU）、物理処理装置（PPU）、デジタルシグナルプロセッサ（DSP）、フィールドプログラマブルゲートアレイ（FPGA）、プログラマブルロジックデバイス（PLD）、コントローラ、マイクロコントローラユニット、縮小命令セットコンピュータ（RISC）、マイクロプロセッサなど、またはそれらの任意の組み合わせを含んでもよい。
【００３２】
ネットワーク120は、情報および／またはデータの交換を容易にすることができる。いくつかの実施形態では、オンラインからオフラインへのサービスシステム100の1つまたは複数の構成要素（例えば、サーバ110、サービス要求者端末130、サービス提供者端末140、車両150、記憶装置160、および航法システム170）は、ネットワーク120を介してオンラインからオフラインへのサービスシステム100の他の構成要素に情報および／またはデータを送信することができる。例えば、サーバ110は、ネットワーク120を介してサービス要求者端末130からサービス要求を受信することができる。いくつかの実施形態では、ネットワーク120は、任意のタイプの有線または無線ネットワーク、あるいはそれらの組み合わせであってもよい。単なる例として、ネットワーク120は、ケーブルネットワーク、有線ネットワーク、光ファイバーネットワーク、電気通信ネットワーク、イントラネット、インターネット、ローカルエリアネットワーク（LAN）、ワイドエリアネットワーク（WAN）、無線ローカルエリアネットワーク（WLAN）、メトロポリタンエリアネットワーク（MAN）、ワイドエリアネットワーク（WAN）、公衆交換電話網（PSTN）、ブルートゥース（登録商標）ネットワーク、ZigBeeネットワーク、近距離無線通信（NFC）ネットワークなど、またはそれらの任意の組み合わせを含んでもよい。いくつかの実施形態では、ネットワーク120は、1つまたは複数のネットワークアクセスポイントを含んでもよい。例えば、ネットワーク120は、基地局および／またはインターネット交換ポイント120−1、120−2、…などの有線または無線ネットワークアクセスポイントを含むことができ、それを介して、オンラインからオフラインへのサービスシステム100の1つまたは複数の構成要素がネットワーク120に接続されて、データおよび／または情報を交換することができる。
【００３３】
いくつかの実施形態では、乗客は、サービス要求者端末130の所有者であってもよい。いくつかの実施形態では、サービス要求者端末130の所有者は、乗客以外の誰かであってもよい。例えば、サービス要求者端末130の所有者Aは、サービス要求者端末130を使用して、乗客Bのためのサービス要求を送信するか、あるいはサーバ110からサービス確認および／または情報もしくは命令を受信することができる。いくつかの実施形態では、サービス提供者は、サービス提供者端末140のユーザーであってもよい。いくつかの実施形態では、サービス提供者端末140のユーザーは、サービス提供者以外の誰かであってもよい。例えば、サービス提供者端末140のユーザーCは、サービス提供者端末140を使用して、サービス提供者Dに対するサービス要求、および／またはサーバ110からの情報もしくは命令を受信することができる。いくつかの実施形態では、「乗客」と「乗客端末」は交換可能に使用されてもよく、「サービス提供者」と「サービス提供者端末」は交換可能に使用されてもよい。いくつかの実施形態では、サービス提供者端末は、1つまたは複数のサービス提供者（例えば、夜勤サービス提供者、または日勤サービス提供者）に関連付けられてもよい。
【００３４】
いくつかの実施形態では、サービス要求者端末130は、モバイルデバイス130−1、タブレットコンピュータ130−2、ラップトップコンピュータ130−3、車両内の組み込みデバイス130−4など、またはそれらの任意の組み合わせを含んでもよい。いくつかの実施形態では、モバイルデバイス130−1は、スマートホームデバイス、ウェアラブルデバイス、スマートモバイルデバイス、仮想現実デバイス、拡張現実デバイスなど、またはそれらの任意の組み合わせを含んでもよい。いくつかの実施形態では、スマートホームデバイスは、スマート照明デバイス、インテリジェント電気装置の制御デバイス、スマートモニタリングデバイス、スマートテレビ、スマートビデオカメラ、インターホンなど、またはそれらの任意の組み合わせを含んでもよい。いくつかの実施形態では、ウェアラブルデバイスは、スマートブレスレット、スマートフットギア、スマートメガネ、スマートヘルメット、スマートウォッチ、スマート衣類、スマートバックパック、スマートアクセサリなど、またはそれらの任意の組み合わせを含んでもよい。いくつかの実施形態では、スマートモバイルデバイスは、スマートフォン、携帯情報端末（PDA）、ゲームデバイス、ナビゲーションデバイス、販売時点情報管理（POS）デバイスなど、またはそれらの任意の組み合わせを含んでもよい。いくつかの実施形態では、仮想現実デバイスおよび／または拡張現実デバイスは、仮想現実ヘルメット、仮想現実メガネ、仮想現実パッチ、拡張現実ヘルメット、拡張現実メガネ、拡張現実パッチなど、またはそれらの任意の組み合わせを含んでもよい。例えば、仮想現実デバイスおよび／または拡張現実デバイスは、Google（登録商標）Glass、Oculus Rift、HoloLens、Gear VRなどを含んでもよい。いくつかの実施形態では、車両130−4の組み込みデバイスは、車載コンピュータ、車載テレビなどを含んでもよい。いくつかの実施形態では、サービス要求者端末130は、乗客および／またはサービス要求者端末130の位置を見つけるための測位技術を備えたデバイスであってもよい。
【００３５】
サービス提供者端末140は、複数のサービス提供者端末140−1、140−2、…、140−nを含んでもよい。いくつかの実施形態では、サービス提供者端末140は、サービス要求者端末130と同様のデバイス、または同じデバイスであってもよい。いくつかの実施形態では、サービス提供者端末140は、オンラインからオフラインへのサービスを実施できるようにカスタマイズされてもよい。いくつかの実施形態では、サービス提供者端末140は、サービス提供者、サービス提供者端末140、および／またはサービス提供者端末140に関連付けられた車両150の位置を見つけるための測位技術を備えたデバイスであってもよい。いくつかの実施形態では、サービス要求者端末130および／またはサービス提供者端末140は、乗客、サービス要求者端末130、サービス提供者、および／またはサービス提供者端末140の位置を決定するために別の測位デバイスと通信してもよい。いくつかの実施形態では、サービス要求者端末130および／またはサービス提供者端末140は、定期的に測位情報をサーバ110に送信してもよい。いくつかの実施形態では、サービス提供者端末140はまた、利用可能性ステータスをサーバ110に定期的に送信してもよい。利用可能性ステータスは、サービス提供者端末140に関連付けられた車両150が乗客を運ぶのに利用可能であるかどうかを示すことができる。例えば、サービス要求者端末130および／またはサービス提供者端末140は、30分ごとに、測位情報および利用可能性ステータスをサーバ110に送信してもよい。別の例として、サービス要求者端末130および／またはサービス提供者端末140は、ユーザーがオンラインからオフラインへのサービスに関連付けられたモバイルアプリケーションにログインするたびに、測位情報および利用可能性ステータスをサーバ110に送信してもよい。
【００３６】
いくつかの実施形態では、サービス提供者端末140は、1つまたは複数の車両150に対応することができる。車両150は、乗客を運び、目的地まで移動することができる。車両150は、複数の車両150−1、150−2、…、150−nを含んでもよい。1台の車両は、サービス（例えば、タクシーを呼ぶサービス、ドライバーサービス、エクスプレスカーサービス、カープールサービス、バスサービス、ドライバーハイヤーサービス、またはシャトルサービス）のうちの1つのタイプに対応することができる。
【００３７】
記憶装置160は、データおよび／または命令を格納することができる。いくつかの実施形態では、記憶装置160は、サービス要求者端末130および／またはサービス提供者端末140から取得されたデータを格納することができる。いくつかの実施形態では、記憶装置160は、本開示で説明される例示的な方法を実行するためにサーバ110が実行または使用することができるデータおよび／または命令を格納することができる。いくつかの実施形態では、記憶装置160は、大容量記憶装置、取り外し可能記憶装置、揮発性読み書きメモリ、読み出し専用メモリ（ROM）など、またはそれらの任意の組み合わせを含んでもよい。例示的な大容量記憶装置は、磁気ディスク、光ディスク、ソリッドステートドライブなどを含んでもよい。例示的な取り外し可能記憶装置は、フラッシュドライブ、フロッピーディスク、光ディスク、メモリカード、zipディスク、磁気テープなどを含んでもよい。例示的な揮発性読み書きメモリは、ランダムアクセスメモリ（RAM）を含んでもよい。例示的なRAMは、ダイナミックRAM（DRAM）、ダブルデータレート同期ダイナミックRAM（DDR SDRAM）、スタティックRAM（SRAM）、サイリスタRAM（T−RAM）、およびゼロキャパシタRAM（Z−RAM）などを含んでもよい。例示的なROMは、マスクROM（MROM）、プログラム可能ROM（PROM）、消去可能プログラム可能ROM（EPROM）、電気的消去可能プログラム可能ROM（EEPROM）、コンパクトディスクROM（CD−ROM）、およびデジタル多用途ディスクROMなどを含んでもよい。いくつかの実施形態では、記憶装置160は、クラウドプラットフォーム上に実装されてもよい。単なる例として、クラウドプラットフォームは、プライベートクラウド、パブリッククラウド、ハイブリッドクラウド、コミュニティクラウド、分散クラウド、インタークラウド、マルチクラウドなど、またはそれらの任意の組み合わせを含んでもよい。
【００３８】
いくつかの実施形態では、記憶装置160は、オンラインからオフラインへのサービスシステム100の1つまたは複数の構成要素（例えば、サーバ110、サービス要求者端末130、またはサービス提供者端末140）と通信するためにネットワーク120に接続されてもよい。オンラインからオフラインへのサービスシステム100の1つまたは複数の構成要素は、ネットワーク120を介して記憶装置160に格納されたデータまたは命令にアクセスすることができる。いくつかの実施形態では、記憶装置160は、オンラインからオフラインへのサービスシステム100の1つまたは複数の構成要素（例えば、サーバ110、サービス要求者端末130、サービス提供者端末140）に直接接続または通信することができる。いくつかの実施形態では、記憶装置160は、サーバ110の一部であってもよい。
【００３９】
航法システム170は、対象物、例えば、サービス要求者端末130、サービス提供者端末140、車両150などのうちの1つまたは複数に関連する情報を決定することができる。いくつかの実施形態では、航法システム170は、全地球測位システム（GPS）、全地球航法衛星システム（GLONASS）、コンパス航法システム（COMPASS）、北斗航法衛星システム、ガリレオ測位システム、準天頂衛星システム（QZSS）などであってもよい。情報には、対象物の位置、高度、速度、加速度、または現在の時刻が含まれてもよい。航法システム170は、1つまたは複数の衛星、例えば、衛星170−1、衛星170−2、および衛星170−3を含んでもよい。衛星170−1から170−3は、独立してまたは共同で上記の情報を決定することができる。衛星航法システム170は、無線接続を介して、上述の情報をネットワーク120、サービス要求者端末130、サービス提供者端末140、または車両150に送信することができる。
【００４０】
いくつかの実施形態では、オンラインからオフラインへのサービスシステム100の1つまたは複数の構成要素（例えば、サーバ110、サービス要求者端末130、サービス提供者端末140）は、記憶装置160にアクセスする許可を有してもよい。いくつかの実施形態では、オンラインからオフラインへのサービスシステム100の1つまたは複数の構成要素は、1つまたは複数の条件が満たされた場合に、乗客、サービス提供者、および／または公衆に関する情報を読み取りおよび／または変更することができる。例えば、サーバ110は、サービスが完了した後に1人または複数の乗客の情報を読み取りおよび／または変更することができる。別の例として、サーバ110は、サービスが完了した後に、1つまたは複数のサービス提供者の情報を読み取りおよび／または変更することができる。
【００４１】
いくつかの実施形態では、オンラインからオフラインへのサービスシステム100の1つまたは複数の構成要素の情報交換は、サービスを要求することによって開始され得る。サービス要求の対象は、任意の製品であってもよい。いくつかの実施形態では、製品は、食品、医薬品、商品、化学製品、電化製品、衣料品、自動車、住宅、高級品など、またはそれらの任意の組み合わせを含んでもよい。他のいくつかの実施形態では、製品は、サービス製品、金融製品、知識製品、インターネット製品など、またはそれらの任意の組み合わせを含んでもよい。インターネット製品は、個々のホスト製品、ウェブ製品、モバイルインターネット製品、商用ホスト製品、埋め込み製品など、またはそれらの任意の組み合わせを含んでもよい。モバイルインターネット製品は、モバイル端末のソフトウェア、プログラム、システムなど、またはそれらの任意の組み合わせで使用されてもよい。携帯端末は、タブレットコンピュータ、ラップトップコンピュータ、携帯電話、携帯情報端末（PDA）、スマートウォッチ、販売時点情報管理（POS）デバイス、車載コンピュータ、車載テレビ、ウェアラブルデバイスなど、またはそれらの任意の組み合わせを含んでもよい。例えば、製品は、コンピュータまたは携帯電話で使用される任意のソフトウェアおよび／またはアプリケーションであってもよい。ソフトウェアおよび／またはアプリケーションは、社交、買い物、輸送、娯楽、学習、投資など、またはそれらの任意の組み合わせに関連してもよい。いくつかの実施形態では、輸送に関するソフトウェアおよび／またはアプリケーションは、移動ソフトウェアおよび／またはアプリケーション、車両スケジューリングソフトウェアおよび／またはアプリケーション、マッピングソフトウェアおよび／またはアプリケーションなどを含んでもよい。車両スケジューリングソフトウェアおよび／またはアプリケーションにおいて、車両は、馬、馬車、人力車（例えば、手押し車、自転車、三輪車など）、自動車（例えば、タクシー、バス、自家用車など）、列車、地下鉄、船舶、航空機（例えば、飛行機、ヘリコプタ、スペースシャトル、ロケット、熱気球など）など、またはそれらの任意の組み合わせを含んでもよい。
【００４２】
当業者は、オンラインからオフラインへのサービスシステム100の要素（または構成要素）が実行する場合、その要素が電気信号および／または電磁信号を通じて実行し得ることを理解するであろう。例えば、サービス要求者端末130がサービス要求をサーバ110に送信する場合、サービス要求者端末130のプロセッサは、要求を符号化する電気信号を生成することができる。次に、サービス要求者端末130のプロセッサは、電気信号を出力ポートに送信することができる。サービス要求者端末130が有線ネットワークを介してサーバ110と通信する場合、出力ポートはケーブルに物理的に接続することができ、ケーブルはさらに電気信号をサーバ110の入力ポートに送信することができる。サービス要求者端末130が無線ネットワークを介してサーバ110と通信する場合には、サービス要求者端末130の出力ポートは、電気信号を電磁信号に変換する1つまたは複数のアンテナであってもよい。同様に、サービス提供者端末130は、電気信号または電磁信号を介してサーバ110から命令および／またはサービス要求を受信することができる。サービス要求者端末130、サービス提供者端末140、および／またはサーバ110などの電子デバイス内で、そのプロセッサが命令を処理し、命令を送信し、および／またはアクションを実行する場合、その命令および／またはアクションは電気信号を介して行われる。例えば、プロセッサが記憶媒体からデータを検索または保存する場合、プロセッサは、記憶媒体の構造化データを読み取りまたは書き込むことができる記憶媒体の読み取り／書き込みデバイスに電気信号を送信することができる。構造化データは、電子デバイスのバスを介して電気信号の形でプロセッサに送信されてもよい。ここで、電気信号は、1つの電気信号、一連の電気信号、および／または複数の個別の電気信号を指すことができる。
【００４３】
図2は、本開示のいくつかの実施形態による、サーバ110、サービス要求者端末130、および／またはサービス提供者端末140が実装され得るコンピューティングデバイス200の例示的なハードウェアおよびソフトウェアの構成要素を示す概略図である。例えば、処理エンジン112は、コンピューティングデバイス200上に実装され、本開示で開示される処理エンジン112の機能を実行するように構成され得る。
【００４４】
コンピューティングデバイス200は、いくつかの実施形態では、専用コンピュータであってもよい。コンピューティングデバイス200は、本開示のためのオンラインからオフラインへのシステムを実装するために使用され得る。コンピューティングデバイス200は、本明細書で説明するように、オンラインからオフラインへのサービスの任意の構成要素を実装することができる。図1〜図2では、単に便宜上の目的で、このようなコンピュータデバイスを1つだけ示している。当業者は、本願の出願時に、本明細書に記載されるオンラインからオフラインへのサービスに関連するコンピュータ機能が、多くの同様のプラットフォーム上に分散して実装され、処理負荷を分散できることを理解するであろう。
【００４５】
コンピューティングデバイス200は、例えば、データ通信を容易にするために、それに接続されたネットワークに接続され、かつネットワークから接続されたCOMポート250を含んでもよい。コンピューティングデバイス200はまた、プログラム命令を実行するための1つまたは複数のプロセッサの形態の中央処理装置（CPU、またはプロセッサ）220を含んでもよい。例示的なコンピュータプラットフォームは、コンピュータによって処理および／または送信される様々なデータファイルのために、内部通信バス210、異なる形式のプログラムストレージおよびデータストレージ、例えば、ディスク270、および読み取り専用メモリ（ROM）230、またはランダムアクセスメモリ（RAM）240を含んでもよい。例示的なコンピュータプラットフォームはまた、ROM230、RAM240、および／またはCPU／プロセッサ220によって実行される他のタイプの非一時的記憶媒体に格納されたプログラム命令を含んでもよい。本開示の方法および／またはプロセスは、プログラム命令として実装されてもよい。コンピューティングデバイス200はまた、コンピュータとユーザーインターフェース要素280などの他の構成要素との間の入力／出力をサポートするI／O構成要素260を含んでもよい。コンピューティングデバイス200はまた、ネットワーク通信を介してプログラミングおよびデータを受信してもよい。
【００４６】
単なる例示のために、コンピューティングデバイス200には、1つのCPU／プロセッサ220のみが記載されている。しかしながら、本開示におけるコンピューティングデバイス200はまた、複数のCPU／プロセッサを含んでもよく、したがって、本開示において説明されるような1つのCPU／プロセッサ220によって実行される動作および／または方法ステップはまた、複数のCPU／プロセッサによって共同でまたは個別に実行されてもよい。例えば、本開示において、コンピューティングデバイス200のCPU／プロセッサ220がステップAおよびステップBの両方を実行する場合には、ステップAおよびステップBはまた、コンピューティングデバイス200において2つの異なるCPU／プロセッサによって共同でまたは別々に実行されてもよいことを理解されたい（例えば、第1のプロセッサがステップAを実行し、第2のプロセッサがステップBを実行する、あるいは第1および第2のプロセッサが共同してステップAおよびBを実行する）。
【００４７】
図3は、本開示のいくつかの実施形態による、使用端末が実装され得る例示的なモバイルデバイス300の例示的なハードウェアおよび／またはソフトウェア構成要素を示す概略図である。図3に示すように、モバイルデバイス300は、通信プラットフォーム310、ディスプレイ320、グラフィック処理ユニット（GPU）330、中央処理装置（CPU）340、I／O350、メモリ360、および記憶装置390を含んでもよい。いくつかの実施形態では、システムバスまたはコントローラ（図示せず）を含むが、これらに限定されない他の任意の適切な構成要素も、モバイルデバイス300に含まれてもよい。いくつかの実施形態では、モバイルオペレーティングシステム370（例えば、iOS（商標）、Android（商標）、Windows Phone（商標）など）ならびに1つまたは複数のアプリケーション380は、CPU340によって実行されるために、記憶装置390からメモリ360にロードされてもよい。アプリケーション380は、画像処理に関連する情報または処理エンジン112からの他の情報を受信およびレンダリングするためのブラウザまたは任意の他の適切なモバイルアプリを含んでもよい。情報ストリームとのユーザー対話は、I／O350を介して達成され、ネットワーク120を介してオンラインからオフラインへのサービスシステム100の処理エンジン112および／または他の構成要素に提供されてもよい。
【００４８】
本開示で説明する様々なモジュール、ユニット、およびそれらの機能を実装するために、コンピュータハードウェアプラットフォームを、本明細書で説明する要素の1つまたは複数のためのハードウェアプラットフォームとして使用することができる。ユーザーインターフェース要素を備えたコンピュータは、パーソナルコンピュータ（PC）または他の任意のタイプのワークステーションもしくは端末装置を実装するために使用され得る。適切にプログラムされている場合には、コンピュータはサーバとしても機能することができる。
【００４９】
図4は、本開示のいくつかの実施形態による例示的な処理エンジンを示すブロック図である。処理エンジン112は、取得モジュール410、第1の候補経路生成モジュール420、第2の候補経路決定モジュール430、ターゲット経路決定モジュール440、および長さ計算モジュール450を含んでもよい。各モジュールは、例えば、1つまたは複数の記憶媒体に格納された命令のセットに従って、特定のアクションを実行するように設計されたハードウェア回路、および／またはハードウェア回路と1つもしくは複数の記憶媒体の任意の組み合わせであってもよい。
【００５０】
取得モジュール410は、1つまたは複数の要求を取得するように構成され得る。いくつかの実施形態では、1つまたは複数の要求は、1つまたは複数の端末130から送信されてもよい。いくつかの実施形態では、1つまたは複数の要求は、オンラインからオフラインへのサービス要求であってもよい。車両のオンラインからオフラインへの注文を例にとると、1つまたは複数の要求は、1つまたは複数のサービス要求者（例えば、乗客）によって端末130の1つまたは複数から送信され得る。1つまたは複数の要求の各々は、出発地、目的地、出発時刻などのサービス要求者の情報を含んでもよい。取得モジュール410はまた、出発地、目的地、車両タイプ、サービスステータスなどのサービス提供者の情報を取得するように構成されてもよい。1つまたは複数の出発地ならびに1つまたは複数の目的地は、複数のノードと呼ばれることがある。出発地は出発ノードを指すことができ、目的地は行先ノードを指すことができる。例えば、サービス要求者（例えば、乗客）は、サービス要求者端末130およびサーバ110を介して、サービス要求注文をサービス提供者端末140に送信することができる。サービス要求注文は、出発地と目的地に関連してもよい。出発地は出発ノードに対応することができ、目的地は行先ノードに対応することができる。いくつかの実施形態では、1つまたは複数の要求の各々は、出発ノード、行先ノード、および1つもしくは複数の中間ノードを含んでもよい。1つまたは複数の中間ノードは、サービス要求者またはサービス提供者によって選択または設定されてもよい。例えば、サービス提供者（例えば、ドライバー）は、ガソリンスタンドを中間ノードとして設定することができる。いくつかの実施形態では、複数のノードは、サービス提供者（例えば、ドライバー）の出発地および目的地を含んでもよい。いくつかの実施形態では、サービス提供者は特定の目的地をもたず、移動の最終目的地は最後の乗客の目的地である。
【００５１】
第1の候補経路生成モジュール420は、複数の第1の候補経路を生成するように構成され得る。第1の候補経路生成モジュール420は、複数のノードに基づいて初期閉路を決定するように構成され得る。いくつかの実施形態では、初期閉路は、第1のノードシーケンスを有するオイラー閉路であってもよい。第1の候補経路生成モジュール420は、第1のノードシーケンスおよび複数のノードに関する第1の条件に基づいて、複数の第2のノードシーケンスを決定することができる。第1の候補経路生成モジュール420は、複数の第2のノードシーケンスに基づいて複数の第1の候補経路を決定することができる。
【００５２】
第2の候補経路決定モジュール430は、複数の第1の候補経路の中から1つまたは複数の第2の候補経路を決定するように構成され得る。第2の候補経路決定モジュール430は、複数の第1の候補経路の中から基準経路を決定することができる。第2の候補経路決定モジュール430は、基準経路内の隣接ノード間のナビゲーション長に基づいて、基準経路のナビゲーション長を決定することができる。第2の候補経路決定モジュール430は、1つまたは複数の第2の候補経路を決定することができる。第2の候補経路の地理的長さは、基準経路のナビゲーション長よりも短くてもよい。
【００５３】
ターゲット経路決定モジュール440は、最短のナビゲーション長を有する第2の候補経路をターゲット経路として指定するように構成され得る。いくつかの実施形態では、ターゲット経路決定モジュール440は、1つまたは複数の第2の候補経路の各々のナビゲーション長に基づいてターゲット経路を決定することができる。例えば、ターゲット経路のナビゲーション長は、1つまたは複数の第2の候補経路のうちで最短であってもよい。いくつかの実施形態では、ターゲット経路決定モジュール440は、ナビゲーション長、制限速度、および／または交通状況、気象条件、および道路工事の配置などのリアルタイム要因を考慮して、移動時間に基づいてターゲット経路を決定することができる。いくつかの実施形態では、基準経路のナビゲーション長は、1つまたは複数の第2の候補経路の中で最短であり得るので、基準経路がターゲット経路であってもよい。
【００５４】
長さ計算モジュール450は、複数のノードのうちの任意の2つの間の長さを計算するように構成され得る。長さには、球形の長さ、直線の長さ、ナビゲーション長などが含まれてもよい。いくつかの実施形態では、長さ計算モジュール450は、複数のノードのうちの任意の2つの間の地理的長さに基づいて、複数の第1の候補経路の各々の地理的長さを決定することができる。地理的長さは、2つのノード間の空間距離を指すことができる。いくつかの実施形態では、長さ計算モジュール450は、基準経路内の隣接ノード間のナビゲーション長に基づいて、基準経路のナビゲーション長を決定することができる。いくつかの実施形態では、長さ計算モジュール450は、1つまたは複数の第2の候補経路の各々のナビゲーション長を決定することができる。
【００５５】
処理エンジン112の上記の説明は、例示の目的で提供されており、本開示の範囲を限定することを意図していないことに留意されたい。当業者には、本開示の原理から逸脱することなく、上記の方法およびシステムの適用の形態および詳細における様々な修正および変更が行われてもよい。しかしながら、それらの変形および修正もまた、本開示の範囲内に含まれる。いくつかの実施形態では、処理エンジン112は、1つまたは複数の他のモジュールを含んでもよい。例えば、処理エンジン112は、モジュールによって生成されたデータを処理エンジン112に格納するための記憶モジュールを含んでもよい。いくつかの実施形態では、モジュールのいずれか2つを単一のモジュールとして組み合わせることができ、モジュールのいずれか1つを2つ以上のユニットに分割することができる。
【００５６】
図5は、本開示のいくつかの実施形態による、ターゲット経路を決定するための例示的なプロセスを示すフローチャートである。いくつかの実施形態では、プロセス500は、オンラインからオフラインへのサービスシステム100によって実行されてもよい。例えば、プロセス500は、記憶装置160に格納された命令のセット（例えば、アプリケーション）として実装されてもよい。いくつかの実施形態では、処理エンジン112は、命令のセットを実行することができ、したがって、オンラインからオフラインへのサービスプラットフォームでプロセス500を実行するように指示され得る。プラットフォームは、インターネットを介してサービス提供者と要求者を接続するインターネットベースのプラットフォームであってもよい。
【００５７】
510では、処理エンジン112（例えば、取得モジュール410）は、1つまたは複数の要求に基づいて複数のノードを取得することができる。処理された後に、1つまたは複数の要求は、オンラインからオフラインへのサービス注文（例えば、カープールサービス注文）に対応することができる。例えば、カープール注文は、車両に対するサービス要求者Aからの要求A1と、同じ車両に対するサービス要求者Bからの要求B1と、を含んでもよい。1つまたは複数の要求の各々は、出発地および目的地を含んでもよい。いくつかの実施形態では、要求の出発地または要求の目的地は、ノードと呼ばれてもよい。出発地は出発ノードを指すことができ、目的地は行先ノードを指すことができる。例えば、サービス要求者端末130およびサーバ110を介したサービス要求者（例えば、乗客）は、サービス提供者端末140に要求を送信することができる。要求は、出発地と目的地を含んでもよい。出発地は出発ノードに対応し、目的地は行先ノードに対応することができる。いくつかの実施形態では、1つまたは複数の要求の各々は、出発ノード、行先ノード、および1つもしくは複数の中間ノードを含んでもよい。1つまたは複数の中間ノードは、サービス要求者またはサービス提供者によって、通過ノードとして選択または設定されてもよい。例えば、要求A1は、出発ノードおよび行先ノードを含むことができ、中間ノードはサービス要求者Aによって決定されてもよく、それはサービス要求者Aが出発ノードから行先ノードへの移動中に中間ノードを通過したいことを示している。
【００５８】
別の例として、処理エンジン112（例えば、取得モジュール410）は、例えば、第1のサービス要求者の第1のサービス要求および第2のサービス要求者の第2のサービス要求を含む、複数のサービス要求を受け取ることができる。第1のサービス要求注文は、第1のノードに対応する第1の出発地と、第2のノードに対応する第1の目的地と、を含んでもよい。第2の注文は、第3のノードに対応する第2の出発地、および第4のノードに対応する第2の目的地に対応することができる。さらに、処理エンジン112は、第1のノード、第2のノード、第3のノード、第4のノード、サービス提供者（例えば、ドライバー）の出発地に対応する第5のノード、およびサービス提供者の目的地に対応する第6のノードを含む6つのノードを取得することができる。
【００５９】
520では、処理エンジン112（例えば、第1の候補経路生成モジュール420）は、複数のノードをつなぎ合わせて、複数の第1の候補経路を生成することができる。例えば、サービス要求者Aからの要求A1は、出発ノードA’および行先ノードB’を含んでもよい。サービス要求者Bからの要求B1は、出発ノードC’および行先ノードD’を含んでもよい。処理エンジン112は、車両がノードA’、ノードB’、ノードC’およびノードD’のシーケンスで進むことを表すように、ノードA’、ノードB’、ノードC’およびノードD’をABCDなどのノードシーケンスでつなぎ合わせて、第1の候補経路を生成することができる。特に、複数の第1の候補経路は、複数のノードに関する第1の条件を満たすことができる。第1の候補経路における要求の出発ノードの、経路における待ち行列位置を指す優先順位は、第1の候補経路における行先ノードの優先順位よりも高い。例えば、第1の条件によれば、ノードB’は第1の候補経路のノードA’の前には現れず、ノードD’は第1の候補経路のノードC’の前には現れない。いくつかの実施形態では、ノードA’はノードC’の前または後に現れてもよく、ノードB’はノードD’の前または後に現れてもよい。複数の第1の候補経路を生成することに関する詳細な説明は、図6およびその説明で提供される。
【００６０】
530では、処理エンジン112（例えば、長さ計算モジュール450）は、複数のノードのうちの任意の2つの間の地理的長さに基づいて、複数の第1の候補経路の各々の地理的長さを決定することができる。地理的長さは、2つのノード間の空間距離を指すことができる。2つのノード間の地理的長さは、2つのノードによって形成される線分の長さであってもよい。いくつかの実施形態では、地球が球形であることを考慮して、2つのノード間の地理的長さは、地球上の2つのノードによって形成される弧の長さであってもよい。経路（例えば、第1の候補経路）の地理的長さは、経路の複数のノードのシーケンスにおける任意の2つの隣接ノード間の地理的長さの合計である。例えば、ステップ520で説明した例を使用すると、第1の候補経路A’B’C’D’の地理的長さは、ノードA’およびB’、ノードB’およびC’、ならびにノードC’およびD’の地理的長さの合計を指すことができる。別の例では、処理エンジン112（例えば、長さ計算モジュール440）は、経度および緯度を含む2つのノードに関するGPSデータを使用して、2つのノード間の地理的長さを決定することができる。したがって、特定の実施形態では、地理的長さを決定することは、ノード間のナビゲーション情報を取得することを必要としない。いくつかの実施形態では、処理エンジン112（例えば、長さ計算モジュール450）は、複数の第1の候補経路の各々について地理的長さを決定することができる。
【００６１】
540では、処理エンジン112（例えば、第1の候補経路生成モジュール420）は、複数の第1の候補経路の中から基準経路を決定することができる。いくつかの実施形態では、基準経路は、基準経路の地理的長さが複数の第1の候補経路のうちで最短である第1の候補経路である。
【００６２】
550では、処理エンジン112（例えば、長さ計算モジュール450）は、基準経路内の隣接ノード間のナビゲーション長に基づいて、基準経路のナビゲーション長を決定することができる。2つのノード間のナビゲーション長は、車両が通り抜けることができる長さと呼ばれることがある。いくつかの実施形態では、ナビゲーション長は、確立された道路（リンク）に基づく経路から導出される。例えば、処理エンジン112は、基準経路内の隣接ノード間の複数のナビゲーション長を決定することができる。基準経路は、第1のノード、第2のノード、第3のノード、および第4のノードを連続的に含むことができる。処理エンジン112は、第1のノードと第2のノードとの間の第1のナビゲーション長、第2のノードと第3のノードとの間の第2のナビゲーション長、および第3のノードと第4のノードとの間の第3のナビゲーション長を決定することができる。さらに、処理エンジン112は、第1のナビゲーション長、第2のナビゲーション長、および第3のナビゲーション長の合計を計算することにより、基準経路のナビゲーション長を決定することができる。基準経路のナビゲーション長の決定に関する詳細な説明は、図8およびその説明を参照することができる。
【００６３】
560では、処理エンジン112（例えば、第2の候補経路生成モジュール420）は、複数の第1の候補経路の中から1つまたは複数の第2の候補経路を決定することができる。いくつかの実施形態では、1つまたは複数の第2の候補経路の各々の地理的長さは、基準経路のナビゲーション長よりも短くてもよい。複数の第1の候補経路の生成に関する詳細な説明は、図6およびその説明を参照することができる。いくつかの実施形態では、基準経路は、第2の候補経路のうちの1つである。いくつかの実施形態では、他の第1の候補経路は、基準経路のナビゲーション長よりも短い地理的長さをもたないので、基準経路は唯一の第2の候補経路である。
【００６４】
570では、処理エンジン112（例えば、長さ計算モジュール450）は、1つまたは複数の第2の候補経路の各々のナビゲーション長を決定することができる。一例として第2の候補経路を取り上げると、第2の候補経路のナビゲーション長を決定する方法は、ステップ550で説明される基準経路のナビゲーション長を決定する方法と同じであってもよい。
【００６５】
ステップ540〜570は、第2の候補経路を決定するための一例を提供し、そこからターゲット経路を選択することができる。しかしながら、複数の第1の候補経路の各々の地理的長さに少なくとも部分的に基づいて第2の候補経路を決定するための他の実施形態があることに留意されたい。例えば、第1の候補経路の各々の地理的長さの決定後に、処理エンジン112は、第2の候補経路となる最短の地理的長さを有する第1の候補経路の固定数（例えば、1、2、3、5、または10）を選択することができる。別の例として、処理エンジン112は、最初に、最短の地理的長さを有する第1の候補経路を基準経路として選択し、次に、基準経路と比較したときに所定のしきい値よりも短い地理的長さの差を有する任意の第1の候補経路を第2の候補経路として選択することができる。
【００６６】
580では、処理エンジン112（例えば、ターゲット経路決定モジュール440）は、1つまたは複数の第2の候補経路の中からターゲット経路を決定することができる。いくつかの実施形態では、ターゲット経路は、ナビゲーション長に基づいて決定されてもよい。例えば、ターゲット経路のナビゲーション長は、1つまたは複数の第2の候補経路のうちで最短であってもよい。いくつかの実施形態では、ターゲット経路は、ナビゲーション長、制限速度、および／または交通状況、気象条件、および道路工事の配置などのリアルタイム要因を考慮して、移動時間に基づいて決定されてもよい。いくつかの実施形態では、基準経路のナビゲーション長は、1つまたは複数の第2の候補経路の中で最短であり得るので、基準経路がターゲット経路であってもよい。
【００６７】
プロセス500の上記の説明は、例示の目的で提供されており、本開示の範囲を限定することを意図していないことに留意されたい。当業者には、本開示の原理から逸脱することなく、上記の方法およびシステムの適用の形態および詳細における様々な修正および変更が行われてもよい。しかしながら、それらの変形および修正もまた、本開示の範囲内に含まれる。いくつかの実施形態では、1つまたは複数のステップが追加または省略されてもよい。例えば、ステップ540およびステップ550は、1つのステップに統合されてもよい。別の例として、ステップ560およびステップ570は、1つのステップに統合されてもよい。
【００６８】
図6は、本開示のいくつかの実施形態による、複数の第1の候補経路を決定するための例示的なプロセスを示すフローチャートである。いくつかの実施形態では、プロセス600は、オンラインからオフラインへのサービスシステム100によって実行されてもよい。例えば、プロセス600は、記憶装置160に格納された命令のセット（例えば、アプリケーション）として実装されてもよい。いくつかの実施形態では、処理エンジン112は、命令のセットを実行することができ、したがって、オンラインからオフラインへのサービスプラットフォームでプロセス600を実行するように指示され得る。プラットフォームは、インターネットを介してサービス提供者と要求者を接続するインターネットベースのプラットフォームであってもよい。
【００６９】
610では、処理エンジン112は、複数のノードに基づいて初期閉路を決定することができる。いくつかの実施形態では、初期閉路は、第1のノードシーケンスを有するオイラー閉路であってもよい。第1のノードシーケンスのオイラー閉路は、クリストフィードのアルゴリズムと配車計画（VRP）に基づいて決定することができる。オイラー閉路は、複数の辺の各々を一度だけ通過する複数の辺を含む経路を指すことができる。例えば、サービス提供者または車両は、ノードA’から移動し、ノードB’、ノードC’、ノードD’、ノードE’、ノードF’、ノードG’、およびノードH’を通過して、ノードA’に戻ってくることができる。ポイントまたはノードのシーケンスは、第1のノードシーケンスと呼ばれてもよい。例えば、サービス提供者の移動のオイラー閉路は、第1のノードシーケンス（A’B’C’D’E’F’G’H’A’など）で表すことができる。いくつかの実施形態では、処理エンジン112は、複数のノードの1つまたは複数のオイラー閉路を決定することができる。
【００７０】
620では、処理エンジン112は、第1のノードシーケンスおよび複数のノードに関する第1の条件に基づいて、複数の第2のノードシーケンスを決定することができる。いくつかの実施形態では、処理エンジン112は、第1のノードシーケンスおよび複数のノードに関する第1の条件に基づいて2最適化アルゴリズムを使用して複数の第2のノードシーケンスを決定することができる。例えば、ステップ610で説明されたオイラー閉路（例えば、A’B’C’D’E’F’G’H’A’）は、第1のノードシーケンス、例えば、A’→B’→C’→D’→E’→F’→G’→H’→A’を含んでもよい。2つのノードiおよびk（例えば、i＝4、すなわちノードD’およびk＝7、すなわちノードG’）をランダムに選択することにより、第2のノードシーケンスは、ノードiの前の初期ノードシーケンスの第1の部分（すなわち、A’→B’→C’）、ノードiからノードjまでの第1のノードシーケンスの第2の部分を反転することで得られる逆ノードシーケンス（すなわち、G’→F’→E’→D’）、および、ノードjの後の初期ノードシーケンスの第3の部分（すなわち、H’→A’）を連続的に組み合わせることにより決定され得る。第2のノードシーケンスは、「A’→B’→C’→G’→F’→E’→D’→H’→A’」で表すことができる。同様に、処理エンジン112は、複数の第2のノードシーケンスを決定することができる。さらに、処理エンジン112は、複数のノードに関する第1の条件を適用することによって、複数の第2のノードシーケンスを決定することができる。例えば、ノードB’がサービス要求A1の出発ノードであり、ノードD’がサービス要求A1の行先ノードであり、ノードE’がサービス要求B1の出発ノードであり、ノードH’がサービス要求B1の行先ノードである場合には、ノードD’がノードB’よりも先に現れる、またはノードH’がノードE’よりも先に現れるノードシーケンスは、第2のノードシーケンスではない。
【００７１】
630では、処理エンジン112は、複数の第2のノードシーケンスに基づいて複数の第1の候補経路を決定することができる。第2のノードシーケンスは、第1の候補経路に対応することができる。例えば、第2のシーケンスは、「A’→B’→C’→G’→F’→E’→D’→H’→A’」で表すことができる。処理エンジン112は、第2のシーケンス「A’→B’→C’→G’→F’→E’→D’→H’→A’」の複数のノードをつなぎ合わせることによって第1の候補経路を生成することができる。
【００７２】
図7は、本開示のいくつかの実施形態による、第2の候補経路を決定するための例示的なプロセスを示すフローチャートである。いくつかの実施形態では、プロセス700は、オンラインからオフラインへのサービスシステム100によって実行されてもよい。例えば、プロセス700は、記憶装置160に格納された命令のセット（例えば、アプリケーション）として実装されてもよい。いくつかの実施形態では、処理エンジン112は、命令のセットを実行することができ、したがって、オンラインからオフラインへのサービスプラットフォームでプロセス700を実行するように指示され得る。プラットフォームは、インターネットを介してサービス提供者と要求者を接続するインターネットベースのプラットフォームであってもよい。
【００７３】
710では、処理エンジン112は、基準経路の地理的長さと複数の第1の候補経路の各々の地理的長さとの間の複数の第1の差を決定することができる。基準経路の地理的長さはQ0で表すことができる。複数の第1の候補経路の地理的長さは、Q1、Q2、…、Qnで表すことができ、ここで、nは第1の候補経路の数を示すことができる。基準経路の地理的長さと複数の第1の候補経路の各々の地理的長さとの間の複数の第1の差は、Q1−Q0、Q2−Q0、…、Qn−Q0で表すことができる。いくつかの実施形態では、Q0はQ1−Qnのうちの1つである。いくつかの実施形態では、地理的長さおよび第1の差の決定は、航法システムのアクセスまたは利用を必要としない。
【００７４】
720では、処理エンジン112は、基準経路のナビゲーション長と基準経路の地理的長さとの間の差に基づいて第1のパラメータを決定することができる。いくつかの実施形態では、基準経路のナビゲーション長は、N0で表すことができる。基準経路のナビゲーション長と基準経路の地理的長さとの間の差は、N0−Q0で表すことができる。さらに、処理エンジン112は、基準経路のナビゲーション長と基準経路の地理的長さとの間の差に基づいて第1のパラメータを決定することができる。いくつかの実施形態では、第1のパラメータは、基準経路のナビゲーション長と基準経路の地理的長さとの間の差（すなわち、N0−G0）に等しくてもよい。いくつかの実施形態では、第1のパラメータは、基準経路のナビゲーション長と基準経路の地理的長さとの間の差のパーセンテージに等しくてもよい（例えば、（N0−G0）＊80％）。
【００７５】
730では、処理エンジン112は、対応する第1の候補経路の第1の差が第1のパラメータより小さいならば、対応する第1の候補経路を第2の候補経路として割り当てることができる。例えば、対応する第1の候補経路の第1の差（例えば、Q2−Q0）が第1のパラメータ（例えば、N0−G0）よりも小さいならば、処理エンジン112は、対応する第1の候補経路（すなわち、地理的長さQ2に対応する第1の候補経路）を第2の候補経路として割り当てることができる。同様に、処理エンジン112は、複数の第1の候補経路の中から1つまたは複数の第2の候補経路を決定することができる。
【００７６】
図8は、本開示のいくつかの実施形態による、基準経路のナビゲーション長を決定するための例示的なプロセスを示すフローチャートである。いくつかの実施形態では、プロセス800は、オンラインからオフラインへのサービスシステム100によって実行されてもよい。例えば、プロセス800は、記憶装置160に格納された命令のセット（例えば、アプリケーション）として実装されてもよい。いくつかの実施形態では、処理エンジン112は、命令のセットを実行することができ、したがって、オンラインからオフラインへのサービスプラットフォームでプロセス800を実行するように指示され得る。プラットフォームは、インターネットを介してサービス提供者と要求者を接続するインターネットベースのプラットフォームであってもよい。
【００７７】
基準経路は、複数のセクションを含んでもよい。各セクションは、基準経路の2つの隣接ノードを接続することを指すことができる。セクションは、2つの異なるノード間の接続を指すことができる。810では、処理エンジン112は、基準経路の複数のセクションを含む基準セクションセットを取得することができる。例えば、基準経路は、「1→2→3→4」によって表されてもよく、基準セクションセットは、基準経路の複数のセクション、例えば、「1→2」、「2→3」、および「3→4」を含んでもよい。1から4までの数は、複数のノードを示すことができる。
【００７８】
820で、処理エンジン112は、基準経路のナビゲーション長を決定するために基準セクションセット内の各セクションのナビゲーション長を決定することができる。例えば、基準セクションセットは、基準経路の複数のセクション、例えば、「1→2」、「2→3」、および「3→4」を含んでもよい。処理エンジン112は、セクション（「1→2」）の第1のナビゲーション長、セクション（「2→3」）の第2のナビゲーション長、およびセクション（「3→4」）の第3のナビゲーション長を決定することができる。さらに、処理エンジン112は、セクション（「1→2」）の第1のナビゲーション長、セクション（「2→3」）の第2のナビゲーション長、およびセクション（「3→4」）の第3のナビゲーション長の合計を計算することにより、基準経路のナビゲーション長を決定することができる。
【００７９】
図9は、本開示のいくつかの実施形態による、1つまたは複数の第2の候補経路の各々のナビゲーション長を決定するための例示的なプロセスを示すフローチャートである。いくつかの実施形態では、プロセス900は、オンラインからオフラインへのサービスシステム100によって実行されてもよい。例えば、プロセス900は、記憶装置160に格納された命令のセット（例えば、アプリケーション）として実装されてもよい。いくつかの実施形態では、処理エンジン112は、命令のセットを実行することができ、したがって、オンラインからオフラインへのサービスプラットフォームでプロセス900を実行するように指示され得る。プラットフォームは、インターネットを介してサービス提供者と要求者を接続するインターネットベースのプラットフォームであってもよい。
【００８０】
候補経路の各々は、複数のセクションを含んでもよい。セクションは、2つの異なるノード間の接続を指すことができる。910では、処理エンジン112は、基準経路と第2の候補経路との間の1つまたは複数の異なるセクションを決定することができる。例えば、基準経路の複数のセクションは、「1→2」、「2→3」、および「3→4」を含んでもよい。候補経路（例えば、第1の候補経路または第2の候補経路）は、「1→3→2→4」によって表されてもよく、候補経路は複数のセクション、例えば、「1→3」、「3→2」、および「2→4」を含んでもよい。基準経路と第2の候補経路との間の1つまたは複数の異なるセクションは、「1→3」、「3→2」、および「2→4」を含んでもよい。
【００８１】
920では、処理エンジン112は、1つまたは複数の異なるセクションを基準セクションセットに追加することができる。例えば、基準経路の複数のセクションは、「1→2」、「2→3」、および「3→4」を含んでもよい。第2の候補経路は、「1→3→2→4」によって表されてもよく、候補経路は複数のセクション、例えば、「1→3」、「3→2」、および「2→4」を含んでもよい。基準経路と第2の候補経路との間の1つまたは複数の異なるセクションは、「1→3」、「3→2」、および「2→4」を含んでもよい。処理エンジン112は、1つまたは複数の異なるセクションを基準セクションセットに追加することができ、基準セクションセットは、「1→2」、「2→3」、「3→4」、「1→3」、「3→2」、および「2→4」を含む新しい複数のセクションになってもよい。処理エンジン112は、基準セクションセットを記憶装置160に格納することができる。
【００８２】
930では、処理エンジン112は、基準セクションセットに基づいて第2の候補経路のナビゲーション長を決定することができる。処理エンジン112は、第2の候補経路の複数のセクションを決定し、第2の候補経路の複数のセクションを記憶装置160から検索することができる。例えば、第2の候補経路「1→3→2→4」の場合、処理エンジン112は、記憶装置160に予め格納された「1→3」、「3→2」、および「2→4」を検索することができる。
【００８３】
基本的な概念をこのように説明してきたが、この詳細な開示を読んだ後に、前述の詳細な開示は例としてのみ提示されることを意図しており、限定的ではないことが当業者には明らかであろう。本明細書では明示的に述べられていないが、当業者には、様々な変更、改良、および修正が可能であり、意図される。これらの変更、改良、および修正は、本開示によって示唆されることが意図されており、本開示の例示的な実施形態の趣旨および範囲内にある。
【００８４】
さらに、本開示の実施形態を説明するために特定の用語が使用されている。例えば、「一実施形態」、「実施形態」、および／または「いくつかの実施形態」という用語は、実施形態に関連して説明される特定の特徴、構造または特性が本開示の少なくとも1つの実施形態に含まれることを意味する。したがって、本明細書の様々な部分における「実施形態」、「一実施形態」、または「代替的な実施形態」への2つ以上の言及は、必ずしもすべてが同じ実施形態を指しているわけではないことが強調されており、それを理解されたい。さらに、特定の特徴、構造、または特性は、本開示の1つまたは複数の実施形態において適切であるように組み合わせることができる。
【００８５】
さらに、当業者には理解されるであろうが、本開示の態様は、新規で有用なプロセス、機械、製造、または物質の組成、またはその新しい有用な改良を含む、いくつかの特許可能なクラスまたはコンテキストのいずれかで本明細書に図示および記載され得る。したがって、本開示の態様は、完全にハードウェア、完全にソフトウェア（ファームウェア、常駐ソフトウェア、マイクロコードなどを含む）、または本明細書で「ブロック」、「モジュール」、「エンジン」、「ユニット」、「構成要素」、もしくは「システム」と一般的に総称されるソフトウェアおよびハードウェア実装の組み合わせで実装され得る。さらに、本開示の態様は、コンピュータ可読プログラムコードが具体化された1つまたは複数のコンピュータ可読媒体で具体化されたコンピュータプログラム製品の形をとることができる。
【００８６】
コンピュータ可読信号媒体は、例えば、ベースバンド内または搬送波の一部として、コンピュータ可読プログラムコードがその中に具体化された伝搬データ信号を含んでもよい。そのような伝搬信号は、電磁的、光学的など、またはそれらの任意の適切な組み合わせを含む、様々な形態のいずれかをとることができる。コンピュータ可読信号媒体は、コンピュータ可読記憶媒体ではなく、命令実行システム、装置、またはデバイスによって、またはそれらに関連して使用するためのプログラムを通信、伝播、または移送することができる任意のコンピュータ可読媒体であってもよい。コンピュータ可読信号媒体上で具体化されたプログラムコードは、無線、有線、光ファイバケーブル、RFなど、または前述の任意の適切な組み合わせを含む、任意の適切な媒体を使用して送信されてもよい。
【００８７】
本開示の態様の動作を実行するためのコンピュータプログラムコードは、Java、Scala、Smalltalk、Eiffel、JADE、Emerald、C＋＋、C＃、VB．NET、Pythonなどのオブジェクト指向プログラミング言語、「C」プログラミング言語、Visual Basic、Fortran 1703、Perl、COBOL 1702、PHP、ABAPなどの従来の手続き型プログラミング言語、Python、Ruby、Groovyなどの動的プログラミング言語、またはその他のプログラミング言語を含む、1つまたは複数のプログラミング言語の任意の組み合わせで書くことができる。プログラムコードは、完全にユーザーのコンピュータで、一部はユーザーのコンピュータで、スタンドアロンソフトウェアパッケージとして、一部はユーザーのコンピュータで、一部はリモートコンピュータで、または完全にリモートコンピュータもしくはサーバで実行することができる。後者のシナリオでは、リモートコンピュータは、ローカルエリアネットワーク（LAN）またはワイドエリアネットワーク（WAN）を含む任意のタイプのネットワークを介してユーザーのコンピュータに接続されてもよく、あるいは、外部コンピュータへの接続（例えば、インターネットサービスプロバイダを使用したインターネットを通して）、またはクラウドコンピューティング環境での接続、またはサービスとしてのソフトウェア（SaaS）などのサービスとして提供される接続が行われてもよい。
【００８８】
さらに、処理要素またはシーケンスの列挙された順序、または数字、文字、または他の指定の使用は、したがって、特許請求されたプロセスおよび方法を、特許請求の範囲で指定される場合を除いて、任意の順序に限定することを意図しない。上記の開示は、現在開示の様々な有用な実施形態であると考えられるものを様々な例を通して説明しているが、そのような詳細は単にその目的のためであり、添付の特許請求の範囲は開示された実施形態に限定されないが、反対に、開示された実施形態の趣旨および範囲内にある修正および等価な配置を包含することを意図していることを理解されたい。例えば、上記の様々な構成要素の実施態様はハードウェアデバイスで具体化できるが、ソフトウェアのみのソリューション、例えば既存のサーバまたはモバイルデバイスへのインストールとして実施することもできる。
【００８９】
同様に、本開示の実施形態の前述の説明では、様々な特徴が、様々な実施形態の1つまたは複数の理解を助ける開示を簡素化する目的で、単一の実施形態、図面、またはその説明に一緒にグループ化されることがあることを理解されたい。しかしながら、この開示の方法は、特許請求される主題が各請求項で明示的に列挙されるよりも多くの特徴を必要とするという意図を反映するものとして解釈されるべきではない。むしろ、特許請求される主題は、前述の単一の開示された実施形態のすべての特徴より少ない場合がある。
【符号の説明】
【００９０】
100  サービスシステム
110  サーバ
112  処理エンジン
120  ネットワーク
130  サービス要求者端末
130−1  モバイルデバイス
130−2  タブレットコンピュータ
130−3  ラップトップコンピュータ
130−4  車両内の組み込みデバイス
140  サービス提供者端末
150  車両
160  記憶装置
170  航法システム
170−1  衛星
170−2  衛星
170−3  衛星
200  コンピューティングデバイス
210  内部通信バス
220  CPU／プロセッサ
230  読み取り専用メモリ（ROM）
240  ランダムアクセスメモリ（RAM）
250  COMポート
260  I／O構成要素
270  ディスク
280  ユーザーインターフェース要素
300  モバイルデバイス
310  通信プラットフォーム
320  ディスプレイ
330  グラフィック処理ユニット（GPU）
340  中央処理装置（CPU）
350  I／O
360  メモリ
370  モバイルオペレーティングシステム
380  アプリケーション
390  記憶装置
410  取得モジュール
420  第1の候補経路生成モジュール
430  第2の候補経路決定モジュール
440  ターゲット経路決定モジュール
450  長さ計算モジュール
500  プロセス
600  プロセス
700  プロセス
800  プロセス
900  プロセス
【図１】
2021512291.tif 000003
【図２】
2021512291.tif 000004
【図３】
2021512291.tif 000005
【図４】
2021512291.tif 000006
【図５】
2021512291.tif 000007
【図６】
2021512291.tif 000008
【図７】
2021512291.tif 000009
【図８】
2021512291.tif 000010
【図９】
2021512291.tif 000011
【手続補正書】
【提出日】令和2年7月22日(2020.7.22)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
命令のセットを含む少なくとも1つの非一時的コンピュータ可読記憶媒体と、
前記少なくとも1つの非一時的コンピュータ可読記憶媒体と通信する少なくとも1つのプロセッサであって、前記命令を実行するとき、前記少なくとも1つのプロセッサは、
複数の第1の候補経路を生成するために複数のノードをつなぎ合わせ、前記複数のノードは1つまたは複数の要求に基づいて決定され、前記複数の第1の候補経路は前記複数のノードに関する第1の条件を満たし、
前記複数のノードのうちのいずれか2つの間の地理的距離に基づいて、前記複数の第1の候補経路の各々の地理的長さを決定し、
前記複数の第1の候補経路の各々の前記地理的長さに基づいて、前記複数の第1の候補経路の中から1つまたは複数の第2の候補経路を決定し、
前記1つまたは複数の第2の候補経路の各々のナビゲーション長を決定し、
前記1つまたは複数の第2の候補経路の前記1つまたは複数のナビゲーション長に基づいて、前記1つまたは複数の第2の候補経路の中からターゲット経路を決定し、前記ターゲット経路の前記ナビゲーション長は、前記1つまたは複数の第2の候補経路のうちで最短である、ように指示される、少なくとも1つのプロセッサと、
を含む、システム。
【請求項２】
1つまたは複数の第2の候補経路を生成するために、前記少なくとも1つのプロセッサは、
前記複数の第1の候補経路の中から基準経路を決定し、前記基準経路の前記地理的長さは、前記複数の第1の候補経路のうちで最短であり、
前記基準経路内の一対の隣接ノード間の各々の1つまたは複数のナビゲーション長に基づいて、前記基準経路のナビゲーション長を決定し、
前記1つまたは複数の第2の候補経路を決定し、第2の候補経路の前記地理的長さは、前記基準経路の前記ナビゲーション長よりも短い、ようにさらに指示される、請求項1に記載のシステム。
【請求項３】
複数の第1の候補経路を生成するために、前記少なくとも1つのプロセッサは、
前記複数のノードに基づいて初期閉路を決定し、前記初期閉路は第1のノードシーケンスを有するオイラー閉路であり、
前記第1のノードシーケンスおよび前記複数のノードに関する前記第1の条件に基づいて、複数の第2のノードシーケンスを決定し、
前記複数の第2のノードシーケンスに基づいて、前記複数の前記第1の候補経路を決定する、ようにさらに指示される、請求項1または2に記載のシステム。
【請求項４】
前記複数の第1の候補経路の中から前記1つまたは複数の第2の候補経路を決定するために、前記少なくとも1つのプロセッサは、
前記基準経路の前記地理的長さと前記複数の第1の候補経路の各々の地理的長さとの間の複数の第1の差を決定し、
前記基準経路の前記ナビゲーション長と前記基準経路の前記地理的長さとの間の差に基づいて第1のパラメータを決定し、
対応する第1の候補経路の第1の差が前記第1のパラメータより小さいならば、前記対応する第1の候補経路を第2の候補経路として割り当てる、ようにさらに指示される、請求項2に記載のシステム。
【請求項５】
前記第2の候補経路の各々は、1つまたは複数のセクションを含み、各セクションは、前記第2の候補経路の2つの隣接ノードを接続し、
前記基準経路のナビゲーション長を決定するために、前記少なくとも1つのプロセッサは、
前記基準経路の複数のセクションを含む基準セクションセットを取得し、
前記基準経路の前記ナビゲーション長を決定するために、前記基準セクションセットの各セクションの前記ナビゲーション長を決定する、ようにさらに指示される、請求項2または4に記載のシステム。
【請求項６】
前記1つまたは複数の第2の候補経路の各々の前記ナビゲーション長を決定するために、前記少なくとも1つのプロセッサは、
前記基準経路と前記第2の候補経路との間の1つまたは複数の異なるセクションを決定し、
前記1つまたは複数の異なるセクションを前記基準セクションセットに追加し、
前記基準セクションセットに基づいて、前記第2の候補経路の前記ナビゲーション長を決定する、ようにさらに指示される、請求項5に記載のシステム。
【請求項７】
前記第2の候補経路のセクションの前記ノードシーケンスが前記基準経路のセクションのノードシーケンスと反対であり、かつ、
前記セクションの前記ナビゲーション長と前記地理的長さとの差がしきい値を超えない場合には、
前記第2の候補経路の前記セクションは異なるセクションではない、請求項6に記載のシステム。
【請求項８】
各々が少なくとも1つのプロセッサおよび記憶媒体を有する少なくとも1つのデバイス上で実施される方法であって、前記方法は、
複数の第1の候補経路を生成するために複数のノードをつなぎ合わせるステップであって、前記複数のノードは1つまたは複数の要求に基づいて決定され、前記複数の第1の候補経路は前記複数のノードに関する第1の条件を満たす、ステップと、
前記複数のノードのうちのいずれか2つの間の地理的距離に基づいて、前記複数の第1の候補経路の各々の地理的長さを決定するステップと、
前記複数の第1の候補経路の各々の前記地理的長さに基づいて、前記複数の第1の候補経路の中から1つまたは複数の第2の候補経路を決定するステップと、
前記1つまたは複数の第2の候補経路の各々のナビゲーション長を決定するステップと、
前記1つまたは複数の第2の候補経路の前記1つまたは複数のナビゲーション長に基づいて、前記1つまたは複数の第2の候補経路の中からターゲット経路を決定するステップであって、前記ターゲット経路の前記ナビゲーション長は、前記1つまたは複数の第2の候補経路のうちで最短である、ステップと、
を含む、方法。
【請求項９】
1つまたは複数の第2の候補経路を生成するために、前記方法は、
前記複数の第1の候補経路の中から基準経路を決定するステップであって、前記基準経路の前記地理的長さは、前記複数の第1の候補経路のうちで最短である、ステップと、
前記基準経路内の一対の隣接ノード間の各々の1つまたは複数のナビゲーション長に基づいて、前記基準経路のナビゲーション長を決定するステップと、
前記1つまたは複数の第2の候補経路を決定するステップであって、第2の候補経路の前記地理的長さは、前記基準経路の前記ナビゲーション長よりも短い、ステップと、
をさらに含む、請求項8に記載の方法。
【請求項１０】
複数の第1の候補経路を生成するために、前記方法は、
前記複数のノードに基づいて初期閉路を決定するステップであって、前記初期閉路は第1のノードシーケンスを有するオイラー閉路である、ステップと、
前記第1のノードシーケンスおよび前記複数のノードに関する前記第1の条件に基づいて、複数の第2のノードシーケンスを決定するステップと、
前記複数の第2のノードシーケンスに基づいて、前記複数の前記第1の候補経路を決定するステップと、
をさらに含む、請求項8または9に記載の方法。
【請求項１１】
前記複数の第1の候補経路の中から前記1つまたは複数の第2の候補経路を決定するために、前記方法は、
前記基準経路の前記地理的長さと前記複数の第1の候補経路の各々の地理的長さとの間の複数の第1の差を決定するステップと、
前記基準経路の前記ナビゲーション長と前記基準経路の前記地理的長さとの間の差に基づいて第1のパラメータを決定するステップと、
対応する第1の候補経路の第1の差が前記第1のパラメータより小さいならば場合には、前記対応する第1の候補経路を第2の候補経路として割り当てるステップと、
をさらに含む、請求項9に記載の方法。
【請求項１２】
前記第2の候補経路の各々は、1つまたは複数のセクションを含み、各セクションは、前記第2の候補経路の2つの隣接ノードを接続し、
前記基準経路の前記ナビゲーション長を決定するために、前記方法は、
前記基準経路の複数のセクションを含む基準セクションセットを取得するステップと、
前記基準経路の前記ナビゲーション長を決定するために、前記基準セクションセットの各セクションのナビゲーション長を決定するステップと、
をさらに含む、請求項9または11に記載の方法。
【請求項１３】
前記1つまたは複数の第2の候補経路の各々の前記ナビゲーション長を決定するために、前記方法は、
前記基準経路と前記第2の候補経路との間の1つまたは複数の異なるセクションを決定するステップと、
前記1つまたは複数の異なるセクションを前記基準セクションセットに追加するステップと、
前記基準セクションセットに基づいて、前記第2の候補経路の前記ナビゲーション長を決定するステップと、
をさらに含む、請求項12に記載の方法。
【請求項１４】
前記第2の候補経路のセクションの前記ノードシーケンスが前記基準経路のセクションのノードシーケンスと反対であり、かつ、
前記セクションの前記ナビゲーション長と前記地理的長さとの差がしきい値を超えない場合には、
前記第2の候補経路の前記セクションは異なるセクションではない、請求項13に記載の方法。
【請求項１５】
コンピュータプログラム製品を具体化する非一時的コンピュータ可読媒体であって、前記コンピュータプログラム製品は、コンピューティングデバイスに対して、
複数の第1の候補経路を生成するために複数のノードをつなぎ合わせ、前記複数のノードは1つまたは複数の要求に基づいて決定され、前記複数の第1の候補経路は前記複数のノードに関する第1の条件を満たし、
前記複数のノードのうちのいずれか2つの間の地理的距離に基づいて、前記複数の第1の候補経路の各々の地理的長さを決定し、
前記複数の第1の候補経路の各々の前記地理的長さに基づいて、前記複数の第1の候補経路の中から1つまたは複数の第2の候補経路を決定し、
前記1つまたは複数の第2の候補経路の各々のナビゲーション長を決定し、
前記1つまたは複数の第2の候補経路の前記1つまたは複数のナビゲーション長に基づいて、前記1つまたは複数の第2の候補経路の中からターゲット経路を決定し、前記ターゲット経路の前記ナビゲーション長は、前記1つまたは複数の第2の候補経路のうちで最短である、
ことをさせるように構成された命令を含む、非一時的コンピュータ可読媒体。
【国際調査報告】
2021512291.tif 000012
2021512291.tif 000013