図面 (/)

技術 経路探索方法および経路探索プログラムおよび経路探索システム

出願人 株式会社日立情報システムズ
発明者 奥田学
出願日 2005年9月21日 (15年3ヶ月経過) 出願番号 2005-273132
公開日 2007年4月5日 (13年8ヶ月経過) 公開番号 2007-083800
状態 特許登録済
技術分野 教示用装置 鉄道交通の監視、制御、保安
主要キーワード ループ区間 保持数 通過経路情報 現リンク 停車駅間 複数条件 経路補正 通過済み
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2007年4月5日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (13)

課題

公共交通網において最優秀経路情報の他に複数の最優秀経路情報に次ぐ優秀代替経路を探索できる経路探索方法および経路探索プログラムを提供する。

解決手段

出発駅および到着駅および出発駅から到着駅までの所要時間と距離を格納したリンクテーブルと、リンクテーブルの出発駅を到着駅とするリンクテーブルのレコードの位置を格納するブリッジテーブルを用いて、ダイクストラ法によって最優秀経路情報を生成すると共に、その生成過程で探索した経路をもとに、代替経路を生成すると共に、GA法によって代替経路を補正し、最優秀経路情報に次いで優秀な代替可能な複数の経路を探索する。

概要

背景

一般に従来技術による公共交通網経路探索方法は、ダイクストラ法が用いられてきた。この方法は通過点に複数の選択できる経路が存在するとき、最優秀経路情報を選択し、その経路を進んで複数の選択できる経路が存在する点に至った場合には再度最優秀な経路を選択し、以下これを繰り返すことにより、全体として最優秀経路情報を探索する技術である。

ここで、公共交通網とは鉄道を始めとする出発時間と到着時間区間距離運賃が予め定められている交通手段を言う。
また、最優秀経路情報とは、例えば時間を探索条件とした探索の場合には最短時間の経路をいい、乗換え回数を探索条件とした場合には合計乗換え回数が最少の経路を言い、料金を探索条件とした場合には料金が最低な経路のように、探索条件が最適な経路を言う。

また、特許文献1にはダイクストラ法によって最優秀経路情報を探索した後、前記最優秀経路情報で使用した乗換駅使用禁止にして、再度ダイクストラ法で最優秀経路情報に次ぐ経路を順次探索する技術が記載されている。
さらに、特許文献2には遺伝的アルゴリズムを利用して最適経路とそれに準ずる複数の代替経路を求めるカーナビゲーションシステムに関する技術が記載されている。
特開平11−44547号公報
特開平9−178500号公報

概要

公共交通網において最優秀経路情報の他に複数の最優秀経路情報に次ぐ優秀な代替経路を探索できる経路探索方法および経路探索プログラムを提供する。出発駅および到着駅および出発駅から到着駅までの所要時間と距離を格納したリンクテーブルと、リンクテーブルの出発駅を到着駅とするリンクテーブルのレコードの位置を格納するブリッジテーブルを用いて、ダイクストラ法によって最優秀経路情報を生成すると共に、その生成過程で探索した経路をもとに、代替経路を生成すると共に、GA法によって代替経路を補正し、最優秀経路情報に次いで優秀な代替可能な複数の経路を探索する。

目的

本発明の目的は、前述の従来技術による不具合を除去することであり、公共交通網において最優秀経路情報の他に複数の最優秀経路情報に次ぐ優秀な代替経路を探索できる経路探索方法および経路探索プログラムおよび経路探索システムを提供することである。

効果

実績

技術文献被引用数
2件
牽制数
1件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

出発駅から到着駅に至る探索条件合致した経路情報を探索する経路探索システムであって、出発駅,到着駅,出発駅から到着駅に至る所要時間,出発駅から到着駅に至る距離,これらを含むレコード一意割り振られたリンクIDとを格納するリンクテーブルと、該リンクテーブルに格納したレコードを入力とし、該レコードを基にダイクストラ法を用いて出発駅から到達に至る最も探索条件に合致した最優秀経路情報及び該最優秀経路情報を算出する経緯で得た複数の通過経路情報を保持する経路探索部と、該経路探索部が保持した通過経路情報から複数の生成経路情報を算出する経路生成部と、該複数の生成経路情報を用いて遺伝的アルゴリズムによる通過経路情報の補正を行う経路補正部とを備えることを特徴とする経路探索システム。

請求項2

前記リンクテーブルの到着駅が出発駅となっている対応レコード接続リンクID,乗換え時間,接続の種別を示す接続情報,これらを含むレコードに一意に割り当てられたブリッジIDとを格納するブリッジテーブルを設けると共に、前記リンクテーブルの到着駅が出発駅となっている対応レコードに前記ブリッジIDを追加し、前記経路探索部が、リンクテーブルの到着駅が出発駅となっている対応レコードを検索する場合、前記リンクテーブルのレコードに格納されているブリッジIDを読み込み、当該ブリッジIDを持つレコードをブリッジテーブルから検索し、該検索されたレコードに格納された接続リンクIDを読み込み、該接続リンクIDを含むレコードをリンクテーブルから検索することを特徴とする請求項1記載の経路探索システム。

請求項3

出発駅から到着駅に至る探索条件に合致した経路情報を探索する経路探索システムの経路探索方法であって、出発駅,到着駅,出発駅から到着駅に至る所要時間,出発駅から到着駅に至る距離,これらを含むレコードに一意に割り振られたリンクIDとを格納するリンクテーブルと、該リンクテーブルに格納したレコードを入力とし、該レコードを基にダイクストラ法を用いて出発駅から到達駅に至る最も探索条件に合致した最優秀経路情報及び該最優秀経路情報を算出する経緯で得た複数の通過経路情報を保持する経路探索部と、該経路探索部が保持した通過経路情報から複数の生成経路情報を算出する経路生成部と、該複数の生成経路情報を用いて遺伝的アルゴリズムによる通過経路情報の補正を行う経路補正部とを設け、前記経路探索部が、リンクテーブルに格納した複数レコードを基にダイクストラ法を用いて出発駅から到達駅に至る複数の通過経路情報の探索を行って最優秀経路情報の探索及び複数の通過経路情報の保持を行い、前記経路生成部が、前記通過経路情報を基に複数の生成経路情報を算出し、前記経路補正部が、前記最優秀経路情報以外の経路から最優秀経路情報の代替経路優秀な順に求めることを特徴とする経路探索システムの経路探索方法。

請求項4

前記リンクテーブルの到着駅が出発駅となっている対応レコードの接続リンクID,乗換え時間,接続の種別を示す接続情報,これらを含むレコードに一意に割り当てられたブリッジIDとを格納するブリッジテーブルを設けると共に、前記リンクテーブルの到着駅が出発駅となっている対応レコードに前記ブリッジIDを追加し、前記経路探索部が、リンクテーブルの到着駅が出発駅となっている対応レコードを検索する場合、前記リンクテーブルのレコードに格納されているブリッジIDを読み込み、当該ブリッジIDを持つレコードをブリッジテーブルから検索し、該検索されたレコードに格納された接続リンクIDを読み込み、該接続リンクIDを含むレコードをリンクテーブルから検索することを特徴とする請求項3記載の経路探索方法。

請求項5

出発駅,到着駅,出発駅から到着駅に至る所要時間,出発駅から到着駅に至る距離,これらを含むレコードに一意に割り振られたリンクIDとを格納するリンクテーブルと、該リンクテーブルに格納したレコードを入力とし、該レコードを基にダイクストラ法を用いて出発駅から到達駅に至る最も探索条件に合致した最優秀経路情報及び該最優秀経路情報を算出する経緯で得た複数の通過経路情報を保持する経路探索部と、該経路探索部が保持した通過経路情報から複数の生成経路情報を算出する経路生成部と、該複数の生成経路情報を用いて遺伝的アルゴリズムによる通過経路情報の補正を行う経路補正部と、前記各構成を制御するコンピュータとを備え、出発駅から到着駅に至る探索条件に合致した経路情報を探索する経路探索システムの経路探索プログラムであって、前記コンピュータに、前記経路探索部が、リンクテーブルに格納した複数レコードを基にダイクストラ法を用いて出発駅から到達駅に至る複数の通過経路情報の探索を行って最優秀経路情報の探索及び複数の通過経路情報の保持を行う機能と、前記経路生成部が、前記通過経路情報を基に複数の生成経路情報を算出する機能と、前記経路補正部が、前記最優秀経路情報以外の経路から最優秀経路情報の代替経路を優秀な順に求める機能とを実現させることを特徴とする経路探索システムの経路探索プログラム。

請求項6

前記リンクテーブルの到着駅が出発駅となっている対応レコードの接続リンクID,乗換え時間,接続の種別を示す接続情報,これらを含むレコードに一意に割り当てられたブリッジIDとを格納するブリッジテーブルを設けると共に、前記リンクテーブルの到着駅が出発駅となっている対応レコードに前記ブリッジIDを追加した請求項5記載の経路探索システムの経路探索プログラムであって、前記コンピュータに、前記経路探索部が、リンクテーブルの到着駅が出発駅となっている対応レコードを検索する場合、前記リンクテーブルのレコードに格納されているブリッジIDを読み込む機能と、当該ブリッジIDを持つレコードをブリッジテーブルから検索する機能と、該検索されたレコードに格納された接続リンクIDを読み込む機能と、該接続リンクIDを含むレコードをリンクテーブルから検索する機能とを実現することを特徴とする請求項5記載の経路探索プロラム

技術分野

0001

本発明は、コンピュータを用いて公共交通網出発駅から目的駅までの最適な経路複数種類探索する方法およびプログラムおよびシステム係り、特にダイクストラ法によって最優秀経路情報を求めるとともに前記最優秀経路情報を求める過程で使用した通過経路情報を再利用し、遺伝的アルゴリズム(Genetic Algorithm、以下GAと略す。)を用いて最優秀経路情報の代替経路優秀な順に求める経路探索方法および経路探索プログラムおよび経路探索システムに関する。

背景技術

0002

一般に従来技術による公共交通網の経路探索方法は、ダイクストラ法が用いられてきた。この方法は通過点に複数の選択できる経路が存在するとき、最優秀経路情報を選択し、その経路を進んで複数の選択できる経路が存在する点に至った場合には再度最優秀な経路を選択し、以下これを繰り返すことにより、全体として最優秀経路情報を探索する技術である。

0003

ここで、公共交通網とは鉄道を始めとする出発時間と到着時間区間距離運賃が予め定められている交通手段を言う。
また、最優秀経路情報とは、例えば時間を探索条件とした探索の場合には最短時間の経路をいい、乗換え回数を探索条件とした場合には合計乗換え回数が最少の経路を言い、料金を探索条件とした場合には料金が最低な経路のように、探索条件が最適な経路を言う。

0004

また、特許文献1にはダイクストラ法によって最優秀経路情報を探索した後、前記最優秀経路情報で使用した乗換駅使用禁止にして、再度ダイクストラ法で最優秀経路情報に次ぐ経路を順次探索する技術が記載されている。
さらに、特許文献2には遺伝的アルゴリズムを利用して最適経路とそれに準ずる複数の代替経路を求めるカーナビゲーションシステムに関する技術が記載されている。
特開平11−44547号公報
特開平9−178500号公報

発明が解決しようとする課題

0005

前述の従来技術による公共交通網の経路探索方法には次のような不具合があった。
先ず、ダイクストラ法は高速に最優秀経路情報を求めることが可能であり、広く用いられている。しかし、この方法は最優秀経路情報以外の代替経路を求めることはできないという不具合があった。

0006

これに対し、特許文献1に開示されている技術は、有効な代替経路を探索できない場合がある。
例えば、ダイクストラ法によれば、崎から鹿児島中央までの経路を探索した場合、最優秀経路情報として(枕崎)−JR指宿枕崎線(枕崎−山川)−(山川)−JR指宿枕崎線(山川−鹿児島中央)−鹿児島中央という、枕崎から山川まで行き、山川で乗換え、鹿児島中央に行くという経路が探索される。
これに対して、特許文献1に開示されている技術に従い、山川での乗換えを経路探索において使用禁止にしてしまうと、有効な代替経路は探索できない。しかし実際には、(枕崎)−JR指宿枕崎線(枕崎−山川)−(山川)−JR指宿枕崎線(山川−鹿児島中央)−(鹿児島)−徒歩−(南鹿児島前)−鹿児島市電1系統−(元)−鹿児島市電2系統−(鹿児島中央駅前)−徒歩−(鹿児島中央)、というように、山川での乗換え後、南鹿児島で乗り換える経路も存在する。
このように、特許文献1記載の技術では、最優秀経路情報に乗換駅が1つしか存在しない場合、また、乗換駅が存在しない場合には、代替経路を探索できないという不具合が存在する。

0007

また、特許文献2に記載の技術は、カーナビゲーションシステムに広く用いられている。しかし、道路交通網においては運転者が自由に経路を選択することができるのに対し、鉄道網では列車運行時刻行き先、乗換駅などを条件として考慮しなければならない。また、カーナビゲーションシステムがGPSを使用して現在位置と目的地から距離や右左折の回数等を基に経路を選択するのに対し、鉄道網においては所要時間を基に経路を選択する場合がある。このため、特許文献2記載の技術を単純に鉄道網に適用することはできないという不具合が存在する。

0008

本発明の目的は、前述の従来技術による不具合を除去することであり、公共交通網において最優秀経路情報の他に複数の最優秀経路情報に次ぐ優秀な代替経路を探索できる経路探索方法および経路探索プログラムおよび経路探索システムを提供することである。

課題を解決するための手段

0009

前記目的を達成するために請求項1記載の発明は、出発駅から到着駅に至る探索条件に合致した経路情報を探索する経路探索システムであって、
出発駅,到着駅,出発駅から到着駅に至る所要時間,出発駅から到着駅に至る距離,これらを含むレコード一意割り振られたリンクIDとを格納するリンクテーブルと、
該リンクテーブルに格納したレコードを入力とし、該レコードを基にダイクストラ法を用いて出発駅から到達駅に至る最も探索条件に合致した最優秀経路情報及び該最優秀経路情報を算出する経緯で得た複数の通過経路情報を保持する経路探索部と、
該経路探索部が保持した通過経路情報から複数の生成経路情報を算出する経路生成部と、
該複数の生成経路情報を用いて遺伝的アルゴリズムによる通過経路情報の補正を行う経路補正部とを備えることを特徴とする。

0010

また、請求項2記載の発明は、前記経路探索システムにおいて、前記リンクテーブルの到着駅が出発駅となっている対応レコード接続リンクID,乗換え時間,接続の種別を示す接続情報,これらを含むレコードに一意に割り当てられたブリッジIDとを格納するブリッジテーブルを設けると共に、前記リンクテーブルの到着駅が出発駅となっている対応レコードに前記ブリッジIDを追加し、
前記経路探索部が、リンクテーブルの到着駅が出発駅となっている対応レコードを検索する場合、前記リンクテーブルのレコードに格納されているブリッジIDを読み込み、当該ブリッジIDを持つレコードをブリッジテーブルから検索し、該検索されたレコードに格納された接続リンクIDを読み込み、該接続リンクIDを含むレコードをリンクテーブルから検索することを特徴とする。

0011

また、請求項3記載の発明は、出発駅から到着駅に至る探索条件に合致した経路情報を探索する経路探索システムの経路探索方法であって、
出発駅,到着駅,出発駅から到着駅に至る所要時間,出発駅から到着駅に至る距離,これらを含むレコードに一意に割り振られたリンクIDとを格納するリンクテーブルと、該リンクテーブルに格納したレコードを入力とし、該レコードを基にダイクストラ法を用いて出発駅から到達駅に至る最も探索条件に合致した最優秀経路情報及び該最優秀経路情報を算出する経緯で得た複数の通過経路情報を保持する経路探索部と、該経路探索部が保持した通過経路情報から複数の生成経路情報を算出する経路生成部と、該複数の生成経路情報を用いて遺伝的アルゴリズムによる通過経路情報の補正を行う経路補正部とを設け、
前記経路探索部が、リンクテーブルに格納した複数レコードを基にダイクストラ法を用いて出発駅から到達駅に至る複数の通過経路情報の探索を行って最優秀経路情報の探索及び複数の通過経路情報の保持を行い、
前記経路生成部が、前記通過経路情報を基に複数の生成経路情報を算出し、
前記経路補正部が、前記最優秀経路情報以外の経路から最優秀経路情報の代替経路を優秀な順に求めることを特徴とする。

0012

また、請求項4記載の発明は、前記経路探索方法において前記リンクテーブルの到着駅が出発駅となっている対応レコードの接続リンクID,乗換え時間,接続の種別を示す接続情報,これらを含むレコードに一意に割り当てられたブリッジIDとを格納するブリッジテーブルを設けると共に、前記リンクテーブルの到着駅が出発駅となっている対応レコードに前記ブリッジIDを追加し、
前記経路探索部が、リンクテーブルの到着駅が出発駅となっている対応レコードを検索する場合、前記リンクテーブルのレコードに格納されているブリッジIDを読み込み、当該ブリッジIDを持つレコードをブリッジテーブルから検索し、該検索されたレコードに格納された接続リンクIDを読み込み、該接続リンクIDを含むレコードをリンクテーブルから検索することを特徴とする。

0013

また、請求項5記載の発明は、出発駅,到着駅,出発駅から到着駅に至る所要時間,出発駅から到着駅に至る距離,これらを含むレコードに一意に割り振られたリンクIDとを格納するリンクテーブルと、該リンクテーブルに格納したレコードを入力とし、該レコードを基にダイクストラ法を用いて出発駅から到達駅に至る最も探索条件に合致した最優秀経路情報及び該最優秀経路情報を算出する経緯で得た複数の通過経路情報を保持する経路探索部と、該経路探索部が保持した通過経路情報から複数の生成経路情報を算出する経路生成部と、該複数の生成経路情報を用いて遺伝的アルゴリズムによる通過経路情報の補正を行う経路補正部と、前記各構成を制御するコンピュータとを備え、出発駅から到着駅に至る探索条件に合致した経路情報を探索する経路探索システムの経路探索プログラムであって、
前記コンピュータに、
前記経路探索部が、リンクテーブルに格納した複数レコードを基にダイクストラ法を用いて出発駅から到達駅に至る複数の通過経路情報の探索を行って最優秀経路情報の探索及び複数の通過経路情報の保持を行う機能と、
前記経路生成部が、前記通過経路情報を基に複数の生成経路情報を算出する機能と、
前記経路補正部が、前記最優秀経路情報以外の経路から最優秀経路情報の代替経路を優秀な順に求める機能とを実現させることを特徴とする。

0014

また、請求項6記載の発明は、前記経路探索プログラムにおいて、前記リンクテーブルの到着駅が出発駅となっている対応レコードの接続リンクID,乗換え時間,接続の種別を示す接続情報,これらを含むレコードに一意に割り当てられたブリッジIDとを格納するブリッジテーブルを設けると共に、前記リンクテーブルの到着駅が出発駅となっている対応レコードに前記ブリッジIDを追加した請求項5記載の経路探索システムの経路探索プログラムであって、
前記コンピュータに、
前記経路探索部が、リンクテーブルの到着駅が出発駅となっている対応レコードを検索する場合、前記リンクテーブルのレコードに格納されているブリッジIDを読み込む機能と、当該ブリッジIDを持つレコードをブリッジテーブルから検索する機能と、該検索されたレコードに格納された接続リンクIDを読み込む機能と、該接続リンクIDを含むレコードをリンクテーブルから検索する機能とを実現することを特徴とする。

発明の効果

0015

本発明による経路探索方法および経路探索プログラムおよび経路探索システムによれば、出発駅および到着駅および出発駅から到着駅までの所要時間と距離を格納したリンクテーブルと、リンクテーブルの出発駅を到着駅とするリンクテーブルのレコードの位置を格納するブリッジテーブルを予め用意し、これらのテーブルを読み込んで、ダイクストラ法によって最優秀経路情報を生成すると共に、その生成過程で探索した通過経路情報をもとに、生成経路情報を生成すると共に、GA法によって生成経路情報を補正するように構成したため、従来はダイクストラ法では最優秀経路情報しか導出できなかったのに対し、本願発明においては最優秀経路情報に次いで優秀な代替可能な複数の経路を探索することができる。

発明を実施するための最良の形態

0016

以下、本発明による経路探索方法および経路探索プログラムおよび経路探索システムの一実施形態を、図面を参照して詳細に説明する。
図1は、本発明の実施形態における経路検索システムの全体構成図である。
図2は、本発明の実施形態における処理のフローチャートである。
図3は、リンクテーブルとブリッジテーブルの例である。
図4は、路線図停車駅単位のリンクおよび乗換駅単位のリンクの例である。
図5は、経路探索プログラムのフローチャートである。
図6は、路線図の例と通過経路情報の例である。
図7は、経路生成プログラムのフローチャートである。
図8は、経路生成プログラムによって生成された経路の例である。
図9は、遺伝的アルゴリズムによる経路補正プログラムのフローチャートである。
図10は、経路補正プログラムによる経路分割例である。
図11は、経路補正プログラムにより分割した経路の合成例である。
図12は、経路補正プログラムによって補正された結果の例である。

0017

<構成の説明>
本発明の一実施形態による経路探索方法および経路探索プログラムが実施される経路探索システムを、図1を用いて説明する。
本実施形態のシステムは、経路検索システム100と、ユーザーの保持するコンピュータ30と、経路探索システム100とユーザーの保持するコンピュータ30とを接続する公衆通信回線網20とを備える。

0018

前記経路検索システム100は、プログラムが稼動するサーバ10と、ダイクストラ法によって経路を探索する経路探索部11と、前記経路探索部11によって探索した経路から代替経路を生成する経路生成部12と、前記経路生成部12によって生成されて経路を遺伝的アルゴリズムによって補正する経路補正部13と、出発駅から到着駅までの所要時間および距離を格納するリンクテーブル14と、リンクテーブル14において到着駅を出発駅とするレコードのIDおよび乗換え時間および列車の接続に関する情報である接続情報を格納するブリッジテーブル15と、経路探索部11によって使用された通過経路を格納する通過経路情報テーブル16と、通過経路情報テーブル16から生成された生成経路情報を格納する生成経路情報テーブル17を備える。

0019

経路探索部11は、ダイクストラ法によって最優秀経路情報を求めると共に、その過程で使用した経路を全て通過経路情報テーブル16に格納する。
経路生成部12は、前記通過経路情報テーブル16に格納された通過経路情報から最優秀経路情報に代替可能な生成経路情報を導出し、生成経路情報テーブル17に格納する。
経路補正部13は、前記生成経路情報テーブル17に格納された生成経路情報を補正し、最優秀経路情報についで優秀な複数の代替経路を導出する。

0020

<データの説明>
図3(A)を用いてリンクテーブル14のデータ構成例を説明する。
リンクテーブル14は、レコードに一意に定められたリンクID301と、出発駅名を表す出発駅302と、到着駅名を表す到着駅303と、特急急行といった列車の種別を表す列車304と、ブリッジテーブル15内のブリッジID308を示す開始ブリッジID305と、出発駅から到着駅までかかる時間を表す所要時間306と、出発駅から到着駅までの距離を表す距離307とを備え、具体的なデータの例は、リンクID301が「1」、出発駅302が「n(1)」、到着駅303が「n(2)」、開始ブリッジID305が「1」、所要時間306が「x(1)」、距離307が「d(1)」である。
ここで、リンクとは出発駅,到着駅,列車,出発駅から到着駅に至るのに必要な所要時間、出発駅から到着駅の距離などを保持したデータを言う。リンクテーブル14は全ての駅間のリンクを保持している。

0021

図3(B)を用いてブリッジテーブル15のデータ構成例を説明する。
ブリッジテーブル15は、レコードに一意に定められたブリッジID308と、リンクテーブル14において、あるレコードの到着駅を出発駅とするレコードのリンクIDを示す接続リンクID309と、乗換えにかかる時間を表す乗換え時間310と、乗換えまたは直通または折返しなど列車の接続に関する情報を表す接続情報311とを備え、具体的なデータの例は、ブリッジID308が「1」、接続リンクID309が「112」、乗換え時間310が「32」、接続情報が「乗換え」である。

0022

ここで、ブリッジテーブル15の存在意義を説明する。
経路探索において、あるリンクから接続するリンクがどれなのかを探す場合に、リンクテーブル全体から検索していてはリンクテーブル14のデータ量は膨大なものであるため時間がかかる。例えば、図3(A)のリンクIDが「1」のリンクは到着駅がn(2)なので、これに接続するリンクはn(2)を出発駅とするリンクであるが、n(2)を出発駅とするリンクはリンクテーブル14のどこにあるか判らない。この為n(2)を出発駅とするリンクをテーブル全体から探す必要があるが、リンクテーブル14はレコード数が膨大な量に及ぶため、その中から探すのには時間がかかってしまう。そこで、あるリンクに対して接続するリンク情報を格納したデータを用意する。このデータをブリッジと呼ぶ。リンクにはブリッジの開始IDを格納しておく。また、ブリッジには次に接続するリンクIDと、接続にかかる乗換え時間や接続情報を格納しておく。

0023

このように構成することにより、例えば、図3(A)のリンクテーブル14のリンクID301が「1」のリンクでは、このリンクの開始ブリッジID305は「1」であるから、図3(B)のブリッジテーブル15のブリッジID308が「1」のブリッジを参照する。ブリッジID308が「1」のブリッジの接続リンクID309は「112」であるから、リンクID301から接続するリンクはリンクID301が「112」であることがわかる。また、リンクID301が「1」のリンクから接続するリンク、具体的にはこのリンクの着駅n(2)を出発駅とするリンクは複数存在するので、このリンクと同数だけブリッジも存在する。リンクID301が「2」のリンクの開始ブリッジID305が「51」であることから、リンクID301が「1」のリンクから接続するリンクは、ブリッジテーブル15のブリッジID308が「1」から「50」までのブリッジに接続情報があることがわかる。これらのブリッジを全て参照することにより、接続するリンクを全て取得することができる。

0024

また、取得したリンクの開始ブリッジID305を基に次に接続するリンクID301を取得することを繰り返すことにより、経路のネットワークを探索することができる。
このブリッジを用いることにより、次に接続するリンクを簡単に、かつ高速に取得することができる。また、このブリッジにリンクからリンクへの接続情報を予め持たせることにより、乗換なのか直通なのか等の判定処理経路探索処理から省くことができ、経路探索の処理効率の向上が図れる。

0025

図4を用いて、リンクテーブル14のデータ構成例を説明する。
図4(A)のような駅と路線が配置されている場合、図4(B)の様に停車駅単位でリンクを設定するのではなく、図4(C)の様に乗換可能駅単位にリンクを設定する。これにより、リンクデータを削減することができ、メモリ使用量の削減、探索対象現象による処理効率の向上が図れる。出発駅または目的駅が乗換え可能駅ではない場合は、その出発駅または目的駅を乗換駅と仮定し、最寄りの乗換え可能駅までのリンクを生成することにより乗換え可能駅のみの鉄道経路のネットワークにおいて経路探索を行うことができる。

0026

図6を用いて、通過経路情報テーブル16のデータ構成例を説明する。
図6(A)に経路のネットワークの例を示す。例えば、リンクIDが「5453」の経路は、B駅を出発駅とし、その直前の経路はリンクIDが「777」のものと、「1677」のものと「2245」がある。この場合の通過経路情報テーブル16の例として、図6(B)を示す。通過経路情報テーブル15のデータ構成例は、各リンクに対し、直前の経路である直前リンクID601と、直前格納位置602と、経路評価値603とを備え、経路評価値603は、所要時間604と、乗換え回数605と、距離606とを備え、具体的なデータの例は、リンクIDが「4553」の場合、直前リンクID601が「1667」、直前格納位置602が「3」、所要時間604が「78」、乗換え回数605が「2」、距離606が「114.3km」である。

0027

図8を用いて生成経路情報テーブル17のデータ構成例を説明する。生成経路情報テーブル17は、生成された生成経路情報を示す経路801と、出発駅から目的駅までの所要時間を示す所要時間802と、乗換え回数を示す乗換回数803と、出発駅から目的駅までの距離を示す距離804とを備え、具体的なデータの例は、経路801が「S−A−B−C−G」、所要時間802が「25」、乗換回数803が「1」、距離804が「23.8km」である。

0028

<動作の説明>
図2を用いて、本発明の実施形態の処理の流れの概要を説明する。
先ず、経路探索に必要なデータを読み込む[ステップ201]。
次に、探索条件を設定する[ステップ202]。ここで、探索条件とは、例えば出発駅、目的駅、利用列車種別、所要時間優先か乗換え回数優先か等の探索において優先すべき事項である探索種別等を指す。

0029

次に、経路探索部11はダイクストラ法による経路探索を行う[ステップ203]。ダイクストラ法では最優秀経路情報求め、同時に最優秀経路情報を求めるときに使用したリンクテーブルの全通過経路情報を通過経路情報テーブル16に保持しておく。
ついで前記全通過情報から経路生成部12によって複数の生成経路情報を生成する[ステップ204]。

0030

次に、前記経路生成部12によって生成された複数の生成経路情報をGAによって経路補正を行う[ステップ205]。GAにおいては、一つの経路、つまり出発駅から目的駅までつながった経路を1つの遺伝子とし、1点交叉により新経路を生成し、この生成された経路の中から最優秀経路情報に次ぐ複数の代替経路が選択される[ステップ206]。
ここで1点交差とは、二つの経路を経路の途中の1点でそれ以降の経路を交換することを言う。

0031

以上のように、本発明の実施形態の処理の概要は、先ず経路探索部11がダイクストラ法によって最優秀経路情報と前記最優秀経路情報を求めるときに使用した通過経路情報を求め、次に経路生成部12が前記最優秀経路情報を求めるときに使用した通過経路情報から生成経路情報を生成し、最後に経路補正部13がGAによって経路補正を行い、最優秀経路情報に次いで優秀な複数の代替経路を求める、というものである。

0032

次に、図5を用いて、経路探索部11であるダイクストラ法による経路探索203の詳細動作を説明する。始めに経路探索部11で用いる変数および値について説明する。
・N:探索対象指定駅を格納する変数である。
・L(i):指定駅を出発駅とするリンク群である。
・E:通過経路情報を格納する変数である。現リンクID、直前リンクID、直前通過経路情報格納位置、経路評価値を格納する。
・T(x,y):当該リンク通過時の通過経路情報を格納する2次元配列である。xはリンクIDであり、yは格納位置である。
・S(j):経路探索対象の通過経路情報を格納する配列である。
・D(k):通過経路情報配列である。目的駅到達通過経路情報を保持する。

0033

次に、処理フローを説明する。
経路探索部11は、最初に出発駅を設定する[ステップS501]。
次に、経路探索部11は、Nを出発駅とするリンク群をLに代入する[ステップS502]。
次に、経路探索部11は、リンク群が存在するかどうか判定する[ステップS503]。リンク群が存在しなければ処理を終了し、存在する場合、直前のリンクまでの通過経路情報を保持するための変数E1、現在のリンクまでの通過経過情報を保持するための変数E2を用意し、ステップS504に進む。E1およびE2の初期値は0(空)である。リンク群の添字をiとし、i=1とする[ステップ504]。

0034

次に、経路探索部11は、L(i)が存在するかどうか判定する[ステップS505]。存在すればステップS506に進む。存在しなければステップ516に進む。
現在のリンクL(i)の通過経路情報E2の経路評価値をE1にL(i)のリンクが持つ評価値加算して求める[ステップS506]。
次に、経路探索部11はL(i)が通過か未通過かの判定を行う[ステップS507]。L(i)が未通過の場合、SにL(i)についての通過経路情報を追加し[ステップS508]T(L(i))にE2を追加する[ステップS511]。L(i)が通過の場合、ステップS509に進む。

0035

経路探索部11は、L(i)が既に通過済みである場合、E2がT(L(i))の最優秀経路情報評価値よりも優秀かどうか判定する[ステップS509]。最優秀のものより優秀である場合にはSのL(i)についての通過経路情報をE2に書換え[ステップS510]、T(L(i))にE2を追加する[ステップS511]。

0036

従来、ダイクストラ法では、最優秀経路情報のみを求めるために、最優秀経路情報のみを保持しており、より優秀な通過経路情報があった場合は元の値を書き換える。しかし、本実施形態では後の経路作成時に利用するために、最優秀でない通過経路情報も保持しておく。この為T(L(i))へE2は書き換えではなく追加としている。
経路探索部11は、E2がT(L(i))の最優秀経路情報評価値よりも優秀でない場合、L(i)がループ区間を含むかどうか判定する[ステップS512]。含まなければS511に進む。含む場合にはステップS515に進む。
ここで、「ループ区間を含む」とは、経路内で重複する列車停車駅が存在することを意味する。重複停車駅間冗長区間となり、非実用的な経路となるため、ループ区間を含む経路は切り捨てる。

0037

経路探索部11は、ステップS511に続き、L(i)の到着駅が目的駅であるかどうかを判定する[ステップS513]。目的駅でない場合にはステップS515に進む。目的駅であった場合にはDにE2を追加し[ステップS514]、ステップS515に進む。
ステップS515では、iに1を加えステップS505に戻る。
また、経路探索部11はステップS505でL(i)が存在しなくなった場合、つまり、Nを出発駅とするリンクの処理が全て完了すると、ステップS516に進む。ステップS516ではSが空かどうかを判定する。空の場合は処理を終了する。空でない場合には、Sから次の検索対象となる通過経路情報を取得するために、Sの最優秀通過経路情報をE1に代入する[ステップS517]、E1に設定した値は検索対象となったので、E1への設定値をSから削除する[ステップS518]。
次に、経路探索部11はNにE1の現リンクの到着駅を代入する[ステップS519]。

0038

次に、経路探索部11はNが目的駅であるかどうか判定し[ステップS520]、Nが目的駅であれば、DにE1を追加し、ステップS516に戻る。Nが目的駅でなければ、ステップS520に戻り、Nを出発駅とするリンク群を取得する。ここで、Nを出発駅とするとするリンク群を取得する際に、リンクのブリッジ開始IDをもとにブリッジを取得し、乗換えに関する情報と次に接続するリンクを取得することができる。このようにブリッジテーブル15に予めデータを用意しておくことにより、次につながるリンクの探索、乗換情報に関する情報の判定、取得等を省略することができ、探索の処理を少なくし、探索時間の向上を図ることができる。
経路探索部11はSが空になったところで処理を終了する[ステップS516]。

0039

以上の処理により、各リンクが通過経路情報を保持した状態となる。例えば、図6(A)のようなネットワークにおいて、リンクID4553のリンクには、リンクID1667から来た場合の通過経路情報、リンクID777から来た場合の通過経路情報、リンクID2245から来た場合の通過経路情報、というように、前記経路探索終了時には、経路探索時に生成された通過経路情報を各リンクが干しした状態のネットワークおよび生成経路情報テーブル17が生成される。この通過経路情報を用いて、出発駅から目的駅までの経路を作成する。

0040

図7を用いて、経路生成部12が前記経路探索部11で求めた通過経路情報を元に経路作成を行う方法を説明する。
前記経路探索部11で取得した目的駅へ到達する通過経路情報群Dを用いて、目的駅から出発駅へとたどってゆくことによって、出発駅から目的駅への経路を取得する。
まず、経路生成部12は、kに1を代入する[ステップS701]。
次に、経路生成部12はD(k)が存在するかどうか判定する[ステップS702]。D(k)が存在しない場合は既設経路を生成するか、新規経路を生成するかの判定を行い[ステップS714]、新規経路を生成する場合にはステップS701に戻り、既設経路を生成する場合には処理を終了する。D(k)が存在する場合には、D(k)の持つリンクを取得し[ステップS703]、ステップS740に進む。

0041

次に、経路生成部12は、ステップS703において取得したリンクが出発駅に到達しているかどうか判定する。到達していなければ直前の通過経路情報を取得する[ステップS705]。
次に、経路生成部12は、ステップS705で取得した通過経路情報が使用済みかどうか判定する[ステップS706]。使用済みでなければそのまま利用し、ステップS709に進む。使用済みであればステップS705で取得した通過経路情報が他に未使用通過経路情報があるかどうか判定する[ステップS708]。未使用通過経路情報がある場合には未使用通過経路情報のうち、最優秀の通過経路情報を取得し[ステップS708]ステップS709に進む。

0042

次に、経路生成部12はステップS705において取得した通過経路情報またはステップS708において取得した通過経路情報と、現在まで取得している通過経路情報を比較して、経路がループ区間を含むかどうか判定する[ステップS709,S710]。ループ区間を含まなければステップS705において取得した通過経路情報またはステップS708において取得した通過経路情報の持つリンクを取得し[ステップS711]ステップS704に戻る。
ステップS704でリンクが出発駅に到達している場合、及びステップS710がループ区間を含む場合は、経路生成部12は経路生成のために取得した通過経路情報を全て使用済みにし[ステップS712]、kに1を加算し[ステップS713]、ステップS702に戻る。
以上のようにして生成された経路情報を、生成経路情報という。

0043

図8に経路生成部12が生成した生成経路情報テーブル17の例を示す。図8では出発駅をS、目的駅をGとしている。経路生成部12が生成した生成経路情報は、使用済み通過経路情報を避けて無理やり接続しているものであり、精度の低いものであるが、この後にGAを用いて生成された経路を補正する。

0044

次に図9を用いて、GAによる経路補正部13の処理フロー例を説明する。
先ず、経路補正部13は前記経路生成部12が生成した生成経路情報を取得し、ランキングを生成する。ここでランキングとは、一定数の生成経路情報を、重複を排除し、評価順に保持しているテーブルである。経路補正部13が新しい生成経路情報をランキングに挿入する場合には、例えばその生成経路情報が、現ランキングの11位の生成経路情報より優秀で、10位の生成経路情報より優秀でなければ、10位と11位の間に挿入する。11位以下の生成経路情報は全て順位が1つ繰り下がり最下位の生成経路情報を削除し、ランキング内の生成経路情報保持数は一定に保つ、という動作をする。

0045

ランキングに経路を挿入後、経路生成部12が生成した全生成経路情報に付き、各停車駅で分割し、前半経路後半経路集合を生成する。例えば図10に示すように、A−B−C−D−Eという経路がある場合、(A−B)(B−C−D−E)、(A−B−C)(C−D−E)、(A−B−C−D)(D−E)のように分割することができる。
次に経路補正部13は、分割した前半経路と後半経路を分割した経路毎にまとめ[ステップS902]、経路に停車駅があるかどうか判定する[ステップS903]。停車駅がなければ処理を終了する。停車駅がある場合、経路補正部13は、停車駅毎に全ての接続パターンの評価を試み、評価の高い優秀な経路を取得してゆく。具体的には、先ず1つの停車駅を選び、前半経路の有無を判定する[ステップ905]。前半経路が存在しない場合、次の停車駅を取得し[ステップS904]、ステップS903に戻る。前半経路が存在する場合、後半経路の有無を判定する[ステップS907]。後半経路も存在する場合、前半経路と後半経路を接続し、出発駅から目的駅までの経路を作成する[ステップS908]。

0046

生成した経路をランキングに挿入し[ステップS909]、挿入が成功したかどうか判定する[ステップS910]。挿入に成功した場合新経路としてその経路を別途保持しておく[ステップS911]。挿入に失敗した場合、現在のランキング最下位よりも評価値が低い、またはランキングに既に同じ経路があるということを意味するので、この経路は削除する。

0047

図11にB駅で分割した場合を示す。前半経路と後半経路を組み合わせて接続し、評価を行ってランキングへの挿入を試みることを示している。ランキングへの挿入成功とはランキング内にその経路が保持される状態を言い、失敗とはランキングの最下位よりも優秀でないためにランキング内にその経路が保持されないことを意味する。
次に経路補正部13は、次の後半経路を取得し[ステップS912]、ステップS907に戻る。
次に経路補正部13は、ステップ907で後半経路が存在しなくなったら、次の前半経路を取得し[ステップS906]、ステップS905に戻り、ステップS905で前半経路が存在しなくなったら、次の停車駅を取得し[ステップS904]、ステップS903に戻り、ステップS903で停車駅が存在しなくなったら処理を終了する。

0048

図12に、前記経路補正部13による処理結果を示す。例として、出発駅をSとし、目的駅をGとした場合を示している。結果は、ダイクストラ法による経路探索部11および経路生成部12によって生成された経路が補正され、経路評価値の優秀な順に並んでいる。

0049

以上述べた経路探索方法の具体的な実施例を挙げる。経路評価は所要時間、乗換回数、距離の3つの値を用い、所要時間探索、乗換探索、距離探索を行う。核探索における経路評価方法は以下の通りである。
(所要時間探索)
所要時間を基準に経路探索を行う。この場合、所要時間が短い方が優秀な経路となる。所要時間が同じ場合は乗換回数を比較し、乗換回数が少ない方を優先する。所要時間、乗換回数共に同じ場合は、距離が短いものを優先する。
(乗換回数探索)
乗換回数を基準に経路探索を行う。この場合、乗換回数が少ない方が優秀な経路となる。乗換回数が同じ場合は所要時間を比較し、所要時間が短いほうを優先する。乗換回数、所要時間共に同じ場合は、距離の短いものを優先する。

0050

(距離探索)
距離を基準に経路探索を行う。この場合、距離が短い方が優秀な経路となる。鉄道経路は距離を元に運賃料金を計算している場合が多く、一概には言えないが、距離が短ければ金額が安い、という場合が多い。またJRの運賃規則において、ある区間内ではではどのように列車に乗っても最安となる運賃で計算する、といった規則があり、この場合に最安経路を求めるために、最短距離経路を求める必要がある。距離が同じ場合は所要時間を比較し、所要時間が短いほうを優先する。距離、所要時間共に同じ場合は、乗換回数が少ないものを優先する。

0051

以下に(溝口)−(東京)間で行った結果を示す。[表1]が所要時間探索結果、[表2]が乗換回数探索結果、[表3]が距離探索結果で、
全て上位5経路を示している。なお本経路探索では、前記ランキングの数を200として実行している。

0052

上記のように、第2経路以降も、第1最優秀評価経路に近い実用的な有効代替経路を導出している。また、各探索法によってさまざまな結果を導出していることがわかる。各表では上位5経路のみを表示したが、実際にはランキングの数だけの経路、今回であれば200経路を保持している。[表3]の距離探索の結果では同じような経路ばかり導出されているが、例えば「乗換パターンが同じ経路をどういつのけいろとみなす」というような条件でランキング内の経路をグループ化し、各グループの上位から経路を導出する等により、さまざまなパターンの経路を導出できる。

0053

また、上記の例では単純な所要時間探索、乗換回数探索、距離探索を示したが、例えば所要時間1分を1ポイント、乗換1回を10ポイント、というように複数のパラメータを一意のポイントに変換し、それを経路評価値として用いれば、GAによって評価値に応じた経路補正により、複数条件を用いた柔軟な経路探索が可能な経路探索システムを提供することが可能である。

図面の簡単な説明

0054

本発明の実施形態における経路検索システムの全体構成図である。
本発明の実施形態における処理のフローチャートである。
リンクテーブルとブリッジテーブルの例である。
路線図と停車駅単位のリンクおよび乗換駅単位のリンクの例である。
経路探索プログラムのフローチャートである。
路線図の例と通過経路情報の例である。
経路生成プログラムのフローチャートである。
経路生成プログラムによって生成された生成経路情報の例である。
遺伝的アルゴリズムによる経路補正プログラムのフローチャートである。
経路補正プログラムによる経路分割例である。
経路補正プログラムにより分割した経路の合成例である。
経路補正プログラムによって補正された結果の例である。

符号の説明

0055

10:サーバ、11:ダイクストラ法経路作成部、12:GA経路作成部、13:リンクテーブル、14:ブリッジテーブル、15:通過経路情報テーブル、16:生成経路情報テーブル、20:公衆通信回線網、30:ユーザー端末

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

該当するデータがありません

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

  • ユシロ化学工業株式会社の「 3次元外科治療研修モデル用組成物及びその製造方法」が 公開されました。( 2020/10/29)

    【課題・解決手段】切断されたとしても繰り返し使用可能な3次元外科治療研修モデル用組成物を提供することを課題とし、3次元外科治療研修モデル用組成物は自己修復性を有するポリマーゲルを含む。... 詳細

  • 日本電産シンポ株式会社の「 地図作成システムおよび地図作成装置」が 公開されました。( 2020/10/29)

    【課題・解決手段】地図作成システム(101、200)は、移動体が移動する空間に固定的に設置され、複数の異なる時刻に空間の一部をセンシングして、各時刻のセンサデータを出力する固定センサ(103)と、各時... 詳細

  • 鉄道情報システム株式会社の「 予約数予測装置」が 公開されました。( 2020/10/29)

    【課題】列車ごとの交通手段の利用客数(席予約数)を予測することができる予約数予測装置を提供する。【解決手段】予測対象列車の運行月と同月であって年が異なる運行済予測用データから求められた回帰式に基づいて... 詳細

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

該当するデータがありません

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ