(57)【要約】本発明の一実施例に係るサーバーによって計算された複数の経由地を含む旅行（ｔｒｉｐ）の経路を受信するための方法であって、前記方法は、端末によって行われ、前記複数の経由地を含む旅行に対する経路の要請をサーバーに伝送すること―前記要請は、前記複数の経由地を含む経路を要請することを示す指示子及び前記複数の経由地情報を含む。―、及び前記複数の経由地を含む旅行の提案経路に対する情報を前記サーバーから受信する段階を含み、前記方法は、前記旅行の提案経路が複数のサブ経路で構成され、前記提案経路に対する情報が、前記旅行の提案経路が何個のサブ経路で構成されたのかを指示する情報、及び前記サブ経路のうち１番目のサブ経路に対するリンクを含むと、前記１番目のサブ経路に対するリンクを通じて前記１番目のサブ経路に対する情報を受信することを含むことができる。
2016512604.tif 000002
【特許請求の範囲】
【請求項１】
サーバーによって計算された複数の経由地を含む旅行（ｔｒｉｐ）の経路を受信するための方法であって、前記方法は、端末によって行われ、
前記複数の経由地を含む旅行に対する経路の要請をサーバーに伝送すること―前記要請は、前記複数の経由地を含む経路を要請することを示す指示子及び前記複数の経由地情報を含む。―；及び
前記複数の経由地を含む旅行の提案経路に対する情報を前記サーバーから受信することを含み、
前記方法は：
前記旅行の提案経路が複数のサブ経路で構成され、前記提案経路に対する情報が、前記旅行の提案経路が何個のサブ経路で構成されたのかを指示する情報、及び前記サブ経路のうち１番目のサブ経路に対するリンクを含むと、前記１番目のサブ経路に対するリンクを通じて前記１番目のサブ経路に対する情報を受信することを含み、
前記１番目のサブ経路に対する情報は、前記１番目のサブ経路に後続する２番目のサブ経路が存在するか否かを指示する指示子及び前記２番目のサブ経路に対するリンクを含むことを特徴とする、経路受信方法。
【請求項２】
前記方法は：
Ｎ（Ｎ＞２）番目のサブ経路に対するリンクを通じて前記Ｎ番目のサブ経路に対する情報を受信することをさらに含むことを特徴とする、請求項１に記載の経路受信方法。
【請求項３】
前記Ｎ番目のサブ経路に対する情報は、Ｎ＋１番目のサブ経路が存在するか否かを指示する指示子、及び前記Ｎ＋１番目のサブ経路に対するリンクを含み、
前記Ｎ＋１番目のサブ経路に対するリンクは、前記Ｎ＋１番目のサブ経路が存在する場合に前記Ｎ番目のサブ経路に対する情報に含まれることを特徴とする、請求項２に記載の経路受信方法。
【請求項４】
前記要請は、前記経路の最大許容運行時間、前記複数の経由地のそれぞれに対する優先順位、及び前記複数の経由地のそれぞれで留まる時間のうち少なくとも一つで構成された経路条件を含み、
前記提案経路は、前記経路条件に基づいて計算されることを特徴とする、請求項１に記載の経路受信方法。
【請求項５】
前記サーバーによって計算された特定提案経路の運行所要時間が前記最大許容運行時間を超える場合、前記特定提案経路から前記優先順位によって前記複数の経由地のうち少なくとも一つが除外されることを特徴とする、請求項４に記載の経路受信方法。
【請求項６】
前記提案経路は、運行所要時間基準又は運行距離基準で複数のサブ経路に分割されることを特徴とする、請求項１に記載の経路受信方法。
【請求項７】
前記複数のサブ経路のそれぞれは、互いに異なる時点の道路交通情報に基づくことを特徴とする、請求項１に記載の経路受信方法。
【請求項８】
前記複数のサブ経路のそれぞれは、時間差を置いて受信されることを特徴とする、請求項１に記載の経路受信方法。
【請求項９】
サーバーによって計算された複数の経由地を含む旅行（ｔｒｉｐ）の経路を端末に提供するための方法であって、前記方法は、サーバーによって行われ、
前記複数の経由地を含む旅行に対する経路の要請を前記端末から受信すること―前記要請は、前記複数の経由地を含む経路を要請することを示す情報及び前記複数の経由地情報を含む。―；
前記複数の経由地を含む旅行の提案経路を計算すること；及び
前記提案経路に対する情報を前記端末に伝送することを含み、
前記旅行の提案経路が複数のサブ経路で構成され、前記提案経路に対する情報が、前記旅行の提案経路が何個のサブ経路で構成されたのかを指示する情報、及び前記サブ経路のうち１番目のサブ経路に対するリンクを含むと、前記端末は、前記１番目のサブ経路に対するリンクを通じて前記１番目のサブ経路に対する情報を受信するように構成され、
前記１番目のサブ経路に対する情報は、前記１番目のサブ経路に後続する２番目のサブ経路が存在するか否かを指示する指示子、及び前記２番目のサブ経路に対するリンクを含むことを特徴とする、経路提供方法。
【請求項１０】
Ｎ（Ｎ＞２）番目のサブ経路に対するリンクを通じて前記Ｎ番目のサブ経路に対する情報が前記端末に提供されることを特徴とする、請求項９に記載の経路提供方法。
【請求項１１】
前記Ｎ番目のサブ経路に対する情報は、Ｎ＋１番目のサブ経路が存在するか否かを指示する指示子、及び前記Ｎ＋１番目のサブ経路に対するリンクを含み、
前記Ｎ＋１番目のサブ経路に対するリンクは、前記Ｎ＋１番目のサブ経路が存在する場合に前記Ｎ番目のサブ経路に対する情報に含まれることを特徴とする、請求項１０に記載の経路提供方法。
【請求項１２】
前記要請は、前記経路の最大許容運行時間、前記複数の経由地のそれぞれに対する優先順位、及び前記複数の経由地のそれぞれで留まる時間のうち少なくとも一つで構成された経路条件を含み、
前記提案経路は、前記経路条件に基づいて計算されることを特徴とする、請求項９に記載の経路提供方法。
【請求項１３】
前記サーバーによって計算された特定提案経路の運行所要時間が前記最大許容運行時間を超える場合、前記特定提案経路から前記優先順位によって前記複数の経由地のうち少なくとも一つが除外されることを特徴とする、請求項１２に記載の経路提供方法。
【請求項１４】
前記提案経路は、運行所要時間基準又は運行距離基準で複数のサブ経路に分割されることを特徴とする、請求項９に記載の経路提供方法。
【請求項１５】
前記複数のサブ経路のそれぞれは、互いに異なる時点の道路交通情報に基づくことを特徴とする、請求項９に記載の経路提供方法。
【請求項１６】
前記複数のサブ経路のそれぞれは、時間差を置いて提供されることを特徴とする、請求項９に記載の経路提供方法。
【請求項１７】
サーバーによって計算された複数の経由地を含む旅行（ｔｒｉｐ）の経路を受信するように構成された端末であって、
サーバーと通信するように構成された送受信機；及び
前記サーバーから受信される情報に基づいて前記経路に対する更新情報を獲得するように構成されたプロセッサを含み、
前記プロセッサは：
前記複数の経由地を含む旅行に対する経路の要請をサーバーに伝送し、前記要請は、前記複数の経由地を含む経路を要請することを示す情報、及び前記複数の経由地情報を含み；前記複数の経由地を含む旅行の提案経路に対する情報を前記サーバーから受信するように構成され、
前記旅行の提案経路に対する情報が、前記旅行の提案経路が何個のサブ経路で構成されたのかを指示する情報、及び前記サブ経路のうち１番目のサブ経路に対するリンクを含むと、前記プロセッサは、前記１番目のサブ経路に対するリンクを通じて前記１番目のサブ経路に対する情報を受信するように構成され、
前記１番目のサブ経路に対する情報は、前記１番目のサブ経路に後続する２番目のサブ経路が存在するか否かを指示する指示子、及び前記２番目のサブ経路に対するリンクを含むことを特徴とする、端末。
【請求項１８】
サーバーによって計算された複数の経由地を含む旅行（ｔｒｉｐ）の経路を端末に提供するように構成されたサーバーであって、
端末と通信するように構成された送受信機；及び
前記端末から受信される情報に基づいて前記経路に対する更新情報を生成するように構成されたプロセッサを含み、
前記プロセッサは：
前記複数の経由地を含む旅行に対する経路の要請を前記端末から受信し、前記要請は、前記複数の経由地を含む経路を要請することを示す情報及び前記複数の経由地情報を含み；前記複数の経由地を含む旅行の提案経路に対する情報を前記端末に伝送するように構成され、
前記旅行の提案経路が複数のサブ経路で構成され、前記提案経路に対する情報が、前記旅行の提案経路が何個のサブ経路で構成されたのかを指示する情報、及び前記サブ経路のうち１番目のサブ経路に対するリンクを含むと、前記端末は、前記１番目のサブ経路に対するリンクを通じて前記１番目のサブ経路に対する情報を受信するように構成され、
前記１番目のサブ経路に対する情報は、前記１番目のサブ経路に後続する２番目のサブ経路が存在するか否かを指示する指示子、及び前記２番目のサブ経路に対するリンクを含むことを特徴とする、サーバー。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路を伝達する方法及びこのための装置に関し、より詳細には、複数の経由地を含む経路を伝達するための方法及びこのための装置に関する。
【背景技術】
【０００２】
従来は、ナビゲーション（ｎａｖｉｇａｔｉｏｎ）端末がＧＰＳ（Ｇｌｏｂａｌ  Ｐｏｓｉｔｉｏｎｉｎｇ  Ｓｙｓｔｅｍ）との連結を通じて現在の位置、すなわち、出発地を検出し、ユーザーから旅行の目的地の入力を受け、端末機自体で経路を計算する方式が用いられた。しかし、最近、スマートフォンの普及と性能向上により、移動通信網でＰＮＤｓ（Ｐｅｒｓｏｎａｌ  Ｎａｖｉｇａｔｉｏｎ  Ｄｅｖｉｃｅｓ）を用いて交通情報及び経路情報を提供するサーバーから経路情報、経路関連リアルタイム交通情報及び多様な情報を提供するサービス方式が活用されている。
【０００３】
特に、多様な形態のナビゲーションサービスが提供される中、ＯＭＡ（Ｏｐｅｎ  Ｍｏｂｉｌｅ  Ａｌｌｉａｎｃｅ）標準化団体では、既存の放送形態で情報が提供されるＤＭＢ（Ｄｉｇｉｔａｌ  Ｍｕｌｔｉｍｅｄｉａ  Ｂｒｏａｄｃａｓｔｉｎｇ）網でＴＰＥＧ（Ｔｒａｆｆｉｃ  Ｐｒｏｔｏｃｏｌ  Ｅｘｐｅｒｔ  Ｇｒｏｕｐ）情報を伝達する方式ではなく、移動通信網や無線網のＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）基盤のネットワークを介してリアルタイム交通情報をＰ２Ｐ（Ｐｅｅｒ―ｔｏ―Ｐｅｅｒ）で伝達するダイナミックナビゲーションイネーブラー（Ｄｙｎａｍｉｃ  Ｎａｖｉｇａｔｉｏｎ  Ｅｎａｂｌｅｒ、ＤｙｎＮａｖ）を標準化している。該当の標準では、スマートフォンのナビゲーション端末とサービスの形態を大きく二つに分けている。
【０００４】
第一の形態は、複雑な経路計算をスマートフォンに搭載されたナビゲーションアプリケーションで行わず、交通情報及び経路情報を提供するサーバーで行い、該当の経路を前記スマートフォンに伝達する形態である。第二の形態は、スマートフォンの性能向上により、経路計算をスマートフォンに搭載されたアプリケーション自体で行う場合、又は移動通信モデムを装着したナビゲーション端末機が経路計算を行う場合であって、経路情報を交通情報を提供するサーバーが伝達せず、前記端末が計算した経路を前記サーバーに登録すると、前記経路と関連したリアルタイム交通情報のみを既存の放送の形態でないＩＰ基盤のＰ２Ｐで前記サーバーからカスタマイズ型で受け取ることができる形態である。
【０００５】
図１は、ナビゲーション装置に対する区分を示している。ナビゲーション装置は、ＤＭＢなどの放送網を介して伝達されるＴＰＥＧ基盤の交通情報を追加的に伝達する形態１１０、移動通信網又はＷｉ―ＦｉなどのＩＰ基盤で交通情報を追加的に伝達する形態１２０、そして、他の通信媒体との連結なく、ＧＰＳとの連結を通じて車両の位置を追跡し、経路情報を生成及び提供するスタンドアローン（Ｓｔａｎｄａｌｏｎｅ）形態１３０に区分することができる。
【０００６】
また、ＯＭＡ  ＬＯＣ  ＷＧで現在標準化しているＤｙｎＮａｖは、前記の区分においてＩＰ基盤の交通情報を伝達する形態１２０、より詳細には、Ｐ２Ｐ形態で伝達する区分に属し、ＤｙｎＮａｖでは、ナビゲーション装置を下記のように２つに区分している。
【０００７】
１．スマートＮＤ（Ｓｍａｒｔ  ＮＤ、１２２）：自ら経路計算が可能であり、ＤｙｎＮａｖサーバーを介して経路情報を受信せず、リアルタイム交通情報のみを要請する装置
２．軽量ＮＤ（Ｌｉｇｈｔｗｅｉｇｈｔ  ＮＤ、１２１）：自ら経路計算が不可能であり、ＤｙｎＮａｖサーバーを介して経路情報を含む全てのリアルタイム交通情報を要請する装置
従来のＤｙｎＮａｖシステムでは、該当の交通情報を要請して伝達する過程をＲＥＳＴｆｕｌ基盤で行うので、次のような経路情報形式を使用し、各情報形式はＸＳＤ（ＸＭＬ  Ｓｃｈｅｍａ  Ｄｅｆｉｎｉｔｉｏｎ）として定義可能である。
【０００８】
１）Ｔｒｉｐ  Ｓｔｒｕｃｔｕｒｅ（トリップ構造）：最初の端末がユーザーから経路設定のために伝達を受けた情報であって、基本的に出発地と目的地などの情報を獲得した後、該当の情報をサーバーに伝達する。トリップ構造は、多数の経路構造に該当する部分集合からなる。
【０００９】
【表１−１】
2016512604.tif 000003
【００１０】
【表１−２】
2016512604.tif 000004
【００１１】
【表１−３】
2016512604.tif 000005
２）Ｒｏｕｔｅ  Ｓｔｒｕｃｔｕｒｅ（経路構造）：トリップ構造を通じて計算された全体の経路を表現する方式であって、経路構造は、多数のセグメントで表現される。
【００１２】
【表２−１】
2016512604.tif 000006
【００１３】
【表２−２】
2016512604.tif 000007
【００１４】
【表２−３】
2016512604.tif 000008
３）Ｓｅｇｍｅｎｔ  Ｓｔｒｕｃｔｕｒｅ：各セグメントを表現する構造体であって、各セグメントの長さのみならず、該当のセグメントに該当するリアルタイム交通状況を（ＴＰＥＧ）の表現基盤で定義することができる。
【００１５】
【表３−１】
2016512604.tif 000009
【００１６】
【表３−２】
2016512604.tif 000010
４）Ｓｕｂｓｃｒｉｐｔｉｏｎ  Ｌｉｓｔ  Ｓｔｒｕｃｔｕｒｅ：加入（ｓｕｂｓｃｒｉｐｔｉｏｎ）のリストを示す。
【００１７】
【表４】
2016512604.tif 000011
５）Ｓｕｂｓｃｒｉｐｔｉｏｎ  ｓｔｒｕｃｔｕｒｅ：加入
【００１８】
【表５−１】
2016512604.tif 000012
【表５−２】
2016512604.tif 000013
図２は、従来のＤｙｎＮａｖシステムでの軽量ＮＤ（Ｌｉｇｈｔｗｅｉｇｈｔ  ＮＤ）の動作を示したフローチャートである。軽量ＮＤは、自体の性能（Ｃａｐａｂｉｌｉｔｙ）が経路計算をサポートしないので、サーバーに経路情報を要請し、サーバーから経路情報を受信しなければならない。代表的な機能は、次の通りである。
【００１９】
―  軽量ＮＤがサーバーの経路計算のための旅行（Ｔｒｉｐ）情報をサーバーに伝達
―  軽量ＮＤがサーバーによって計算された経路（推薦経路を含む）のセット（ｓｅｔ）をサーバーから受信
―  軽量ＮＤがサーバーからリアルタイム交通情報通報（Ｎｏｔｉｆｉｃａｔｉｏｎ）サービスを受信するためにサービス加入（Ｓｕｂｓｃｒｉｐｔｉｏｎ）
図２に示したフローチャートの大略的な内容は、次の通りである。
【００２０】
１．アプリケーションのユーザーは、各旅行パラメーター（ｊｏｕｒｎｅｙ  ｐａｒａｍｅｔｅｒ）を定義し、前記アプリケーションは、前記各パラメーターをサーバーに伝送する：前記サーバーは、関連交通（ｔｒａｆｆｉｃ）情報を用いて受信されたパラメーターに基づいて一つのセットの各提案経路を計算する。前記サーバーは、前記アプリケーションに前記各提案経路の各経路識別子を含む生成された「トリップ（ｔｒｉｐ）」リソースで応答する。
【００２１】
２．前記アプリケーションは、要約されたフォーマット（ｓｕｍｍａｒｉｚｅｄ  ｆｏｒｍａｔ）の前記一つのセットの各経路にアクセスする。この段階は、前記サーバーによって提案された全ての経路に対して繰り返される。しかし、前記トリップの長さ及び複雑度が制限されたり、ネットワーク品質が不適切であると、全体のフォーマット（ｆｕｌｌ  ｆｏｒｍａｔ）経路情報をこの段階で使用することができる。前記アプリケーションは、前記提案された各経路に対するシェイプ（ｓｈａｐｅ）情報（ＷＧＳ８４座標ポリライン）がナビゲーション装置で利用可能でない場合、これを要請することができる。
【００２２】
３．前記ユーザーは、前記提案されたセットのうち一つの経路を選択し、前記アプリケーションは、前記ユーザーが選択した経路に対する全体のフォーマット情報にアクセスする。前記アプリケーションは、前記提案された各経路に対するシェイプ（ｓｈａｐｅ）情報（ＷＧＳ８４座標ポリライン）がナビゲーション装置で利用可能でない場合、これを要請することができる。段階２において、前記全体のフォーマット経路が獲得されると、この段階は必要でない。前記サーバーは、前記選択された経路情報に関連交通情報と共に応答する。
【００２３】
４．前記アプリケーションは、提供された各交通イベントリソースに対する各リンクを使用して前記経路と関連する各交通イベントにアクセスする。前記各交通イベントに対するアクセスは、前記ユーザーによって選択された各カテゴリーに制限することができる。
【００２４】
５．前記アプリケーションは、前記サーバーによって以前に提案されたが、前記ユーザーによって選択されていない不必要な各経路を除去する。
【００２５】
６．前記アプリケーションは、前記トリップ（経路）に対する通知サービスに加入（ｓｕｂｓｃｒｉｐｔｉｏｎ）を生成するように前記サーバーに要請する。前記アプリケーションは、次の各イベントに対して前記サーバーによって通知される：
ａ．前記トリップと関連する全ての経路に対する各パフォーマンスパラメーターのアップデート及び新たな各トラフィックイベント（選択された各カテゴリーに対する）
ｂ．使用する各経路による交通問題による各代案経路の提案
ｃ．前記トリップの目的地が第３者の位置で、前記第３者の位置が変更された場合、更新された目的地及び／又は前記第３者への経路。この情報の通知を可能にするために、前記アプリケーションは、前記通知の加入で前記サーバーによる前記第３者の位置の追跡手順を要請しなければならない。
【００２６】
７．（前記アプリケーションが搭載された）車両が使用している経路から逸脱したり迂回する場合；前記アプリケーションは、トリップリソースの出発地パラメーターを修正する。前記サーバーは、現在の位置が使用している前記経路に属していないと認識し、新たな出発地を用いて新たな経路を計算する。前記サーバーは、前記新たな経路の識別子で応答し、以前の経路（及び識別子）を削除する。前記修正された出発地パラメーターが前記以前の経路に属する場合、前記サーバーは、前記経路から既に運行されたセグメントを削除するためにこの情報を使用する。
【００２７】
―  前記段階７は、前記車両が迂回したり経路から逸脱した場合、そして、前記車両が以前に報告された地点から特定距離だけ移動した場合、そして／又は前記車両が、前記サーバーが現在の位置をアップロードするように要請したセグメントに進入した場合に発生する。
【００２８】
８．前記サーバーは、前記更新されたトラフィック情報（各トラフィックイベント及び各パフォーマンスパラメーター）を含むトリップ及び経路を含む、変更された各リソースに対する各リンクを用いて前記アプリケーションに通知リソースを伝達する。
【００２９】
９．前記アプリケーションは、各パフォーマンスパラメーター及び各交通イベントと共に、前記新たな提案経路にアクセスする。前記アプリケーションが前記トリップリソースに対する通知サービスに加入したので、前記加入は前記新たな提案経路をカバーし得る。
【００３０】
１０．前記提案された各経路上の各トラフィックイベント、深刻な停滞及び／又は前記第３者の位置変更が前記サーバーによって検出されると、前記サーバーは、更新された情報のＵＲＬ（Ｕｎｉｆｏｒｍ  Ｒｅｓｏｕｒｃｅ  Ｌｏｃａｔｏｒ）を使用して通知する。
【００３１】
１１．前記アプリケーションは、使用している前記経路に対する更新情報、新たな関連する各交通イベント及び前記提案された代案経路にアクセスし、前記通知サービスの加入が前記トリップと関連する全ての経路を含むので、前記通知は、前記提案された代案経路にまで拡張される。前記第３者の位置が変更された場合、前記アプリケーションは、目的地として前記変更された第３者の位置及び／又は前記更新された経路リソースにアクセスする。
【００３２】
一方、このような軽量ＮＤサービスにおいて、ユーザーが一つ以上の経由地を含む経路を要請する必要が度々発生する。例えば、ナビゲーションサービスに対するより多様なサービス提供、ユーザー満足度／経験向上などのために一つ以上の経由地を含む経路が要請され、これをサーバー側で提供する方案が考慮される。例えば、ユーザーが一定時間内に多くの地理的場所を訪問しなければならないので、経路要請時に多くの経由地を入力することができる。
【００３３】
併せて、このような一つ以上の経由地を含む経路を要請又は提供する方案は、前記経路の経由地が一つ以上であるので、いくつかの重要に考慮する事項がある。本明細書では、このような一つ以上の経由地を含む経路を提供する方案とそれに伴ういくつかの問題を解決するための具体的な方案を提案しようとする。
【発明の概要】
【発明が解決しようとする課題】
【００３４】
本発明では、上述した一つ以上の経由地を含む経路を提供するサービスの形態で発生する問題を解消するための方式を提案することを主要な目的とする。
【００３５】
本発明で達成しようとする技術的課題は、前記技術的課題に制限されず、言及していない更に他の技術的課題は、下記の記載から本発明の属する技術分野で通常の知識を有する者に明確に理解され得るだろう。
【課題を解決するための手段】
【００３６】
本発明の一実施例に係るサーバーによって計算された複数の経由地を含む旅行（ｔｒｉｐ）の経路を受信するための方法であって、前記方法は、端末によって行われ、前記複数の経由地を含む旅行に対する経路の要請をサーバーに伝送すること―前記要請は、前記複数の経由地を含む経路を要請することを示す指示子及び前記複数の経由地情報を含む。―、及び前記複数の経由地を含む旅行の提案経路に対する情報を前記サーバーから受信することを含み、前記方法は、前記旅行の提案経路が複数のサブ経路で構成され、前記提案経路に対する情報が、前記旅行の提案経路が何個のサブ経路で構成されたのかを指示する情報、及び前記サブ経路のうち１番目のサブ経路に対するリンクを含むと、前記１番目のサブ経路に対するリンクを通じて前記１番目のサブ経路に対する情報を受信することを含み、前記１番目のサブ経路に対する情報は、前記１番目のサブ経路に後続する２番目のサブ経路が存在するか否かを指示する指示子、及び前記２番目のサブ経路に対するリンクを含むことができる。
【００３７】
好ましくは、前記方法は、Ｎ（Ｎ＞２）番目のサブ経路に対するリンクを通じて前記Ｎ番目のサブ経路に対する情報を受信することをさらに含むことができる
好ましくは、前記Ｎ番目のサブ経路に対する情報は、Ｎ＋１番目のサブ経路が存在するか否かを指示する指示子、及び前記Ｎ＋１番目のサブ経路に対するリンクを含み、前記Ｎ＋１番目のサブ経路に対するリンクは、前記Ｎ＋１番目のサブ経路が存在する場合、前記Ｎ番目のサブ経路に対する情報に含ませることができる。
【００３８】
好ましくは、前記要請は、前記経路の最大許容運行時間、前記複数の経由地のそれぞれに対する優先順位、及び前記複数の経由地のそれぞれで留まる時間のうち少なくとも一つで構成された経路条件を含み、前記提案経路は、前記経路条件に基づいて計算することができる。
【００３９】
好ましくは、前記サーバーによって計算された特定提案経路の運行所要時間が前記最大許容運行時間を超える場合、前記特定提案経路から前記優先順位によって前記複数の経由地のうち少なくとも一つを除外することができる。
【００４０】
好ましくは、前記提案経路は、運行所要時間基準又は運行距離基準で複数のサブ経路に分割することができる。
【００４１】
好ましくは、前記複数のサブ経路のそれぞれは、互いに異なる時点の道路交通情報に基づくことができる。
【００４２】
好ましくは、前記複数のサブ経路のそれぞれは、時間差を置いて受信することができる。
【００４３】
本発明の一実施例に係るサーバーによって計算された複数の経由地を含む旅行（ｔｒｉｐ）の経路を端末に提供するための方法であって、前記方法は、サーバーによって行われ、前記複数の経由地を含む旅行に対する経路の要請を前記端末から受信すること―前記要請は、前記複数の経由地を含む経路を要請することを示す情報及び前記複数の経由地情報を含む。―；前記複数の経由地を含む旅行の提案経路を計算すること；及び前記提案経路に対する情報を前記端末に伝送することを含み、前記旅行の提案経路が複数のサブ経路で構成され、前記提案経路に対する情報が、前記旅行の提案経路が何個のサブ経路で構成されたのかを指示する情報、及び前記サブ経路のうち１番目のサブ経路に対するリンクを含むと、前記端末は、前記１番目のサブ経路に対するリンクを通じて前記１番目のサブ経路に対する情報を受信するように構成され、前記１番目のサブ経路に対する情報は、前記１番目のサブ経路に後続する２番目のサブ経路が存在するか否かを指示する指示子、及び前記２番目のサブ経路に対するリンクを含むことができる。
【００４４】
好ましくは、Ｎ（Ｎ＞２）番目のサブ経路に対するリンクを通じて前記Ｎ番目のサブ経路に対する情報を前記端末に提供することができる。
【００４５】
好ましくは、前記Ｎ番目のサブ経路に対する情報は、Ｎ＋１番目のサブ経路が存在するか否かを指示する指示子、及び前記Ｎ＋１番目のサブ経路に対するリンクを含み、前記Ｎ＋１番目のサブ経路に対するリンクは、前記Ｎ＋１番目のサブ経路が存在する場合に前記Ｎ番目のサブ経路に対する情報に含ませることができる。
【００４６】
好ましくは、前記要請は、前記経路の最大許容運行時間、前記複数の経由地のそれぞれに対する優先順位、及び前記複数の経由地のそれぞれで留まる時間のうち少なくとも一つで構成された経路条件を含み、前記提案経路は、前記経路条件に基づいて計算することができる。
【００４７】
好ましくは、前記サーバーによって計算された特定提案経路の運行所要時間が前記最大許容運行時間を超える場合、前記特定提案経路から前記優先順位によって前記複数の経由地のうち少なくとも一つを除外することができる。
【００４８】
好ましくは、前記提案経路は、運行所要時間基準又は運行距離基準で複数のサブ経路に分割することができる。
【００４９】
好ましくは、前記複数のサブ経路のそれぞれは、互いに異なる時点の道路交通情報に基づくことができる。
【００５０】
好ましくは、前記複数のサブ経路のそれぞれは、時間差を置いて提供することができる。
【００５１】
本発明の一実施例に係るサーバーによって計算された複数の経由地を含む旅行（ｔｒｉｐ）の経路を受信するように構成された端末であって、サーバーと通信するように構成された送受信機；及び前記サーバーから受信される情報に基づいて前記経路に対する更新情報を獲得するように構成されたプロセッサを含み、前記プロセッサは、前記複数の経由地を含む旅行に対する経路の要請をサーバーに伝送し、前記要請は、前記複数の経由地を含む経路を要請することを示す情報及び前記複数の経由地情報を含み、前記複数の経由地を含む旅行の提案経路に対する情報を前記サーバーから受信するように構成され、前記旅行の提案経路に対する情報が、前記旅行の提案経路が何個のサブ経路で構成されたのかを指示する情報、及び前記サブ経路のうち１番目のサブ経路に対するリンクを含むと、前記プロセッサは、前記１番目のサブ経路に対するリンクを通じて前記１番目のサブ経路に対する情報を受信するように構成され、前記１番目のサブ経路に対する情報は、前記１番目のサブ経路に後続する２番目のサブ経路が存在するか否かを指示する指示子、及び前記２番目のサブ経路に対するリンクを含むことができる。
【００５２】
本発明の一実施例に係るサーバーによって計算された複数の経由地を含む旅行（ｔｒｉｐ）の経路を端末に提供するように構成されたサーバーであって、端末と通信するように構成された送受信機；及び前記端末から受信される情報に基づいて前記経路に対する更新情報を生成するように構成されたプロセッサを含み、前記プロセッサは、前記複数の経由地を含む旅行に対する経路の要請を前記端末から受信し、前記要請は、前記複数の経由地を含む経路を要請することを示す情報及び前記複数の経由地情報を含み；前記複数の経由地を含む旅行の提案経路に対する情報を前記端末に伝送するように構成され、前記旅行の提案経路が複数のサブ経路で構成され、前記提案経路に対する情報が、前記旅行の提案経路が何個のサブ経路で構成されたのかを指示する情報、及び前記サブ経路のうち１番目のサブ経路に対するリンクを含むと、前記端末は、前記１番目のサブ経路に対するリンクを通じて前記１番目のサブ経路に対する情報を受信するように構成され、前記１番目のサブ経路に対する情報は、前記１番目のサブ経路に後続する２番目のサブ経路が存在するか否かを指示する指示子、及び前記２番目のサブ経路に対するリンクを含むことができる。
【００５３】
前記技術的解決方法は、本発明の各実施例の一部に過ぎなく、本願発明の技術的特徴が反映された多様な実施例は、当該技術分野で通常の知識を有する者によって以下で説明する本発明の詳細な説明に基づいて導出されて理解され得る。
【発明の効果】
【００５４】
本発明の実施例によると、ナビゲーション装置（又はアプリケーション）とサーバーとの間に発生し得る不必要なデータ伝送及び伝達を減少させ、これを通じて、サービス品質及び／又はユーザーのサービス経験（ＱｏＥ：Ｑｕａｌｉｔｙ  ｏｆ  Ｅｘｐｅｒｉｅｎｃｅ）を高めることができる。
【図面の簡単な説明】
【００５５】
本発明に関する理解を促進するために詳細な説明の一部として含まれる添付の図面は、本発明に対する実施例を提供し、詳細な説明と共に本発明の技術的思想を説明する。
【図１】ナビゲーション装置に対する区分を示す図である。
【図２】従来のＤｙｎＮａｖシステムにおける軽量ＮＤ（Ｌｉｇｈｔｗｅｉｇｈｔ  ＮＤ）の動作を示したフローチャートである。
【図３】本発明のナビゲーションシステムであるＩＰ基盤のＤｙｎＮａｖシステム全般を説明するためのネットワーク構成図である。
【図４】ＴＰＥＧの階層構造を示す図である。
【図５】本発明の一実施例に係る複数の経由地を含む経路を例示する図である。
【図６】本発明の一実施例に係るそれぞれの経由地で留まる時間を考慮した複数の経由地を含む経路を例示する図である。
【図７】本発明の一実施例に係る分割経由地情報提供方案に対して例示する図である。
【図８】本発明の一実施例に係る動作を例示する図である。
【図９】本発明の各実施例が具現され得る装置のブロック図である。
【発明を実施するための形態】
【００５６】
以下では、本発明に係る好ましい実施形態を添付の図面を参照して詳細に説明する。添付の図面と共に、以下で開示する詳細な説明は、本発明の例示的な実施形態を説明するためのものであって、本発明が実施され得る唯一の実施形態を示すためのものではない。以下の詳細な説明は、本発明の完全な理解を提供するために具体的な細部事項を含む。しかし、当業者であれば、本発明がこのような具体的な細部事項がなくても実施され得ることが分かる。
【００５７】
いくつかの場合、本発明の概念が曖昧になることを避けるために、公知の構造及び装置は省略したり、各構造及び装置の核心機能を中心にしたブロック図の形式で図示することができる。また、本明細書全体にわたって同一の構成要素に対しては、同一の図面符号を使用して説明する。
【００５８】
一方、本明細書で使用される用語について定義する。
【００５９】
（アプリケーション（Ａｐｐｌｉｃａｔｉｏｎ））
本明細書において、アプリケーションは、ユーザーの代わりに業務を行う、よく定義されたが、標準化されていない各機能のセットの具現を意味する。前記アプリケーションは、ソフトウェア及び／又はハードウェア要素、そして、関連したユーザーインターフェースからなり得る（Ａｎ  ｉｍｐｌｅｍｅｎｔａｔｉｏｎ  ｏｆ  ａ  ｗｅｌｌ―ｄｅｆｉｎｅｄ  ｂｕｔ  ｎｏｔ  ｓｔａｎｄａｒｄｉｚｅｄ  ｓｅｔ  ｏｆ  ｆｕｎｃｔｉｏｎｓ  ｔｈａｔ  ｐｅｒｆｏｒｍｓ  ｗｏｒｋ  ｏｎ  ｂｅｈａｌｆ  ｏｆ  ｔｈｅ  ｕｓｅｒ．Ｉｔ  ｍａｙ  ｃｏｎｓｉｓｔ  ｏｆ  ｓｏｆｔｗａｒｅ  ａｎｄ／ｏｒ  ｈａｒｄｗａｒｅ  ｅｌｅｍｅｎｔｓ  ａｎｄ  ａｓｓｏｃｉａｔｅｄ  ｕｓｅｒ  ｉｎｔｅｒｆａｃｅｓ．）。
【００６０】
（サーバー（Ｓｅｒｖｅｒ））
一般に、本発明の属する技術分野において、サーバーは、各要請に応答して各クライアントに各資源を提供するエンティティに該当する（Ａｎ  ｅｎｔｉｔｙ  ｔｈａｔ  ｐｒｏｖｉｄｅｓ  ｒｅｓｏｕｒｃｅｓ  ｔｏ  Ｃｌｉｅｎｔｓ  ｉｎ  ｒｅｓｐｏｎｓｅ  ｔｏ  ｒｅｑｕｅｓｔｓ．）。
【００６１】
（クライアント（Ｃｌｉｅｎｔ））
一般に、本発明の属する技術分野において、クライアントは、サービスの受信者として動作するデバイス、ユーザーエージェント又は他のエンティティに該当する（Ａ  ｄｅｖｉｃｅ，ｕｓｅｒ  ａｇｅｎｔ，ｏｒ  ｏｔｈｅｒ  ｅｎｔｉｔｙ  ｔｈａｔ  ａｃｔｓ  ａｓ  ｔｈｅ  ｒｅｃｅｉｖｅｒ  ｏｆ  ａ  ｓｅｒｖｉｃｅ．）。
【００６２】
（ＤｙｎＮａｖアプリケーション（ＤｙｎＮａｖ  Ａｐｐｌｉｃａｔｉｏｎ））
本明細書において、ＤｙｎＮａｖは、最適な経路、リアルタイム及び未来に予想される交通情報及び補助データを得るためにＤｙｎＮａｖサーバーと相互作用する責任を有するエンティティに該当する（Ａｎ  ｅｎｔｉｔｙ  ｔｈａｔ  ｉｓ  ｉｎ  ｃｈａｒｇｅ  ｏｆ  ｉｎｔｅｒａｃｔｉｎｇ  ｗｉｔｈ  ａ  ＤｙｎＮａｖ  Ｓｅｒｖｅｒ  ｔｏ  ｇｅｔ  ｏｐｔｉｍａｌ  ｒｏｕｔｅ（ｓ），ｒｅａｌ―ｔｉｍｅ  ａｎｄ  ｆｏｒｅｃａｓｔｅｄ  ｔｒａｆｆｉｃ  ｉｎｆｏｒｍａｔｉｏｎ  ａｎｄ  ｃｏｍｐｌｉｍｅｎｔａｒｙ  ｄａｔａ．）。したがって、前記ＤｙｎＮａｖアプリケーションは、スマートフォン、モバイルフォン、ナビゲーションデバイスなどを含む端末に搭載され、これによって、本明細書において、前記ＤｙｎＮａｖアプリケーションは、端末と相互交換可能なものと称することができる。このような側面で、前記ＤｙｎＮａｖアプリケーションは、クライアントの一種に該当する。本発明においては、ＤｙｎＮａｖアプリケーションをソース端末又は目的端末、あるいはそのまま「端末」と称する。ソース端末は、目的端末位置基盤の経路設定サービスを要請する端末を意味し、目的端末は、該当のサービスで目的地となる個体を意味する。
【００６３】
（ＤｙｎＮａｖサーバー（ＤｙｎＮａｖ  Ｓｅｒｖｅｒ））
本明細書において、ＤｙｎＮａｖサーバーは、前記アプリケーションに最適な経路、リアルタイム及び未来に予想される交通情報及び補助データを提供する責任を有するエンティティに該当する（Ａｎ  ｅｎｔｉｔｙ  ｔｈａｔ  ｉｓ  ｉｎ  ｃｈａｒｇｅ  ｏｆ  ｐｒｏｖｉｄｉｎｇ  ｔｏ  ｔｈｅ  ａｐｐｌｉｃａｔｉｏｎ  ｏｐｔｉｍａｌ  ｒｏｕｔｅ（ｓ），ｒｅａｌ―ｔｉｍｅ  ａｎｄ  ｆｏｒｅｃａｓｔｅｄ  ｔｒａｆｆｉｃ  ｉｎｆｏｒｍａｔｉｏｎ，ａｎｄ  ｃｏｍｐｌｉｍｅｎｔａｒｙ  ｄａｔａ．）。このような側面で、前記ＤｙｎＮａｖサーバーは、前記サーバーの一種に該当する。本発明においては、前記ＤｙｎＮａｖサーバーを「交通情報サーバー」又は単純に「サーバー」と称する。
【００６４】
（位置ＵＲＩ（Ｌｏｃａｔｉｏｎ  ＵＲＩ））
本明細書において、位置ＵＲＩは、位置を獲得するプロトコルを用いてデバイスの現在の位置が特定の位置サーバーから獲得されるようにするＵＲＩに該当する（Ａ  ＵＲＩ  ｔｈａｔ  ｅｎａｂｌｅｓ  ｔｈｅ  ｃｕｒｒｅｎｔ  ｌｏｃａｔｉｏｎ  ｏｆ  ａ  ｄｅｖｉｃｅ  ｔｏ  ｂｅ  ｏｂｔａｉｎｅｄ  ｆｒｏｍ  ａ  ｐａｒｔｉｃｕｌａｒ  ｌｏｃａｔｉｏｎ  ｓｅｒｖｅｒ  ｕｓｉｎｇ  ａ  ｐａｒｔｉｃｕｌａｒ  ｄｅｒｅｆｅｒｅｎｃｉｎｇ  ｐｒｏｔｏｃｏｌ．）。
【００６５】
（ナビゲーションデバイス（Ｎａｖｉｇａｔｉｏｎ  Ｄｅｖｉｃｅ（ＮＤ）））
本明細書において、ナビゲーションデバイスは、ＧＮＳＳ（Ｇｌｏｂａｌ  Ｎａｖｉｇａｔｉｏｎ  Ｓａｔｅｌｌｉｔｅ  Ｓｙｓｔｅｍ）サービスを用いて最終目的地に到逹するために正しい経路を示す運転手を補助するエンティティに該当する。このエンティティは、ユーザーの選好度によってリアルタイム及び予測された交通情報を処理し、最適な経路を動的に推定することができる（Ａｎ  ｅｎｔｉｔｙ  ｔｈａｔ，ｕｓｉｎｇ  ＧＮＳＳ  ｓｅｒｖｉｃｅ，ａｓｓｉｓｔｓ  ｔｈｅ  ｄｒｉｖｅｒ  ｓｈｏｗｉｎｇ  ｃｏｒｒｅｃｔ  ｒｏｕｔｅ  ｔｏ  ｒｅａｃｈ  ｔｈｅ  ｆｉｎａｌ  ｄｅｓｔｉｎａｔｉｏｎ．Ｔｈｉｓ  ｅｎｔｉｔｙ  ｍａｙ  ｐｒｏｃｅｓｓ  ｒｅａｌ―ｔｉｍｅ  ａｎｄ  ｐｒｅｄｉｃｔｅｄ  ｔｒａｆｆｉｃ  ｉｎｆｏｒｍａｔｉｏｎ  ａｎｄ  ｄｙｎａｍｉｃａｌｌｙ  ｅｓｔｉｍａｔｅｓ  ｔｈｅ  ｏｐｔｉｍａｌ  ｒｏｕｔｅ，ａｃｃｏｒｄｉｎｇ  ｔｏ  ｕｓｅｒ  ｐｒｅｆｅｒｅｎｃｅｓ．）。
【００６６】
（軽量ＮＤ（Ｌｉｇｈｔｗｅｉｇｈｔ  ＮＤ））
本明細書において、軽量ＮＤは、経路計算のための機能がなく、サーバーから計算された経路を要請及び受信するナビゲーションデバイスを意味し、ローカルマップデータベースが利用可能でないと、各経路予測機能のために、そして、道路形状（ｓｈａｐｅ）表現を検索するためにサーバーにアクセスするナビゲーションデバイスに該当する（Ａ  ｎａｖｉｇａｔｉｏｎ  ｄｅｖｉｃｅ  ｔｈａｔ  ａｃｃｅｓｓｅｓ  ｔｏ  ａ  ｓｅｒｖｅｒ  ｆｏｒ  ｒｏｕｔｅ  ｅｓｔｍａｔｉｏｎ  ｆｕｎｃｔｉｏｎａｌｉｔｉｅｓ  ａｎｄ  ｆｏｒ  ｒｅｔｒｅｉｖｉｎｇ  ｒｏａｄｓ  ｓｈａｐｅ  ｒｅｐｒｅｓｅｎｔａｔｉｏｎ，ｉｆ  ｎｏｔ  ａｖａｉｌａｂｌｅ  ｉｎ  ａ  ｌｏｃａｌ  ｍａｐ  ｄａｔａｂａｓｅ．）。
【００６７】
（スマートＮＤ（Ｓｍａｒｔ  ＮＤ））
本明細書において、スマートＮＤは、デバイス自体で利用可能な道路ネットワークデータベースを用いて経路を計算できるナビゲーションデバイスに該当する（Ａ  ｎａｖｉｇａｔｉｏｎ  ｄｅｖｉｃｅ  ｔｈａｔ  ｉｓ  ａｂｌｅ  ｔｏ  ｃａｌｃｕｌａｔｅ  ｔｈｅ  ｒｏｕｔｅ（ｓ），ｕｓｉｎｇ  ａ  ｒｏａｄｓ  ｎｅｔｗｏｒｋ  ｄａｔａｂａｓｅ  ａｖａｉｌａｂｌｅ  ｏｎ  ｔｈｅ  ｄｅｖｉｃｅ  ｉｔｓｅｌｆ．）。
【００６８】
（関心ポイント（Ｐｏｉｎｔ  Ｏｆ  Ｉｎｔｅｒｅｓｔ；ＰＯＩ））
本明細書において、関心ポイントは、名前、カテゴリー、固有識別子又は市内住所などの各位置に関する情報を説明する（ＰＯＩ  ｄｅｓｃｒｉｂｅｓ  ｉｎｆｏｒｍａｔｉｏｎ  ａｂｏｕｔ  ｌｏｃａｔｉｏｎｓ  ｓｕｃｈ  ａｓ  ｎａｍｅ，ｃａｔｅｇｏｒｙ，ｕｎｉｑｕｅ  ｉｄｅｎｔｉｆｉｅｒ，ｏｒ  ｃｉｖｉｃ  ａｄｄｒｅｓｓ．）。
【００６９】
（セグメント（Ｓｅｇｍｅｎｔ））
道路を区分する単位であって、一般道路では各交差路間の連続した道路をセグメントといい、高速道路では、各高速道路の政策によって道路を分けてセグメントと定義する。このようなセグメント単位で交通の停滞や通過時間などを決定することができる。本明細書においては、セグメントを道路区間と相互互換可能に使用する。
【００７０】
（セグメントシーケンス（Ｓｅｇｍｅｎｔ  Ｓｅｑｕｅｎｃｅ））
一つ以上の連続したセグメントの集合を称する。必要に応じて、一つのセグメントで構成されたセグメントシーケンスも可能である。また、例えば、二つ以上のセグメントで構成されたセグメントシーケンスは、１番目のセグメントの終了ポイントが２番目のセグメントの開始ポイントと同一である。
【００７１】
（ポリライン（Ｐｏｌｙｌｉｎｅ））
本明細書において、ポリラインは、各セグメントの各端点を特定することによって定義された、一つ以上の線セグメントで構成されたグラフィックコンピューティングに使用される連続線に該当する（Ａ  ｃｏｎｔｉｎｕｏｕｓ  ｌｉｎｅ  ｕｓｅｄ  ｉｎ  ｇｒａｐｈｉｃ  ｃｏｍｐｕｔｉｎｇ  ｃｏｍｐｏｓｅｄ  ｏｆ  ｏｎｅ  ｏｒ  ｍｏｒｅ  ｌｉｎｅ  ｓｅｇｍｅｎｔｓ，ｄｅｆｉｎｅｄ  ｂｙ  ｓｐｅｃｉｆｙｉｎｇ  ｔｈｅ  ｅｎｄｐｏｉｎｔｓ  ｏｆ  ｅａｃｈ  ｓｅｇｍｅｎｔ．）。
【００７２】
（経路情報（Ｒｏｕｔｅ  Ｉｎｆｏｒｍａｔｉｏｎ））
本明細書において、経路情報は、定義された出発地から目的地までのセグメントの集合及び補助データの各座標の情報に該当する（Ｉｎｆｏｒｍａｔｉｏｎ  ｗｈｉｃｈ  ｃｏｏｒｄｉｎａｔｅｓ  ｏｆ  ｓｅｇｍｅｎｔ  ｅｎｄ  ｐｏｉｎｔｓ  ａｎｄ  ｃｏｍｐｌｉｍｅｎｔａｒｙ  ｄａｔａ  ｆｒｏｍ  ｔｈｅ  ｄｅｆｉｎｅｄ  ｏｒｉｇｉｎ  ａｎｄ  ｔｈｅ  ｄｅｓｔｉｎａｔｉｏｎ）。
【００７３】
（交通情報（Ｔｒａｆｆｉｃ  Ｉｎｆｏｒｍａｔｉｏｎ））
本明細書において、交通情報は、領域又は経路と関連した各交通イベント及び各ネットワークパフォーマンスパラメーターで構成された情報に該当する（Ｉｎｆｏｒｍａｔｉｏｎ  ｗｈｉｃｈ  ｃｏｎｓｉｓｔｓ  ｏｆ  ｔｒａｆｆｉｃ  ｅｖｅｎｔｓ  ａｎｄ  ｎｅｔｗｏｒｋ  ｐｅｒｆｏｒｍａｎｃｅ  ｐａｒａｍｅｔｅｒｓ  ｒｅｌａｔｅｄ  ｔｏ  ａｎ  ａｒｅａ  ｏｒ  ａ  ｒｏｕｔｅ．）。また、前記交通情報は、現在又はこれから発生する、すなわち、未来の交通情報を含むことができる。
【００７４】
（交通イベント（Ｔｒａｆｆｉｃ  Ｅｖｅｎｔ））
本明細書において、交通イベントは、道路ネットワーク運営者によって賦課又は計画された領域又は経路と関連した各イベント（すなわち、道路閉鎖を誘発する各道路工事）又は前記ネットワーク運営者の制御外的に発生する各イベント（すなわち、各事故）に関する情報に該当する（Ｉｎｆｏｒｍａｔｉｏｎ  ｒｅｇａｒｄｉｎｇ  ｅｖｅｎｔｓ  ｒｅｌａｔｅｄ  ｔｏ  ａｎ  ａｒｅａ  ｏｒ  ａ  ｒｏｕｔｅ  ｔｈａｔ  ａｒｅ  ｅｉｔｈｅｒ  ｉｍｐｏｓｅｄ  ｏｒ  ｐｌａｎｎｅｄ  ｂｙ  ｔｈｅ  ｒｏａｄ  ｎｅｔｗｏｒｋ  ｏｐｅｒａｏｒ（ｉ．ｅ．ｒｏａｄ  ｗｏｒｋｓ  ｌｅａｄｉｎｇ  ｔｏ  ｌａｎｅ  ｃｌｏｓｕｒｅｓ）  ｏｒ  ｅｖｅｎｔｓ  ｔｈａｔ  ｏｃｃｕｒ  ｏｕｔｓｉｄｅ  ｔｈｅ  ｃｏｎｔｒｏｌ  ｏｆ  ｔｈｅ  ｎｅｔｗｏｒｋ  ｏｐｅａｔｏｒ（ｉ．ｅ．ａｃｃｉｄｅｎｔｓ）．）。
【００７５】
（ネットワークパフォーマンスパラメーター（Ｎｅｔｗｏｒｋ  Ｐｅｒｆｏｒｍａｎｃｅ  Ｐａｒａｍｅｔｅｒ））
本明細書において、ネットワークパフォーマンスパラメーターは、領域又は経路に存在する各セグメントのパフォーマンス又は交通の流れ（すなわち、速度、遅延及び所要時間）に関する情報に該当する（Ｉｎｆｏｒｍａｔｉｏｎ  ｒｅｇａｒｄｉｎｇ  ｔｈｅ  ｐｅｒｆｏｒｍａｎｃｅｓ（ｉ．ｅ．ｓｐｅｅｄ，ｄｅｌａｙ  ａｎｄ  ｔｒａｖｅｌ  ｔｉｍｅ）  ｏｆ  ｒｏａｄ  ｓｅｇｍｅｎｔｓ  ｒｅｌａｔｅｄ  ｔｏ  ａｎ  ａｒｅａ  ｏｒ  ａ  ｒｏｕｔｅ．）。
【００７６】
（全体の経路情報（Ｒｏｕｔｅ  Ｉｎｆｏｒｍａｔｉｏｎ  ｉｎ  Ｆｕｌｌ  Ｆｏｒｍａｔ））
出発地から目的地までの全てのセグメントを含む経路情報の一形態を意味する。別途の言及がない場合、経路情報は全体の経路を意味する。
【００７７】
（要約経路情報（Ｒｏｕｔｅ  Ｉｎｆｏｒｍａｔｉｏｎ  ｉｎ  Ｓｕｍｍａｒｉｚｅｄ  Ｆｏｒｍａｔ））
出発地から目的地までの全てのセグメントのうち情報の要約のために選択されたセグメント（選択する方式は本発明で取り扱わない）のみを含む経路情報の一形態を意味する。
【００７８】
最近、スマートフォンの活発な普及と共に、既存のＤＭＢ放送網を用いていた形式から逸脱し、移動通信端末機に移動経路を提供するナビゲーションサービスが普遍化されており、ＯＭＡ  ＬＯＣ  ＷＧでは、前記のようなサービスをＤｙｎＮａｖ（Ｄｙｎａｍｉｃ  Ｎａｖｉｇａｔｉｏｎ）と称する。
【００７９】
本明細書において、ナビゲーション装置とは、経路案内機能を行える装置を称し、前記ナビゲーション装置は、スマートフォン、モバイルフォン、モバイルデバイス、ラップトップ、タブレットＰＣ、スマートパッドなどのように、携帯可能であるか、携帯可能な物体に付着可能な全ての電子的装置を含む。
【００８０】
図３は、本発明のナビゲーションシステムであるＩＰ基盤のＤｙｎＮａｖシステム全般を説明するためのネットワーク構成図である。図３に示したように、本発明のナビゲーションシステムは、移動通信網接続が可能なナビゲーション装置（Ｎａｖｉｇａｔｉｏｎ  Ｄｅｖｉｃｅ、ＮＤ）、無線送受信のための移動通信網、交通情報を提供するための交通情報収集装置、交通情報及び経路情報提供サーバー（ＤｙｎＮａｖ  Ｓｅｒｖｅｒ）、及びナビゲーション装置の位置獲得のための補助データ（Ａｓｓｉｓｔａｎｃｅ  Ｄａｔａ）を生成して伝達する位置サーバーを含むことができる。
【００８１】
簡略に表現するために、本明細書において、交通情報提供サーバー又はＤｙｎＮａｖサーバーは、「サーバー」と表現し、ナビゲーション装置は、「端末」、「ＮＤ」又は各端末の能力による「Ｓｍａｒｔ  ＮＤ」や「Ｌｉｇｈｔｗｅｉｇｈｔ  ＮＤ」と表現する。
【００８２】
本発明において、端末（上述したように、２つの端末の形態に区分可能である）は、図面に示したように、移動通信網又はＷｉ―ＦｉなどのＩＰ網との連結が可能であり、経路案内のためのナビゲーションアプリケーションを備えており、該当のアプリケーションは、サーバーに接続して経路案内データとリアルタイム交通情報を受信し、経路を案内することができる。一方、図面には別途に示していないが、経路計算が自体的に可能な端末は、サーバーから経路案内データを受信せず、リアルタイム交通情報のみを選択的に受信することができる。
【００８３】
ここで、リアルタイム交通情報とは、ＤｙｎＮａｖサーバーで計算され、端末に伝達される最適な経路情報、リアルタイム及び予測交通情報、ＰＯＩ（Ｐｏｉｎｔ  ｏｆ  Ｉｎｔｅｒｅｓｔ）及び天気などの交通と関連した付加情報を意味する。また、表現の重複を除去するために、ナビゲーションアプリケーション、端末又はユーザーを統合して端末と表現する。したがって、本明細書において、「端末」、「ＮＤ」、「Ｓｍａｒｔ  ＮＤ」、「Ｌｉｇｈｔｗｅｉｇｈｔ  ＮＤ」と「ナビゲーションアプリケーション」、「ユーザー」、及びこれらと同等の概念に用語などは、いずれも「端末」と称することができる。
【００８４】
上述したリアルタイム交通情報は、ＩＳＯ標準化団体で推進されているＴＰＥＧ（Ｔｒａｎｓｐｏｒｔ  Ｐｒｏｔｏｃｏｌ  Ｅｘｐｅｒｔｓ  Ｇｒｏｕｐ）を通じて表現することができる。ここで、ＴＰＥＧとは、デジタル放送網を介して交通及び旅行情報を伝送する標準プロトコルを意味する。図４に表現したように、ＴＰＥＧの階層構造は、ＩＳＯ／ＯＳＩレイヤーモデルのネットワーク階層（第３の階層）からアプリケーション階層（第７の階層）に対応する。ネットワーク階層は、ＴＰＥＧフレーム同期及びルーティングを定義し、第４、第５及び第６の階層のパケット化階層では、各アプリケーションの各コンポーネントが一つのストリームに併合され、それぞれのメッセージ規格は、応用階層である第７の階層に該当する。ＤｙｎＮａｖでは、前記ＴＰＥＧのリアルタイム交通情報表現方式に従ってリアルタイム交通情報を端末に提供することができ、別途の表現方式を使用することができる。
【００８５】
一般に、ユーザーがサーバーに経路を要請するとき、開始地、目的地、経由地、開始時間などの情報を提供することができる。前記サーバーは、ユーザーが要請した開始地、目的地、経由地、開始時間などの情報、及びリアルタイム又は予測道路交通情報に基づいてユーザーに提供する最適化された経路を構成して伝達することができる。この場合、ユーザーは、開始地及び目的地を必ず前記サーバーに提供しなければならない。
【００８６】
本発明で提案する方法は、ユーザーが前記サーバーに経路を要請するとき、一つ以上の多くの経由地を含み、これら経由地を通過する最適な経路を要請する方式である。このとき、前記サーバーは、リアルタイム又は予測した道路交通情報を考慮して、それぞれの経由地を通過する順序と該当の経由地を通過する最適経路を生成する。このとき、ユーザーが特定目的地を選択していないと、前記サーバーは、多くの経由地のうち一つを目的地として考慮して経路を選択する。このような経路要請／提供の例として、複数の地点を訪問しなければならない宅配配送やセールスマンを考慮することができる。また、このような例において、多くの経由地を通過しなければならないが、必ず最終目的地を指定して経路を要請する必要はない。このような例の場合、既存の方式（経路の要請時に必ず開始地と目的地を指定）では経路を提供しにくい。
【００８７】
一方、道路の交通状況によって多くの経由地を通過する最短経路が必ず最適化された経路でない場合もある。そのため、道路交通状況によって多くの経由地を通過する最適な経路を提供する方式が必要である。この場合、多くの経由地を通過する順序は道路交通状況によって変わり得る。また、道路の交通状況は、時間の経過と共に変わるので、これに合わせて効率的に経路を提供する方式も考慮しなければならない。
【００８８】
本発明は、ユーザーが一つ以上の経由地を通過する経路を要請し、サーバーが最適な経路を提供する方式を提案する。また、交通状況の変化によって経路及び交通情報をアップデートしなければならない状況で、アップデートを減少させるための方法も考慮する。
【００８９】
（第１の例．一つ以上の経由地を含む経路要請及び提供）
ユーザーに二つ以上の経由地を通過する最適経路を提供する方法は、ユーザーが前記サーバーに経路を要請する段階と、前記サーバーがユーザーに経路を提供する段階とを有する。本発明では、前記サーバーがユーザーの要請によって最適経路を計算する方法は取り扱わない。最適経路を計算する方法は、既存の多様なアルゴリズムを通じて具現することができる。
【００９０】
（１―１．経路要請）
従来のＤｙｎＮａｖでユーザーがサーバーに経路を要請するときは、経路を構成するのに必要な基本的な情報を含んで要請する（表１参照）。このとき、開始地（ｏｒｉｇｉｎＷＧＳ８４又はｏｒｉｇｉｎＡｄｄｒｅｓｓ）と目的地（ｄｅｓｔｉｎａｔｉｏｎＷＧＳ８４又はｄｅｓｔｉｎａｔｉｏｎＡｄｄｒｅｓｓ）は必ず含まれなければならない。
【００９１】
ユーザーが前記サーバーに多くの経由地を通過する最適な経路を要請するための条件は、下記の通りである。
【００９２】
―  経路の要請時、二つ又はそれ以上の経由地を含む。
【００９３】
―  経路の要請時、目的地情報を含むか、又は目的地情報を含まない（目的地情報が含まれない場合、要請した多数の経由地のうち一ヶ所が目的地として考慮され、経路が生成される）。
【００９４】
―  経路の要請時、複数の経由地を通過する最適な経路を要請する指示子（ｒｏｕｔｅＦｏｒＭｕｌｔｉｐｌｅＷａｙｐｏｉｎｔｓ）を含む。
【００９５】
前記複数の経由地を通過する最適経路を要請する指示子は、下記に詳細に示した。「ｒｏｕｔｅＦｏｒＭｕｌｔｉｐｌｅＷａｙｐｏｉｎｔｓ」パラメーターは、ユーザーが前記サーバーに経路を要請するときに使用するＴｒｉｐパラメーターの下位パラメーターとして定義される。
【００９６】
【表６】
2016512604.tif 000014
ユーザーから経路の要請を受けた前記サーバーは、「ｒｏｕｔｅＦｏｒＭｕｌｔｉｐｌｅＷａｙｐｏｉｎｔｓ」パラメーターを確認し、ユーザーが複数の経由地を通過する経路を要請することを確認することができる。前記サーバーは、開始地、目的地（目的地が含まれている場合）、経由地及び道路の交通状況を考慮して最適な経路を計算する。このとき、経由地に到逹する順序は最適経路によって変わり得、目的地が含まれていない場合、最適経路を考慮して多数の経由地のうち一つが最終目的地として考慮される。
【００９７】
ユーザーが複数の経由地を表現する方式は、Ｔｒｉｐパラメーターの下位パラメーターである「ｗａｙｐｏｉｎｔｓ」を用いて表現できるが（表１参照）、具現によっては、複数の「ｄｅｓｔｉｎａｔｉｏｎ」（ｄｅｓｔｉｎａｔｉｏｎＷＧＳ８４又はｄｅｓｔｉｎａｔｉｏｎＡｄｄｒｅｓｓ）を通じて示すこともできる。
【００９８】
また、ユーザーは、経路の要請時、時間条件及び経由地の優先順位条件を追加して経路を要請することができる。第一に、時間条件は、ユーザーが経路を要請するとき、総経路走行時間を指定する方式である。経路走行時間に関するパラメーターは、下記の通りである。
【００９９】
【表７】
2016512604.tif 000015
ユーザーが経路走行時間を指定した場合、サーバーは、前記指定された走行時間の間、全ての経由地を通過できる経路を提供しなければならない。このとき、ユーザーが経路開始時間（ｓｔａｒｔｉｎｇ  Ｔｉｍｅ）を指定しない場合、現在の時間を経路開始時間として考慮することができる。
【０１００】
前記経路走行時間は、新規な代替経路を計算して提供すべきであるか否かを判断する基準になり得る。提供した経路の交通状況が悪くなって経路走行時間が増加したが、前記の経路走行時間を超えない場合、該当の経路に継続して進行し、悪くなった交通状況によって増加した走行時間が経路走行時間を超える場合、前記サーバーは、経路走行時間を超えない新規経路を計算してユーザーに提供することができる。
【０１０１】
また、ユーザーは、経路の要請時、時間条件と共に経由地優先順位条件を設定することができる。経由地優先順位条件に関するパラメーターは、下記の通りである。
【０１０２】
【表８】
2016512604.tif 000016
ユーザーが前記サーバーに複数の経由地を通過する経路を要請するとき、前記の時間条件及び優先順位条件を含む場合、前記サーバーは、指定した条件に合う最適経路を算出し、経路を提供する。ユーザーが要請した複数の経由地を指定した時間条件内に全て通過できる場合、前記サーバーは、最適経路の生成時、経由地優先順位条件を考慮しない。しかし、ユーザーが要請した複数の経由地を指定した時間条件内に全て通過できない場合、前記サーバーは、経由地優先順位条件に基づいて優先順位の高い経由地を優先的に考慮して最適経路を生成し、時間条件に合わせるために優先順位の低い経由地を最適経路で含まずに最適経路を生成することができる。
【０１０３】
（１―２．経路提供）
サーバーがユーザーに経路を提供する方式は二つに分けることができる。第一の方式は、既存のように一度に全体の経路を提供する方式であり、第二の方式は、経路を分けて提供する方式である。
【０１０４】
第一の方式は既存と同一である。ユーザーが前記サーバーに経路を要請すると、前記サーバーは、計算された最適な出発地から目的地までの全体の経路を一度に提供する。また、経路進行中に、経路上の交通情報の変更又は代替経路の発生時、既存のように通知し、ユーザーに情報を伝達する。
【０１０５】
経路が長くなるか、走行時間が長くなると、交通情報の変更及び代替経路が発生する確率が高く、これらが頻繁に発生し得る。特に、前記の例示で提示した宅配配送やセールスマンの場合、業務の特性上、移動距離や走行時間が長いので、このような変更情報の発生が頻繁であり得る。そのため、第一の方式は、前記サーバーがユーザーに変更された情報を頻繁に再び提供する可能性が高く、その分だけネットワーク資源を多く使用するようになる。このような問題を解決するために新たに提案する第二の方式は、全体の経路を部分経路に分けて提供する方式である。
【０１０６】
全体の経路が長いか、走行時間が長い場合、前記サーバーは、一定基準で経路を分けてユーザーに伝達する。ここで、考慮できる基準は、下記の通りである。
【０１０７】
―  走行距離を考慮した経由地基準
（例えば、１０ｋｍの間に移動できる経由地単位）
―  走行時間を考慮した経由地基準
（例えば、１時間の間に移動できる経由地単位）
図５は、本発明の一実施例に係る複数の経由地を含む経路を例示する。図５（ａ）において、ユーザーは、Ａを開始地とし、ＢからＨまでの経由地を通過する経路を要請し、サーバーは、下記のような最適経路を計算した。前記サーバーが走行距離を考慮した経由地を基準にして経路を段階的に伝達し、その基準走行距離が１０ｋｍである場合、下記の経路に対して、前記サーバーは、下記のような段階でユーザーに経路を伝達する。各段階に該当する経路は、分割（された）経路と称する。
【０１０８】
―  １段階の経路：Ａ〜Ｃ（１２ｋｍ）
―  ２段階の経路：Ｃ〜Ｅ（１２ｋｍ）
―  ３段階の経路：Ｅ〜Ｈ（１５ｋｍ）
同一の開始地と経由地を通過するとしても、前記サーバーが他の経路を計算した場合、提供する方式は異なり得ることを図５（ｂ）に示した。
【０１０９】
―  １段階の経路：Ａ〜Ｇ（１８ｋｍ）
―  ２段階の経路：Ｇ〜Ｆ（１０ｋｍ）
―  ３段階の経路：Ｆ〜Ｃ（１３ｋｍ）
前記の図５（ａ）及び図５（ｂ）に示すように、同一の開始地と経由地であるとしても、他の最適経路がユーザーに提供され得る。また、前記の例において、基準走行距離が１０ｋｍであるが、各経由地を通過する経路が１０ｋｍに正確に分けられないので、１０ｋｍ前後の近似値を有する距離に分けられる。
【０１１０】
図５（ｃ）では、走行時間を基準とする複数の経由地を含む経路を示す。ユーザーは、Ａを開始地とし、ＢからＦまでの経由地を通過する経路を要請し、サーバーは、図５（ｃ）のような最適経路を計算した。サーバーが走行時間を考慮した経由地を基準にして経路を段階的に伝達し、その基準走行時間が１時間である場合、下記の経路に対して、前記サーバーは、下記のような段階でユーザーに経路を伝達する。
【０１１１】
―  １段階の経路：Ａ〜Ｃ（１時間２０分）
―  ２段階の経路：Ｃ〜Ｅ（１時間１７分）
―  ３段階の経路：Ｅ〜Ｆ（１時間２２分）
前記の例題において、基準走行時間が１時間であるが、各経由地を通過する経路の走行時間が１時間に正確に分けられないので、１時間前後の近似値を有する距離に分けられる。
【０１１２】
前記のように、サーバーは、計算した最適経路を基準に従って分割し、ユーザーに分割された経路を提供することができる。このとき、提供する方式としては、二つの方式を考慮することができる。第一の方式は、前記サーバーがユーザーに分割された経路を一度に提供する方式で、第二の方式は、前記サーバーがユーザーに一つの経路の終了後に次の段階の経路を提供する方式である。
【０１１３】
第一の方式は、サーバーがユーザーに分割経路を一度に提供する方式で、前記サーバーがユーザーの要請に応じて最適な経路を計算し、前記最適経路を分割した後、ユーザーに分割経路を受けるられる各住所を提供することができる。例えば、最適経路が５個の分割経路からなっている場合、サーバーは、前記５個の分割経路を受けられる５個の住所を最初からユーザーに提供することができる。５個の住所を受けたユーザーは、同時に各住所に接続して各分割経路を一度に受信したり、又は一つの分割経路が完了する前に、その次の分割経路を受けられる住所に接続して経路を受けることができる。
【０１１４】
第二の方式は、前記サーバーがユーザーに一つの分割経路の終了後に次の段階の分割経路を提供する方式で、前記サーバーがユーザーの要請に応じて最適な経路を計算し、前記最適経路を分割した後、ユーザーに一つの分割経路が終了する前にその次の分割経路を提供することができる。最適経路が５個の分割経路に分けられた場合、まず、前記サーバーは、ユーザーに１番目の分割経路を提供することができる。前記１番目の分割経路を提供するとき、前記サーバーは、前記ユーザーに前記分割経路と共に追加分割経路がさらにあることを知らせる指示子を共に伝達することができる。ユーザーは、前記指示子を通じて追加分割経路がさらに存在することを確認することができる。ユーザーは、１番目の分割経路の進行中に２番目の分割経路を要請して受信することができる。前記２番目の分割経路の提供時にも、前記サーバーは、ユーザーに追加分割経路がさらにあることを知らせる指示子を共に伝達することができる。このような方式で、ユーザーは、その後の分割経路を受けることができる。ユーザーが前記最適経路の最後の分割経路を受けるとき、前記サーバーは、これ以上提供を受ける経路がないことを知らせる指示子を含み、ユーザーに最適経路の最後であることを知らせることができる。
【０１１５】
前記の提案した経路を提供する方法のために必要な追加パラメーターは、下記の通りである。
【０１１６】
第一のパラメーターは、最適経路を多数に分けて提供するとき、サーバーがユーザーに経路をいくつに分けて提供するのか（計算された最適経路を分割して提供するとき、分割経路を「Ｓｕｂｒｏｕｔｅ」と表現）を示すパラメーターである。
【０１１７】
【表９】
2016512604.tif 000017
これによって、サーバーが最初の旅行（Ｔｒｉｐ）情報をユーザー（端末）に提供するとき、最初の分割経路に対する情報を提供しなければならない。これは、次のパラメーターで提供することができる。
【０１１８】
【表１０】
2016512604.tif 000018
第二のパラメーターは、現在ユーザーが進行する経路の他に、以後の追加経路があることを知らせる指示子と該当の経路を受けられるリンク（Ｌｉｎｋ）を提供するパラメーターである。前記第二のパラメーターは、旅行（Ｔｒｉｐ）が定義された後、前記定義された旅行に対する経路（Ｒｏｕｔｅ）情報を前記ユーザーに提供するときに提供され得る。
【０１１９】
【表１１】
2016512604.tif 000019
前記の説明において、最適経路を複数の分割経路に分けるとき、分けられたそれぞれの経路（Ｓｕｂｒｏｕｔｅ）の開始地と目的地が経由地であることを仮定して説明した。しかし、分けられた経路の開始地と目的地が必ず経由地である必要はない。開発する方法によって分けられた経路の開始地と目的地は、経由地でないサーバーが指定する任意の位置になり得る。
【０１２０】
（第２の例．交通及び経路情報アップデート回数の減少方案）
本発明の更に他の実施例によって交通及び経路情報アップデートを減少させ得る方案を説明することにする。ユーザーが走行中に経由地がある場合、経由地に到着して他の業務を行った後、再び出発する場合がある。例えば、宅配配送やセールスマンの場合、ユーザーは、経由地に到着して業務を行った後、再び出発するようになる。しかし、既存のナビゲーションサービスは、経由地に到着して消費する時間に対する考慮がないので、実際に経由地で消費する時間の間は前記経路に対する移動がなく、その結果、最適経路の計算時に使用された道路交通情報が実際に移動時の道路交通情報と異なり得る。すなわち、前記経由地で消費する時間の間、ユーザーの経路と関連した交通情報の変更が発生し得るので、最適経路計算が実際には最適化されないこともある。以下、このような問題を図６を通じて再び説明する。
【０１２１】
図６は、本発明の一実施例に係る各経由地での消費時間を反映した最適経路を示す。図６において、Ａを開始地点として、経由地Ｂ、Ｃ、Ｄ、Ｅ、Ｆを通過する経路を示し、各経由地間の走行時間と各経由地で泊まる時間を示した。既存のナビゲーションサービスでは、総走行時間は２３９分で、経由地に留まる時間を考慮すると、総走行時間は３０９分として７０分の差が発生する。サーバーが経路を計算するとき、走行経路が長いと、道路交通情報をアップデートする周期によって経路計算に適用する道路交通情報が変わり得る。前記サーバーが経路を計算するとき、経路の長さによる走行時間によってリアルタイム道路交通情報と予測道路交通情報を適用することができる。例えば、前記サーバーが１時間単位で予測道路交通情報を生成し、要請された経路の走行時間が２時間以上である場合、最初の１時間の間に移動する経路にはリアルタイム交通情報を適用し、その後の１時間の間に移動する経路には予測交通情報を適用することによって経路を計算することができる。そのため、前記の例題のように、経由地で留まった時間を考慮しないと、正確な総走行時間を計算できないので、それに合う適切なリアルタイム及び予測道路交通情報を適用しにくい。特に、走行距離、時間及び経由地が多い場合、このような誤差は大きくなり、その結果、道路交通情報の変更通知の回数が増加するようになる。
【０１２２】
そのため、本発明の一実施例は、ユーザーが前記サーバーに多くの経由地を通過する最適経路を要請するとき、各経由地での留まる時間を提供することにする。提案するパラメーターは、下記の通りである。
【０１２３】
【表１２】
2016512604.tif 000020
これを通じて、前記サーバーは、最適経路の計算時、既存より正確な走行時間の予測が可能であり、また、リアルタイム道路交通情報と予測道路交通情報をより効率的に適用して経路を計算することができ、結局、これを通じて、道路交通情報変更（アップデート）を知らせる回数の減少が可能である。
【０１２４】
（第３の例．経由地順序伝達基盤の経路伝達方案）
本発明の更に他の一実施例によって、ユーザーに複数の経由地を通過する最適経路を提供する他の方式を提案する。
【０１２５】
ユーザーは、サーバーに多くの経由地を通過する最適経路を要請しながら、ユーザーが通過する多くの経由地情報を前記サーバーに伝達することができる。このとき、各経由地の情報は、経由地を通過する順序を考慮しない状態で伝達することができる。前記サーバーは、現在及び予測道路交通情報に基づいて複数の経由地を最適経路として考慮し、ユーザーには複数の経由地を通過する順序を伝達する。
【０１２６】
詳細な手順は、図７を参照して説明することにする。
【０１２７】
（１）ユーザーは、前記サーバーに複数の経由地情報を伝達しながら、複数の経由地を通過する最適経路を要請することができる。このとき、前記経由地情報は、経由地を通過する順序を考慮しない状態で伝達される。
【０１２８】
（２）要請された前記サーバーは、現在及び予測道路交通情報を考慮して、複数の経由地を通過する最適経路を計算し、複数の経由地を如何なる順序で通過するのかを決定することができる。
【０１２９】
（３）前記サーバーは、前記（２）で計算した結果に基づいてユーザーに各経由地を通過する順序情報を伝達する。
【０１３０】
前記のように各経由地を通過する順序情報を受信したユーザーは、前記順序情報によって前記サーバーにそれぞれの経由地まで到逹するための経路情報又は道路交通情報を要請する。（スマートＮＤの経由交通情報要請、軽量ＮＤの経由経路情報要請）。例えば、図７（３）の表のように経由地順序を受けた場合、ユーザーは、最初は開始点（Ｏｒｉｇｉｎ）からＡ地点に行く経路（又は交通情報）を要請することができる。その次に、Ａ地点からＤ地点に行く経路を要請することができる。このような方式で、ユーザーは、Ｅ地点までの経路を要請して受信することができる。このように経路を要請して受ける方式は、既存のＤｙｎＮａｖサービスで行う方式と同一である。
【０１３１】
本実施例を簡略に要約すると、ユーザーが多くの経由地を通過する経路を要請する場合、前記サーバーは、それぞれの経由地を通過する順序を指定して知らせる。これに基づいて、ユーザーは、一つの経由地から次の経由地に行く経路を前記サーバーに要請して受ける。
【０１３２】
以下では、本発明の実施例を図２を参照して再び説明することにする。
【０１３３】
図２の動作は、ＤｙｎＮａｖアプリケーション（以下、端末）がＤｙｎＮａｖサーバー（以下、サーバー）に経路情報を伝達することを要請するシナリオに関する。このシナリオの主な機能は、（１）要約経路及び／又は全体経路の伝達、（２）通知サービスの加入、（３）前記端末による現在の位置の報告、（４）（ａ）提案された経路上の深刻な停滞、（ｂ）使用する経路からの迂回、（ｃ）目的地が第３者で、前記第３者の位置が変更される場合の経路再計算である。
【０１３４】
前記端末のユーザーは、出発地と目的地、そして、他の選好事項に基づいて旅行を定義し、これらパラメーターは、直ぐ前記端末によって前記サーバーに伝送される。前記目的地は、前記第３者のＩＤを使用して定義され、この場合、前記サーバーは、外部位置アプリケーション（サーバー）を通じて前記第３者の位置を獲得することができ、前記第３者の位置を目的地として使用することができる。前記サーバーは、リアルタイム及び予測道路交通情報を考慮して各旅行パラメーターとマッチングする一セットの各経路で応答し得る。帯域幅の最適化のために、各経路は、二つの他のフォーマット、すなわち、要約及び全体で前記サーバーで利用可能である。前記端末は、要約経路にアクセスし、この情報を用いて、前記端末のユーザーは、ナビゲーションのために使用される提案されたセットのうち一つの経路を選択することができる。前記第３者に伝達される経路を前記提案された各経路から選択することができる。前記端末は、選択された経路に対する全体の経路を要請することができ、使用されない各経路を削除することもできる。制限された長さ、旅行の複雑度及びネットワーク性能により、提案された各経路は、開始時から直ぐ全体の経路をエンコーディングすることができ、；この場合、前記サーバーは、要約経路をエンコーディングする必要がない。このデータが道路データベースで前記端末に対して利用可能でないと、前記端末は、各経路のセグメント形状（ＷＧＳ８４座標多角形）に対する情報をサーバーから要請することができる。
【０１３５】
前記端末は、使用する経路に対する交通情報をアップデート（パフォーマンスパラメーター及び交通イベント）するために、そして、経路に沿って停滞がある場合、代案経路提案を受信するために、第３者のＩＤが目的地として使用される。また、前記端末は、前記第３者の位置が変更される場合、更新された情報（更新された目的地、追加セグメント又は代案経路）を受信するための各通知サービスに加入することができる。前記端末は、（前記端末が搭載された）車両が特定距離を運転した後、前記サーバー上に自分の現在の位置をアップデートし得る。この情報を用いて、前記サーバーは、使用する経路から既に旅行された各セグメントを削除し（前記端末によって以前に削除されていない場合）、現在の位置とこれ以上互換され得ない各経路を削除し得る。
【０１３６】
その後、ユーザーは、使用経路から迂回することができる。このような条件下で、前記端末は、自分のアップデートされた現在の位置をアップロードすることができ、前記サーバーは、前記端末の現在の位置が使用経路と互換されないことを認識し、アップデートされた位置情報に基づいて新たな経路推定を進行することができる。新たな経路識別子が現在の位置アップデート手順で前記端末に伝送され得る（前記新たな経路に対する通知手順は必要でない）。安全上の理由で、ユーザーとの相互作用を最小化するために、前記通知サービスは、新たな提案経路に自動的に拡張され得る。
【０１３７】
提供された経路上の交通停滞により、前記サーバーは、前記端末に使用経路に対するアップデート交通情報及び代案経路の提案を知らせ、前記端末は、知られた各リソースにアクセスすることができる。前記サーバーは、削除されていないと、新たな提案経路のための通知サービスを自動的に提供し得る。
【０１３８】
第３者のＩＤが目的地として使用される場合、目的地は、前記第３者が移動し得るので変更可能である。この場合、前記サーバーは、前記端末にアップデートされた情報を通知することができる。前記アップデートされた情報の各類型は、（１）アップデートされた目的地、（２）追加セグメント、（３）代案経路である。相互作用の回数を減少させるために、前記サーバーは、アップデートされた情報の類型によって、前記端末が目的地付近にある場合のみに前記アップデートされた情報を通知することができる。
【０１３９】
前記端末が複数の経由地を訪問するために経路を要請する場合、前記サーバーは、経路情報を効率的に管理してアップデートするために、予測された経路（計算された経路）をいくつかのサブ経路に分けることができる。この場合、前記サーバーは、前記各サブ経路を順次提供できるので、前記端末は、順次使用する各サブ経路を獲得（ｒｅｔｒｉｅｖｅ）することができる。
【０１４０】
本発明の一実施例に係る複数の経由地を含む経路が要請され、それに対する最適経路が提供されるシナリオの場合、図２の過程のうち１と３の過程で追加又は変更事項がある。
【０１４１】
１．ユーザー（端末）は、自分が望む旅行に関する各パラメーター、すなわち、出発地、目的地及び経由地などで構成された旅行（ｔｒｉｐ）を生成することができる。また、前記経由地を含む旅行に対する経路を要請するために、前記経由地を含む経路を要請することを指示する指示子（ｒｏｕｔｅＦｏｒＭｕｌｔｉｐｌｅＷａｙｐｏｉｎｔｓ）が追加されなければならなく、この場合、少なくとも二つ以上の経由地（ｗａｙｐｏｉｎｔｓ）に対する情報が追加されなければならない。
【０１４２】
また、ユーザーは、要請する経路に対する制約条件をさらに付加することができる。例えば、ユーザー自身が前記経路を移動するのに許容される最大時間（ｒｅｑｕｅｓｔｅｄＴｒａｖｅｌｌｉｎｇＴｉｍｅ）を追加することができる。例えば、ユーザーが出発地（普通、現在のユーザーの位置）からＡ〜Ｅの全ての経由地に立ち寄るのに最大４時間（２４０分）が許容される場合、ユーザーは、経路の要請時に前記４時間を条件として付加することができる。
【０１４３】
そして、現在／予測道路交通情報に基づいて全ての経由地に立ち寄るのに前記最大時間を超える予測経路のみが存在する場合、優先順位によって全ての経由地のうち少なくとも一つが前記予測経路から除去され得る。前記優先順位は、各経由地に対する優先順位を称し、これは、端末によって入力され、低い優先順位を有する経由地から除去され得る。
【０１４４】
また、ユーザーは、各経由地に留まる時間を前記経路の要請時に設定することができ、これは、必ず前記サーバーによって経路の計算時に考慮されなければならない。
【０１４５】
そこで、前記サーバーは、ユーザーによって複数の経由地を含む経路の要請を受けた場合、提案経路を複数の部分経路（ｓｕｂｒｏｕｔｅ）に分けることができる。このように複数の部分経路を提供しようと決定した場合、前記サーバーは、前記ユーザーで提案経路が何個の部分経路からなっているのかを知らせることができる。また、前記提案経路の１番目の部分経路に対する参照経路リソースをユーザーに提供することができる。
【０１４６】
３．ユーザーは、提案された複数の要約経路のうち一つを選択し、これに対する全体の経路を要請又はアクセスすることができる。ユーザーが複数の経由地を含む経路をサーバーに要請し、前記サーバーが前記経路を複数の分割経路として提供する場合、前記ユーザー又は端末は、前記全体の経路の代わりに、前記分割経路情報にアクセスすることができる。
【０１４７】
前記分割経路を受信するにおいて、前記ユーザーは、前記サーバーから１番目の分割経路に対する情報と、後続する分割経路があるか否かを指示する指示子、そして、後続する分割経路がある場合、その後（すなわち、２番目の）分割経路に対する参照（リンク）に対する情報を含む経路情報を受信することができる。
【０１４８】
前記分割経路が前記サーバーによって提供される場合、３番の過程は、前記ユーザーが進行中の分割経路の目的地に到着する前に後続する分割経路にアクセスするために繰り返すことができる。また、前記３番の過程は、これ以上追加分割経路がないと指示されるまで繰り返すことができる。
【０１４９】
図８は、本発明の一実施例に係る動作を示す。
【０１５０】
端末８１０は、ユーザー、ユーザー端末、及びユーザー端末内のアプリケーションのうち一つとして称することができ、サーバー８２０は、サーバー、サーバー装置及びサーバー装置内のアプリケーションのうち一つとして称することができ、特定名称に本発明の範囲が制限されることはない。
【０１５１】
前記端末は、前記サーバーに複数の経由地を含む経路を要請することができる（Ｓ８１）。前記要請は、出発地及び複数の経由地を含まなければならなく、目的地は必ず指定される必要はない。目的地が指定されていない場合、前記複数の経由地のうち一つを目的地として指定することができる。また、前記複数の経由地を含む経路を要請する場合、前記要請に前記複数の経由地を含む経路を要請することを知らせる指示子が含まれなければならなく、この場合、二つ以上の経由地が前記要請に含まれなければならない。
【０１５２】
また、前記端末は、前記要請を伝送するとき、追加的な制約条件を付加することができる。例えば、前記経路を運行するのに要される最大時間を設定することができる。これと関連して、各経由地に対して優先順位を設定することができる。前記サーバーが計算した経路を運行するのに必要な予測所要時間が前記設定された最大時間を超える場合、前記計算した経路から前記優先順位によって少なくとも一つの経由地を削除することができる。
【０１５３】
また、それぞれの経由地で留まる時間を設定することができる。一般に、複数の経由地を含む経路を要請した場合、各経由地で特定時間の間に留まる可能性が高く、また、前記特定時間によって現在／予測道路交通情報のアップデートが必要であり得るので、前記それぞれの経由地で留まる時間を設定することが、より正確な経路予測のために必要であり得る。
【０１５４】
そのため、前記サーバーは、Ｓ８１での要請によって提案経路を計算し、前記提案経路に対する情報を含む応答を前記端末に伝送することができる（Ｓ８２）。
【０１５５】
前記の表７、表８及び表１２で説明したパラメーターのうち少なくとも一つを、前記端末（又はユーザー）が複数の経由地を含む旅行の経路を要請するときに入力することができ、サーバーは、前記入力されたパラメーターに基づいて提案経路を計算することができる。
【０１５６】
前記応答は、前記提案経路がいくつの分割経路に分割されたのかを示す情報、及び１番目の分割経路に対する参照リンクを含むことができる。前記端末は、前記参照リンクに接続し、前記１番目の分割経路を要請することができる（Ｓ８３）。
【０１５７】
前記端末は、前記サーバーから前記１番目の分割経路を含む情報を獲得することができる（Ｓ８４）。前記情報は、前記１番目の分割経路及び２番目の分割経路に対する参照リンク（２番目の分割経路がある場合）を含むことができる。
【０１５８】
後続する分割経路がある場合、前記端末は、参照リンクを通じて前記サーバーから特定分割経路及びその後の分割経路に対する参照リンクを獲得することができる。これは、これ以上後続する分割経路がないときまで繰り返すことができる。
【０１５９】
このように、複数の分割経路は、一定時間間隔で順次送受信することができる。これによって、各分割経路を計算するのに使用された現在／予測道路交通情報は、互いに異なる時間の道路交通情報であり、すなわち、前記現在／予測道路交通情報は、互いに異なる時間にアップデートされた情報であり得る。
【０１６０】
図９は、本発明の各実施例を具現するように構成された端末とサーバーのブロック図である。前記端末９１０は、前記サーバー９２０と通信するように構成された送受信機９１１；及び前記サーバーから受信される情報に基づいて前記経路に対する更新情報を獲得するように構成されたプロセッサ９１２を含むことができる。前記サーバー９２０は、前記端末と通信するように構成された送受信機９２１；及び前記端末から受信された情報に基づいて前記経路に対する更新情報を生成するように構成されたプロセッサ９２２を含むことができる。
【０１６１】
図９と関連して説明する本発明の一実施例は、前記端末９１０が軽量ＮＤである場合の実施例で、前記端末は、サーバーによって計算された複数の経由地を含む旅行（ｔｒｉｐ）の経路を受信するように構成される。この実施例において、経路の出発地は前記端末の位置で、前記目的地は、別途に指定されたり、複数の経由地のうち一つに決定される。この実施例において、前記プロセッサ９１２は、前記複数の経由地を含む旅行に対する経路の要請をサーバーに伝送するように構成することができる。前記要請は、前記複数の経由地を含む経路を要請することを示す情報及び前記複数の経由地情報を含むことができる。また、前記プロセッサ９１２は、前記複数の経由地を含む旅行の提案経路に対する情報を前記サーバーから受信するように構成することができる。
【０１６２】
前記旅行の提案経路が複数のサブ経路で構成され、前記提案経路に対する情報が、前記旅行の提案経路が何個のサブ経路で構成されたのかを指示する情報、及び前記サブ経路のうち１番目のサブ経路に対するリンクを含むと、前記プロセッサ９１２は、前記１番目のサブ経路に対するリンクを通じて前記１番目のサブ経路に対する情報を受信するように構成することができる。また、前記１番目のサブ経路に対する情報は、前記１番目のサブ経路に後続する２番目のサブ経路が存在するか否かを指示する指示子、及び前記２番目のサブ経路に対するリンクを含むことができる。
【０１６３】
前記プロセッサ９１２は、Ｎ（Ｎは２以上の整数）番目のサブ経路に対するリンクを通じて前記Ｎ番目のサブ経路に対する情報を受信するように構成することができる。
【０１６４】
また、前記Ｎ番目のサブ経路に対する情報は、Ｎ＋１番目のサブ経路が存在するか否かを指示する指示子、及び前記Ｎ＋１番目のサブ経路に対するリンクを含むことができ、前記Ｎ＋１番目のサブ経路に対するリンクは、前記Ｎ＋１番目のサブ経路が存在する場合に前記Ｎ番目のサブ経路に対する情報に含ませることができる。
【０１６５】
前記プロセッサ９１２は、前記要請に前記経路の最大許容運行時間、前記複数の経由地のそれぞれに対する優先順位、及び前記複数の経由地のそれぞれで留まる時間のうち少なくとも一つで構成された経路条件を含ませるように構成することができる。好ましくは、前記最大許容運行時間と前記複数の経由地のそれぞれに対する優先順位は同時に含ませることができる。前記サーバーによって計算された特定提案経路の運行所要時間が前記最大許容運行時間を超える場合、前記特定提案経路から前記優先順位によって前記複数の経由地のうち少なくとも一つを除外することができる。
【０１６６】
前記提案経路は、運行所要時間基準又は運行距離基準で複数のサブ経路に分割することができる。前記複数のサブ経路のそれぞれは、互いに異なる時点の道路交通情報に基づいて計算することができる。併せて、前記プロセッサ９１２は、前記複数のサブ経路のそれぞれを時間差を置いて受信するように構成することができる。
【０１６７】
前記サーバーのプロセッサ９２２と関連する内容は、上述した各実施例のうち少なくとも一つを参照することにする。
【０１６８】
本発明の実施例に係る方案は、端末がサーバーに複数の経由地を訪問するための経路情報を要請し、この場合、前記経路の運行距離又は運行時間が著しく大きくなり得る。長い経路が提供されてそのまま使用される場合、前記経路情報を管理してアップデートすることが非効率的であり、より多くのリソースを使用することもできる。この場合、前記サーバーは、前記長い経路をいくつかの短い経路（すなわち、サブ又は分割経路）に分けて短い経路を順次提供し、前記経路情報の管理及びアップデートを効率的に行うことができる。それぞれのサブ経路は、前記端末に順次提供されるので、変わる交通条件によって、前記サーバーは、未だに前記端末に提供されていない経路情報を内部的にアップデートすることができる。したがって、ネットワーク資源の消費が減少し得る。
【０１６９】
前記サーバーが要請された旅行と関連する経路を計算又は予測した後、前記経路の運行距離又は運行時間が特定しきい値を超えると、前記サーバーは、前記予測された経路をいくつかのサブ経路に分けることができる。前記サーバーがサブ経路を生成するとき、元の（全体）経路は、運行距離（例えば、２０ｋｍごとに）又は運行時間（例えば、２時間ごとに）に基づいて分けることができる。
【０１７０】
前記サブ経路が生成された後、前記サーバーは、旅行と関連する情報を通じて前記端末に１番目のサブ経路情報を提供することができる。その後、前記端末は、前記１番目のサブ経路情報にアクセスすることができる。前記１番目のサブ経路情報に、２番目のサブ経路のリンクが含まれる。前記１番目のサブ経路の目的地に到着する前に、前記端末は、３番目のサブ経路のリンクを含む前記２番目のサブ経路情報にアクセスすることができる。前記端末は、後続するサブ経路にアクセスするために、この手順を追加的なサブ経路がこれ以上存在しいことが指示されるとき（すなわち、Ｒｏｕｔｅリソース内の"ａｄｄｉｔｉｏｎａｌＳｕｂｒｏｕｔｅ"パラメーターがｆａｌｓｅ値を有するとき）まで繰り返すことができる。
【０１７１】
本発明は、ユーザーが目的地を指定せずに多くの経由地を通過する経路を要請及び提供する方法を提案し、また、経路提供方法及び経由地で留まった時間提供を通じて代替経路及び交通情報変更に対する通知回数を減少させ得る方法を提案した。
【０１７２】
本発明で提案した方法を通じて、多様なナビゲーションサービスの提供が可能になる。また、代替経路及び交通情報変更の通知回数を減少させる方法を通じて、端末のネットワーク資源の使用を減少させることができる。
【０１７３】
一方、前記端末又は前記サーバーは、上述した各実施例のうち一つ又は二つ以上の実施例の組み合わせを行うことができ、各実施例のうち一部を組み合わせたり結合して行うことができる。
【０１７４】
上述したように開示された本発明の好ましい各実施例に対する詳細な説明は、当業者が本発明を具現して実施できるように提供された。以上では、本発明の好ましい各実施例を参照して説明したが、該当の技術分野で熟練した当業者であれば、下記の特許請求の範囲に記載した本発明を多様に修正及び変更させ得ることを理解できるだろう。したがって、本発明は、ここで示した各実施形態に制限されるものではなく、ここで開示した各原理及び新規の各特徴と一致する最広の範囲を付与するものである。
【産業上の利用可能性】
【０１７５】
本発明の各実施例は、ナビゲーション装置又はサーバーに適用可能である。
【図１】
2016512604.tif 000021
【図２】
2016512604.tif 000022
【図３】
2016512604.tif 000023
【図４】
2016512604.tif 000024
【図５（ａ）】
2016512604.tif 000025
【図５（ｂ）】
2016512604.tif 000026
【図５（ｃ）】
2016512604.tif 000027
【図６】
2016512604.tif 000028
【図７】
2016512604.tif 000029
【図８】
2016512604.tif 000030
【図９】
2016512604.tif 000031
【国際調査報告】
2016512604.tif 000032
2016512604.tif 000033
2016512604.tif 000034
2016512604.tif 000035