図面 (/)

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

出願人 株式会社日立システムズ
発明者 奥田学
出願日 2011年9月12日 (9年3ヶ月経過) 出願番号 2011-198158
公開日 2013年4月4日 (7年8ヶ月経過) 公開番号 2013-060039
状態 特許登録済
技術分野 航行(Navigation) 鉄道交通の監視、制御、保安
主要キーワード 日パターン 通過経路情報 運行列車 現リンク 運転区間 通過済み ブリッジテーブル 運転時刻
関連する未来課題
重要な関連分野

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

図面 (6)

課題

鉄道経路網において、少ない負荷時刻表を加味した経路探索を実現することができる経路探索システムを提供する。

解決手段

経路探索システムにおいて、出発駅到着駅、出発駅から到着駅の間を走行する列車、出発駅から到着駅に至る平均所要時間、出発駅から到着駅に至る距離、およびこれらを含むレコード一意割り振られた第1のリンクIDが格納されたリンクデータ103と、リンクデータ103と関連付けるための第2のリンクID、第2のリンクIDに対応した列車の運転日および列車の1日の出発時刻特定ビットで表したビット列、および列車の時間帯別最短所要時間が格納された時刻表ビットパターンデータ104と、探索対象の出発駅から到着駅に至る前記リンクデータの複数のレコードに対応する時刻表ビットパターンデータ104の各ビット検索し、探索対象の出発駅から到着駅に至る経路を取得する経路探索部102とを備えた。

概要

背景

鉄道経路網において、出発駅から目的駅に到達するまでの経路は多数存在しており、これらの経路の中から最適な経路を導出するための手法として、例えば特開平11−44547号公報(特許文献1)や、特開2007−83800号公報(特許文献2)等に記載のものがある。

これらの技術は、各駅間に一定のコストを設定し、当該コストを用いて経路探索を行っているが、鉄道経路網においては、列車時刻表に従って運行しており、各駅間のコストは一定ではないため、導出された経路について時刻表を加味した場合、最適な経路でない可能性がある。

一般的な鉄道経路探索では、以下のような手法となる。
(1)上記特許文献1や、特許文献2の技術を用い、各駅間に平均的な所要時間を設定した鉄道経路ネットワークを生成し、経路探索を実施する。
(2)(1)で求まった経路に対し、経路探索条件として指定された時刻に対して最適となる時刻表を設定する。

概要

鉄道経路網において、少ない負荷で時刻表を加味した経路探索を実現することができる経路探索システムを提供する。経路探索システムにおいて、出発駅、到着駅、出発駅から到着駅の間を走行する列車、出発駅から到着駅に至る平均所要時間、出発駅から到着駅に至る距離、およびこれらを含むレコード一意割り振られた第1のリンクIDが格納されたリンクデータ103と、リンクデータ103と関連付けるための第2のリンクID、第2のリンクIDに対応した列車の運転日および列車の1日の出発時刻特定ビットで表したビット列、および列車の時間帯別最短所要時間が格納された時刻表ビットパターンデータ104と、探索対象の出発駅から到着駅に至る前記リンクデータの複数のレコードに対応する時刻表ビットパターンデータ104の各ビット検索し、探索対象の出発駅から到着駅に至る経路を取得する経路探索部102とを備えた。

目的

本発明の目的は、鉄道経路網において、少ない負荷で時刻表を加味した経路探索を実現することができる経路探索システム、経路探索方法および経路探索プログラムを提供する

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

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

請求項1

出発駅から到着駅に至る探索条件合致した経路情報を探索する経路探索システムであって、出発駅、到着駅、前記出発駅から前記到着駅の間を走行する列車、前記出発駅から前記到着駅に至る平均所要時間、前記出発駅から前記到着駅に至る距離、およびこれらを含むレコード一意割り振られた第1のリンクIDが格納されたリンクデータと、前記リンクデータと関連付けるための第2のリンクID、前記第2のリンクIDに対応した前記列車の運転日および前記列車の1日の出発時刻特定ビットで表したビット列、および前記列車の時間帯別最短所要時間が格納された時刻表ビットパターンデータと、探索対象の出発駅から到着駅に至る前記リンクデータの複数のレコードに対応する前記時刻表ビットパターンデータの各ビット検索し、前記探索対象の出発駅から到着駅に至る経路乗り継ぎ可能な経路を取得する経路探索部とを備えたことを特徴とする経路探索システム。

請求項2

請求項1に記載の経路探索システムにおいて、前記時刻表ビットパターンデータは、ビット列として、1日を1ビットとし、該当する前記リンクIDで運行している列車が運行する日を「1」、運休する日を「0」に設定した列車運転日ビットパターン、および1分を1ビットとし、1日を1440ビットで表し、該当する前記リンクIDで運行している列車の出発時刻の位置に「1」、それ以外を「0」に設定した列車出発時刻ビットパターンを有することを特徴とする経路探索システム。

請求項3

出発駅、到着駅、列車、前記出発駅から前記到着駅に至る平均所要時間、前記出発駅から前記到着駅に至る距離、およびこれらを含むレコードに一意に割り振られた第1のリンクIDが格納されたリンクデータと、前記リンクデータと関連付けるための第2のリンクID、前記第2のリンクIDに対応した前記列車の運転日および前記列車の1日の出発時刻を特定ビットで表したビット列、および前記列車の時間帯別の最短所要時間が格納された時刻表ビットパターンデータとを保有し、経路探索部により、出発駅から到着駅に至る探索条件に合致した経路情報を探索する経路探索システムの経路探索方法であって、前記経路探索部により、探索対象の出発駅から到着駅に至る前記リンクデータの複数のレコードに対応する前記時刻表ビットパターンデータの各ビットを検索し、前記探索対象の出発駅から到着駅に至る経路で乗り継ぎ可能な経路を取得することを特徴とする経路探索方法。

請求項4

請求項3に記載の経路探索方法において、前記時刻表ビットパターンデータは、ビット列として、1日を1ビットとし、該当する前記リンクIDで運行している列車が運行する日を「1」、運休する日を「0」に設定した列車運転日ビットパターン、および1分を1ビットとし、1日を1440ビットで表し、該当する前記リンクIDで運行している列車の出発時刻の位置に「1」、それ以外を「0」に設定した列車出発時刻ビットパターンから構成されたことを特徴とする経路探索方法。

請求項5

出発駅、到着駅、列車、前記出発駅から前記到着駅に至る平均所要時間、前記出発駅から前記到着駅に至る距離、およびこれらを含むレコードに一意に割り振られた第1のリンクIDが格納されたリンクデータと、前記リンクデータと関連付けるための第2のリンクID、前記第2のリンクIDに対応した前記列車の運転日および前記列車の1日の出発時刻を特定ビットで表したビット列、および前記列車の時間帯別の最短所要時間が格納された時刻表ビットパターンデータとを保有したコンピュータ上で実行され、出発駅から到着駅に至る探索条件に合致した経路情報を探索する経路探索プログラムであって、前記コンピュータを、探索対象の出発駅から到着駅に至る前記リンクデータの複数のレコードに対応する前記時刻表ビットパターンデータの各ビットを検索し、前記探索対象の出発駅から到着駅に至る経路で乗り継ぎ可能な経路を取得する経路探索部として機能させることを特徴とする経路探索プログラム。

請求項6

請求項5に記載の経路探索プログラムにおいて、前記時刻表ビットパターンデータは、ビット列として、1日を1ビットとし、該当する前記リンクIDで運行している列車が運行する日を「1」、運休する日を「0」に設定した列車運転日ビットパターン、および1分を1ビットとし、1日を1440ビットで表し、該当する前記リンクIDで運行している列車の出発時刻の位置に「1」、それ以外を「0」に設定した列車出発時刻ビットパターンから構成されたことを特徴とする経路探索プログラム。

技術分野

0001

本発明は、出発駅から目的駅までの最適な経路を取得する経路探索システム経路探索方法および経路探索プログラムに関し、特に少ない負荷で処理可能な技術に関するものである。

背景技術

0002

鉄道経路網において、出発駅から目的駅に到達するまでの経路は多数存在しており、これらの経路の中から最適な経路を導出するための手法として、例えば特開平11−44547号公報(特許文献1)や、特開2007−83800号公報(特許文献2)等に記載のものがある。

0003

これらの技術は、各駅間に一定のコストを設定し、当該コストを用いて経路探索を行っているが、鉄道経路網においては、列車時刻表に従って運行しており、各駅間のコストは一定ではないため、導出された経路について時刻表を加味した場合、最適な経路でない可能性がある。

0004

一般的な鉄道経路探索では、以下のような手法となる。
(1)上記特許文献1や、特許文献2の技術を用い、各駅間に平均的な所要時間を設定した鉄道経路ネットワークを生成し、経路探索を実施する。
(2)(1)で求まった経路に対し、経路探索条件として指定された時刻に対して最適となる時刻表を設定する。

先行技術

0005

特開平11−44547号公報
特開2007−83800号公報

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

0006

ところで、前述した一般的な鉄道経路探索の場合、(1)の段階では時刻表を考慮しない探索となるため、臨時列車等の平均的に運行していない列車についての最適な探索が困難である。時刻表を直接探索するという選択もあるが、時刻表データは膨大であるため、探索負荷が大きく、性能面で問題がある。

0007

また、鉄道経路網(空路、バス船舶等の交通網も含む)は、出発駅、到着駅、列車、出発駅から到着駅に至る所要時間、距離等の駅間列車情報を表す「リンク」と、前記リンクで表現されるネットワーク上を実際に運行する列車の発着時刻(出発駅XX時XX分出発〜到着駅XX時XX分到着)を表す「時刻表」で構成されている。

0008

前記時刻表は、例えばリンクA→B駅に対して、06:00出発、06:30出発、・・・というように、1つのリンクに対して複数存在している。日本全国の鉄道に対する時刻表データのレコード数は膨大であり、またリンクと時刻表が1対多の関係であることが、時刻表を加味して経路探索を行うことを困難にしている。

0009

以上のように、従来の技術では、鉄道経路網(空路、バス、船舶等の交通網も含む)において、時刻表を加味した経路探索を少ない探索負荷で実施することは困難であった。

0010

そこで、本発明の目的は、鉄道経路網において、少ない負荷で時刻表を加味した経路探索を実現することができる経路探索システム、経路探索方法および経路探索プログラムを提供することにある。

0011

本発明の前記ならびにその他の目的と新規な特徴は、本明細書の記述および添付図面から明らかになるであろう。

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

0012

本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、次の通りである。

0013

すなわち、代表的なものの概要は、経路探索システムにおいて、出発駅、到着駅、出発駅から到着駅の間を走行する列車、出発駅から到着駅に至る平均所要時間、出発駅から到着駅に至る距離、およびこれらを含むレコード一意割り振られた第1のリンクIDが格納されたリンクデータと、リンクデータと関連付けるための第2のリンクID、第2のリンクIDに対応した列車の運転日および列車の1日の出発時刻特定ビットで表したビット列、および列車の時間帯別最短所要時間が格納された時刻表ビットパターンデータと、探索対象の出発駅から到着駅に至るリンクデータの複数のレコードに対応する時刻表ビットパターンデータの各ビット検索し、探索対象の出発駅から到着駅に至る経路で乗り継ぎ可能な経路を取得する経路探索部とを備えたものである。

0014

また、経路探索方法において、出発駅、到着駅、列車、出発駅から到着駅に至る平均所要時間、出発駅から到着駅に至る距離、およびこれらを含むレコードに一意に割り振られた第1のリンクIDが格納されたリンクデータと、リンクデータと関連付けるための第2のリンクID、第2のリンクIDに対応した列車の運転日および列車の1日の出発時刻を特定ビットで表したビット列、および列車の時間帯別の最短所要時間が格納された時刻表ビットパターンデータとを保有し、経路探索部により、探索対象の出発駅から到着駅に至るリンクデータの複数のレコードに対応する時刻表ビットパターンデータの各ビットを検索し、探索対象の出発駅から到着駅に至る経路で乗り継ぎ可能な経路を取得するものである。

0015

また、経路探索プログラムにおいて、出発駅、到着駅、列車、出発駅から到着駅に至る平均所要時間、出発駅から到着駅に至る距離、およびこれらを含むレコードに一意に割り振られた第1のリンクIDが格納されたリンクデータと、リンクデータと関連付けるための第2のリンクID、第2のリンクIDに対応した列車の運転日および列車の1日の出発時刻を特定ビットで表したビット列、および列車の時間帯別の最短所要時間が格納された時刻表ビットパターンデータとを保有したコンピュータ上で実行され、コンピュータを、探索対象の出発駅から到着駅に至るリンクデータの複数のレコードに対応する時刻表ビットパターンデータの各ビットを検索し、探索対象の出発駅から到着駅に至る経路で乗り継ぎ可能な経路を取得する経路探索部として機能させるものである。

発明の効果

0016

本願において開示される発明のうち、代表的なものによって得られる効果を簡単に説明すれば以下の通りである。

0017

すなわち、代表的なものによって得られる効果は、時刻表を加味し、臨時運行列車や臨時運休列車を加味した経路探索を、高い精度で且つ少ない負荷で実行することができる。例えば、災害時等、急遽変更が発生した状態においても、変更内容を反映した時刻表を取り込むことにより、当変更内容を加味した精度の高い経路探索を実行することができる。

図面の簡単な説明

0018

本発明の一実施の形態にかかる経路探索システムの構成を示す構成図である。
本発明の一実施の形態にかかる経路探索システムで使用されるリンクデータおよび時刻表ビットパターンデータの一例を示す図である。
本発明の一実施の形態にかかる経路探索システムで使用されるリンクデータおよび時刻表ビットパターンデータの生成の一例を示す図である。
本発明の一実施の形態にかかる経路探索システムによる経路探索方法を示すフローチャートである。
本発明の一実施の形態にかかる経路探索システムによる経路探索方法の経路探索処理の具体例を示す図である。

実施例

0019

以下、本発明の実施の形態を図面に基づいて詳細に説明する。なお、実施の形態を説明するための全図において、同一の部材には原則として同一の符号を付し、その繰り返しの説明は省略する。

0020

<経路探索システムの構成>
図1および図2により、本発明の一実施の形態にかかる経路探索システムの構成について説明する。図1は本発明の一実施の形態にかかる経路探索システムの構成を示す構成図、図2は本発明の一実施の形態にかかる経路探索システムで使用されるリンクデータおよび時刻表ビットパターンデータの一例を示す図である。

0021

図1において、経路探索システム100は、経路探索サーバ101および経路探索部102から構成され、経路探索サーバ101には、公衆通信回線網106を介して利用者107が操作する端末などが接続され、利用者からの経路探索の条件の入力や利用者への経路探索結果の送信などが行われる。

0022

経路探索部102には、リンクデータ103、リンクデータ103と1対1に関連付けられビットパターン化した時刻表データ(以下、時刻表ビットパターンデータ104と呼ぶ)、列車の乗り換えに関する情報が格納された乗換情報データ105が格納されたデータベースが接続され、各データは経路探索部102で実行される経路探索プログラムによる経路探索処理に使用される。

0023

図1においては、経路探索部102で実行されている経路探索プログラムにより、リンクデータ103、時刻表ビットパターンデータ104、および乗換情報データ105を用いて、経路探索部102で経路探索を行い、回答経路を導出している。

0024

図2において、リンクデータ103とは、レコードに一意に割り振られたリンクID、出発駅、到着駅、列車、出発駅から到着駅に至るのに必要な平均的な所要時間、距離等を保持したデータである。このリンクデータ103を全ての駅間について保持したリンクテーブルを用いて、出発駅から目的駅まで接続するリンクを順に探索していくことにより、経路を導出することができる。

0025

時刻表ビットパターンデータ104とは、リンクデータ103の各レコードと関連付けるためのリンクID、1分を1ビットとし、1日(60分×24時間=1440分)を1440ビットで表し、該当するリンクIDで運行している列車の出発時刻の位置に「1」、それ以外を「0」に設定した列車出発時刻ビットパターンと、1日を1ビットとし、該当するリンクIDで運行している列車が運行する日を「1」、運休する日を「0」に設定した列車運転日ビットパターン、および該当するリンクIDで運行している列車群の出発駅から到着駅までの所要時間において、各時間帯別(0時台、1時台、…、23時台)に最も短い所要時間を設定した時間帯別最短所要時間からなるデータである。リンクデータ103と時刻表ビットパターンデータ104は、リンクIDで関連付けられており、1対1の関連となる。

0026

<リンクデータ103および時刻表ビットパターンデータ104の生成>
次に、図3により、本発明の一実施の形態にかかる経路探索システムで使用されるリンクデータおよび時刻表ビットパターンデータの生成について説明する。図3は本発明の一実施の形態にかかる経路探索システムで使用されるリンクデータおよび時刻表ビットパターンデータの生成の一例を示す図である。

0027

まず鉄道の時刻表は、図3の時刻表に示すように、列車毎に、列車名、運転日、運転区間の出発駅、出発時刻、到着駅、到着時刻等の項目で表現されている。図3の時刻表に示したようなフォーマットで日本全国全ての列車についてデータ化されたものが、鉄道時刻表販売業者により販売されており、当該時刻表データより、リンクデータ103、時刻表ビットパターンデータ104を生成する。

0028

まず、リンクデータ103については、時刻表データの全列車の駅間について、図3に示すようなフォーマットで生成される。リンクデータ103は、図3に示すように、「JR山手線」は、1日にから晩まで何本も運行しているため、時刻表データ上に同一区間を別時刻で運行する列車データが複数存在している。同一区間については1レコードに纏める。平均所要時間については、当該区間を1日に運行する全列車の所要時間の平均値から求める等して設定する。距離については、各駅間において固定で定められているので、その値を設定する。

0029

次に、時刻表ビットパターンデータ104については、該当リンクの区間を運行する列車の出発時刻を基に、列車出発時刻ビットパターンの該当位置に「1」を設定し、当該列車の運転日情報を基に、列車運転日ビットパターンの該当位置に「1」を設定する。例えば図3に示した「JR山手線」は、同一区間を1日に朝から晩まで何本も運行しているため、1レコードの時刻表ビットパターンデータにおける列車出発時刻ビットパターンの様々な位置に「1」が設定される。

0030

図3に示す時刻表ビットパターンデータ104の網掛け太字箇所が、図3の時刻表で示している時刻表データに対するビット設定であり、それ以外は別時刻に運行する列車に対するものである。

0031

列車運転日ビットパターンについては、当該区間を運行する全列車に対して設定するものである。例えば、図3に示した「JR山手線」の時刻表においては、「#1」の列車は「全日運転」であり、毎日同じ時刻で運行するが、「#2」の列車は「平日運転」、「#3」の列車は「土休運転」であり、運転日によって運行時刻が異なる。リンクデータ103と時刻表ビットパターンデータ104を1対1に関連付けるため、該当リンク区間に対して、運転日パターン毎に時刻表ビットパターンレコードを生成する必要がある。

0032

図3に示す例では、「#2」と「#3」は運転時刻が異なるため、平日運転日のレコードと、土休運転日のレコードを別々に生成する必要がある。

0033

時間帯別最短所要時間については、該当リンク区間を該当運転日に運行する該当時間帯の全列車の中で、最短の所要時間を設定する。ここで平均ではなく最短の所要時間を設定しているのは、経路探索時にリンクAからリンクBへの乗継が可能かを判定する際、リンクBに対する時刻表ビットパターンデータ104の列車出発時刻ビットパターンで、リンクBの最短乗継可能時刻をチェックするが、リンクAの所要時間が平均値であった場合、最短乗継時間をオーバーし、最適なリンクBへの乗継を取得できない可能性がある。このため、確実に最短の乗継が取得できるよう、最短所要時間を設定する。

0034

このリンクデータ103、時刻表ビットパターンデータ104について、経路探索時に時刻表データから生成するのは負荷が非常に大きいため、時刻表データからリンクデータ103、時刻表ビットパターンデータ104を生成する変換プログラム等を用意しておき、事前データファイル化しておく。

0035

当該データファイルを用いることで、経路検索時にリンクデータ103、時刻表ビットパターンデータ104を当フォーマットのまま利用でき、データ生成の負荷をなくすことができる。

0036

<経路探索方法の詳細>
次に、図4により、本発明の一実施の形態にかかる経路探索システムによる経路探索方法について説明する。図4は本発明の一実施の形態にかかる経路探索システムによる経路探索方法を示すフローチャートであり、リンクデータ103、時刻表ビットパターンデータ104を用いた経路探索処理を示している。

0037

始めに、経路探索処理で用いる値について説明する。
●N:探索対象指定駅を格納する値。
●M:経路探索中の現在時分を格納する値、1日の時刻を分(0〜1439)で保持する。
●D:経路探索中の現在日を格納する値。
●B:現リンクに対する時刻表ビットパターンを格納する値。
●L(i):指定駅を発駅とするリンク群
●E1,E2:通過経路情報。現リンクID、直前リンクID、現在時分、現在日を保持。
●T(x):該当リンク通過時の通過経路情報を格納する配列。x=リンクID。
●B1(x):探索指定日に運行する時刻表ビットパターンを格納した配列。x=リンクID、レコード数はリンクと同一。
●B2(x):探索指定日の翌日に運行する時刻表ビットパターンを格納した配列。x=リンクID、レコード数はリンクと同一。
●S(j):経路探索対象の通過経路情報を格納する配列。

0038

まず、Nに出発駅、Mに探索指定日時、Dに0を設定する(ステップ401)。次に、時刻表ビットパターンデータ104を取得する。日本国内を運行する列車であれば、寝台列車等、翌日へ跨いで運行する列車が存在するが、翌々日まで跨いで運行する列車は存在しない。よって、必要となる時刻表ビットパターンデータは、探索指定日分と、その翌日分である。B1に探索指定日に運行(列車運転日ビットパターンの探索指定日位置に「1」が設定されている)の時刻表ビットパターンデータ104を設定し(ステップ402)、B2に探索指定日の翌日に運行(列車運転日ビットパターンの探索指定日翌日位置に「1」が設定されている)の時刻表ビットパターンデータ104を設定する(ステップ403)。

0039

1つのリンクに対して、1運行日に対する時刻表ビットパターンデータ104は1レコードのみなので、リンクデータ103とB1およびB2に設定された時刻表ビットパターンデータ104のレコード数は同一となり、1対1の関連となる。

0040

次に、Nを発駅とするリンク群をLに設定し(ステップ404)、リンク群が存在するか否かを判定し(ステップ405)、ステップ405でLが空である場合はNから繋がるリンクが存在しないので、ここで探索終了とする。

0041

ステップ405でNから繋がるリンクが存在する場合、リンク群Lの添字をiとし、i=1として、リンクL(i)の通過経路情報についての処理を行う(ステップ406)。

0042

まず、リンクL(i)が存在するか否かを判定し(ステップ431)、ステップ431でリンクL(i)が存在する場合は、Mに直前リンクからの乗換時間を加算する(ステップ407)。

0043

乗換時間は、直前リンク、現リンクを基に、乗換情報データより取得する。乗換時間を加算したことで、Mが1440以上となっているか否かを判定する(ステップ408)。

0044

ステップ408でMが1440以上となっている場合、1日分の時間範囲(60分×24時間=1440分)を超えているので、翌日設定をする必要がある。ここで、Dが0であるか否かを判定し(ステップ409)、ステップ409でDが0でなければ、既に翌日であり、翌々日となってしまうので、探索終了とする。

0045

ステップ409でDが0であれば、Mから1440を減算し、翌日の時刻に設定し、Dを1に設定する(ステップ410)。

0046

ステップ408でMが1440未満であれば、Dが0か否かを判定する(ステップ411)。ステップ411でDが0であれば、探索指定日当日であるので、時刻表ビットパターンデータB1から該当リンクに対する時刻表ビットパターンデータレコードB1(L(i))を取得し、Bに格納する(ステップ412)。

0047

ステップ411でDが0でなければ(Dが1)、探索指定日翌日であるので、時刻表ビットパターンデータB2から取得し、Bに格納する(ステップ413)。

0048

現在時刻Mで乗継可能な最早の列車は、現在時刻以降で最も小さい時刻の列車である。Bの列車出発時刻ビットパターンから、M以上で最小となるビット位置を検索する(ステップ414)。

0049

具体的には、Bの列車出発時刻ビットパターンにおいて、現在時刻Mのビット位置から、ビット位置を1つずつインクリメントし、最初に「1」となる位置を取得する。

0050

次に、ステップ414での検索によりビット位置が見つかるか否かを判定し(ステップ415)、ステップ415でビット位置が見つからない場合、つまり列車出発時刻ビットパターンの最終位置(1440)まで検索しても「1」がなかった場合は、翌日に跨いでいる可能性がある。

0051

この場合は、Dが0か否かを判定し(ステップ416)、ステップ416でDが0でなかった場合は、翌々日へ跨いでしまうので、探索終了とする。

0052

ステップ416でDが0の場合は、翌日となるので、時刻表ビットパターンデータB2から該当リンクに対する時刻表ビットパターンデータレコードB2(L(i))を取得し、Bに格納し(ステップ417)、Mに0を設定、Dに1を設定し(ステップ418)、ステップ414を再度実行する。

0053

ステップ415で、ビット位置が見つかった場合は、Mに見つかったビット位置を設定する(ステップ419)。その後、当該リンクの運行時間を加算するため、Mから現在時刻を判定し、該当するBの時間帯別最短所要時間値を取得し、Mに加算する(ステップ420)。

0054

次に、ステップ408〜ステップ410と同様に、翌日判定、設定を行い(ステップ421〜ステップ423)、E2にM,Dの値を設定する(ステップ424)。

0055

次に、L(i)が未通過か否かを判定し(ステップ425)、ステップ425でL(i)が未通過の場合、SにL(i)についての通過経路情報E2を追加し(ステップ426)、T(L(i))にE2を追加する(ステップ429)。

0056

ステップ425でL(i)が未通過ではなく既に通過済みである場合、MがT(L(i))の持つ時分より小さいか否かを判定し(ステップ427)、ステップ427で小さければ、SのL(i)についての通過経路情報をE2に書き換え(ステップ428)、T(L(i))にE2を追加する(ステップ429)。

0057

ステップ427で小さくなければ、iを1加算し(ステップ430)、ステップ431に戻り、L(i)が存在しなくなるまで前記処理を繰り返す。

0058

ステップ431で、L(i)が存在しなくなった、つまりNを発駅とするリンク全てについて処理が完了すると、Sが空か否かを判定し(ステップ432)、ステップ432でSが空の場合は、探索対象となる通過経路情報がないため終了する。

0059

ステップ432でSが空でない場合は、Sから次の探索対象となる通過経路情報を取得する。Sの最早通過経路情報をE1に設定し(ステップ433)、E1に設定した値は探索対象となったので、Sから削除する(ステップ434)。NにE1の現リンクの着駅、MにE1の時分、DにE1の日を設定する(ステップ435)。

0060

次に、Nが目的駅か否かを判定し(ステップ436)、ステップ436でNが目的駅であれば、出発駅から目的駅まで到達しているので、現リンクに対するTから、直前リンクIDを基に出発駅まで辿って、出発駅から目的駅の経路を生成する(ステップ437)。

0061

ステップ436でNが目的駅でなければ、ステップ404に戻り、Nを発駅とするリンク群を取得し、これまでの処理を目的駅に到達するまで繰り返す。

0062

以上で出発駅から目的駅までの経路を取得することができる。

0063

前記で説明した処理では、出発駅の出発時刻を指定した出発時刻指定経路探索であるが、経路探索時の使用者要望としては、目的駅の到着時刻を指定した経路探索もある。到着時刻指定経路探索では、探索指定日と探索指定日前日の時刻表ビットパターンデータ104を取得し、目的駅から出発駅の方向に、現在時刻を減算していくように前記経路探索処理を実行することで実現できる。

0064

<経路探索処理の具体例>
次に、図5により、本発明の一実施の形態にかかる経路探索システムによる経路探索方法の経路探索処理の具体例について説明する。図5は本発明の一実施の形態にかかる経路探索システムによる経路探索方法の経路探索処理の具体例を示す図であり、図5(a)は出発が谷駅、到着が恵比寿駅のデータ、図5(b)は出発が恵比寿駅、到着が目黒駅のデータ、図5(c)は出発が目黒駅、到着が白金台駅のデータであり、出発駅:渋谷駅、目的駅:白金台駅、8/2(月)9:00出発の経路探索の一例を示している。

0065

まず、図5(a)に示すように、最初に検索指定日8/2(月)と検索指定日翌日8/3(火)が運転となっている時刻表ビットパターンデータ104のみを取得する。

0066

次に、渋谷駅を出発し、恵比寿駅へ運行するJR山手線のリンクIDが1のレコードを取得する。リンクIDが1のレコードに該当する時刻表ビットパターンを取得すると、9:00以降で最小の出発時刻は9:01であることがわかる。現在時刻9:01に9時台の最短所要時間2分を加算し、現在時刻を9:03とする。

0067

次に、図5(b)に示すように、恵比寿駅を出発するリンクIDのレコードを取得する。恵比寿駅を出発し、目黒駅へ運行するJR山手線のリンクIDが2のレコードを取得する。リンクIDが2のレコードには、8/2(月)は運行しない時刻表ビットパターンデータも存在するが、当データは運転日不一致で取得されない。リンクIDが1のレコードの列車とリンクIDが2のレコードの列車は両方ともJR山手線であり、乗換が発生しないため、乗換時間の加算はない。

0068

リンクIDが2のレコードに該当する時刻表ビットパターンデータ104を取得すると、9:01出発の列車があることがわかるが、現在時刻より過去であるため、乗継不可であることがわかる。現在時刻9:03以降では、9:03出発となる列車があることがわかるので、リンクIDが1のレコードからリンクIDが2のレコードは乗継可能である。9:03に9時台の最短所要時間3分を加算し、現在時刻を9:06とする。

0069

次に、図5(c)に示すように、目黒駅を出発するリンクIDを取得する。目黒駅を出発し、白金台駅へ運行する東京メトロ線のリンクIDが3のレコードを取得する。リンクIDが2のレコードとリンクIDが3のレコードは別列車で乗換が発生するため、乗換情報データ105より乗換時間5分が取得される。現在時刻9:06に乗換時間5分を加算し、現在時刻を9:11とする。リンクIDが3のレコードに該当する時刻表ビットパターンデータ104を取得すると、9:11以降では9:12に出発する列車があるので、リンクIDが2のレコードの列車からリンクIDが3のレコードの列車は乗継可能であることがわかる。当該リンクにより、目的駅である白金台駅へ到達する。このような手法で経路探索を行う。

0070

1つのリンクIDで特定される区間を運行する列車は、1日の間で数多く存在する。例えば、図5の(a)に示すリンクIDが1のレコードの区間(渋谷駅出発、恵比寿駅到着のJR山手線)を運行する列車は、1日で500本以上存在する。このため、時刻表データをそのまま利用する場合、当該リンクIDに対して500本以上の列車から最適な時間で乗継可能な列車を選択し、次のリンクIDを取得、当リンクIDに対してまた数多くの列車を探索・・・、という処理を繰り返すことになり、経路探索処理の負荷が非常に大きい。

0071

本実施の形態では、上述したような経路探索方法を用いることにより、1つのリンクIDに対して1つの時刻表となり、数多くの列車を探索する負荷を省くことが可能である。

0072

また、乗継可能時刻をビット位置検索で実現しているが、ビット位置検索は、Number of Leading Zero(NLZ)(ビット列を左側から見て、最初に1が立っているビット位置を探す)、Number of Training Zero(NTZ)(ビット列を右側から見て、最初に1が立っているビット位置を探す)という分野で、高速に実行するアルゴリズムが研究されており、このような高速アルゴリズムを適用することで、高速な処理を実現することが可能である。

0073

更に、特許第4358806号公報などで述べられているブリッジテーブル概念を用いることで、リンク間乗継時の検索処理の負荷を省くことができ、更なる処理効率の向上が図れる。また、特許第4358806号公報などに記載の探索方法を適用することで、時刻表を加味した優秀代替経路を導出することができる。

0074

以上、本発明者によってなされた発明を実施の形態に基づき具体的に説明したが、本発明は前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることはいうまでもない。

0075

本発明は、出発駅から目的駅までの最適な経路を取得する経路探索システム、経路探索方法および経路探索プログラムに関し、特に少ない負荷で処理する必要のあるシステムプログラムに広く適用可能である。

0076

100…経路探索システム、101…経路探索サーバ、102…経路探索部、103…リンクデータ、104…時刻表ビットパターンデータ、105…乗換情報データ、106…公衆通信回線網、107…利用者。

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

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

関連する公募課題

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

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

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

  • 京セラ株式会社の「 電子機器、制御方法、及びプログラム」が 公開されました。( 2020/10/29)

    【課題】操作性を向上させた電子機器、制御方法、及びプログラムを提供する。【解決手段】電子機器1は、自機器に接触されないジェスチャを検出する第1センサ(近接センサ18)と、自機器に接触されるタッチを検出... 詳細

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

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

  • 京セラ株式会社の「 電子機器、制御方法、及びプログラム」が 公開されました。( 2020/10/29)

    【課題】移動体の運転の安全性を向上可能な電子機器、制御方法、及びプログラムを提供する。【解決手段】自動車に搭載可能な電子機器は、自機器に触れられずにジェスチャを検出する第1センサと、自機器に接触される... 詳細

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

関連性が強い人物一覧

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

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

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

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

astavision 新着記事

サイト情報について

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

主たる情報の出典

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