Search

JP-2026076619-A - データ構造及び結節点探索方法

JP2026076619AJP 2026076619 AJP2026076619 AJP 2026076619AJP-2026076619-A

Abstract

【課題】自動車の乗降が可能な複数の乗降地点の候補の中から、最適な乗降地点を探索することができるデータ構造等を提供する。 【解決手段】歩道ネットワークデータ１１と、車道ネットワークデータ１２と、結節点データ群１３と、を含むデータは、歩道網ＮＷ１上の第１地点（目的地）Ｐ１に近い複数の結節点Ｎ１、Ｎ２を探索して第１地点Ｐ１と個々の結節点Ｎ１、Ｎ２とを結ぶ経路Ｒ１、Ｒ２の歩行に要する歩行コストＣ１、Ｃ２をそれぞれ算出するとともに、車道網ＮＷ２上の第２地点（出発地）Ｐ２と個々の結節点Ｎ１、Ｎ２とを結ぶ経路Ｒ３、Ｒ４の走行に要する自動車コストＣ３、Ｃ４をそれぞれ算出する探索処理と、探索された複数の結節点Ｎ１、Ｎ２の中から、歩行コストＣ１、Ｃ２及び自動車コストＣ３、Ｃ４の合計が最も小さい経路上の結節点を、最適な降車地点として選択する選択処理と、に用いられる。 【選択図】図２

Inventors

  • 益田 勝也

Assignees

  • 株式会社ゼンリン

Dates

Publication Date
20260512
Application Date
20241024

Claims (8)

  1. 制御部及び記憶部を備えるコンピュータに用いられ、前記記憶部に記憶されるデータのデータ構造であって、 利用者が歩行可能な歩道網のデータであり、前記歩道網を構成する個々の歩道の位置情報及び歩行に要するコスト情報を有する歩道ネットワークデータと、 自動車が走行可能な車道網のデータであり、前記車道網を構成する個々の車道の位置情報及び走行に要するコスト情報を有する車道ネットワークデータと、 歩道と車道とが接する地点であり、利用者による自動車の乗降が可能な複数の結節点のデータである結節点データ群と、を含み、 前記制御部が、前記歩道ネットワークデータ、前記車道ネットワークデータ及び前記結節点データ群を参照して、前記歩道網上の目的地に近い複数の結節点を探索して前記目的地と個々の結節点とを結ぶ経路の歩行に要する歩行コストをそれぞれ算出するとともに、前記車道網上の出発地と前記個々の結節点とを結ぶ経路の走行に要する自動車コストをそれぞれ算出する探索処理と、 前記制御部が、探索された複数の結節点の中から、前記歩行コスト及び前記自動車コストの合計が最も小さい経路上の結節点を、最適な降車地点として選択する選択処理と、 に用いられるデータのデータ構造。
  2. 制御部及び記憶部を備えるコンピュータに用いられ、前記記憶部に記憶されるデータのデータ構造であって、 利用者が歩行可能な歩道網のデータであり、前記歩道網を構成する個々の歩道の位置情報及び歩行に要するコスト情報を有する歩道ネットワークデータと、 自動車が走行可能な車道網のデータであり、前記車道網を構成する個々の車道の位置情報及び走行に要するコスト情報を有する車道ネットワークデータと、 歩道と車道とが接する地点であり、利用者による自動車の乗降が可能な複数の結節点のデータである結節点データ群と、を含み、 前記制御部が、前記歩道ネットワークデータ、前記車道ネットワークデータ及び前記結節点データ群を参照して、前記歩道網上の出発地に近い複数の結節点を探索して前記出発地と個々の結節点とを結ぶ経路の歩行に要する歩行コストをそれぞれ算出し、前記車道網上の目的地と前記個々の結節点とを結ぶ経路の走行に要する自動車コストをそれぞれ算出するとともに、前記車道網における前記個々の結節点と前記結節点へ配車可能な自動車の位置とを結ぶ複数の経路の配車コストをそれぞれ算出する探索処理と、 前記制御部が、探索された複数の結節点の中から、前記歩行コスト、前記自動車コスト及び前記配車コストの合計が最も小さい経路上の結節点を、最適な乗車地点として選択する選択処理と、 に用いられるデータのデータ構造。
  3. 前記探索処理として、前記車道網における前記個々の結節点と前記結節点へ配車可能な複数の自動車の位置とを結ぶ複数の経路の配車コストをそれぞれ算出する処理と、 前記選択処理として、探索された配車可能な複数の自動車の中から、前記歩行コスト、前記自動車コスト及び前記配車コストの合計が最も小さい自動車を、配車される自動車として選択する処理と、 に用いられる、 請求項２に記載のデータ構造。
  4. 前記選択処理として、前記結節点へ配車可能な自動車の位置から前記目的地までの経路における自動車の右折及び左折の回数が少なくなるように、最適な結節点と、配車される自動車とを選択する処理に用いられる、 請求項３に記載のデータ構造。
  5. 前記結節点データでは、所定の領域内にある複数の結節点に固有の共通識別情報が付与され、 前記探索処理として、前記結節点データを参照し、探索された結節点と前記共通識別情報が同じである全ての結節点を探索する処理に用いられる、 請求項２から４のいずれか一項に記載のデータ構造。
  6. 結節点探索システムによって実行される結節点探索方法であって、 利用者が歩行可能な歩道網のデータであり、前記歩道網を構成する個々の歩道の位置情報及び歩行に要するコスト情報を有する歩道ネットワークデータと、自動車が走行可能な車道網のデータであり、前記車道網を構成する個々の車道の位置情報及び走行に要するコスト情報を有する車道ネットワークデータと、歩道と車道とが接する地点であり、利用者による自動車の乗降が可能な複数の結節点のデータである結節点データ群と、を参照して、前記歩道網上の目的地に近い複数の結節点を探索して前記目的地と個々の結節点とを結ぶ経路の歩行に要する歩行コストをそれぞれ算出するとともに、前記車道網上の出発地と前記個々の結節点とを結ぶ経路の走行に要する自動車コストをそれぞれ算出する探索ステップと、 探索された複数の結節点の中から、前記歩行コスト及び前記自動車コストの合計が最も小さい経路上の結節点を、自動車の最適な降車地点として選択する選択ステップと、 を含む結節点探索方法。
  7. 結節点探索システムによって実行される結節点探索方法であって、 利用者が歩行可能な歩道網のデータであり、前記歩道網を構成する個々の歩道の位置情報及び歩行に要するコスト情報を有する歩道ネットワークデータと、自動車が走行可能な車道網のデータであり、前記車道網を構成する個々の車道の位置情報及び走行に要するコスト情報を有する車道ネットワークデータと、歩道と車道とが接する地点であり、利用者による自動車の乗降が可能な複数の結節点のデータである結節点データ群と、を参照して、前記歩道網上の出発地に近い複数の結節点を探索して前記出発地と個々の結節点とを結ぶ経路の歩行に要する歩行コストをそれぞれ算出し、前記車道網上の目的地と前記個々の結節点とを結ぶ経路の走行に要する自動車コストをそれぞれ算出するとともに、前記車道網における前記個々の結節点と前記結節点へ配車可能な自動車の位置とを結ぶ複数の経路の配車コストをそれぞれ算出する探索ステップと、 探索された複数の結節点の中から、前記歩行コスト、前記自動車コスト及び前記配車コストの合計が最も小さい経路上の結節点を、最適な乗車地点として選択する選択ステップと、 を含む結節点探索方法。
  8. 前記探索ステップでは、前記車道網における前記個々の結節点と前記結節点へ配車可能な複数の自動車の位置とを結ぶ複数の経路の配車コストをそれぞれ算出し、 前記選択ステップでは、探索された配車可能な複数の自動車の中から、前記歩行コスト、前記自動車コスト及び前記配車コストの合計が最も小さい自動車を、配車される自動車として選択する、 請求項７に記載の結節点探索方法。

Description

本発明は、データ構造及び結節点探索方法に関する。 公園、コンサート会場、球場などの大きな施設では、その場所と車道とが接する結節点というべき場所（出口）が複数存在する。このような施設では、例えばどの出口に利用者を迎えに行ったらよいか判断に迷うことがある。そこで、特許文献１には、自動車で施設の利用者を迎えに行く場合に待ち合わせ場所を設定する技術が開示されている。この技術によれば、待ち合わせ場所（ピックアップ候補地）のデータベースを参照して、複数の待ち合わせ場所の候補を利用者であるユーザに提示し、ユーザに待ち合わせ場所を選択させる。 特開２０１９－１２１３７８号公報 本発明の実施の形態に係る結節点探索システムの構成を示すブロック図である。図１の結節点探索システムにおけるデータ構造の第１の例を示す模式図である。（Ａ）は、出発地から自動車で移動し、自動車を降りて目的地に向かう経路を示す模式図である。（Ｂ）は、出発地から徒歩で移動し、自動車に乗って目的地に向かう経路を示す模式図である。歩道網と車道網の一例を示す図である。図１の結節点探索システムのハードウエア構成を示すブロック図である。結節点探索処理のフローチャートである。出発地から自動車で移動し、自動車を降りて目的地に向かう経路の一例を示す図である。出発地から徒歩で移動し、自動車に乗って目的地に向かう経路の一例を示す図である。（Ａ）は、データ構造の第２の例を示す図である。（Ｂ）は、結節点を探索する様子を示す模式図である。（Ａ）は、データ構造の第３の例を示す図である。（Ｂ）は、結節点を探索する様子を示す模式図である。（Ａ）は、結節点データの他の例を示す図である。（Ｂ）は、結節点を探索する様子を示す模式図である。Ｕターンをしないことを条件とする結節点及び配車される車を探索する様子を示す模式図である。 以下、本発明の実施の形態について図面を参照して詳細に説明する。各図面においては、同一又は同等の部分に同一の符号を付す。なお、下記の実施の形態において、“有する”、“含む”又は“含有する”といった表現は、“からなる”又は“から構成される”という意味も包含する。 本実施の形態に係る結節点探索システム１（図１参照）は、自動車送迎サービスを対象とし、自動車送迎時の移動経路が最適化され、自動車の最適な乗降地点（乗車地点又は降車地点）を探索するシステムである。なお、本実施の形態では、例えば図２等に示すように、主として、第１地点Ｐ１と第２地点Ｐ２との間の移動経路について説明する。 自動車送迎時の移動経路には、以下の（１）、（２）の移動経路が考えられる。 （１）出発地から自動車で移動し、自動車を降りて目的地に向かう経路 この移動経路では、利用者は、自動車で目的地の近くまで移動し、自動車を降りてから徒歩で目的地まで移動する。この場合、例えば図２及び図３（Ａ）に示すように、第２地点Ｐ２が出発地となり、第１地点Ｐ１が目的地となる。結節点探索システム１は、例えば第２地点Ｐ２から降車位置である結節点Ｎ１、Ｎ２までの自動車の経路Ｒ３、Ｒ４と、その後の結節点Ｎ１、Ｎ２から第１地点Ｐ１までの利用者の徒歩の経路Ｒ１、Ｒ２と、を探索し、結節点Ｎ１、Ｎ２のうち、自動車の最適な降車地点を選択する。 （２）出発地から徒歩で移動し、自動車に乗って目的地に向かう経路 この移動経路では、利用者は、徒歩で出発地から自動車の乗車位置まで歩道を移動し、自動車に乗ってから目的地まで車道を移動する。この場合、例えば図２及び図３（Ｂ）に示すように、第１地点Ｐ１が出発地となり、第２地点Ｐ２が目的地となり、第３地点Ｐ３が配車可能な車１、２の位置となる。結節点探索システム１は、例えば第１地点Ｐ１から乗車位置である結節点Ｎ１、Ｎ２までの徒歩の経路Ｒ１、Ｒ２と、その後の結節点Ｎ１、Ｎ２から第２地点Ｐ２までの自動車の経路Ｒ３、Ｒ４と、車１から結節点Ｎ１までの経路Ｒ５、車１から結節点Ｎ２までの経路Ｒ６、車２から結節点Ｎ１までの経路Ｒ７、車２から結節点Ｎ２までの経路Ｒ８と、を探索する。さらに、結節点探索システム１は、結節点Ｎ１、Ｎ２のうち、自動車の最適な乗車地点を選択するとともに、車１、２のうち、その乗車地点に配車される車を選択する。なお、配車可能な車が１台である場合には、第３地点Ｐ３は１つとなり、車の選択は行われない。 図１に示すように、本実施の形態１に係る結節点探索システム１は、サーバ装置２と、通信端末３と、配車システム４と、を備える。サーバ装置２は、通信ネットワークに接続可能なサーバコンピュータである。通信端末３は、通信ネットワークに接続可能な端末である。通信端末３は、スマートフォン等の携帯端末であってもよいし、カーナビゲーション装置等他の端末装置であってもよい。配車システム４は、タクシーなどの配車を行うコンピュータシステムである。サーバ装置２と、通信端末３と、配車システム４は、通信ネットワークを介して互いにデータ送受信が可能である。 通信端末３には、探索される移動経路が、上述の（１）であるか、（２）であるかの種別が設定される。さらに、通信端末３では、探索される移動経路の種別、出発地及び目的地が設定され、通信端末３の現在位置情報が検出される。通信端末３は、サーバ装置２に、移動経路の種別、出発地及び目的地の設定情報及び検出された現在位置情報を送信する。サーバ装置２は、受信した移動経路の種別、出発地及び目的地及び現在位置情報に基づいて、（１）または（２）の移動経路の探索を行い、自動車の最適な乗降地点を探索する。 配車システム４は、（２）の移動経路の場合、サーバ装置２に配車可能な自動車の現在位置情報を提供する。配車可能な自動車の位置（現在位置情報）が、図３（Ｂ）に示す第３地点Ｐ３となる。現在位置情報が提供される自動車の台数は、複数台とすることができる。例えば、図３（Ｂ）に示すように、車１の位置と、車２の位置とが、それぞれ第３地点Ｐ３となる。サーバ装置２は、受信した自動車の現在位置情報（第３地点Ｐ３）に基づいて、（２）の移動経路の探索を行い、自動車の最適な乗車地点を探索する。 ＜サーバ装置＞ 図１に示すように、サーバ装置２は、記憶部１０と、制御部２０と、を備えるコンピュータで構成される。記憶部１０は、サーバ装置２の（１）または（２）の移動経路の探索に用いられるデータを記憶する。制御部２０は、記憶部１０に記憶されるデータを参照して、移動経路の探索を行う。制御部２０は、通信端末３から受信した種別、出発地及び目的地及び現在位置情報と、配車システム４から提供される配車可能な自動車の現在位置情報に基づいて、（１）または（２）の移動経路の探索を行い、自動車の最適な乗降地点を探索する。図２に示す場合、車１、２の最適な乗降地点として結節点Ｎ１又は結節点Ｎ２のいずれかが探索される。 図１に示すように、記憶部１０は、歩道ネットワークデータ１１と、車道ネットワークデータ１２と、結節点データ群１３と、を備える。以下、制御部２０及び記憶部１０を備えるサーバ装置２に用いられ、記憶部１０に記憶されるデータのデータ構造について説明する。 ＜歩道ネットワークデータ＞ 歩道ネットワークデータ１１は、利用者が歩行可能な歩道網ＮＷ１（図４参照）のデータである。例えば図４において点線で示される歩道網ＮＷ１は、歩行者が歩行可能な個々の歩道が互いに結びつくことにより構成される。個々の歩道のデータは、歩道データ１１ａ（図２参照）としてまとめられている。 図２に示すように、歩道データ１１ａは、歩道ＩＤ（IDentification）と、位置座標と、第１接続歩道ＩＤと、第２接続歩道ＩＤと、コストのデータで構成される。歩道ＩＤは、対応する歩道に付与された固有の識別情報である。位置座標は、対応する歩道の位置座標である。第１接続歩道ＩＤは、対応する歩道につながる一方の歩道のＩＤである。第２接続歩道ＩＤは、対応する歩道につながる他方の歩道のＩＤである。コストは、その歩道を走行するのに必要なコスト情報である。コストは、基本的に、その歩道の進行方向の長さが長くなるにつれて大きくなるように設定されている。しかしながら、これには限られない。コストは、歩道の長さだけでなく、その歩道の通りにくさに応じて大きくなるように設定されてもよい。歩道の通りにくさとは、例えば、その歩道に階段が含まれているか、急な斜面であるか、非常に狭いかなどによって、決定することができる。コストは、この通りにくさに応じた通行に必要な平均時間によって決定するようにしてもよい。歩道のコストは、単純な距離でなく、その歩道の属性に基づいて定められる。 以上のように、歩道ネットワークデータ１１は、歩道網ＮＷ１を構成する個々の歩道の位置座標、接続される歩道ＩＤ及び歩行に要するコスト情報を有する。 ＜車道ネットワークデータ＞ 車道ネットワークデータ１２は、自動車が走行可能な車道網ＮＷ２（図４参照）のデータである。車道網ＮＷ２は、図４において太い実線で示されるように、個々の車道が互いに結びつくことにより構成される。個々の車道のデータは、車道データ１２ａ（図２参照）としてまとめられている。 図２に示すように、車道データ１２ａは、車道ＩＤ（IDentification）と、位置座標と、進入側車道ＩＤと、退出側車道ＩＤと、コストのデータで構成される。車道ＩＤは、対応する車道に付与された固有の識別情報である。位置座標は、対応する車道の位置座標である。進入側車道ＩＤは、対応する車道に進入するために自動車が走行する車道のＩＤである。退出側車道ＩＤは、対応する車道から退出した後に自動車が走行する車道のＩＤである。コストは、その車道を走行するのに必要なコスト情報である。コストは、その車道の進行方向の長さが長くなるにつれて大きくなるように設定されている。しかしながら、これには限られない。コストは、車道等の長さだけでなく、その車道を一般的な速度で通過するときに要する時間が長くなるにつれて大きくなるように設定されてもよい。車道のコストは、単純な距離でなく、その車道の属性に基づいて定められる。 以上のように、車道ネットワークデータ１２は、車道網ＮＷ２を構成する個々の車道の位置座標、接続される車道ＩＤ及び自動車の走行に要するコスト情報を有する。 ＜結節点データ群＞ 結節点データ群１３は、歩道網ＮＷ１を構成する歩道と車道網ＮＷ２を構成する車道とが接する地点のデータであり、利用者による自動車の乗降が可能な複数の結節点のデータである。車道と、その車道に接する歩道がある場合、その車道と、歩道とが、結節点となる。ここで、車道と歩道が「接する」とは、当該車道の自動車に対して当該歩道からの乗降が可能な関係にあることをいい、自動車の乗降が可能でなければ「接する」とは言わない。例えば、図４に示す地図では、地点ＳＧに近い結節点として結節点Ｎ１、Ｎ２がある。図２に示すように、各結節点には、識別情報として結節点ＩＤが付与される。この結節点ＩＤと、歩道ＩＤと、車道ＩＤとで、結節点データ１３ａが構成される。 ＜制御部＞ 図１に示すように、制御部２０は、探索部２１と、選択部２２と、を備える。図１及び図２に示すように、探索部２１は、記憶部１０に記憶された、歩道ネットワークデータ１１、車道ネットワークデータ１２及び結節点データ群１３を参照して、歩道網ＮＷ１における第１地点Ｐ１と車道網ＮＷ２における第２地点Ｐ２との間の結節点（例えば図４の結節点Ｎ１、Ｎ２）を介した移動経路の探索を行う。 図３（Ａ）に示すように、上述の（１）の移動経路を探索する場合、探索部２１は、第１地点Ｐ１として、利用者が自動車を降りた後に向かう目的地を設定し、第２地点Ｐ２として、利用者が乗車する自動車の位置である出発地を設定する。また、図３（Ｂ）に示すように、上述の（２）の移動経路を探索する場合、探索部２１は、第１地点Ｐ１として、利