(57)【要約】【課題】二次災害による影響も考慮した最適な経路を実用的な時間で算出する。【解決手段】１以上のノードとリンクとで構成されるネットワークの所定の範囲内の領域を、複数の領域に分割する分割部と、前記分割部により分割された複数の領域と、前記１以上のノードに含まれる始点ノード及び終点ノードをそれぞれ含む領域とから、隣り合う２つの領域を選択して、選択した２つの領域にそれぞれ含まれるノード間のルートを示す部分ルートを算出する部分ルート算出部と、前記部分ルートに基づいて、前記２つの領域毎に、予め定義された複数の目的関数の値の組を示す目的関数値を算出する目的関数値算出部と、前記始点ノードから前記終点ノードまでの１以上のルートを、前記部分ルートを継ぎ合わせることで算出するルート算出部と、前記目的関数値と、予め定義された前記目的関数の序列とに基づき、前記ルートを出力する出力部と、を有する。【選択図】図３
2018137718.tif 000002
【特許請求の範囲】
【請求項１】
１以上のノードとリンクとで構成されるネットワークの所定の範囲内の領域を、複数の領域に分割する分割部と、
前記分割部により分割された複数の領域と、前記１以上のノードに含まれる始点ノード及び終点ノードをそれぞれ含む領域とから、隣り合う２つの領域を選択して、選択した２つの領域にそれぞれ含まれるノード間のルートを示す部分ルートを算出する部分ルート算出部と、
前記部分ルート算出部が算出した前記部分ルートに基づいて、前記２つの領域毎に、予め定義された複数の目的関数の値の組を示す目的関数値を算出する目的関数値算出部と、
前記始点ノードから前記終点ノードまでの１以上のルートを、前記部分ルート算出部が算出した前記部分ルートを継ぎ合わせることで算出するルート算出部と、
前記目的関数値算出部が算出した前記目的関数値と、予め定義された前記目的関数の序列とに基づき、前記ルート算出部が算出した前記ルートを出力する出力部と、
を有するルート算出装置。
【請求項２】
前記始点ノードを含む領域と、前記始点ノードと前記終点ノードとの間の１以上の領域と、前記終点ノードを含む領域とを組み合わせた領域の組を作成する領域組作成部と、
前記目的関数値算出部が算出した前記目的関数値に基づいて、前記領域組作成部が作成した前記領域の組をソートして、予め決められた所定の件数の前記領域の組を抽出する抽出部と、を有し、
前記ルート算出部は、
前記抽出部が抽出した前記領域の組に含まれる隣り合う２つの領域において、前記部分ルート算出部が算出した前記部分ルートを繋ぎ合わせることで前記ルートを算出する、請求項１に記載のルート算出装置。
【請求項３】
前記領域組作成部は、
前記始点ノードと前記終点ノードとの間の１以上の領域間の距離と、所定の閾値とに基づいて、前記距離が前記所定の閾値未満となる前記領域の組を作成する、請求項２に記載のルート算出装置。
【請求項４】
前記所定の閾値は、
前記ネットワークに含まれる耐災性が高いリンクと、前記ネットワークが含まれる地域における災害の大きさと、前記地域における地形との少なくとも１つに基づいて設定又は算出される、請求項３に記載のルート算出装置。
【請求項５】
前記抽出部は、
更に、前記目的関数値と、前記領域の組の類似度とに基づいて、前記所定の件数の前記領域の組を抽出する、請求項２乃至４の何れか一項に記載のルート算出装置。
【請求項６】
前記出力部は、
前記目的関数値算出部が算出した前記目的関数値と、前記目的関数の序列とに基づく統計値が最大又は最小である前記ルートを出力する、請求項１乃至５の何れか一項に記載のルート算出装置。
【請求項７】
前記分割部は、
複数のノードが含まれるネットワークの所定の範囲内の領域を、予め設定された範囲のメッシュ状の複数の領域に分割する、請求項１乃至６の何れか一項に記載のルート算出装置。
【請求項８】
前記部分ルート算出部は、
選択した前記２つの領域にそれぞれ含まれるノードに対して、所定の経路探索アルゴリズムを用いることで、前記部分ルートを算出する、請求項１乃至７の何れか一項に記載のルート算出装置。
【請求項９】
前記経路探索アルゴリズムは、ダイクストラ法である、請求項８に記載のルート算出装置。
【請求項１０】
1以上のノードとリンクとで構成されるネットワークの所定の範囲内の領域を、複数の領域に分割する分割手順と、
前記分割手順により分割された複数の領域と、前記１以上のノードに含まれる始点ノード及び終点ノードをそれぞれ含む領域とから、隣り合う２つの領域を選択して、選択した２つの領域にそれぞれ含まれるノード間のルートを示す部分ルートを算出する部分ルート算出手順と、
前記部分ルート算出手順が算出した前記部分ルートに基づいて、前記２つの領域毎に、予め定義された複数の目的関数の値の組を示す目的関数値を算出する目的関数値算出手順と、
前記始点ノードから前記終点ノードまでの１以上のルートを、前記部分ルート算出手順が算出した前記部分ルートを継ぎ合わせることで算出するルート算出手順と、
前記目的関数値算出手順が算出した前記目的関数値と、予め定義された前記目的関数の序列とに基づき、前記ルート算出手順が算出した前記ルートを出力する出力手順と、
をコンピュータが実行するルート算出方法。
【請求項１１】
1以上のノードとリンクとで構成されるネットワークの所定の範囲内の領域を、複数の領域に分割する分割手順と、
前記分割手順により分割された複数の領域と、前記１以上のノードに含まれる始点ノード及び終点ノードをそれぞれ含む領域とから、隣り合う２つの領域を選択して、選択した２つの領域にそれぞれ含まれるノード間のルートを示す部分ルートを算出する部分ルート算出手順と、
前記部分ルート算出手順が算出した前記部分ルートに基づいて、前記２つの領域毎に、予め定義された複数の目的関数の値の組を示す目的関数値を算出する目的関数値算出手順と、
前記始点ノードから前記終点ノードまでの１以上のルートを、前記部分ルート算出手順が算出した前記部分ルートを継ぎ合わせることで算出するルート算出手順と、
前記目的関数値算出手順が算出した前記目的関数値と、予め定義された前記目的関数の序列とに基づき、前記ルート算出手順が算出した前記ルートを出力する出力手順と、
をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ルート算出装置、ルート算出方法、及びプログラムに関する。
【背景技術】
【０００２】
ネットワークに対して追加されるリンクについて、災害による影響が相対的に小さくなるような物理経路の選択を支援することができる経路探索手法が知られている（非特許文献１）。非特許文献１では、経路探索の対象となる始点と終点との間に適当な間隔で碁盤の目（格子）を設定し、各格子の頂点（格子点）付近の設備（ノード）を選択する。そして、選択したノード間について経路長が最小となる経路（リンクの組み合わせ）を探索する部分問題を設定し、これらの部分問題から得られた格子間の経路（部分経路）を複数組み合わせることで、全体の経路を探索している。
【０００３】
また、全体の経路を探索するとき、複数の多目的関数を用いて経路を評価する方法が知られている（非特許文献２）。非特許文献２では、複数の多目的関数を利用するときは、地理的条件や設備補強の可否等に基づいて、多目的関数の順位付けを行うことで、経路を評価している。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Tran, Phuong Nga, and Hiroshi Saito. "Enhancing Physical Network Robustness Against Earthquake Disasters With Additional Links." Journal of Lightwave Technology 34.22 (2016): 5226-5238.APA
【非特許文献２】鍔木拓磨， 石塚美加， 松川達哉， 井上洋思， 丸山雅人， 廣瀬貴史． B-7-4 設備補強の効果を考慮したビル間通信路の地震影響評価手法の検討． 電子情報通信学会 ソサイエティ大会講演論文集， 2016
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ここで、大規模な地震発生時には、地震動による損傷だけでなく、例えば、津波や土砂災害等の二次災害によってもネットワーク設備に甚大な被害が発生する場合がある。
【０００６】
しかしながら、非特許文献１に開示された経路探索手法は、地震動による損傷のみを考慮した単一の目的関数に基づいた経路探索手法であり、二次災害による影響が考慮されていない。このため、災害による影響の最小化を図るという観点で最適な経路が探索されない場合があった。
【０００７】
一方、非特許文献２では、リンクの被災率や二次災害発生エリアを通過するリンク数やリンク長を用いて複数の目的関数と目的関数の序列とにより経路を評価する手法が開示されている。しかしながら、評価を行うための経路の候補は始点ノードと終点ノードとを繋ぐノード・リンクの組み合わせを全探索で取得することを前提としており、ノードやリンクの数が増加すると計算時間が指数関数的に増大する。このため、多くのノードやリンクから構成されるネットワークに対しては、実用的な時間で、目的関数値が最良となる経路を探索することができない場合があった。
【０００８】
そこで、多くのノードやリンクから構成されるネットワークに対して、二次災害による影響も考慮した複数の目的関数に基づく探索を行い、かつ、実用的な時間でこれら目的関数の値が最良となる経路（すなわち、最適な経路）を探索する経路探索手法が求められている。
【０００９】
本発明は、上記の点に鑑みてなされたものであって、二次災害による影響も考慮した最適な経路を実用的な時間で算出することを目的とする。
【課題を解決するための手段】
【００１０】
上記課題を解決するため、１以上のノードとリンクとで構成されるネットワークの所定の範囲内の領域を、複数の領域に分割する分割部と、前記分割部により分割された複数の領域と、前記１以上のノードに含まれる始点ノード及び終点ノードをそれぞれ含む領域とから、隣り合う２つの領域を選択して、選択した２つの領域にそれぞれ含まれるノード間のルートを示す部分ルートを算出する部分ルート算出部と、前記部分ルート算出部が算出した前記部分ルートに基づいて、前記２つの領域毎に、予め定義された複数の目的関数の値の組を示す目的関数値を算出する目的関数値算出部と、前記始点ノードから前記終点ノードまでの１以上のルートを、前記部分ルート算出部が算出した前記部分ルートを継ぎ合わせることで算出するルート算出部と、前記目的関数値算出部が算出した前記目的関数値と、予め定義された前記目的関数の序列とに基づき、前記ルート算出部が算出した前記ルートを出力する出力部と、を有する。
【発明の効果】
【００１１】
二次災害による影響も考慮した最適な経路を実用的な時間で算出する。
【図面の簡単な説明】
【００１２】
【図１】本発明の実施の形態におけるルート算出装置の構成の一例を示す図である。
【図２】本発明の実施の形態におけるルート算出装置のハードウェア構成の一例を示す図である。
【図３】本発明の実施の形態におけるルート算出処理部の機能構成の一例を示す図である。
【図４】本発明の実施の形態におけるルート算出処理部が実行する処理の一例を示すフローチャートである。
【図５】ネットワークの一例を示す図である。
【図６】探索領域が定義されたネットワークの一例を示す図である。
【図７】探索領域がメッシュに分割されたネットワークの一例を示す図である。
【図８】ジャンプ幅に応じて構築される部分メッシュ組と構築されない部分メッシュ組との一例を示す図である。
【図９】ジャンプ幅の上限値の算出の一例を示す図である。
【図１０】部分メッシュ組の多目的関数値の算出の一例を示す図である。
【図１１】部分メッシュ組の多目的関数値の一例を示す図である。
【図１２】メッシュ組の多目的関数値の一例を示す図である。
【図１３】メッシュ組の類似度と多目的関数値とからメッシュ組が削除される場合の一例を示す図である。
【図１４】ルート算出の一例を示す図である。
【図１５】多目的関数値によるルート算出の打ち切りの一例を示す図である。
【図１６】出力されるルートの一例を示す図である。
【図１７】ルートの比較例を示す図である。
【発明を実施するための形態】
【００１３】
以下、本発明の実施の形態について、図面を参照しながら説明する。
【００１４】
＜ルート算出装置１０の構成＞
まず、本発明の実施の形態におけるルート算出装置１０の構成について、図１を参照しながら説明する。図１は、本発明の実施の形態におけるルート算出装置１０の構成の一例を示す図である。
【００１５】
図１に示すルート算出装置１０は、二次災害による影響も考慮した最適な経路（以降、経路を「ルート」とも表す。）を探索するコンピュータである。ルート算出装置１０は、ルート算出処理部１００を有する。ルート算出装置１０は、ルート算出処理部１００により、二次災害による影響も考慮した複数の目的関数（多目的関数）と、目的関数の序列とに基づき、多目的関数値が最良となるルート（すなわち、最適なルート）を探索して、探索したルートを出力する。このとき、ルート算出処理部１００は、始点ノードと終点ノードとの間を複数の領域（メッシュ）に分割した上で、これらのメッシュのうち、所定のメッシュに含まれるノードに対して経路探索を行う。これにより、ルート算出処理部１００は、実用的な時間で上記の最適なルートを探索することができる。
【００１６】
なお、図１に示すルート算出装置１０の構成は、一例であって、他の構成であっても良い。例えば、図１に示すルート算出装置１０は、複数台のコンピュータで構成されていても良い。
【００１７】
＜ルート算出装置１０のハードウェア構成＞
次に、ルート算出装置１０のハードウェア構成について、図２を参照しながら説明する。図２は、本発明の実施の形態におけるルート算出装置１０のハードウェア構成の一例を示す図である。
【００１８】
図２に示すように、ルート算出装置１０は、入力装置２０１と、表示装置２０２と、外部Ｉ／Ｆ２０３と、通信Ｉ／Ｆ２０４と、ＲＡＭ（Random Access Memory）２０５と、ＲＯＭ（Read Only Memory）２０６と、ＣＰＵ（Central Processing Unit）２０７と、補助記憶装置２０８とを有する。これら各ハードウェアは、それぞれがバスＢを介して通信可能に接続されている。
【００１９】
入力装置２０１は、例えばキーボードやマウス、タッチパネル等であり、ユーザが各種操作を入力するのに用いられる。表示装置２０２は、例えばディスプレイ等であり、ルート算出装置１０の処理結果を表示する。なお、入力装置２０１及び表示装置２０２の少なくとも一方は、必要なときにルート算出装置１０に接続して利用する形態であっても良い。
【００２０】
外部Ｉ／Ｆ２０３は、外部装置とのインタフェースである。外部装置には、記録媒体２０３ａ等がある。ルート算出装置１０は、外部Ｉ／Ｆ２０３を介して記録媒体２０３ａ等の読み取りや書き込みを行うことができる。
【００２１】
記録媒体２０３ａには、例えば、フレキシブルディスク、ＣＤ（Compact Disc）、ＤＶＤ（Digital Versatile Disk）、ＳＤメモリカード（Secure Digital memory card）、ＵＳＢ（Universal Serial Bus）メモリカード等がある。
【００２２】
通信Ｉ／Ｆ２０４は、ルート算出装置１０をネットワークに接続するためのインタフェースである。
【００２３】
ＲＡＭ２０５は、プログラムやデータを一時保持する揮発性の半導体メモリである。ＲＯＭ２０６は、電源を切ってもプログラムやデータを保持することができる不揮発性の半導体メモリである。ＲＯＭ２０６には、例えば、ＯＳ（Operating System）設定やネットワーク設定等が格納されている。
【００２４】
ＣＰＵ２０７は、ＲＯＭ２０６や補助記憶装置２０８等からプログラムやデータをＲＡＭ２０５上に読み出して処理を実行する演算装置である。
【００２５】
補助記憶装置２０８は、例えばＨＤＤ（Hard Disk Drive）やＳＳＤ（Solid State Drive）等であり、プログラムやデータを格納している不揮発性の記憶装置である。補助記憶装置２０８に格納されているプログラムやデータには、例えば、ＯＳ、当該ＯＳ上において各種機能を実現するアプリケーションソフトウェア、ルート算出処理部１００を実現するプログラム等がある。
【００２６】
本実施形態に係るルート算出装置１０は、図２に示すハードウェア構成を有することにより、後述する各種処理を実現することができる。
【００２７】
＜ルート算出処理部１００の機能構成＞
次に、ルート算出処理部１００の機能構成について、図３を参照しながら説明する。図３は、本発明の実施の形態におけるルート算出処理部１００の機能構成の一例を示す図である。
【００２８】
図３に示すように、ルート算出処理部１００は、入力部１０１と、探索領域定義部１０２と、メッシュ構築部１０３と、部分メッシュ組構築部１０４と、メッシュ組構築部１０５と、メッシュ組絞込部１０６と、ルート算出部１０７と、出力部１０８とを有する。これら各機能部は、ルート算出装置１０にインストールされた１以上のプログラム（ルート算出処理部１００を実現する１以上のプログラム）が、ＣＰＵ２０７に実行させる処理により実現される。
【００２９】
入力部１０１は、各種情報を入力する。入力部１０１が入力する情報には、例えば、始終点ノード情報と、ネットワーク情報と、多目的関数情報と、序列情報と、探索領域情報と、閾値情報とが挙げられる。
【００３０】
始終点ノード情報は、ネットワークの経路探索における始点及び終点となるノードを示す情報である。ネットワーク情報は、ネットワークを構成するノード及びリンクに関する情報である。ノードには、例えば、ルータ、ビル、マンホール、電柱等が挙げられる。リンクには、ケーブル、とう道、共同溝、管路等が挙げられる。
【００３１】
ネットワーク情報には、属性情報を付与することができる。属性情報には、例えば、位置情報（緯度及び経度情報）、リンクの長さ（ケーブルの長さ、とう道の長さ、共同溝の長さ、管路の長さ等）、リンクの被災率、二次災害（津波、土砂災害、洪水、液状化、雪崩、落雷、火山噴火）の有無等が挙げられる。
【００３２】
多目的関数情報は、多目的関数に関する情報である。多目的関数には、例えば、ネットワーク設備のコスト（設備自体のコスト、設置コスト、保守コスト等）、リンクの被災率、二次災害エリアに含まれるリンク数やリンク長等が挙げられる。多目的関数情報には、１以上の任意の数の目的関数が含まれる。
【００３３】
序列情報は、１以上の多目的関数の優先度に関する情報である。以降では、多目的関数情報に含まれる１以上の多目的関数のうち、優先度が高い順に、第１の多目的関数、第２の多目的関数、第３の多目的関数等とする。
【００３４】
閾値情報は、経路探索の打ち切りに関する情報である。例えば、ネットワーク設備の設備コストの上限金額、ケーブルの長さの上限値等が挙げられる。上限値は、任意の多目的関数に対して設定することができる。また、閾値情報には、部分メッシュ組構築及びルートを探索するためのダイクストラ法の実行回数の上限値、メッシュ組数の上限値が含まれる。
【００３５】
なお、探索領域及び閾値情報のうちの少なくとも一方は、他の情報（始終点ノード情報、ネットワーク情報、多目的関数情報、及び序列情報）から算出されても良い。
【００３６】
探索領域定義部１０２は、探索領域情報から、ネットワーク情報が示すネットワークに探索領域を定義する。
【００３７】
メッシュ構築部１０３は、探索領域定義部１０２が定義した探索領域を複数の領域（メッシュ）に分割することで、メッシュを構築する。
【００３８】
部分メッシュ組構築部１０４は、メッシュ構築部１０３が構築したメッシュから部分メッシュ組を構築して、当該部分メッシュ組毎の多目的関数値を算出する。部分メッシュ組を構築する際は、災害のサイズに合わせてジャンプ幅が大きい部分メッシュ組を削除する。ジャンプ幅とは、縦方向（ｙ軸方向）のメッシュの移動量のことである。
【００３９】
部分メッシュ組とは、メッシュ構築部１０３が構築したメッシュのうちの隣り合うメッシュの組のことである。部分メッシュ組毎の多目的関数値は、部分メッシュ組毎に、ダイクストラ法により、２つのノード間を結ぶ部分ルートを探索することで算出される。以降では、部分メッシュ組毎に算出された多目的関数値を「部分メッシュ組多目的関数値」とも表す。
【００４０】
メッシュ組構築部１０５は、部分メッシュ組を組み合わせてメッシュ組を構築して、当該メッシュ組毎の多目的関数値を算出する。メッシュ組は、始点ノードを含むメッシュから、終点ノードをメッシュまでのメッシュを組み合わせた組のことである。メッシュ組毎の多目的関数値は、部分メッシュ組の多目的関数値から所定の統計値を計算することで算出される。以降では、メッシュ組毎に算出された多目的関数値を「メッシュ組多目的関数値」とも表す。
【００４１】
メッシュ組絞込部１０６は、メッシュ組構築部１０５が構築したメッシュ組を、多目的関数値で絞り込む。例えば、メッシュ組絞込部１０６は、メッシュ組構築部１０５が構築したメッシュ組をメッシュ組多目的関数値でソートした上で、上位の所定件数のメッシュ組を抽出する。また、メッシュ組絞込部１０６は、メッシュ組の類似度を閾値として、閾値以上となるメッシュ組で、かつ、多目的関数値が改悪となるメッシュ組を削除する。メッシュ組の類似度とは、任意の２つのメッシュ組に対して、共通のメッシュを含んでいる度合いのことである。
【００４２】
ルート算出部１０７は、メッシュ組絞込部１０６が絞り込んだメッシュ組において部分ルートの探索又は部分ルートの取得を行って、始点ノードから終点ノードまでのルートと、当該ルートの多目的関数値とを算出する。また、ルート算出部１０７は、時間計算量削減のため、例えば、多目的関数値やダイクストラ法の実行回数等に応じて、ルートの算出を途中で終了する。以降では、ルート毎に算出された多目的関数値を「ルート多目的関数値」とも表す。
【００４３】
出力部１０８は、ルート算出部１０７が算出したルートを出力する。このとき、出力部１０８は、ルート多目的関数値により、ルートをソートした上で、ルートを出力する。これにより、出力部１０８は、ルート多目的関数値が最良となるルート（すなわち、最適なルート）を出力することができる。
【００４４】
ルート多目的関数値が最良となるルートとは、例えば、第１の多目的関数が津波エリアに含まれる設備数、第２の多目的関数がリンクの被災率である場合、第１の目的関数値が最小となるルートであって、かつ、当該ルートが複数ある場合はこれらのルートのうち、第２の多目的関数値が最小となるルートのことである。
【００４５】
＜ルート算出処理部１００が実行する処理＞
次に、ルート算出処理部１００が実行する処理について、図４を参照しながら説明する。図４は、本発明の実施の形態におけるルート算出処理部１００が実行する処理の一例を示すフローチャートである。
【００４６】
まず、入力部１０１は、始終点ノード情報と、ネットワーク情報と、多目的関数情報と、序列情報と、探索領域情報と、閾値情報とを入力する（ステップＳ１）。
【００４７】
以降では、一例として、入力部１０１が入力した多目的関数情報及び序列情報は、以下の第１の多目的関数〜第３の多目的関数であるものとする。
【００４８】
・第１の多目的関数：津波エリアに含まれるリンク数ｌ（個）
・第２の多目的関数：リンクの被災率ｐ
・第３の多目的関数：２つのノードを結ぶリンクの長さｄ（ｋｍ）
また、閾値情報は、以下の上限値であるものとする。
【００４９】
・部分メッシュ組の構築における部分メッシュ組毎のダイクストラ法の実行回数の上限値Ｔ１
・部分メッシュ組の構築における部分メッシュ組のジャンプ幅の上限値Ｔ１´（ただし、ジャンプ幅の上限値Ｔ１´は、後述する方法により算出されても良い。）
・メッシュ組の絞込みにおけるメッシュ組数の上限値Ｔ２
・メッシュ組の絞込みにおけるメッシュ組の類似度の閾値Ｔ２´
・ダイクストラ法におけるリンクの長さの上限値Ｔ３
・ルート探索におけるメッシュ組毎のダイクストラ法の実行回数の上限値Ｔ４
ここで、入力部１０１が入力したネットワーク情報及び始終点ノード情報に基づくネットワークＮを図５に示す。図５に示すネットワークＮは、ノードと、リンクとで構成される。また、ネットワークＮには、災害エリアが含まれる。更に、ネットワークＮに含まれるノードのうち、始終点ノード情報で示されるノードが始点ノード及び終点ノードとなる。
【００５０】
例えば、ネットワークＮが電気通信ネットワークである場合、始点ノード及び終点ノードは収容局ビル等、ノードはマンホール等、リンクは管路等である。なお、ネットワーク情報に基づくネットワークは、電気通信ネットワークに限られない。例えば、道路網、鉄道網、電力網、水道網、ガス網等、種々のネットワークであっても良い。
【００５１】
次に、探索領域定義部１０２は、探索領域情報から、ネットワーク情報が示すネットワークＮに探索領域を定義する（ステップＳ２）。
【００５２】
ここで、探索領域が定義されたネットワークＮを図６に示す。図６に示す例では、始点ノードを原点とするｘｙ座標を定義した上で、ｘ軸の正の方向に１０ｋｍ、ｙ方向に正及び負の方向にそれぞれ３ｋｍの範囲内の長方形の領域を探索領域と定義した場合を示している。なお、探索領域は、長方形の領域に限られず、凸領域であれば任意の領域を探索領域とすることができる。
【００５３】
次に、メッシュ構築部１０３は、探索領域定義部１０２が定義した探索領域を複数の領域（メッシュ）に分割することで、メッシュを構築する（ステップＳ３）。
【００５４】
ここで、探索領域がメッシュに分割されたネットワークＮを図７に示す。図７に示す例では、探索領域を４つのメッシュに等分で分割した場合を示している。メッシュには、各メッシュを識別するためのメッシュＩＤが割り当てられる。また、始点ノード及び終点ノードは、探索領域に含まれないため、始点ノードのみを含むメッシュと、終点ノードのみを含むメッシュとを作成して、それぞれにメッシュＩＤを割り当てる。
【００５５】
メッシュＩＤは、例えば、［ｉ，ｊ，ｋ］で表される。ｉは、符号ビットであり、メッシュがｙ軸方向の正の範囲内にあるときに０、負の範囲内にあるときに１とする。ｊは、ｘ軸方向にあるメッシュの数である。ｋは、ｙ軸方向にあるメッシュの数である。
【００５６】
具体的には、探索領域が４つのメッシュに分割された場合、図７に示すように、左上のメッシュにはメッシュＩＤ［０，０，０］が割り当てられる。同様に、右上のメッシュにはメッシュＩＤ［０，１，０］、左下のメッシュにはメッシュＩＤ［１，０，０］、右下のメッシュにはメッシュＩＤ［１，１，０］が割りてられる。また、始点ノードのみを含むメッシュにはメッシュＩＤ［０，−１，０］、終点ノードのみをメッシュにはメッシュＩＤ［０，２，０］が割り当てられる。
【００５７】
なお、ネットワークＮに含まれるｘ軸上のノード及びリンク（ｘ軸上にある、始点ノードから終点ノードへのリンク）は、メッシュＩＤ［０，０，０］のメッシュと、メッシュＩＤ［０，１，０］のメッシュとに含まれるとすれば良い。ただし、メッシュＩＤ［１，０，０］のメッシュと、メッシュＩＤ［１，１，０］のメッシュとに含まれていても良い。すなわち、ｘ軸上にあるノード及びリンクは、ｘ軸の正の範囲内にあるメッシュ又は負の範囲内にあるメッシュのいずれか一方に含まれるようにすれば良い。
【００５８】
以降では、簡単のため、メッシュＩＤ［ｉ，ｊ，ｋ］のメッシュを、単に、メッシュ［ｉ，ｊ，ｋ］とも表す。
【００５９】
部分メッシュ組構築部１０４は、メッシュ構築部１０３が構築したメッシュから部分メッシュ組を構築して、部分ルート多目的関数値を算出する（ステップＳ４）。
【００６０】
すなわち、部分メッシュ組構築部１０４は、メッシュ構築部１０３が構築したメッシュのうちの隣り合うメッシュを１つの組としてメッシュ組を作成する。あるメッシュＩＤ［ｉ，ｊ，ｋ］のメッシュに対して隣り合うメッシュとは、メッシュＩＤ［ｉ，ｊ＋１，ｋ］（ｉ，ｋは整数）で表されるメッシュのことである。言い換えれば、あるメッシュに対して隣り合うメッシュとは、ｘ軸の正の方向にある隣列のメッシュのことである。
【００６１】
また、部分メッシュ組構築部１０４は、部分メッシュ組を構築する際に、部分メッシュ組のジャンプ幅（以降、単に「ジャンプ幅」とも表す。）を超える部分メッシュ組を削除する。ジャンプ幅は、ルート算出が行われるネットワークＮが含まれる地域の災害サイズに合わせて設定することで、算出すべきルートを含む部分メッシュ組のみを構築することができる。算出すべきルートとは、以下の（１）〜（３）の３つのルートである。
【００６２】
（１）とう道を経由したルート（とう道は災害に強いため（耐災性が高いルート））
（２）被災影響が大きい災害を迂回したルート
（３）山や川等で一定の部分メッシュ組のジャンプ幅を設定しないと迂回できないルート
本発明の実施の形態では、災害に強いルート又は災害を回避したルートを算出するために上記の（１）及び（２）を利用する。また、ジャンプ幅によるルートなしを回避するため（すなわち、ジャンプ幅の上限値Ｔ１´が小さいために、山や川等を迂回するルートが含まれる部分メッシュ組が構築されないことを回避するため）に上記の（３）を利用する。
【００６３】
２つの隣り合うメッシュ［ｉ，ｊ，ｋ］及び［ｍ，ｊ＋１，ｎ］があるとき、ジャンプ幅Ｊｍは、Ｊｍ＝｜ｉ−ｍ｜＋｜（−１）ｉ×ｋ−（−１）ｍ×ｎ｜により算出される。ここで、ジャンプ幅の上限値Ｔ１´＝２である場合において、部分メッシュ組を構築できる場合と、部分メッシュ組を構築できない場合とを図８に示す。
【００６４】
図８に示すように、メッシュ［０，０，１］と、メッシュ［０，１，０］とは、部分メッシュ組を構築することができる。これは、メッシュ［０，０，１］と、メッシュ［０，１，０］とのジャンプ幅Ｊｍは、Ｊｍ＝｜０−０｜＋｜１−０｜＝１＜ジャンプ幅の上限値Ｔ１´であるためである。一方で、図８に示すように、メッシュ［０，０，１］と、メッシュ［１，１，０］とは、部分メッシュ組を構築することができない。これは、メッシュ［０，０，１］と、メッシュ［１，１，０］とのジャンプ幅Ｊｍは、Ｊｍ＝｜０−１｜＋｜１−０｜＝２≧ジャンプ幅の上限値Ｔ１´であるためである。したがって、部分メッシュ組構築部１０４は、ジャンプ幅Ｊｍが上限値Ｔ１´を超える部分メッシュ組を削除する（又はジャンプ幅Ｊｍが上限値Ｔ１´を超える部分メッシュ組を構築しない。）。
【００６５】
ここで、ジャンプ幅の上限値Ｔ１´は、次のようにして算出されても良い。ジャンプ幅の上限値Ｔ１´の算出の一例を図９に示す。図９に示す例では、上記の（１）〜（３）の３つのルートのうち、（２）を対象として示している。ジャンプ幅の上限値Ｔ１´の算出は、以下のステップ（ａ−１）及び（ａ−２）で計算される。
【００６６】
（ａ−１）メッシュ毎に災害（図９に示す例では液状化）の有無を判定する。判定結果は、ハザード値ｈ［ｉ，ｊ，ｋ］として、ｈ［ｉ，ｊ，ｋ］＝０のとき災害なし、ｈ［ｉ，ｊ，ｋ］＝１のとき災害ありとする。図９では、各メッシュのハザード値（０又は１）がメッシュ内に示されている。
【００６７】
（ａ−２）ｈ［ｉ，ｊ，ｋ＝０かつｈ［ｉ，ｊ，ｋ］＝１となる条件下で、Ｊｍ＝｜ｉ−ｍ｜＋｜（−１）ｉ×ｋ−（−１）ｍ×ｎ｜を最大にするＪｍをＴ１´として設定する。図９に示す例では、Ｔ１´＝２が設定される。
【００６８】
これにより、被災影響が大きい災害を迂回するのに必要十分な距離の算出ルートを含む部分メッシュ組を構築することができる。
【００６９】
そして、部分メッシュ組構築部１０４は、部分メッシュ組毎に、部分メッシュ組多目的関数値を算出する。部分メッシュ組多目的関数値は、以下のＳｔｅｐ１−１〜ステップＳｔｅｐ１−４により算出される。
【００７０】
Ｓｔｅｐ１−１）部分メッシュ組に含まれるそれぞれのメッシュから１つずつノードを抽出する。
【００７１】
Ｓｔｅｐ１−２）ダイクストラ法により、抽出されたノード間を結ぶ部分ルートの探索と、当該部分ルートの多目的関数値の算出とを行う。なお、ダイクストラ法による部分ルートの探索と、当該部分ルートの多目的関数値の算出とは、ルート算出部１０７により行われる。以降では、部分ルート毎に算出された多目的関数値を「部分ルート多目的関数値」とも表す。
【００７２】
Ｓｔｅｐ１−３）上記のＳｔｅｐ１−２で探索されたた部分ルートと、算出された部分ルート多目的関数値とを、メモリ（例えばＲＡＭ２０５や補助記憶装置２０８等）に記憶させる。
【００７３】
Ｓｔｅｐ１−４）上記のＳｔｅｐ１−１〜Ｓｔｅｐ１−３の実行回数（すなわち、ダイクストラ法の実行回数）が上限値Ｔ１に達した場合、部分ルート多目的関数値から部分メッシュ組多目的関数値を算出する。部分メッシュ組多目的関数値は、部分ルート多目的関数値の平均値、中央値、最大値、最小値等の統計値とすれば良い。
【００７４】
上記のＳｔｅｐ１−１〜Ｓｔｅｐ１−４を部分メッシュ組毎に行うことで、部分メッシュ組毎に、部分メッシュ組多目的関数値が算出される。
【００７５】
ここで、一例として、Ｔ１＝２である場合における部分メッシュ組［０，０，０］−［０，１，０］の多目的関数値の算出について、図１０を参照しながら説明する。図１０は、部分メッシュ組の多目的関数値の算出の一例を示す図である。なお、部分メッシュ組［０，０，０］−［０，１，０］は、メッシュ［０，０，０］と、メッシュ［０，１，０］との組を表す。
【００７６】
まず、メッシュ［０，０，０］からノードＮ１と、メッシュ［０，１，０］からノードＮ２とを抽出する。ノードは、例えば、ランダムに抽出しても良いし、ノードに接続されるリンク数が多い順に抽出しても良い。次に、ノードＮ１とノードＮ２とに対してダイクストラ法を行って、ノードＮ１からノードＮ２までの部分ルートＲ１と、当該部分ルートＲ１の多目的関数値とを算出する。
【００７７】
同様に、メッシュ［０，０，０］からノードＮ３と、メッシュ［０，１，０］からノードＮ４とを抽出する。次に、ノードＮ３とノードＮ４とに対してダイクストラ法を行って、ノードＮ３からノードＮ４までの部分ルートＲ２と、当該部分ルートＲ２の多目的関数値とを算出する。
【００７８】
そして、部分ルートＲ１の多目的関数値と、部分ルートＲ２の多目的関数値との統計値を計算することで、部分メッシュ組多目的関数値を算出する。これにより、部分メッシュ組［０，０，０］−［０，１，０］の多目的関数値が算出される。
【００７９】
以上により、図１１に示すように、部分メッシュ組毎に、部分メッシュ組多目的関数値が算出される。図１１に示す例では、部分メッシュ組［０，−１，０］−［０，０，０］の多目的関数値（ｌ１，ｐ１，ｄ１）が算出されている。同様に、部分メッシュ組［０，１，０］−［１，０，０］の多目的関数値（ｌ２，ｐ２，ｄ２）が算出されている。他の部分メッシュ組についても同様である。
【００８０】
次に、メッシュ組構築部１０５は、部分メッシュ組を組み合わせてメッシュ組を構築して、当該メッシュ組毎の多目的関数値を算出する（ステップＳ５）。すなわち、メッシュ組構築部１０５は、始点ノードを含むメッシュ［０，−１，０］から、終点ノードをメッシュ［０，２，０］までのメッシュを組み合わせることで、メッシュ組を構築する、また、メッシュ組構築部１０５は、メッシュ組に含まれる部分メッシュ組の多目的関数値からメッシュ組多目的関数値を算出する。メッシュ組多目的関数値は、部分メッシュ組多目的関数値から以下の（式１）又は（式２）を用いて算出する。
【００８１】
すなわち、目的関数がリンク数及びリンク長の場合は、以下の（式１）を用いて算出する。
【００８２】
【数１】
2018137718.tif 000003
ここで、Ｌはメッシュ組のリンク数及びリンク長、Ｎはメッシュ組を構成する部分メッシュ組数、ｌｉは部分メッシュ組ｉのリンク数及びリンク長である。
【００８３】
また、目的関数がリンクの被災率である場合は、以下の（式２）を用いて算出する。
【００８４】
【数２】
2018137718.tif 000004
ここで、Ｐはメッシュ組の被災率、ｐｉは部分メッシュ組ｉの被災率である。
【００８５】
例えば、部分メッシュ組［０，−１，０］−［０，０，０］と、部分メッシュ組［０，０，０］−［０，１，０］と、部分メッシュ組［０，１，０］−［０，２，０］とを組み合わせることで、メッシュ組［０，−１，０］−［０，１，０］−［０，２，０］が作成される。
【００８６】
また、このとき、メッシュ組多目的関数値は、部分メッシュ組［０，−１，０］−［０，０，０］の多目的関数値（ｌ１，ｐ１，ｄ１）と、部分メッシュ組［０，０，０］−［０，１，０］の多目的関数値（ｌ３，ｐ３，ｄ３）と、部分メッシュ組［０，１，０］−［０，２，０］の多目的関数値（ｌ７，ｐ７，ｄ７）とから算出される。具体的には、ｌ１とｌ３とｌ７とを上記の（式１）で算出した値が、メッシュ組多目的関数値における第１の多目的関数値となる。同様に、ｐ１とｐ３とｐ７とを上記の（式２）で算出した値が、メッシュ組多目的関数値における第２の多目的関数値となる。同様に、ｄ１とｄ３とｄ７とを上記の（式１）で算出した値が、メッシュ組多目的関数値における第３の多目的関数値となる。
【００８７】
このように、メッシュ組構築部１０５は、始点ノードが含まれるメッシュから、終点ノードが含まれるメッシュまでの部分メッシュ組の組み合わせを作成することで、メッシュ組を構築する。また、メッシュ組多目的関数値は、メッシュ組に含まれる部分メッシュ毎の多目的関数値について、上記の（式１）又は（式２）を計算することで、算出される。
【００８８】
以上により、図１２に示すように、メッシュ組毎に、メッシュ組多目的関数値が算出される。図１２に示す例では、メッシュ組［０，−１，０］−［０，０，０］−［０，１，０］−［０，２，０］の多目的関数値（Ｌ１，Ｐ１，Ｄ１）が算出されている。同様に、メッシュ組［０，−１，０］−［０，０，０］−［１，１，０］−［０，２，０］の多目的関数値（Ｌ２，Ｐ２，Ｄ２）が算出されている。他のメッシュ組についても同様である。
【００８９】
次に、メッシュ組絞込部１０６は、メッシュ組構築部１０５が構築したメッシュ組を、多目的関数値及びメッシュ組の類似度で絞り込む（ステップＳ６）。
【００９０】
例えば、メッシュ組絞込部１０６は、メッシュ組構築部１０５が構築したメッシュ組をメッシュ組多目的関数値でソートした上で、上位Ｔ２件を抽出することで、多目的関数値によりメッシュ組を絞り込む。メッシュ組多目的関数値によるソートの方法としては、例えば、第１の目的関数値の昇順で並び替えれば良い。このとき、第１の目的関数値が同じである場合は、第２の目的関数値の昇順で並び替えれば良い。以降も同様に、一般に、ｎを１以上の整数として、第ｎの目的関数値が同じである場合は、第ｎ＋１の目的関数値の昇順で並び替えれば良い。
【００９１】
なお、メッシュ組多目的関数値によるソートの方法は、上記に限られない。例えば、多目的関数値の降順で並び替えても良い。
【００９２】
以降では、Ｔ２＝２であるものとして、メッシュ組［０，−１，０］−［０，０，０］−［０，１，０］−［０，２，０］と、メッシュ組［０，−１，０］−［１，０，０］−［１，１，０］−［０，２，０］とが、この順で抽出されたものとして説明する。
【００９３】
なお、各メッシュ組は、いずれもメッシュ［０，−１，０］及び［０，２，０］が含まれるため、以降では、これらのメッシュを除いて、簡略化してメッシュ組を表現する。例えば、メッシュ組［０，−１，０］−［０，０，０］−［０，１，０］−［０，２，０］は、メッシュ組［０，０，０］−［０，１，０］と表現する。
【００９４】
そして、メッシュ組絞込部１０６は、上位Ｔ２件に絞り込んだメッシュ組に対して、メッシュ組の類似度が閾値Ｔ２´以上となるメッシュ組で、かつ、多目的関数値が改悪となるメッシュ組を削除することで、更にメッシュ組を絞り込む。
【００９５】
メッシュ組の類似度は、メッシュ組を構築するメッシュ数（始点ノード及び終点ノードを含むメッシュは除く）に対して、任意の２つのメッシュ組に共通のメッシュ組数から算出される。メッシュ組を構築するメッシュ数をＭ、任意の２つのメッシュ組に共通なメッシュ組数をＮとしたとき、メッシュ組の類似度はＮ／Ｍで算出される。
【００９６】
メッシュ組の類似度が閾値Ｔ２´以上となるメッシュ組で、かつ、多目的関数値が改悪となるメッシュ組を削除する場合を図１３に示す。図１３に示す例では、１つ目のメッシュ組が［０，−１，０］−［０，０，１］−［０，１，１］−［０，２，０］であり、その多目的関数値は（０，０．２７，１１）である。また、２つ目のメッシュ組が［０，−１，０］−［０，０，１］−［０，１，０］−［０，２，０］であり、その多目的関数値は（１，０．８２，１４）である。
【００９７】
この場合、Ｍ＝４、Ｎ＝３であるため、これらのメッシュ組の類似度は、３／４である。また、１つ目のメッシュ組の多目的関数値（０，０．２７，１１）の方が２つ目のメッシュ組の多目的関数値（１，０．８２，１４）よりも良い。したがって、メッシュ組の類似度の閾値Ｔ２´が３／４未満である場合、２つ目のメッシュ組が削除される。
【００９８】
次に、ルート算出部１０７は、メッシュ組絞込部１０６が絞り込んだメッシュ組においてルート探索を行って、ルート毎の多目的関数値を算出する（ステップＳ７）。このとき、ルート算出部１０７は、時間計算量削減のため、例えば、多目的関数値やダイクストラ法の実行回数等に応じて、ダイクストラ法によるルート探索を途中で終了する。
【００９９】
ここで、一例として、メッシュ組［０，０，０］−［０，１，０］におけるルート探索について、図１４を参照しながら説明する。図１４は、ルート探索の一例を示す図である。
【０１００】
まず、始点ノードと、メッシュ［０，０，０］のノードＮａ（ノードＮａは、メッシュ［０，０，０］内の任意のノード）とに対して、既に探索されたルート（すなわち、上記のＳｔｅｐ１−２で探索された部分ルート）がメモリに記憶されているか否かを判定する。メモリにルートが記憶されていれば、当該ルートを利用すれば良い。以降では、メモリに当該部分ルートが記憶されていなかったものとして説明を続ける。
【０１０１】
次に、ダイクストラ法により、始点ノードとノードＮａとを結ぶ部分ルートの探索と、当該部分ノードの多目的関数値の算出とを行う。探索された部分ルートＲａと、算出された部分ルートＲａの多目的関数値とは、メモリに記憶される。
【０１０２】
次に、ノードＮａと、メッシュ［０，１，０］のノードＮｂ（ノードＮｂは、メッシュ［０，１，０］内の任意のノード）とに対して、既に探索された部分ルートがメモリに記憶されているか否かを判定する。以降では、メモリに当該部分ルートＲｂが記憶されているものとして説明を続ける。この場合、メモリから当該部分ルートＲｂと、当該部分ルートＲｂの多目的関数値とが取得される。
【０１０３】
次に、ノードＮｂと、終点ノードとに対して、既に探索された部分ルートがメモリに記憶されているか否かを判定する。以降では、メモリに当該部分ルートＲｃが記憶されているものとして説明を続ける。この場合、メモリから当該部分ルートＲｃと、当該部分ルートＲｃの多目的関数値とが取得される。
【０１０４】
最後に、上記で探索又はメモリから取得された部分ルートＲａと、部分ルートＲｂと、部分ルートＲｃとを繋げることで、始点ノードから終点ノードまでのルートＳ１を算出する。また、上記で算出又はメモリから取得された部分ルートＲａの多目的関数値と、部分ルートＲｂの多目的関数値と、部分ルートＲｃの多目的関数値とから、ルートＳ１の多目的関数値を算出する。ルート多目的関数値は、メッシュ組多目的関数値の算出と同様に、部分ルート多目的関数値を用いて上記の（式１）又は（式２）により算出すれば良い。
【０１０５】
これにより、メッシュ組［０，０，０］−［０，１，０］におけるルート（始点ノードから終点ノードまでのルート）が算出される。なお、各メッシュ組から算出されるルートは１つだけでなく、ノードの組み合わせ分だけ算出される可能性がある。
【０１０６】
ルート算出部１０７は、当該メッシュ組［０，０，０］−［０，１，０］におけるルートの算出が終了したら、次のメッシュ組［０，０，０］−［１，１，０］におけるルートの算出を行う。以降では、メッシュ組［０，０，０］−［１，１，０］におけるルートＳ２が算出されたものとする。ルートの算出方法は、同様である。
【０１０７】
ここで、ルート算出部１０７は、ルート探索において、時間計算量の削減のため、例えば、多目的関数値やダイクストラ法の実行回数等に応じて、ダイクストラ法によるルート探索を途中で終了する。例えば、図１５では、始点ノードからノードＮｃへのルート探索と、ノードＮｃからノードＮｄへのルート探索と、ノードＮｄから終点ノードへのルート探索とが行われる場合を示している。
【０１０８】
このとき、ノードＮｄから終点ノードへのルート探索を行った際に、始点ノードからノードＮｃへの部分ルートＲｄと、ノードＮｃからノードＮｄへの部分ルートＲｅと、ノードＮｄからある地点Ａとに含まれるリンクの長さが上限値Ｔ３に達した場合、ルート算出は打ち切られる。このように、始点ノードからのリンク長が上限値を超えるルートの探索を途中で打ち切ることで、ルート算出における時間計算量を削減することができる。
【０１０９】
また、例えば、ルート算出におけるダイクストラ法の実行回数が上限値Ｔ４に達した場合、ルート算出は打ち切られる。この場合、次のメッシュ組におけるルート算出が行われる。
【０１１０】
次に、出力部１０８は、ルート算出部１０７が算出したルートを出力する（ステップＳ８）。このとき、出力部１０８は、ルート多目的関数値により、ルートをソートした上で、ルートを出力する。
【０１１１】
例えば、メッシュ組［０，０，０］−［０，１，０］におけるルートＳ１と、メッシュ組［０，０，０］−［１，１，０］におけるルートＳ２とをルート多目的関数値によりソートする。ルート多目的関数値によるソート方法は、メッシュ組多目的関数値によるソート方法と同様で良い。以降では、ルートＳ１がルートＳ２よりも上位にソートされたものとする。この場合、ルートＳ１が最良のルートとなる。
【０１１２】
ここで、ルートＳ１とルートＳ２との出力例を図１６に示す。図１６に示す例では、ルート算出部１０７により算出されたルートＳ１とルートＳ２とが出力されている。なお、最良のルート（すなわち、ルートＳ１）のみが出力されても良い。
【０１１３】
ここで、例えば非特許文献１の手法（従来手法）で出力されるルートと、本発明で出力されるルートの比較例を図１７に示す。図１７に示すように、従来手法では、格子によって、設備が３つ選択され、３つのルート（従来ルート１、従来ルート２、及び従来ルート３）が算出される。図１７に示すように、従来手法では、地震動による損傷のみを考慮した目的関数に基づくため、災害エリアを経由するルートが算出されることがある。
【０１１４】
一方、本発明では、二次災害も考慮した複数の目的関数を適用した結果、災害エリアを迂回したルート（ルートＳ１及びルートＳ２）が算出される。なお、図１７に示す例では、ルートＳ２と同一の従来ルート３が算出されているが、ルートＳ１は、従来手法では算出されない。
【０１１５】
＜まとめ＞
以上のように、本発明の実施の形態におけるルート算出装置１０では、二次災害による影響も考慮した複数の目的関数（多目的関数）に基づいて、多目的関数値が最良となるルートを算出する。これより、二次災害による影響も考慮した最適なルートを算出することができる。
【０１１６】
しかも、本発明の実施の形態におけるルート算出装置１０は、始点ノードと終点ノードとの間を複数のメッシュに分割した上で、これらメッシュにおける部分ルートを探索する。そして、本発明の実施の形態におけるルート算出装置１０は、多目的関数値が最良となるように部分ルートを繋ぎ合わせることで最適なルートを算出する。これにより、実用的な時間で上記の最適なルートを算出することができる。
【０１１７】
本発明は、具体的に開示された上記の実施形態に限定されるものではなく、特許請求の範囲から逸脱することなく、種々の変形や変更が可能である。
【符号の説明】
【０１１８】
１０        ルート算出装置
１００      ルート算出処理部
１０１      入力部
１０２      探索領域定義部
１０３      メッシュ構築部
１０４      部分メッシュ組構築部
１０５      メッシュ組構築部
１０６      メッシュ組絞込部
１０７      ルート算出部
１０８      出力部
【図１】
2018137718.tif 000005
【図２】
2018137718.tif 000006
【図３】
2018137718.tif 000007
【図４】
2018137718.tif 000008
【図５】
2018137718.tif 000009
【図６】
2018137718.tif 000010
【図７】
2018137718.tif 000011
【図８】
2018137718.tif 000012
【図９】
2018137718.tif 000013
【図１０】
2018137718.tif 000014
【図１１】
2018137718.tif 000015
【図１２】
2018137718.tif 000016
【図１３】
2018137718.tif 000017
【図１４】
2018137718.tif 000018
【図１５】
2018137718.tif 000019
【図１６】
2018137718.tif 000020
【図１７】
2018137718.tif 000021