【０００１】[0001]
【発明の属する技術分野】本発明は、要求者から発信さ
れた航空機の経路リクエストに対応して、最適飛行経路
を出力する飛行経路作成システムに関するものであり、
さらに詳しくいえば最適飛行経路作成のための問題解決
演算装置およびその方法に関するものである。BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a flight route creation system for outputting an optimum flight route in response to an aircraft route request transmitted from a requester.
More specifically, the present invention relates to a problem solving arithmetic device for creating an optimal flight path and a method therefor.
【０００２】[0002]
【従来の技術】航空機が、正確な位置情報を持ち、正し
い飛行経路を維持し、正確に着陸するための航法を得る
装置の従来例として、航空機に搭載されている気圧高度
計によって高度情報を得、慣性航法装置（慣性プラット
ホーム装置）により位置と速度の情報を得る方式があ
る。また地上側から供給される情報によって航法を助け
る装置として、レーダ、ロラン、ＶＯＲ，タカンなどの
誘導制御装置があり、航空機側にはこれに応答できる自
動操縦装置が搭載されていた。しかし航空機に代表され
る非軌道交通では比較的自由に交通具を運転できるのが
特徴であり、そのため、システムとしてはまとまりのな
いものになりがちで、放置すれば安全性や、輸送の質や
容量を低下させるおそれがあった。2. Description of the Related Art As a conventional example of a device which has accurate position information, maintains a correct flight path, and obtains navigation for landing accurately, altitude information is obtained by a barometric altimeter mounted on the aircraft. There is a method of obtaining position and speed information by an inertial navigation device (inertial platform device). In addition, guidance control devices such as radar, Loran, VOR, and Takan have been used as devices for assisting navigation by information supplied from the ground side, and automatic pilot devices capable of responding thereto have been mounted on the aircraft side. However, non-track traffic such as airplanes is characterized by relatively free operation of driving equipment, and as a result, the system tends to be uncoordinated. There was a possibility that the capacity was reduced.
【０００３】近時、この航空機航行システムにおいて、
航空機を安全確実に、かつ最も経済的に航行させる問題
を、最適航空経路を探索する最適値問題として捉えよう
という機運が生まれてきた。しかし、計算時間および解
の精度の点で問題が残されており、決定的な手法はまだ
見つかっていないというのが現状である。Recently, in this aircraft navigation system,
There has been a momentum to consider the problem of making aircraft safe and most economical to navigate as the optimal value problem of finding the optimal air route. However, there are still problems in terms of calculation time and solution accuracy, and no definitive method has yet been found.
【０００４】この中で、組み合わせ最適化問題の有力な
近似解法の１つとして遺伝的アルゴリズムが脚光を浴び
ていて、例えば特開平７―２２５７５２号公報「状態遷
移の概念を導入した問題解決演算装置および方法」に
は、遺伝的アルゴリズムを用いて最適解を探索する装置
と手法が開示されている。この近似的最適化の原理構成
は、遺伝的アルゴリズムに基づく最適解探索手段と、探
索過程観測および状態遷移手段とから構成されていて、
最初に初期集団をランダムに発生させ、その後、最適解
探索手段の動作を探索過程観測および状態遷移手段によ
り監視し、条件により最適解探索手段を変化させるとい
うものである。Among them, a genetic algorithm has been spotlighted as one of the promising approximate solutions to the combination optimization problem. For example, Japanese Patent Laid-Open No. 7-225755 discloses a "problem solving operation apparatus incorporating the concept of state transition". And methods "discloses an apparatus and method for searching for an optimal solution using a genetic algorithm. The principle configuration of this approximate optimization is composed of an optimal solution search means based on a genetic algorithm, and a search process observation and state transition means.
First, an initial group is randomly generated, and then the operation of the optimal solution searching means is monitored by the search process observation and state transition means, and the optimal solution searching means is changed according to conditions.
【０００５】[0005]
【発明が解決しようとする課題】しかし、この技術を動
的飛行経路作成システムに適用する場合、次のような問
題があった。第１にこの最適化手法においては過去の事
例を活用することなく、ランダムに発生させた初期集団
を第１世代の遺伝子群（初期候補飛行経路群）とするた
め、探索の初期段階における評価値（飛行時間または消
費燃料量）の収束が遅いという問題があった。第２に
は、大域的探索と局所的探索を探索の同一フェーズにお
いて組み合わせて遂行し、さらに局所探索においては局
所最適解を求めていないため、探索の全フェーズにおい
ても評価値の収束に時間がかかるという問題があった。
また、遺伝的アルゴリズムと他の最適化手法との組み合
わせによる方法が提案されているが、計算時間および解
の精度の点で問題が残っているのが現状である。However, when this technique is applied to a dynamic flight path creation system, there are the following problems. First, in this optimization method, without utilizing past cases, an initial population randomly generated is used as a first-generation gene group (initial candidate flight path group). (Flight time or fuel consumption) is slow to converge. Second, the global search and the local search are performed in combination in the same phase of the search, and the local optimal solution is not found in the local search. There was such a problem.
Further, a method based on a combination of a genetic algorithm and another optimization method has been proposed, but at present, problems remain in terms of calculation time and solution accuracy.
【０００６】本発明はこのような背景の下になされたも
ので、遺伝的アルゴリズムを動的飛行経路作成システム
に適用するに当たり、過去の事例を有効に活用して、初
期候補経路の探索範囲をある程度絞り込むことにより
（第１世代遺伝子群を絞り込む）、初期フェーズにおけ
る計算時間の短時間化を図り、さらに大域的探索には遺
伝的アルゴリズムを適用し、局所的な精密探索には近似
解法の１つであるシミュレーテッドアニーリング法を適
用するなどして、最終的には、短時間で最適経路を出力
する飛行経路の作成方法と装置を提供することを目的と
する。The present invention has been made under such a background. In applying a genetic algorithm to a dynamic flight path creation system, the search range of an initial candidate path is effectively utilized by effectively utilizing past cases. By narrowing down to a certain extent (the first generation gene group is narrowed down), the calculation time in the initial phase is shortened. Further, a genetic algorithm is applied to global search, and an approximate solution method is used for local precise search. Finally, an object of the present invention is to provide a method and apparatus for creating a flight route that outputs an optimal route in a short time by applying a simulated annealing method.
【０００７】[0007]
【課題を解決するための手段】請求項１に記載の発明
は、航空機の飛行経路作成システムにおける飛行経路作
成装置において、経路要求者からの経路リクエスト情報
などを受け取るための受信装置と、出発空港および到着
空港に対応する複数の候補飛行経路を記憶している初期
経路記憶部と、航空機型式、出発空港および到着空港に
対応する最適経路などに関する過去の事例を記憶してい
る経路事例記憶部を含む記憶装置と、該経路事例記憶部
と該初期経路記憶部より経路に関するデータを呼び出し
て初期候補経路を設定する手段と、該初期候補経路群を
初期状態として目標状態の最適経路を決定する経路探索
手段と、該最適経路を前記経路事例記憶部に追加記憶さ
せる経路事例記憶手段とから構成されるデータ処理装置
と、該経路探索手段により求められた最適経路を経路要
求者に送信するための送信装置とを具備してなる飛行経
路作成装置である。According to a first aspect of the present invention, there is provided a flight route creation device for an aircraft flight route creation system, comprising: a receiving device for receiving route request information from a route requester; And an initial route storage unit that stores a plurality of candidate flight routes corresponding to the arrival airport, and a route case storage unit that stores past cases regarding the aircraft type, the optimal route corresponding to the departure airport and the arrival airport, and the like. Means for setting an initial candidate route by calling data relating to a route from the route case storage unit and the initial route storage unit, and a route for determining an optimal route in a target state using the initial candidate route group as an initial state A data processing apparatus comprising: a search unit; and a route case storage unit for additionally storing the optimum route in the route case storage unit; A flight path generation device formed by a transmitter device for transmitting more the obtained optimal route to the route requester.
【０００８】請求項２に記載の発明は、請求項１に記載
の飛行経路作成装置において、前記飛行経路作成手段は
前記経路事例記憶部と前記初期経路記憶部に記憶されて
いる経路に関するデータを初期状態とし、問題解決型ア
ルゴリズムを利用して、目標状態の最適経路を探索する
手段を具備していることを特徴としている。According to a second aspect of the present invention, in the flight route creation device according to the first aspect, the flight route creation means stores data relating to the route stored in the route case storage unit and the initial route storage unit. It is characterized in that it is provided with means for searching for an optimum route in a target state by using a problem solving algorithm as an initial state.
【０００９】請求項３に記載の発明は、請求項１に記載
の飛行経路作成装置において、前記飛行経路作成手段
は、設定された初期候補経路群に対し、まず遺伝的アル
ゴリズムを利用して大域的探索を行い、次いでシミュレ
ーテッドアニーリング法により局所的探索を行って、最
適経路を探索する経路探索手段を具備していることを特
徴としている。According to a third aspect of the present invention, in the flight route creation device according to the first aspect, the flight route creation means first applies a global algorithm to the set initial candidate route group using a genetic algorithm. It is characterized by having a route search means for searching for an optimal route by performing a local search and then performing a local search by a simulated annealing method.
【００１０】請求項４に記載の発明は、請求項１に記載
の飛行経路作成装置において、前記飛行経路作成手段
は、飛行時間または消費燃料量を計算するための複数個
の評価値算出モジュールと、シミュレーテッドアニーリ
ング法による局所最適解を求めるための複数個の局所探
索モジュールを、前記経路探索手段内に具備しているこ
とを特徴としている。According to a fourth aspect of the present invention, in the flight route creation device according to the first aspect, the flight route creation means includes a plurality of evaluation value calculation modules for calculating flight time or fuel consumption. A plurality of local search modules for obtaining a local optimum solution by a simulated annealing method are provided in the route search means.
【００１１】請求項５に記載の発明は、航空機の飛行経
路作成方法に関するもので、最適飛行経路を求める問題
解決方法として、飛行経路の作成には最適化手法を適用
し、初期状態の設定には、過去の事例として記憶されて
いる最適飛行経路や、候補経路として記憶されている飛
行経路を経路群として設定する過程と、飛行経路の探索
フェーズを大域的探索フェーズと局所的探索フェーズに
分け、大域探索には遺伝的アルゴリズム法を適用し、局
所探索にはシミュレーテッドアニーリング法を適用する
過程を有することを特徴としている。A fifth aspect of the present invention relates to a method for creating a flight path of an aircraft. As a method for solving the problem of obtaining an optimum flight path, an optimization method is applied to the creation of a flight path, and the initial state is set. Is divided into the process of setting the optimal flight route stored as a past case and the flight route stored as a candidate route as a route group, and dividing the search route search phase into a global search phase and a local search phase. The method is characterized in that a genetic algorithm method is applied to the global search, and a simulated annealing method is applied to the local search.
【００１２】請求項６に記載の発明は、請求項５に記載
の飛行経路作成方法において、飛行経路の探索フェーズ
を大域的探索フェーズと局所的探索フェーズに分け、大
域探索には遺伝的アルゴリズム法による並列処理の評価
を行い、局所探索にはシミュレーテッドアニーリング法
による並列処理の最適飛行経路探索を行うことを特徴と
している。According to a sixth aspect of the present invention, in the flight route creation method according to the fifth aspect, the search phase of the flight path is divided into a global search phase and a local search phase, and the global search is performed by a genetic algorithm method. It is characterized by performing parallel processing evaluation based on simulated annealing and performing optimal flight path search based on simulated annealing for local search.
【００１３】[0013]
【発明の実施の形態】以下、図面を参照して、この発明
の一実施形態について説明する。図１はこの発明の一実
施形態による動的飛行経路作成装置の構成を示すブロッ
ク図である。この動的飛行経路作成装置は、プログラム
制御により動作するデータ処理装置１００と、要求者か
らの情報を受信する受信装置１１０と、情報を記憶する
記憶装置１２０と、要求者への情報を送信する送信装置
１３０とから構成されている。受信装置１１０は要求者
から航空機型式、出発空港、到着空港、リクエスト日時
などの経路リクエスト情報を受信する。記憶装置１２０
は、初期経路記憶部１２１と経路事例記憶部１２２を備
えており、初期経路記憶部１２１は出発空港および到着
空港に対応する複数の候補経路を記憶しており、また経
路事例記憶部１２２は、航空機型式、出発空港および到
着空港に対応する過去の最適経路の事例群を記憶してい
る。データ処理装置１００は、初期候補経路設定手段１
０１と、経路探索手段１０２と、経路事例記憶手段１０
３とを含んでいる。初期候補経路設定手段１０１は、受
信装置１１０を通して要求者から受信した経路リクエス
ト情報（航空機型式、出発空港、到着空港、リクエスト
日時）をもとに、経路事例記憶部１２２より、過去の経
路事例を検索し、初期候補経路群を生成する。過去の経
路事例がない、または少ない場合は初期経路記憶部１２
１より取得したものを利用して、初期候補経路群を生成
する。経路探索手段１０２は、初期候補経路群にたい
し、遺伝的アルゴリズムの手法により、あらかじめ設定
した回数の大域的探索による候補経路の絞り込みを行っ
た後、シミュレーテッドアニーリング法による局所探索
を行い、局所最適経路を求める。そして各局所最適経路
の中で最も最適な経路を最終的な最適経路とする。シミ
ュレーテッドアニーリングは、この実施形態のように、
評価関数が多くの最小値を持ち得る場合にパラメータを
変更することにより、局所的な最小値の影響をのがれて
全体の最小値を求める手法である。経路事例記憶手段１
０３は、かくして求められた最適経路を経路事例として
経路事例記憶部１２２に記憶するとともに、送信装置１
３０に出力する。送信装置１３０は、作成された最適飛
行経路を要求者に送信する。DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of the present invention will be described below with reference to the drawings. FIG. 1 is a block diagram showing a configuration of a dynamic flight path creation device according to an embodiment of the present invention. This dynamic flight path creation device transmits a data processing device 100 operated by program control, a receiving device 110 for receiving information from a requester, a storage device 120 for storing information, and information to the requester. And a transmission device 130. The receiving device 110 receives route request information such as aircraft type, departure airport, arrival airport, and request date and time from the requester. Storage device 120
Has an initial route storage unit 121 and a route case storage unit 122. The initial route storage unit 121 stores a plurality of candidate routes corresponding to the departure airport and the arrival airport. The route case storage unit 122 A case group of past optimal routes corresponding to the aircraft type, departure airport and arrival airport is stored. The data processing device 100 includes an initial candidate route setting unit 1
01, route search means 102, and route case storage means 10
3 is included. Based on the route request information (aircraft type, departure airport, arrival airport, request date and time) received from the requester through the receiving device 110, the initial candidate route setting means 101 stores a past route case from the route case storage unit 122. Search and generate an initial candidate route group. If there are no or few past route cases, the initial route storage unit 12
An initial candidate route group is generated by using the one obtained from Step 1. The route search means 102 performs a local search by a simulated annealing method on the initial candidate route group after narrowing down the candidate routes by a predetermined number of global searches by a genetic algorithm technique, and then performs a local search by a simulated annealing method. Find the optimal route. Then, the most optimal route among the local optimal routes is set as the final optimal route. Simulated annealing, as in this embodiment,
In this method, the parameter is changed when the evaluation function can have many minimum values, so that the influence of the local minimum value is removed and the overall minimum value is obtained. Route case storage means 1
03 stores the optimum route thus obtained as a route case in the route case storage unit 122 and the transmitting device 1.
Output to 30. The transmitting device 130 transmits the created optimal flight route to the requester.
【００１４】次に上記構成になる飛行経路作成装置の動
作について、図２のフローチャートを参照して説明す
る。まず受信装置１１０によって受信した要求者からの
経路リクエストは初期候補経路設定手段１０１に送られ
る（ステップＡ１）。経路リクエストの情報は、例えば
航空機型式がＢ７４７−４００，出発空港が成田、到着
空港がシアトル、リクエスト日時は１９９７／１２／１
０ １２：００のように与えられている。初期経路設定
手段１０１では、リクエスト日時、航空機型式、出発空
港および到着空港を検索条件として、経路事例記憶部１
２２を検索し、経路事例群を取得する（ステップＡ
２）。このとき、経路事例記憶部１２２に、指定した検
索条件に当てはまる経路事例が１件も存在しなかった場
合（ステップＡ３）、出発空港および到着空港を検索条
件として、初期経路記憶部１２１を検索し、初期経路群
を取得する（ステップＡ７）。また経路事例検索により
取得した経路事例の件数が、あらかじめ設定した件数に
満たない場合（ステップＡ４）は、初期経路記憶部１２
１の初期経路群と経路事例記憶部１２２から取得した経
路事例を併せたものを初期候補経路とする（ステップＡ
５）。また、あらかじめ設定した件数（ｎ）以上の場合
（ステップＡ４）は、経路事例を初期候補経路に設定す
る（ステップＡ６）。Next, the operation of the flight path creating apparatus having the above configuration will be described with reference to the flowchart of FIG. First, the route request from the requester received by the receiving device 110 is sent to the initial candidate route setting means 101 (step A1). The route request information is, for example, the aircraft type is B747-400, the departure airport is Narita, the arrival airport is Seattle, and the request date and time is December 1, 1997.
0 12:00. The initial route setting means 101 uses the request date and time, the aircraft model, the departure airport and the arrival airport as search conditions, and stores the route case storage unit 1
22 to obtain a route case group (step A
2). At this time, if there is no route case that satisfies the designated search condition in the route case storage unit 122 (step A3), the initial route storage unit 121 is searched using the departure airport and the arrival airport as search conditions. , An initial route group is acquired (step A7). If the number of route cases obtained by the route case search is less than the preset number (step A4), the initial route storage unit 12
A combination of the initial route group 1 and the route case acquired from the route case storage unit 122 is set as an initial candidate route (step A).
5). If the number is equal to or larger than the preset number (n) (step A4), the route case is set as an initial candidate route (step A6).
【００１５】経路探索手段１０２では、各初期候補経路
の飛行時間または消費燃料量に関する評価値を求める
（ステップＡ８）。算出した各候補経路の評価値に対
し、あらかじめ設定した遺伝的アルゴリズムの選択方法
に従い、次世代の候補経路を生成する親となる経路を選
択し、さらに選択した親経路に対し、あらかじめ設定し
た遺伝的アルゴリズムの交叉方法に従って交叉を行い、
次世代の候補経路群を生成する（ステップＡ９）。生成
した次世代の候補経路群に対し、あらかじめ設定した遺
伝的アルゴリズムの突然変異方法に従い、突然変異を発
生させ、最終的な候補経路群を生成する。ここで、突然
変異を発生させるか、否かは、各候補経路の解空間にお
ける集中の度合い（状態空間における状態密度）により
決定し、また、突然変異を発生させる対象はランダムに
決定する（ステップＡ１０）。この遺伝的アルゴリズム
による経路選択ステップ（ステップＡ８からステップＡ
１０）を、あらかじめ設定した回数だけ繰り返して、候
補経路群の絞り込みを行う。以上の遺伝的アルゴリズム
の手法は、短時間で、大域的探索を行うことを可能にし
ている。The route search means 102 obtains an evaluation value relating to the flight time or fuel consumption of each initial candidate route (step A8). For each of the calculated candidate route evaluation values, a parent route for generating a next-generation candidate route is selected according to a preset genetic algorithm selection method. Crossover according to the crossover method of the genetic algorithm,
A next-generation candidate route group is generated (step A9). The generated next-generation candidate path group is mutated according to a preset mutation method of a genetic algorithm to generate a final candidate path group. Here, whether or not to generate a mutation is determined by the degree of concentration of each candidate path in the solution space (state density in the state space), and the target for generating the mutation is determined randomly (step A10). Route selection step (step A8 to step A
Step 10) is repeated a preset number of times to narrow down the candidate route group. The method of the genetic algorithm described above enables a global search to be performed in a short time.
【００１６】遺伝的アルゴリズムによる経路選択ステッ
プを設定回数（ｍ回）だけ繰り返した後（ステップＡ１
１）、各候補経路に対して、シミュレーテッドアニーリ
ング法により局所最適化を行い、局所最適経路群を求め
る。求めた各局所最適経路の中で評価値の高いものを最
終的な最適経路とする（ステップＡ１２）。経路事例記
憶手段１０４では、かくして求めた最適経路を、その後
の経路リクエスト時に利用できるように、経路事例記憶
部１２２に格納する（ステップＡ１３）。最後に送信装
置１３０により、作成した飛行経路を要求者に送信する
（ステップＡ１４）。After repeating the route selection step by the genetic algorithm a set number of times (m times) (step A1)
1) Local optimization is performed on each candidate route by a simulated annealing method to obtain a local optimum route group. Among the obtained local optimum paths, the one with the higher evaluation value is set as the final optimum path (step A12). The route case storage unit 104 stores the optimum route thus obtained in the route case storage unit 122 so that it can be used at the time of a subsequent route request (step A13). Finally, the transmitting device 130 transmits the created flight route to the requester (step A14).
【００１７】次に要求者からの経路リクエスト情報とし
て、リクエスト日時が９月１１日１３：００，航空機型
式がＢ７４７，出発空港が成田（ＲＪＡＡ）および到着
空港シアトル（ＫＳＥＡ）与えられた場合を、具体例と
して取り上げ、説明する。まず、これらの情報をキーに
経路事例記憶部１２２を検索し、図３に示す経路事例を
取得する。検索条件の中のリクエスト日時については、
あらかじめ抽出範囲を±３時間と決めておく（ステップ
Ａ２）。図３に示す表の第１列には１９９６年―９７年
９月１１日のリクエスト日時が記載され、第２列には航
空機型式Ｂ７４７が記載され、第３列には出発空港成田
を表すＲＪＡＡが記載され、第４列には到着空港シアト
ルを表すＫＳＥＡが記載され、第５列には事例経路の経
路構成点の緯度、経度、高度が示されている。この例で
は、経路事例の所要件数を１０件としているが、取得し
た事例の件数が８件であり、所要件数に満たないので、
さらに「ＲＪＡＡ ＫＳＥＡ」を検索キーとして初期経
路記憶部１２１を検索し、条件を満たすものとして、図
４に示す８件の候補経路を取得する。取得された図４の
表の第１列には出発空港のＲＪＡＡ、第２列には到着空
港のＫＳＥＡが示され、第３列には各候補経路の経路構
成点の緯度、経度、高度が示されている。図３、図４に
表示された経路、併せて１６件の検索された経路が図４
に併記されているが、これらが初期候補経路群を形成す
る（ステップＡ５）。Next, as route request information from the requester, a case where the request date and time is given at 13:00 on September 11, the aircraft type is B747, the departure airport is Narita (RJAA) and the arrival airport Seattle (KSEA) is given as follows. This will be described as a specific example. First, the route case storage unit 122 is searched using these pieces of information as a key, and the route case illustrated in FIG. 3 is obtained. For the request date and time in the search condition,
The extraction range is previously determined to be ± 3 hours (step A2). The first column of the table shown in FIG. 3 describes the request date and time from 1996 to September 11, 1997, the second column describes the aircraft model B747, and the third column shows the RJAA representing the departure airport Narita. Is described in the fourth column, and KSEA representing the arrival airport Seattle is described. In the fifth column, the latitude, longitude, and altitude of the route constituting point of the case route are shown. In this example, the required number of route cases is set to 10, but the number of acquired cases is 8, which is less than the required number of cases.
Further, the initial route storage unit 121 is searched using “RJAA KSEA” as a search key, and eight candidate routes shown in FIG. In the acquired table of FIG. 4, the first column shows the RJAA of the departure airport, the second column shows the KSEA of the arrival airport, and the third column shows the latitude, longitude, and altitude of the route constituent points of each candidate route. It is shown. The routes displayed in FIGS. 3 and 4 as well as the 16 searched routes are shown in FIG.
, Form an initial candidate route group (step A5).
【００１８】次に各候補経路の飛行時間を算出し、合計
１６件の経路に対する計算結果が図５に示されている
（ステップＡ８）。Ｎｏ１−Ｎｏ１６の候補経路の経路
構成点の緯度、経度、高度と、その経路を飛行するとき
の飛行時間が示されている。航路の視感的イメージを与
えため、図６には図５の経路Ｎｏ１の飛行プロフィール
を示す。次にあらかじめ設定した遺伝的アルゴリズムの
選択方式に従い、経路を選択し（淘汰）、交叉を行う
（交配）。図７の例では、図５のＮｏ３およびＮｏ４が
親経路として選択されており、交叉位置を１７０Ｅ（東
経１７０度）として子経路１および２を生成している。
図７の交叉前の経路と交叉後の経路を比較すればわかる
ように、１８０Ｅ以降において、そっくり入れ替わった
子経路が生成されている（ステップＡ９）。２個の遺伝
子がお互いに一部を交換するのに相当している。その
後、子２の経路に対して１６０Ｅおよび１８０Ｅの部分
の緯度を、それぞれ突然変異により，３８Ｎから３９Ｎ
へ、３５Ｎから３４Ｎへ変更され、これを最終的な経路
としている（ステップＡ１０）。図８に示す突然変異
は、遺伝子の突然変異に相当するものであり、この突然
変異操作により大域的探索が進められている。上記遺伝
的アルゴリズム法による大域的探索を指定回数実行し、
指定回数実行後の各候補経路の解空間における位置と評
価値の関係を図９のグラフに示した。飛行時間を評価値
とし、●印で示してある。さらに、これらの各候補経路
はシミュレーテッドアニーリング法を用いた局所探索法
により最適化され、求められた局所最適経路の評価値は
図９の○印で示した。そして、各局所最適経路の中で一
番飛行時間の短い経路を最適経路としている（ステップ
Ａ１２）。Next, the flight time of each candidate route is calculated, and the calculation results for a total of 16 routes are shown in FIG. 5 (step A8). The latitude, the longitude, and the altitude of the route constituent points of the candidate routes No. 1 to No. 16 and the flight time when flying on the route are shown. FIG. 6 shows the flight profile of route No. 1 in FIG. 5 to provide a visual image of the route. Next, a route is selected (selection) and crossover is performed (crossing) in accordance with a genetic algorithm selection method set in advance. In the example of FIG. 7, No. 3 and No. 4 in FIG. 5 are selected as the parent routes, and the child routes 1 and 2 are generated with the intersection position being 170E (170 degrees east longitude).
As can be seen by comparing the route before the crossover and the route after the crossover in FIG. 7, a completely replaced child route is generated after 180E (step A9). Two genes are equivalent to exchanging parts for each other. Thereafter, the latitudes of the 160E and 180E portions for the path of the child 2 were respectively changed from 38N to 39N by mutation.
And 35N to 34N, which is the final route (step A10). The mutation shown in FIG. 8 corresponds to a gene mutation, and a global search has been advanced by this mutation operation. Perform the global search by the genetic algorithm method a specified number of times,
The relationship between the position in the solution space of each candidate route after the specified number of executions and the evaluation value is shown in the graph of FIG. The flight time was used as the evaluation value, and is indicated by ●. Further, each of these candidate routes is optimized by a local search method using a simulated annealing method, and the evaluation value of the obtained local optimal route is indicated by a circle in FIG. Then, the route with the shortest flight time among the local optimal routes is set as the optimal route (step A12).
【００１９】なお上記図１の経路探索手段１０２に代わ
る他の経路探索手段を図１０に示す。２０１は経路探索
制御手段であり、各候補経路の評価値算出には、複数個
の評価算出手段２０２を設け、これを並列動作させ、処
理速度を飛躍的に向上させることが可能である（図２の
ステップＡ８）。経路選択・交叉手段２０３は評価値に
基づく経路の選択と交叉を行い（図２のステップＡ
９）、経路突然変異手段２０４は交叉した経路に対し突
然変異を適用する（図２のステップＡ１０）。さらに、
シミュレーテッドアニーリング法による局所探索には複
数の局所探索手段２０５が設けられ、これを並列動作さ
せ、処理速度を処理速度を飛躍的に向上させることが可
能である（図２のステップＡ１２）。FIG. 10 shows another route search means which replaces the route search means 102 shown in FIG. Reference numeral 201 denotes a route search control unit, which is provided with a plurality of evaluation calculation units 202 for calculating the evaluation value of each candidate route, which can be operated in parallel to dramatically improve the processing speed (FIG. Step A8). The route selection / crossover means 203 selects and crosses a route based on the evaluation value (step A in FIG. 2).
9), the path mutation means 204 applies a mutation to the crossed paths (Step A10 in FIG. 2). further,
In the local search by the simulated annealing method, a plurality of local search means 205 are provided, which can be operated in parallel to greatly increase the processing speed (step A12 in FIG. 2).
【００２０】[0020]
【発明の効果】以上説明したように、この発明によれ
ば、問題解決演算方式により最適飛行経路が探索されて
いるが、遺伝的アルゴリズムにより大域的探索を行い、
シミュレーテッドアニーリング法を用いて局所最適経路
を求めている。この最適化方式では、大域的探索フェー
ズと局所的探索フェーズに分けて探索を行い、さらに記
憶装置に記憶されている過去の事例飛行経路などを初期
候補経路群として利用するので、探索範囲を初期局面か
ら特定し、きわめて短時間で最適経路を求めることがで
きる。As described above, according to the present invention, the optimal flight path is searched by the problem solving operation method, but the global search is performed by the genetic algorithm.
The local optimum route is obtained using the simulated annealing method. In this optimization method, the search is performed separately in the global search phase and the local search phase, and the past case flight routes and the like stored in the storage device are used as an initial candidate route group. It is possible to determine the optimal route in a very short time by identifying from the phase.
【図１】 この発明の一実施形態を説明するための、問
題解決型の飛行経路作成装置の構成を示すブロック図で
ある。FIG. 1 is a block diagram showing a configuration of a problem-solving type flight path creation device for explaining an embodiment of the present invention.
【図２】 図１に示す問題解決型飛行経路作成装置の動
作を説明するためのフローチャートである。FIG. 2 is a flowchart for explaining the operation of the problem-solving flight path creating device shown in FIG.
【図３】 図１に示す経路事例記憶部から検索された成
田―シアトル間の飛行経路事例を示す表である。FIG. 3 is a table showing a flight route example between Narita and Seattle retrieved from the route example storage unit shown in FIG. 1;
【図４】 図１に示す初期経路記憶部から検索された成
田―シアトル間の候補経路を示す表である。FIG. 4 is a table showing a candidate route between Narita and Seattle retrieved from the initial route storage unit shown in FIG. 1;
【図５】 成田―シアトル間の初期候補飛行経路の評価
値（飛行時間）を示す表である。FIG. 5 is a table showing evaluation values (flight times) of an initial candidate flight route between Narita and Seattle.
【図６】 図５の表におけるＮｏ１飛行プロフィールを
示す飛行経路の鳥瞰図である。FIG. 6 is a bird's-eye view of the flight route showing the No. 1 flight profile in the table of FIG. 5;
【図７】 図５の表におけるＮｏ３とＮｏ４の飛行経路
を親経路とし、この一部を入れ替えて子経路を生成する
図で、遺伝アルゴリズムにおける交叉方法を説明する図
である。7 is a diagram in which the flight routes of No. 3 and No. 4 in the table of FIG. 5 are set as parent routes, and a part thereof is replaced to generate a child route, illustrating a crossover method in the genetic algorithm.
【図８】 候補飛行経路上で、飛行経路の緯度を突然変
更して子経路を生成する図で、遺伝アルゴリズムにおけ
る突然変異法を説明する図である。FIG. 8 is a diagram for generating a child route by suddenly changing the latitude of a flight route on a candidate flight route, and illustrating a mutation method in a genetic algorithm.
【図９】 遺伝的アルゴリズムで求めた大域的探索解と
シミュレーテッドアニーリング法で求めた局所探索解を
示す図である。FIG. 9 is a diagram showing a global search solution obtained by a genetic algorithm and a local search solution obtained by a simulated annealing method.
【図１０】 遺伝アルゴリズムによる評価値算出に複数
個の評価算出手段を設け、シミュレーテッドアニーリン
グ法による局所最適解探索に複数個の局所探索手段を設
けた経路探索手段の構成図を示す。FIG. 10 is a configuration diagram of a route search means provided with a plurality of evaluation calculation means for calculating an evaluation value by a genetic algorithm and provided with a plurality of local search means for searching for a local optimum solution by a simulated annealing method.
１００ データ処理装置 １０１ 初期候補経路設定手段 １０２ 経路探索手段 １０３ 経路事例記憶手段 １１０ 受信装置 １２０ 記憶装置 １２１ 初期経路記憶部 １２２ 経路事例記憶部 １３０ 送信装置 ２０１ 経路探索制御手段 ２０２ 評価算出手段 ２０３ 経路選択・交叉手段 ２０４ 経路突然変異手段 ２０５ 局所探索手段 REFERENCE SIGNS LIST 100 data processing device 101 initial candidate route setting means 102 route search means 103 route case storage means 110 receiving device 120 storage device 121 initial route storage unit 122 route case storage unit 130 transmission device 201 route search control means 202 evaluation calculation means 203 route selection Crossover means 204 Path mutation means 205 Local search means
───────────────────────────────────────────────────── フロントページの続き (56)参考文献 特開 平８−321000（ＪＰ，Ａ) 特開 平１−302499（ＪＰ，Ａ) 特開 平10−269500（ＪＰ，Ａ) 特開 平６−149376（ＪＰ，Ａ) 特開 平５−324603（ＪＰ，Ａ) 高江康彦、外２名，”ＧＡにおける最 適飛行経路の生成”，日本機械学会計算 力学講演会講演論文集，社団法人日本機 械学会，平成８年11月25日，96−25号, ｐ．３−４ (58)調査した分野(Int.Cl.7，ＤＢ名) G01C 21/00 G08G 5/00────────────────────────────────────────────────── ─── Continuation of front page (56) References JP-A-8-321000 (JP, A) JP-A-1-302499 (JP, A) JP-A 10-269500 (JP, A) JP-A-6-302 149376 (JP, A) JP-A-5-324603 (JP, A) Yasuhiko Takae, et al., "Generation of Optimal Flight Route in GA", Proceedings of the JSME Computational Mechanics Conference, Japan The Japan Society of Mechanical Engineers, November 25, 1996, No. 96-25, p. 3-4 (58) Field surveyed (Int. Cl.7 , DB name) G01C 21/00 G08G 5/00
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP09970398AJP3223880B2 (en) | 1998-04-10 | 1998-04-10 | Flight path creation device and flight path creation method |
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP09970398AJP3223880B2 (en) | 1998-04-10 | 1998-04-10 | Flight path creation device and flight path creation method |
| Publication Number | Publication Date |
|---|---|
| JPH11295098A JPH11295098A (en) | 1999-10-29 |
| JP3223880B2true JP3223880B2 (en) | 2001-10-29 |
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP09970398AExpired - LifetimeJP3223880B2 (en) | 1998-04-10 | 1998-04-10 | Flight path creation device and flight path creation method |
| Country | Link |
|---|---|
| JP (1) | JP3223880B2 (en) |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR100969399B1 (en)* | 2005-12-09 | 2010-07-14 | 캐논 가부시끼가이샤 | Probe Sets, Probe Immobilization Carriers, and Genetic Testing Methods |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20090119135A1 (en)* | 2007-11-02 | 2009-05-07 | David Lawrence Schoeman | Method and apparatus for real time generation of charter flights |
| JP2010097369A (en)* | 2008-10-15 | 2010-04-30 | Sharp Corp | Optimal parameter extraction apparatus and extraction method, and mask data, mask and semiconductor device manufacturing method using the method |
| US20130226373A1 (en)* | 2012-02-27 | 2013-08-29 | Ge Aviation Systems Llc | Methods for in-flight adjusting of a flight plan |
| JP6829858B2 (en)* | 2016-03-08 | 2021-02-17 | 国立大学法人京都大学 | Optimal flight network generation method and system |
| JP2019117211A (en)* | 2019-04-10 | 2019-07-18 | Kddi株式会社 | Determination device, determination method, and program |
| JP6678983B1 (en)* | 2019-08-15 | 2020-04-15 | 株式会社センシンロボティクス | Aircraft management server and management system |
| KR102415604B1 (en)* | 2019-11-26 | 2022-06-30 | 주식회사 엘지유플러스 | Method and apparatus for setting route of drone |
| JP2022090249A (en) | 2020-12-07 | 2022-06-17 | 富士通株式会社 | Optimization device, optimization method, and optimization program |
| IT202200003167A1 (en)* | 2022-02-21 | 2023-08-21 | Nuovo Pignone Srl | Improved performance model matching, augmentation, and prediction. |
| CN115311905B (en)* | 2022-10-12 | 2022-12-30 | 珠海翔翼航空技术有限公司 | Multi-runway flight approach navigation method and system based on attitude and speed prediction |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH01302499A (en)* | 1988-05-30 | 1989-12-06 | Nippon Telegr & Teleph Corp <Ntt> | Route guiding system |
| JP3050277B2 (en)* | 1995-05-25 | 2000-06-12 | 三菱電機株式会社 | Spatial route search device |
| Title |
|---|
| 高江康彦、外２名，"ＧＡにおける最適飛行経路の生成"，日本機械学会計算力学講演会講演論文集，社団法人日本機械学会，平成８年１１月２５日，９６−２５号，ｐ．３−４ |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR100969399B1 (en)* | 2005-12-09 | 2010-07-14 | 캐논 가부시끼가이샤 | Probe Sets, Probe Immobilization Carriers, and Genetic Testing Methods |
| Publication number | Publication date |
|---|---|
| JPH11295098A (en) | 1999-10-29 |
| Publication | Publication Date | Title |
|---|---|---|
| US6668227B2 (en) | Navigation apparatus | |
| US8126644B2 (en) | Travel support system, method thereof, program thereof, and recording medium containing the program | |
| JP3223880B2 (en) | Flight path creation device and flight path creation method | |
| JP2812639B2 (en) | Route search system and route search method | |
| CN109935077A (en) | System for constructing vehicle and cloud real-time traffic map for automatic driving vehicle | |
| Patrón et al. | Horizontal flight trajectories optimisation for commercial aircraft through a flight management system | |
| CN111295569B (en) | System and method for generating road map | |
| CN103459980A (en) | Management of icons for digital maps | |
| CN109435955A (en) | A kind of automated driving system performance estimating method, device, equipment and storage medium | |
| US20130235047A1 (en) | Method for animating characters, with collision avoidance based on tracing information | |
| CN111415024A (en) | Arrival time estimation method and estimation device | |
| JP7628432B2 (en) | Projectile Ranging Using Digital Maps | |
| US7483787B2 (en) | Determining intersections of multi-segment three-dimensional path with portions of partitioned three-dimensional space | |
| JP5162978B2 (en) | Route search method, route search system, and program | |
| CN113758492A (en) | Map detection method and device | |
| JP3050277B2 (en) | Spatial route search device | |
| JP3557443B2 (en) | Flight management method and device | |
| US20060190167A1 (en) | Navigation apparatus and method, and navigation program | |
| JP2018031947A (en) | Map creation device | |
| JP2000155167A (en) | Route prediction device | |
| CN101825473A (en) | Navigation method and navigation system | |
| Bojorquez et al. | Aircraft rerouting under risk tolerance during space launches | |
| JP2004219243A (en) | Navigation system | |
| JP3094960B2 (en) | Airway section display system | |
| Dancila et al. | New flight plan optimisation method utilising a set of alternative final point arrival time targets (RTA constraints) |
| Date | Code | Title | Description |
|---|---|---|---|
| A01 | Written decision to grant a patent or to grant a registration (utility model) | Free format text:JAPANESE INTERMEDIATE CODE: A01 Effective date:20010724 | |
| FPAY | Renewal fee payment (event date is renewal date of database) | Free format text:PAYMENT UNTIL: 20070824 Year of fee payment:6 | |
| FPAY | Renewal fee payment (event date is renewal date of database) | Free format text:PAYMENT UNTIL: 20080824 Year of fee payment:7 | |
| FPAY | Renewal fee payment (event date is renewal date of database) | Free format text:PAYMENT UNTIL: 20080824 Year of fee payment:7 | |
| FPAY | Renewal fee payment (event date is renewal date of database) | Free format text:PAYMENT UNTIL: 20090824 Year of fee payment:8 | |
| FPAY | Renewal fee payment (event date is renewal date of database) | Free format text:PAYMENT UNTIL: 20090824 Year of fee payment:8 | |
| FPAY | Renewal fee payment (event date is renewal date of database) | Free format text:PAYMENT UNTIL: 20100824 Year of fee payment:9 | |
| FPAY | Renewal fee payment (event date is renewal date of database) | Free format text:PAYMENT UNTIL: 20110824 Year of fee payment:10 | |
| FPAY | Renewal fee payment (event date is renewal date of database) | Free format text:PAYMENT UNTIL: 20110824 Year of fee payment:10 | |
| FPAY | Renewal fee payment (event date is renewal date of database) | Free format text:PAYMENT UNTIL: 20120824 Year of fee payment:11 | |
| FPAY | Renewal fee payment (event date is renewal date of database) | Free format text:PAYMENT UNTIL: 20130824 Year of fee payment:12 | |
| EXPY | Cancellation because of completion of term |