JP3596650B2 - Tour search device - Google Patents
Tour search device Download PDFInfo
- Publication number
- JP3596650B2 JP3596650B2 JP5500997A JP5500997A JP3596650B2 JP 3596650 B2 JP3596650 B2 JP 3596650B2 JP 5500997 A JP5500997 A JP 5500997A JP 5500997 A JP5500997 A JP 5500997A JP 3596650 B2 JP3596650 B2 JP 3596650B2
- Authority
- JP
- Japan
- Prior art keywords
- group
- node
- point
- nodes
- intra
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Landscapes
- Traffic Control Systems (AREA)
- Instructional Devices (AREA)
- Navigation (AREA)
Description
【０００１】
【発明の属する技術分野】
本発明は、ノードおよびノードを接続するリンクからなる道路ネットワークにおける始点ノードから複数のノードを経由して終点ノードに至る複数の経路からノード間の距離、移動時間等を与えるコストを最小にする経路を探索する巡回路探索方法および装置に関し、例えば車載ナビゲーションシステム、パソコンなどでセールス、観光等のために複数地点を効率的に回る道順を探す道順案内システム、経路探索システム等に適用しうる巡回路探索装置に関する。
【０００２】
【従来の技術】
巡回路探索については、巡回セールスマン問題として従来から研究されており、ヒューリスティックスの確率的解析、ローカルサーチ、ラグランジュ双対法、分枝限定法、分枝カット法、ホップフィールド型ニューラルネットモデルによる方法等さまざまな方法が知られている。最新の巡回セールスマン問題の解法については、「Ｃｏｍｐｕｔｅｒ Ｔｏｄａｙ」（１９９４年 ９月号Ｎｏ６３）、「巡回セールスマン問題への招待」（オペレーションズリサーチ、１９９４年 １〜 ３月号）等で紹介されている。
【０００３】
【発明が解決しようとする課題】
巡回セールスマン問題においては、最短巡回路解を実時間では見つけられないことが証明されており、近似解を求めることになる。方式の評価基準は、探索時間と見つかった経路の冗長度（最短順路と比べてどの程度長い経路になっているかを表わし、０％の場合最短路と同一であり、１０％の場合見つかった経路は最短路に比べて１０％長い経路である）になるが、両者には相関関係があり、探索時間を短縮すれば冗長度が大きくなり、冗長度を小さくすれば探索時間が長くなる。
【０００４】
例えば、最新の研究成果で探索時間が短く、かつ冗長度も小さい、リアルタイム性が最も高いといわれるホップフィールド型ニューラルネットモデルによる方法では、処理時間はワークステーションで０．１秒以下だが、冗長度は最短解に対して平均３７％となっている。また、一方で、平均冗長度が０％に近い方式もあるが、ワークステーションでの探索処理に数時間かかっている。観光等を考慮した場合、巡回ポイントは１０ポイント程度であるが、探索時間が短く冗長度の小さい解が要求される。更に観光地案内サービス等では、始点と終点が必ずしも同じではなく、始点と違う終点まで途中のポイントを経由して最短で巡回する経路の案内も必要になってくる。ホップフィールド型ニューラルネットモデル等の従来方式に比べ、より冗長度が小さく、かつ始点と終点が違う巡回路探索にも適用できる巡回路探索方式が望まれていた。
【０００５】
本発明は、上記に鑑みてなされたもので、その目的とするところは、ノードおよびノードを接続するリンクからなる道路ネットワークにおいて始点ノードから複数のノードを経由して終点ノードに至る経路を効率的に精度よく探索し得る巡回路探索装置を提供することにある。
【００２２】
【課題を解決するための手段】
上記目的を達成するため、請求項１記載の本発明は、ノードおよびノードを接続するリンクからなる道路ネットワークにおける任意の始点ノードから複数のノードを経由して始点ノードと異なる終点ノードに至る複数の経路からノード間の距離、移動時間等を与えるコストを最小にする経路の近似解を探索する巡回路探索装置であって、始点ノードと終点ノードを結んだ線分に対して、始点ノードを通り前記線分に直交する始点ノード側垂線、および終点ノードを通り前記線分に直交する終点ノード側垂線をそれぞれ引き、前記始点ノード側垂線に対して終点ノードと反対側に存在するノードをまとめた始点側ノード群と、前記終点ノード側垂線に対して始点ノードと反対側に存在するノードをまとめた終点側ノード群と、始点ノード、終点ノード、始点側ノード群、終点側ノード群以外の中間ノード群とに分類するノード分類手段と、始点から始点側ノード群の各ノードまでの角度を求める始点側ノード群角度算出手段と、前記角度をソートし、始点ノードから角度の順に始点側ノード群の各ノードを結んで始点側巡回路を生成する始点側巡回路生成手段と、終点から終点側ノード群の各ノードまでの角度を求める終点側ノード群角度算出手段と、前記角度をソートし、終点ノードから角度の順に終点側ノード群の各ノードを結んで終点側巡回路を生成する終点側巡回路生成手段と、始点と終点を結ぶ線分に対して前記中間ノード群の各ノードから垂線を下ろし、始点と終点を結ぶ線分と各垂線との交点が始点に近い方から順に中間ノード群の各ノードを結んで中間ノード群巡回路を生成する中間ノード群巡回路生成手段と、前記始点側巡回路、中間ノード群巡回路および終点側巡回路の順に巡回路を結んで始点から終点までの巡回路を生成する全巡回路生成手段とを有することを要旨とする。
【００２３】
請求項１記載の本発明にあっては、始点ノードと終点ノードを結んだ線に対して、始点ノードを通り前記線分に直交する始点ノード側垂線、および終点ノードを通り前記線分に直交する終点ノード側垂線をそれぞれ引いて、各ノードを始点側ノード群、終点側ノード群、中間ノード群に分類し、始点側ノード群の各ノードまでの角度の順に始点ノードから始点側ノード群の各ノードを結んで始点側巡回路を生成し、終点側ノード群の各ノードまでの角度の順に終点側ノード群の各ノードを結んで終点側巡回路を生成し、中間ノード群の各ノードを結んで中間ノード群巡回路を生成し、始点側巡回路、中間ノード群巡回路および終点側巡回路の順に巡回路を結んで始点から終点までの巡回路を生成する。
【００２６】
請求項２記載の本発明は、ノードおよびノードを接続するリンクからなる道路ネットワークにおける任意の始点ノードから複数のノードを経由して再び始点ノードに至る複数の経路からノード間の距離、移動時間等を与えるコストを最小にする経路の近似解を探索する巡回路探索装置であって、巡回するすべてのノードを結んだ多角形の重心を求める重心算出手段と、前記重心を中心として、始点から各ノードまでの角度を求める角度算出手段と、前記角度をソートし、始点ノードから角度の小さい順に各ノードを結んで巡回路を生成する巡回路生成手段とを有し、前記巡回路生成手段は、該巡回路生成手段により生成された巡回路を構成する各ノードにおいて、隣り合うノード間の角度が所定値より小さいノードをまとめて、グループを設定するグループ設定手段と、該グループを構成する各ノードにおいて、前記ソート値が最も小さいものをグループ内始点とし、該始点から最も遠いノードをグループ内終点とするグループ内始点終点設定手段と、前記グループ内始点とグループ内終点を結んだ線分に対して、グループ内始点を通り前記線分に直交する始点ノード側垂線、およびグループ内終点を通り前記線分に直交する終点ノード側垂線をそれぞれ引き、前記始点ノード側垂線に対してグループ内終点と反対側に存在するノードをまとめたグループ内始点側ノード群と、前記終点ノード側垂線に対してグループ内始点と反対側にあるノードをまとめたグループ内終点側ノード群と、グループ内始点、グループ内終点、グループ内始点側ノード群、グループ内終点側ノード群以外のグループ内中間ノード群とに分類するグループ内ノード分類手段と、グループ内始点からグループ内始点側ノード群の各ノードまでの角度を求めるグループ内始点側ノード群角度算出手段と、前記角度をソートし、グループ内始点ノードから角度の順にグループ内始点側ノード群の各ノードを結んでグループ内始点側巡回路を生成するグループ内始点側巡回路生成手段と、グループ内終点からグループ内終点側ノード群の各ノードまでの角度を求めるグループ内終点側ノード群角度算出手段と、前記角度をソートし、グループ内終点ノードから角度の順にグループ内終点側ノード群の各ノードを結んでグループ内終点側巡回路を生成するグループ内終点側巡回路生成手段と、グループ内始点とグループ内終点を結ぶ線分に対して前記グループ内中間ノード群の各ノードから垂線を下ろし、グループ内始点とグループ内終点を結ぶ線分と各垂線との交点がグループ内始点に近い方から順にグループ内中間ノード群の各ノードを結んでグループ内中間ノード群巡回路を生成するグループ内中間ノード群巡回路生成手段と、前記グループ内始点側巡回路、グループ内中間ノード群巡回路およびグループ内終点側巡回路の順に巡回路を結んでグループ内始点からグループ内終点までの巡回路を生成するグループ内全巡回路生成手段とを有することを要旨とする。
【００２７】
請求項２記載の本発明にあっては、各ノードを結んだ多角形の重心を求め、該重心を中心として、始点から各ノードまでの角度を求め、始点ノードから角度の小さい順に各ノードを結んで巡回路を生成し、巡回路を構成する各ノードにおいて、隣り合うノード間の角度が所定値より小さいノードをまとめて、グループを設定し、該グループを構成する各ノードに対して、請求項１記載の巡回路探索装置を適用したものである。
【００３０】
請求項３記載の本発明は、請求項１記載の発明において、前記始点側巡回路生成手段、前記終点側巡回路生成手段、および前記中間ノード群巡回路生成手段は、これらの各手段により生成された各巡回路を構成する各ノードにおいて、所定の条件を満たすノードをまとめて、グループを設定するグループ設定手段と、該グループを構成する各ノードにおいて、前記ソート値が最も小さいものをグループ内始点とし、該始点から最も遠いノードをグループ内終点とするグループ内始点終点設定手段と、前記グループ内始点とグループ内終点を結んだ線分に対して、グループ内始点を通り前記線分に直交する始点ノード側垂線、およびグループ内終点を通り前記線分に直交する終点ノード側垂線をそれぞれ引き、前記始点ノード側垂線に対してグループ内終点と反対側に存在するノードをまとめたグループ内始点側ノード群と、前記終点ノード側垂線に対してグループ内始点と反対側にあるノードをまとめたグループ内終点側ノード群と、グループ内始点、グループ内終点、グループ内始点側ノード群、グループ内終点側ノード群以外のグループ内中間ノード群とに分類するグループ内ノード分類手段と、グループ内始点からグループ内始点側ノード群の各ノードまでの角度を求めるグループ内始点側ノード群角度算出手段と、前記角度をソートし、グループ内始点ノードから角度の順にグループ内始点側ノード群の各ノードを結んでグループ内始点側巡回路を生成するグループ内始点側巡回路生成手段と、グループ内終点からグループ内終点側ノード群の各ノードまでの角度を求めるグループ内終点側ノード群角度算出手段と、前記角度をソートし、グループ内終点ノードから角度の順にグループ内終点側ノード群の各ノードを結んでグループ内終点側巡回路を生成するグループ内終点側巡回路生成手段と、グループ内始点とグループ内終点を結ぶ線分に対して前記グループ内中間ノード群の各ノードから垂線を下ろし、グループ内始点とグループ内終点を結ぶ線分と各垂線との交点がグループ内始点に近い方から順にグループ内中間ノード群の各ノードを結んでグループ内中間ノード群巡回路を生成するグループ内中間ノード群巡回路生成手段と、前記グループ内始点側巡回路、グループ内中間ノード群巡回路およびグループ内終点側巡回路の順に巡回路を結んでグループ内始点からグループ内終点までの巡回路を生成するグループ内全巡回路生成手段とを有し、前記始点側巡回路生成手段および前記終点側巡回路生成手段の前記グループ設定手段は、隣り合うノード間の角度が所定値より小さいノードをまとめて、グループを設定する手段を有し、前記中間ノード群巡回路生成手段の前記グループ設定手段は、中間ノード群における各ノードから始点と終点を結ぶ線分に垂線を下ろした点の中で隣り合う点間の距離が所定値より小さいノードをまとめて、グループを設定する手段を有することを要旨とする。
【００３１】
請求項３記載の本発明にあっては、始点側巡回路生成手段、終点側巡回路生成手段、中間ノード群巡回路生成手段により生成された各巡回路を構成する各ノードにおいて、所定の条件を満たすノードをまとめて、グループを設定するグループ設定手段と、該グループを構成する各ノードにおいて、請求項１記載の巡回路探索装置を適用したものである。
【００３４】
【発明の実施の形態】
以下、図面を用いて本発明の実施の形態について説明する。
【００３５】
図１は、一実施形態に係る巡回路探索方法を実施する巡回路探索装置の構成を示すブロック図である。同図に示す巡回路探索装置は、ノードおよびノードを接続するリンクからなる道路ネットワークにおける任意の始点ノードから複数のノードを経由して再び始点ノードに至る複数の経路からノード間の距離、移動時間等を与えるコストを最小にする経路を探索するものであり、すなわち始点と終点が同一の場合の巡回路探索装置であり、巡回するノード等の情報を入力する入力部１と、該入力部１から入力されたノード情報等に基づいて巡回路探索処理を実施する制御部３と、該制御部３で探索された巡回路を出力する出力部５と、制御部３における巡回路探索処理において発生した情報を一時的に格納するワークエリアを構成するワークメモリ７とから構成されている。
【００３６】
また、制御部３は、巡回するすべてのノードを結んだ多角形の重心を求める重心算出処理部９と、前記重心を中心として、始点から各ノードまでの角度を求める角度算出処理部１１と、前記角度をソートし、始点ノードから角度の小さい順に各ノードを結んで巡回路を生成する巡回路生成処理部１３とから構成されている。
【００３７】
次に、このように構成される巡回路探索装置の作用を図２に示すフローチャートに基づき図３を参照しながら説明する。
【００３８】
前記入力部１から巡回すべきノード情報が制御部３に入力されると、制御部３はこのノード情報をワークメモリ７に格納する。制御部３は、巡回すべきすべてのノード情報をワークメモリ７から読み出し、このノード情報を重心算出処理部９に供給する。重心算出処理部９は、該ノードのすべてを結んだ多角形の重心を算出してワークメモリ７に格納する（図２のステップＳ１１０）。
【００３９】
次に、角度算出処理部１１は、ワークメモリ７から巡回するすべてのノードおよび前記重心を読み出し、図３に示すように、該重心を中心として、始点ノードから各ノードまでの角度を算出してワークメモリ７に格納する（ステップＳ１２０）。この角度算出処理は、図３に示すように、重心と始点ノードを結ぶ線をＸ軸とし、このＸ軸の中心に重心を設定し、この重心を中心として各ノードがＸ軸に対してなす角度を０゜〜３６０゜の間で求める。
【００４０】
このように各ノードの角度が算出されると、次に巡回路生成処理部１３は、ワークメモリ７から巡回するすべてのノードおよび始点ノードからの角度を読み出し、この角度をソートし、始点ノードから各ノードを角度の小さい順に結んで再度始点ノードに戻る巡回路を形成し、この巡回路をワークメモリ７に格納するとともに、与えられた始点ノードおよび巡回ノード群に対する最短巡回路として出力部５から出力する（ステップＳ１３０）。
【００４１】
図４は、本発明の他の実施形態に係る巡回路探索方法を実施する巡回路探索装置の構成を示すブロック図である。
【００４２】
図４に示す巡回路探索装置は、ノードおよびノードを接続するリンクからなる道路ネットワークにおける任意の始点ノードから複数のノードを経由して始点ノードと異なる終点ノードに至る複数の経路からノード間の距離、移動時間等を与えるコストを最小にする経路を探索するものであり、すなわち始点と終点が異なる場合の巡回路探索装置であり、巡回するノード等の情報を入力する入力部２１と、該入力部２１から入力されたノード情報等に基づいて巡回路探索処理を実施する制御部２３と、該制御部２３で探索された巡回路を出力する出力部２５と、制御部２３における巡回路探索処理において発生した情報を一時的に格納するワークエリアを構成するワークメモリ２７とから構成されている。
【００４３】
また、制御部２３は、ワークメモリ２７から読み出した巡回する各ノードを、始点ノード近辺にある始点側ノード群と、終点ノード近辺にある終点側ノード群と、始点ノード、終点ノード、始点側ノード群、終点側ノード群以外の中間ノード群とに分類するノード分類処理部２９と、始点から始点側ノード群の各ノードまでの角度を求める始点側ノード群角度算出処理部３１と、前記角度をソートし、始点ノードから角度の順に始点側ノード群の各ノードを結んで始点側巡回路を生成する始点側巡回路生成処理部３３と、終点から終点側ノード群の各ノードまでの角度を求める終点側ノード群角度算出処理部３５と、前記角度をソートし、終点ノードから角度の順に終点側ノード群の各ノードを結んで終点側巡回路を生成する終点側巡回路生成処理部３７と、始点と終点を結ぶ線分に対して前記中間ノード群の各ノードから垂線を下ろし、始点と終点を結ぶ線分と各垂線との交点が始点に近い方から順に中間ノード群の各ノードを結んで中間ノード群巡回路を生成する中間ノード群巡回路生成処理部３９と、前記始点側巡回路、中間ノード群巡回路および終点側巡回路の順に巡回路を結んで始点から終点までの巡回路を生成する全巡回路生成処理部４１とから構成されている。
【００４４】
次に、このように構成される巡回路探索装置の作用を図５に示すフローチャートに基づき図６〜９を参照しながら説明する。
【００４５】
制御部２３は、巡回すべきすべてのノード情報をワークメモリ２７から読み出し、このノード情報をノード分類処理部２９に供給する。ノード分類処理部２９は、図６に示すように、始点ノード近辺にあるノードをまとめた始点側ノード群と、終点ノード近辺にあるノードをまとめた終点側ノード群と、始点ノード、終点ノード、始点側ノード群、終点側ノード群以外の残りのノード群をまとめた中間ノード群とに分類してワークメモリ２７に格納する（ステップＳ２１０）。
【００４６】
図６に示す具体的なノード分類処理では、例えば始点ノードと終点ノードを結んだ始点−終点接続線４−１に対して始点ノードおよび終点ノードをそれぞれ通り前記始点−終点接続線４−１に直交する始点ノード側垂線４−２および終点ノード側垂線４−３を引き、始点ノード側垂線４−２より終点ノードのない側にあるノードをまとめた始点側ノード群４−４と、終点ノード側垂線４−３より始点ノードのない側にあるノードをまとめた終点側ノード群４−５と、始点ノード、終点ノード、始点側ノード群、終点側ノード群以外の残りの各ノードをまとめた中間ノード群とに分類している。
【００４７】
なお、ノード分類処理は、上記に限定されるものでなく、始点ノード側垂線４−２、終点ノード側垂線４−３のような垂線以外にも始点ノード、終点ノードそれぞれから一定距離以内にあるノードを始点側ノード群、終点側ノード群に分類する等のように種々の方法がある。
【００４８】
以上のようにして、ノード分類処理が行われると、次に始点側ノード群角度算出処理部３１は、ワークメモリ２７から始点ノードおよび始点側ノード群４−４を読み出し、図７に示すように始点ノードから始点側ノード群４−４の各ノードまでの角度を求めてワークメモリ２７に格納する（ステップＳ２２０）。
【００４９】
図７では、始点ノード側垂線４−２をＸ軸とし、始点ノードを中心に設定し、始点側ノード群４−４の各ノードとＸ軸とのなす角度を０゜〜１８０゜の間で求めている。
【００５０】
次に、始点側巡回路生成処理部３３は、ワークメモリ２７から始点ノード、始点側ノード群４−４および前記角度を読み出し、該角度をソートし、始点ノードから角度の順に始点側ノード群の各ノードを結んで、図７に太い線で示すように始点側巡回路を生成してワークメモリ２７に格納する（ステップＳ２３０）。なお、角度のソートは図７に示すように角度の大きいノードから小さいノードに降順に行うが、逆に昇順に行ってもよい。
【００５１】
次に、終点側ノード群角度算出処理部３５は、ワークメモリ２７から終点ノードおよび終点側ノード群４−５を読み出し、図８に示すように終点ノードから終点側ノード群４−５の各ノードまでの角度を求めてワークメモリ２７に格納する（ステップＳ２４０）。
【００５２】
図８に示す角度算出処理では、終点ノード側垂線４−３をＸ軸とし、終点ノードを中心に設定し、終点側ノード群４−５の各ノードとＸ軸との間のなす角度を０゜〜１８０゜の間で求めている。
【００５３】
次に、終点側巡回路生成処理部３７は、ワークメモリ２７から終点ノード、終点側ノード群４−５および前記角度を読み出し、該角度をソートし、終点ノードから角度の順に終点側ノード群４−５の各ノードを結んで、図８に太い線で示すように終点側巡回路を生成してワークメモリ２７に格納する（ステップＳ２５０）。
【００５４】
角度のソートは、図８に示すように、角度の大きいノードから小さいノードに降順に行うが、逆に昇順に行ってもよい。
【００５５】
次に、中間ノード群巡回路生成処理部３９は、ワークメモリ２７から中間ノード群４−６を読み出し、この中間ノード群４−６をソートして順序付けを行い、この順序で中間ノード群の各ノードを結んで、図９に太い線で示すように中間ノード群巡回路を生成してワークメモリ２７に格納する（ステップＳ２６０）。
【００５６】
図９に示す中間ノード群巡回路の生成では、始点と終点を結ぶ始点−終点接続線４−１に対して各中間ノードから垂線を下ろし、該垂線と始点−終点接続線４−１との各交点が始点に近い方から順に中間ノード群の各ノードを太い線のように結んで、中間ノード群巡回路を生成している。
【００５７】
次に、全巡回路生成処理部４１は、ワークメモリ２７から始点側巡回路、中間ノード群巡回路および終点側巡回路を読み出し、始点側巡回路、中間ノード群巡回路、終点側巡回路の順に各経路間の距離が最小になるように各巡回路を結んで始点から終点までの巡回路を生成してワークメモリ２７に格納するとともに、出力部２５から出力する。
【００５８】
図１０は、本発明の更に他の実施形態に係る巡回路探索方法におけるグループ化処理を示すフローチャートである。
【００５９】
図１０に示す実施形態のグループ化処理は、ノードのソート方法を改良し、より巡回路の精度を高くするものであり、図１に示す実施形態の巡回路生成処理部１３および図４に示す実施形態の始点側巡回路生成処理部３３および終点側巡回路生成処理部３７における各巡回路生成処理においてソート順にノードを並べた後の並び順の変更処理として行うものである。
【００６０】
本実施形態の作用について図１０に示すフローチャートに基づき図１１および図１２を参照しながら説明する。
【００６１】
図１０の処理では、まずグループ算出処理が行われる（ステップＳ３１０）。このグループ算出処理では、ワークメモリ４７からノード群を読み出し、ソート値の隣り合うノード間の角度、距離などの値が所定値より小さいものを抽出し、図１１に示すように、１グループとしてまとめ、ワークメモリ４７に格納する。
【００６２】
図１１に示すグループ化処理は、始点と終点が異なる場合の中間ノード群に対して行ったものであり、隣り合うノード間の距離が小さいものをグループ化している。
【００６３】
始点と終点が同一の場合のグループ化処理では、例えば巡回するノード数Ｎに対して隣り合うノードの角度が
α（３６０／Ｎ） （αは定数）
の場合にグループ化する。
【００６４】
始点と終点が異なる場合の始点側ノード群に対してのグループ化処理では、例えば、始点側ノード群のノード数Ｎに対して、隣り合うノードの角度が
α（３６０／（Ｎ−１）） （αは定数）
の場合にグループ化する。
【００６５】
始点と終点が異なる場合の終点側ノード群に対してのグループ化処理では、例えば、終点側ノード群のノード数Ｎに対して、隣り合うノードの角度が
α（３６０／（Ｎ−１）） （αは定数）
の場合にグループ化する。
【００６６】
始点と終点が異なる場合の中間ノード群に対してのグループ化処理では、例えば、中間ノード群のノード数Ｎに対して、始点と終点を結ぶ始点−終点接続線（４−１）に各中間ノード群のノードから下ろした垂線との交点（ノード垂線点）に対して、隣り合うノードとのノード垂線点間の距離が
【数１】
α（（始点と終点間の距離）／（Ｎ−１）） （αは定数）
の場合にグループ化する。なお、αは最も効率的な解が見つかるように設定すればよい。
【００６７】
以上のようにして、グループ化処理が行われると、次にグループ内巡回路生成処理が行われる（ステップＳ３２０）。このグループ内巡回路生成処理では、図１２に示すように、グループ内においてソート値が最も小さいものをグループ内始点とし、該グループ内始点からグループ内で最も遠いノードをグループ内終点とし、このグループ内の各ノードに対して、図１および図４に示した実施形態の巡回路探索方法を適用し、グループ内巡回路を生成し、グループ外で既にソート済みの前後のノードと接続するものである。
【００６８】
図１２に示すグループ内における始点および終点算出処理では、グループ内始点に対して最も遠いノード４がグループ内終点とされている。
【００６９】
【発明の効果】
以上説明したように、本発明によれば、請求項１記載の本発明にあっては、始点ノードと終点ノードを結んだ線に対して、始点ノードを通り前記線分に直交する始点ノード側垂線、および終点ノードを通り前記線分に直交する終点ノード側垂線をそれぞれ引いて、各ノードを始点側ノード群、終点側ノード群、中間ノード群に分類し、始点側ノード群の各ノードまでの角度の順に始点ノードから始点側ノード群の各ノードを結んで始点側巡回路を生成し、終点側ノード群の各ノードまでの角度の順に終点側ノード群の各ノードを結んで終点側巡回路を生成し、中間ノード群の各ノードを結んで中間ノード群巡回路を生成し、始点側巡回路、中間ノード群巡回路および終点側巡回路の順に巡回路を結んで始点から終点までの巡回路を生成するので、探索時間も従来方式の最短時間と同程度で、かつ精度のよい解を効率的に求めることができ、例えば観光地等を案内する観光案内システム、宅配便等における配達支援システム等のように探索時間と精度の両方が求められるシステムにおいても適用可能であり、これらのシステムの効率化が図られ、よりよいサービスを提供することができる。
【００７０】
また、本発明によれば、各ノードを結んだ多角形の重心を求め、該重心を中心として、始点から各ノードまでの角度を求め、始点ノードから角度の小さい順に各ノードを結んで巡回路を生成し、巡回路を構成する各ノードにおいて、隣り合うノード間の角度が所定値より小さいノードをまとめて、グループを設定し、該グループを構成する各ノードに対して、請求項１記載の巡回路探索装置を適用しているので、ノードのソート方法を改良し、巡回路の精度をより高くすることができる。
【００７１】
更に、本発明によれば、始点側巡回路生成手段、終点側巡回路生成手段、中間ノード群巡回路生成手段により生成された各巡回路を構成する各ノードにおいて、所定の条件を満たすノードをまとめて、グループを設定するグループ設定手段と、該グループを構成する各ノードにおいて請求項１記載の巡回路探索装置を適用しているので、ノードのソート方法を改良し、巡回路の精度をより高くすることができる。
【図面の簡単な説明】
【図１】本発明の一実施形態に係る巡回路探索方法を実施する巡回路探索装置の構成を示すブロック図である。
【図２】図１に示す巡回路探索装置の作用を示すフローチャートである。
【図３】図１に示す巡回路探索装置における角度算出処理を示す説明図である。
【図４】本発明の他の実施形態に係る巡回路探索方法を実施する巡回路探索装置の構成を示すブロック図である。
【図５】図４に示す巡回路探索装置の作用を示すフローチャートである。
【図６】図４に示す巡回路探索装置における始点側ノード群、終点側ノード群、中間ノード群への分割方法を示す説明図である。
【図７】図４に示す巡回路探索装置における始点側ノード群内の角度算出処理および巡回路生成処理を示す説明図である。
【図８】図４に示す巡回路探索装置における終点側ノード群内の角度算出処理および巡回路生成処理を示す説明図である。
【図９】図４に示す巡回路探索装置における中間ノード群内の巡回路生成処理を示す説明図である。
【図１０】本発明の更に他の実施形態の作用を示すフローチャートである。
【図１１】図１０に示す実施形態における中間ノード群に対するグループ化処理を示す説明図である。
【図１２】図１０に示す実施形態におけるグループ内における始点および終点算出処理を示す説明図である。
【符号の説明】
３，２３ 制御部
９ 重心算出処理部
１１ 角度算出処理部
１３ 巡回路生成処理部
２９ ノード分類処理部
３１ 始点側ノード群角度算出処理部
３３ 始点側巡回路生成処理部
３５ 終点側ノード群角度算出処理部
３７ 終点側巡回路生成処理部
３９ 中間ノード群巡回路生成処理部
４１ 全巡回路生成処理部[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention provides a route that minimizes the cost of providing distances, travel times, and the like between nodes from a plurality of routes from a start node to an end node via a plurality of nodes in a road network including nodes and links connecting the nodes. For example, the present invention can be applied to a route guidance system, a route search system, and the like that search for a route that efficiently turns around a plurality of points for sales, sightseeing, and the like with a vehicle-mounted navigation system, a personal computer, and the like.Tour search deviceAbout.
[0002]
[Prior art]
Traveling circuit search has been studied as a traveling salesman problem, and includes stochastic analysis of heuristics, local search, Lagrange dual method, branch and bound method, branch cut method, method using Hopfield neural network model, etc. Various methods are known. The latest solution to the traveling salesman problem is introduced in "Computer Today" (September 1994, No. 63) and "Invitation to the traveling salesman problem" (Operations Research, January to March 1994). I have.
[0003]
[Problems to be solved by the invention]
In the traveling salesman problem, it has been proven that the shortest traveling route solution cannot be found in real time, and an approximate solution will be obtained. The evaluation criteria of the method are the search time and the redundancy of the found route (showing how long the route is compared with the shortest route, 0% is the same as the shortest route, and 10% is the found route) Is a path that is 10% longer than the shortest path), but there is a correlation between the two. The shorter the search time, the greater the redundancy, and the smaller the redundancy, the longer the search time.
[0004]
For example, in the latest research results, the search time is short and the redundancy is small, and the method based on the Hopfield-type neural network model, which is said to be the most real-time, has a processing time of 0.1 seconds or less at the workstation, but Is 37% on average with respect to the shortest solution. On the other hand, there is a method in which the average redundancy is close to 0%, but it takes several hours for the search processing in the workstation. In consideration of sightseeing and the like, the number of tour points is about 10, but a search time is short, and a solution with low redundancy is required. Furthermore, in a tourist spot guidance service or the like, the start point and the end point are not always the same, and it is necessary to provide a route guidance that goes shortest via an intermediate point to an end point different from the start point. There has been a demand for a traveling route search method which has a lower degree of redundancy than conventional methods such as a Hopfield type neural network model and which can be applied to a traveling route search with a different start point and end point.
[0005]
The present invention has been made in view of the above, and an object of the present invention is to efficiently route a path from a start node to an end node via a plurality of nodes in a road network including nodes and links connecting the nodes. Search with high accuracyTour search deviceIs to provide.
[0022]
[Means for Solving the Problems]
In order to achieve the above object, the present invention described in
[0023]
According to the first aspect of the present invention,For the line connecting the start node and end nodeDraw a perpendicular to the start node passing through the start node and perpendicular to the line segment, and draw a perpendicular to the end node passing through the end node and perpendicular to the line segment, respectively., Each node is classified into a start-side node group, an end-point node group, and an intermediate node group, and the start-side circuit is connected to the start-side node group by connecting each node of the start-side node group in the order of the angle to each node of the start-side node group. Is generated, an end-side circuit is generated by connecting the nodes of the end-point node group in the order of the angle to each node of the end-point node group, and an intermediate-node group circuit is generated by connecting each node of the intermediate-node group Then, the starting point side tour, the intermediate node group tour, and the end point side tour are connected in this order to generate a tour from the start point to the end point.
[0026]
According to a second aspect of the present invention, there is provided a road network including nodes and links connecting the nodes, from a plurality of routes from an arbitrary start node to the start node again via the plurality of nodes, distances between nodes, travel time, and the like. A search device for searching for an approximate solution of a route that minimizes the cost of giving, the center of gravity calculating means for obtaining the center of gravity of a polygon connecting all the circulating nodes; and Angle calculation means for obtaining an angle to a node, and a traveling route generating means for sorting the angles and connecting each node in ascending order from the starting point node to generate a traveling route,A group setting unit configured to collectively set, at each of the nodes constituting the tour generated by the tour generation unit, nodes in which an angle between adjacent nodes is smaller than a predetermined value, and set a group; In each of the nodes forming the group, a group start point and end point setting means for setting a node having the smallest sort value as a start point in the group, and setting a node farthest from the start point as an end point in the group, and a start point in the group and an end point in the group For the line connectingDraw a start node side perpendicular perpendicular to the line segment passing through the start point in the group, and an end node side perpendicular perpendicular to the line segment through the end point in the group, respectively, and oppose the end point in the group with respect to the start node side perpendicular. A group of nodes on the side where the nodes present on the side are grouped, and a group of nodes on the end point side where the nodes on the side opposite to the start point within the group with respect to the end node side perpendicular, Starting point in group, ending point in group, starting node group in group, intermediate node group in group other than ending node group in groupClassifyIntra-group node classifying means, intra-group starting point node group angle calculating means for obtaining an angle from the intra-group starting point to each node of the intra-group starting point node group, and sorting the angles, in the order of the angle from the intra-group starting point node Intra-group start-point traveling circuit generating means for connecting each node of the intra-group start-point node group to generate an intra-group start-point traveling circuit, and a group for obtaining an angle from an intra-group end point to each of the intra-group end-point node groups Inner end-side node group angle calculation means, sorting the angles, and connecting the respective nodes of the intra-group end-point node group in the order of the angles from the intra-group end-point node to generate an intra-group end-point traveling circuit; Path generating means, and a perpendicular line from each node of the group of intermediate nodes in the group to a line segment connecting the start point in the group and the end point in the group. The intersection of the line connecting the start point within the group and the end point within the group and each perpendicular line is connected to each node of the intermediate node group within the group in order from the closest to the start point within the group to generate the intra-group intermediate node group circuit. An intra-group intermediate node group circuit generating means, and a circuit from the intra-group start point to the intra-group end point by connecting the inter-group start node side circuit, the inter-group intermediate node group tour and the intra-group end circuit in this order. Generate a roadIn groupThe gist of the present invention is to have a full circuit generating means.
[0027]
According to the present invention as set forth in
[0030]
The invention according to claim 3 is the invention according to
[0031]
According to the third aspect of the present invention,In each of the nodes constituting each tour generated by the start-side tour generator, the end-side tour generator, and the intermediate node group tour generator, nodes satisfying a predetermined condition are put together to form a group. In a group setting unit and each node constituting the group,Claim 1This is an application of the described traveling route search device.
[0034]
BEST MODE FOR CARRYING OUT THE INVENTION
Hereinafter, embodiments of the present invention will be described with reference to the drawings.
[0035]
FIG. 1 is a block diagram illustrating a configuration of a traveling route search device that performs a traveling route search method according to an embodiment. The traveling route search device shown in FIG. 1 is used for a distance and a travel time between nodes from a plurality of routes from an arbitrary start node to a start node again via a plurality of nodes in a road network including nodes and links connecting the nodes. A search unit for searching for a route that minimizes the cost of giving a route, etc., that is, an
[0036]
Further, the control unit 3 includes a center-of-gravity
[0037]
Next, the operation of the traveling route searching apparatus thus configured will be described with reference to FIG. 3 based on the flowchart shown in FIG.
[0038]
When node information to be visited is input from the
[0039]
Next, the angle
[0040]
When the angles of the respective nodes are calculated in this manner, the traveling route
[0041]
FIG. 4 is a block diagram showing a configuration of a traveling route search apparatus that performs a traveling route search method according to another embodiment of the present invention.
[0042]
The traveling route search device shown in FIG. 4 is a method for determining the distance between nodes from a plurality of routes from an arbitrary start node to an end node different from the start node via a plurality of nodes in a road network including nodes and links connecting the nodes. A search unit for searching for a route that minimizes the cost of providing travel time and the like, that is, an
[0043]
Further, the
[0044]
Next, the operation of the traveling route searching apparatus thus configured will be described with reference to FIGS. 6 to 9 based on the flowchart shown in FIG.
[0045]
The
[0046]
In the specific node classification process shown in FIG. 6, for example, a start-end connection line 4-1 connecting a start-point node and an end-point node passes through a start-point node and an end-point node, and is connected to the start-end connection line 4-1. A start-side node group 4-4 in which nodes perpendicular to the start-point node side 4-2 and an end-point node side 4-3 are drawn, and nodes on the side without the end-point node from the start-point node side perpendicular 4-2 are grouped; An end node group 4-5 in which nodes on the side without the start node from the side perpendicular line 4-3 are collected, and the remaining nodes other than the start node, the end node, the start node group, and the end node group are collected. They are classified into intermediate node groups.
[0047]
Note that the node classification process is not limited to the above, and is within a certain distance from each of the start node and the end node in addition to the perpendicular such as the start node side normal 4-2 and the end node side normal 4-3. There are various methods such as classifying a node into a start node group and an end node group.
[0048]
When the node classification process is performed as described above, the start-point-side node group angle
[0049]
In FIG. 7, the starting node side perpendicular 4-2 is set as the X axis, the starting node is set as the center, and the angle between each node of the starting node group 4-4 and the X axis is between 0 ° and 180 °. I'm asking.
[0050]
Next, the starting point traveling circuit
[0051]
Next, the end point side node group angle
[0052]
In the angle calculation processing shown in FIG. 8, the perpendicular to the end point node side 4-3 is set as the X axis, the end point node is set as the center, and the angle between each node of the end point side node group 4-5 and the X axis is set to 0. I am looking for between {180}.
[0053]
Next, the end point traveling circuit
[0054]
As shown in FIG. 8, the sorting of the angles is performed in descending order from a node having a large angle to a node having a small angle, but may be performed in ascending order.
[0055]
Next, the intermediate node group traveling circuit
[0056]
In the generation of the intermediate node group traveling circuit shown in FIG. 9, a perpendicular line is dropped from each intermediate node to a start point-end point connection line 4-1 connecting the start point and the end point, and the normal line is connected to the start point-end point connection line 4-1. Each node of the intermediate node group is connected like a thick line in order from the one where the intersection is closer to the starting point, thereby generating an intermediate node group traveling circuit.
[0057]
Next, the full tour
[0058]
FIG. 10 is a flowchart showing a grouping process in a traveling route search method according to still another embodiment of the present invention.
[0059]
The grouping process of the embodiment shown in FIG. 10 improves the sorting method of the nodes and further increases the accuracy of the traveling route, and is shown in the traveling route
[0060]
The operation of the present embodiment will be described based on the flowchart shown in FIG. 10 and with reference to FIGS.
[0061]
In the process of FIG. 10, first, a group calculation process is performed (step S310). In this group calculation process, a node group is read out from the
[0062]
The grouping process shown in FIG. 11 is performed on an intermediate node group in which the start point and the end point are different, and groups having a small distance between adjacent nodes are grouped.
[0063]
In the grouping process in which the start point and the end point are the same, for example, the angle of the adjacent node is
α (360 / N) (α is a constant)
Group if.
[0064]
In the grouping process for the start-side node group in the case where the start point and the end point are different, for example, for the number N of nodes in the start-side node group,
α (360 / (N-1)) (α is a constant)
Group if.
[0065]
In the grouping process for the end point side node group in the case where the start point and the end point are different, for example, the angle of the adjacent node is set to the node number N of the end point side node group.
α (360 / (N-1)) (α is a constant)
Group if.
[0066]
In the grouping process for the intermediate node group in the case where the start point and the end point are different, for example, for each node number N of the intermediate node group, each intermediate point is connected to a start-end connection line (4-1) connecting the start point and the end point. The distance between the node perpendicular to the intersection of the node perpendicular to the node group (node perpendicular point) and the node perpendicular to the adjacent node is
(Equation 1)
α ((distance between start point and end point) / (N-1)) (α is a constant)
Group if. Note that α may be set so as to find the most efficient solution.
[0067]
After the grouping process is performed as described above, the in-group traveling route generation process is performed next (step S320). In the intra-group traveling route generation processing, as shown in FIG. 12, the node having the smallest sort value in the group is set as the start point in the group, the node farthest from the start point in the group is set as the end point in the group, and The traveling route search method according to the embodiment shown in FIGS. 1 and 4 is applied to each of the nodes within the group to generate an intra-group traveling route and to connect to the preceding and succeeding nodes already sorted outside the group. is there.
[0068]
In the start point and end point calculation processing in the group shown in FIG. 12, the node 4 farthest from the start point in the group is set as the end point in the group.
[0069]
【The invention's effect】
As described above, according to the present invention, in the present invention described in
[0070]
According to the present invention,Find the center of gravity of the polygon connecting the nodes, find the angle from the starting point to each node around the center of gravity, connect each node from the starting point node in ascending order of angle to generate a traveling circuit, and configure the traveling circuit In each of the nodes, the nodes in which the angle between adjacent nodes is smaller than a predetermined value are put together to form a group, and the traveling route search apparatus according to
[0071]
Furthermore, according to the present invention,In each of the nodes constituting each tour generated by the start point side tour generator, the end point side tour generator, and the intermediate node group tour generator, a group that collectively sets nodes satisfying a predetermined condition and sets a group Since the setting means and the traveling route search apparatus according to
[Brief description of the drawings]
FIG. 1 is a block diagram illustrating a configuration of a traveling route search device that performs a traveling route search method according to an embodiment of the present invention.
FIG. 2 is a flowchart showing the operation of the traveling route search apparatus shown in FIG.
FIG. 3 is an explanatory diagram showing an angle calculation process in the traveling route search device shown in FIG. 1;
FIG. 4 is a block diagram illustrating a configuration of a traveling route search device that performs a traveling route search method according to another embodiment of the present invention.
FIG. 5 is a flowchart showing an operation of the traveling route searching device shown in FIG. 4;
FIG. 6 is an explanatory diagram showing a method of dividing the traveling route searching apparatus shown in FIG. 4 into a starting point side node group, an ending point side node group, and an intermediate node group.
FIG. 7 is an explanatory diagram showing an angle calculation process and a traveling route generation process in a starting point side node group in the traveling route searching device shown in FIG. 4;
FIG. 8 is an explanatory diagram showing an angle calculation process and a traveling route generation process in an end point side node group in the traveling route searching device shown in FIG. 4;
9 is an explanatory diagram showing a traveling route generation process in an intermediate node group in the traveling route searching device shown in FIG. 4;
FIG. 10 is a flowchart showing the operation of still another embodiment of the present invention.
11 is an explanatory diagram showing a grouping process for an intermediate node group in the embodiment shown in FIG.
12 is an explanatory diagram showing a start point and end point calculation process in a group in the embodiment shown in FIG. 10;
[Explanation of symbols]
3,23 control unit
9 Center of gravity calculation processing unit
11 Angle calculation processing unit
13 Traveling circuit generation processing unit
29 Node classification processing unit
31 Start point side node group angle calculation processing unit
33 starting point traveling circuit generation processing unit
35 End point node group angle calculation processing unit
37 end point traveling circuit generation processing unit
39 Intermediate node group circuit generation processing unit
41 Full circuit generation processing unit
Claims (3)
始点ノードと終点ノードを結んだ線分に対して、始点ノードを通り前記線分に直交する始点ノード側垂線、および終点ノードを通り前記線分に直交する終点ノード側垂線をそれぞれ引き、前記始点ノード側垂線に対して終点ノードと反対側に存在するノードをまとめた始点側ノード群と、前記終点ノード側垂線に対して始点ノードと反対側に存在するノードをまとめた終点側ノード群と、始点ノード、終点ノード、始点側ノード群、終点側ノード群以外の中間ノード群とに分類するノード分類手段と、
始点から始点側ノード群の各ノードまでの角度を求める始点側ノード群角度算出手段と、
前記角度をソートし、始点ノードから角度の順に始点側ノード群の各ノードを結んで始点側巡回路を生成する始点側巡回路生成手段と、
終点から終点側ノード群の各ノードまでの角度を求める終点側ノード群角度算出手段と、
前記角度をソートし、終点ノードから角度の順に終点側ノード群の各ノードを結んで終点側巡回路を生成する終点側巡回路生成手段と、
始点と終点を結ぶ線分に対して前記中間ノード群の各ノードから垂線を下ろし、始点と終点を結ぶ線分と各垂線との交点が始点に近い方から順に中間ノード群の各ノードを結んで中間ノード群巡回路を生成する中間ノード群巡回路生成手段と、
前記始点側巡回路、中間ノード群巡回路および終点側巡回路の順に巡回路を結んで始点から終点までの巡回路を生成する全巡回路生成手段と
を有することを特徴とする巡回路探索装置。Minimize the cost of providing the distance, travel time, etc. between nodes from multiple routes from an arbitrary start node to an end node different from the start node via multiple nodes in a road network consisting of nodes and links connecting the nodes A route search device for searching for an approximate solution of a path
For the line segment connecting the start point node and the end point node , a perpendicular line to the start node passing through the start node and perpendicular to the line segment, and a perpendicular line to the end node passing through the end node and perpendicular to the line segment are respectively drawn, A start-side node group in which the nodes existing on the opposite side to the end node with respect to the node-side perpendicular, and an end-point side node group in which the nodes existing on the opposite side to the start node with respect to the end-node side perpendicular , Node classification means for classifying into a start node, an end node, a start node group, and an intermediate node group other than the end node group;
A starting-point-side node group angle calculating means for determining an angle from the starting point to each node of the starting-side node group;
A starting point traveling circuit generating unit that sorts the angles and connects the nodes of the starting node group in the order of angles from the starting node to generate a starting circuit;
End point side node group angle calculating means for obtaining an angle from the end point to each node of the end point side node group,
An end point traveling circuit generating means for sorting the angles and connecting each node of the end point node group in the order of the angle from the end point node to generate an end point traveling circuit;
A perpendicular line is drawn down from each node of the intermediate node group with respect to a line segment connecting the start point and the end point, and each node of the intermediate node group is connected in order from an intersection of the line segment connecting the start point and the end point and each perpendicular line near the start point. An intermediate node group circuit generating means for generating an intermediate node group circuit in;
A complete circuit generating means for generating a circuit from a start point to an end point by connecting a circuit in the order of the starting point side circuit, the intermediate node group circuit and the end point side circuit; .
巡回するすべてのノードを結んだ多角形の重心を求める重心算出手段と、
前記重心を中心として、始点から各ノードまでの角度を求める角度算出手段と、
前記角度をソートし、始点ノードから角度の小さい順に各ノードを結んで巡回路を生成する巡回路生成手段と
を有し、
前記巡回路生成手段は、
該巡回路生成手段により生成された巡回路を構成する各ノードにおいて、隣り合うノード間の角度が所定値より小さいノードをまとめて、グループを設定するグループ設定手段と、
該グループを構成する各ノードにおいて、前記ソート値が最も小さいものをグループ内始点とし、該始点から最も遠いノードをグループ内終点とするグループ内始点終点設定手段と、
前記グループ内始点とグループ内終点を結んだ線分に対して、グループ内始点を通り前記線分に直交する始点ノード側垂線、およびグループ終点を通り前記線分に直交する終点ノード側垂線をそれぞれ引き、前記始点ノード側垂線に対してグループ内終点と反対側に存在するノードをまとめたグループ内始点側ノード群と、前記終点ノード側垂線に対してグループ内始点と反対側にあるノードをまとめたグループ内終点側ノード群と、グループ内始点、グループ内終点、グループ内始点側ノード群、グループ内終点側ノード群以外のグループ内中間ノード群とに分類するグループ内ノード分類手段と、
グループ内始点からグループ内始点側ノード群の各ノードまでの角度を求めるグループ内始点側ノード群角度算出手段と、
前記角度をソートし、グループ内始点ノードから角度の順にグループ内始点側ノード群の各ノードを結んでグループ内始点側巡回路を生成するグループ内始点側巡回路生成手段と、
グループ内終点からグループ内終点側ノード群の各ノードまでの角度を求めるグループ内終点側ノード群角度算出手段と、
前記角度をソートし、グループ内終点ノードから角度の順にグループ内終点側ノード群の各ノードを結んでグループ内終点側巡回路を生成するグループ内終点側巡回路生成手段と、
グループ内始点とグループ内終点を結ぶ線分に対して前記グループ内中間ノード群の各ノードから垂線を下ろし、グループ内始点とグループ内終点を結ぶ線分と各垂線との交点がグループ内始点に近い方から順にグループ内中間ノード群の各ノードを結んでグループ内中間ノード群巡回路を生成するグループ内中間ノード群巡回路生成手段と、
前記グループ内始点側巡回路、グループ内中間ノード群巡回路およびグループ内終点側巡回路の順に巡回路を結んでグループ内始点からグループ内終点までの巡回路を生成するグループ内全巡回路生成手段と
を有することを特徴とする巡回路探索装置。 In a road network consisting of nodes and links connecting the nodes, from a plurality of routes from an arbitrary start node to the start node again via a plurality of nodes, a route which minimizes the cost of providing distances between nodes, travel time, etc. A traveling route search device for searching for an approximate solution,
A center of gravity calculating means for obtaining a center of gravity of a polygon connecting all the circulating nodes;
Angle calculation means for obtaining an angle from the starting point to each node with the center of gravity as a center,
A traveling route generating means for sorting the angles and connecting each node from a starting point node in ascending order of angle to generate a traveling route;
Has,
The traveling route generating means includes:
A group setting unit configured to collectively set, at each of the nodes constituting the tour generated by the tour generation unit, a node in which the angle between adjacent nodes is smaller than a predetermined value;
In each of the nodes constituting the group, a group start point / end point setting unit that sets a node having the smallest sort value as a group start point, and sets a node farthest from the start point as a group end point,
For a line segment connecting the start point in the group and the end point in the group , a perpendicular to the start node side passing through the start point in the group and orthogonal to the line segment, and a perpendicular to the end node side passing through the end point of the group and orthogonal to the line segment, respectively. A group in which the nodes existing on the side opposite to the end point in the group with respect to the vertical line on the start node side are grouped, and the nodes on the side opposite to the start point in the group with respect to the vertical line on the end node side are grouped together. Intra-group end-point nodes in the group, and intra-group start-points, intra-group end-points, intra-group start-side nodes, and intra-group node classification means for classifying into intra-group intermediate nodes other than the intra-group end-side nodes.
An in-group start-point-side node group angle calculating means for obtaining an angle from the in-group start point to each node of the in-group start-point-side node group;
Sorting the angles, in-group start-point traveling circuit generating means for connecting each node of the group-in-start-side node group in order of angle from the in-group start-point node to generate an in-group start-point-side traveling circuit,
An intra-group end-point node group angle calculating means for obtaining an angle from the intra-group end point to each node of the intra-group end-point node group,
Sorting the angles, in-group end-point traveling circuit generating means for generating an intra-group end-point traveling circuit by connecting each node of the intra-group end-point node group in the order of the angle from the intra-group end-point node;
A perpendicular line is drawn from each node in the group of intermediate nodes in the group to a line segment connecting the start point in the group and the end point in the group, and the intersection of the line segment connecting the start point in the group and the end point in the group and each perpendicular line is set as the start point in the group. An intra-group intermediate node group traveling means for connecting each node of the intra-group intermediate node group in order from the closest to generate an intra-group intermediate node group traveling circuit;
Means for generating a whole circuit within a group for connecting a circuit from the start point in the group, the intermediate node group in the group, and the end point in the group in order to generate a circuit from the start point in the group to the end point in the group And a traveling route searching device.
これらの各手段により生成された各巡回路を構成する各ノードにおいて、所定の条件を満たすノードをまとめて、グループを設定するグループ設定手段と、
該グループを構成する各ノードにおいて、前記ソート値が最も小さいものをグループ内始点とし、該始点から最も遠いノードをグループ内終点とするグループ内始点終点設定手段と、
前記グループ内始点とグループ内終点を結んだ線分に対して、グループ内始点を通り前記線分に直交する始点ノード側垂線、およびグループ内終点を通り前記線分に直交する終点ノード側垂線をそれぞれ引き、前記始点ノード側垂線に対してグループ内終点と反対側に存在するノードをまとめたグループ内始点側ノード群と、前記終点ノード側垂線に対してグループ内始点と反対側にあるノードをまとめたグループ内終点側ノード群と、グループ内始点、グループ内終点、グループ内始点側ノード群、グループ内終点側ノード群以外のグループ内中間ノード群とに分類するグループ内ノード分類手段と、
グループ内始点からグループ内始点側ノード群の各ノードまでの角度を求めるグループ内始点側ノード群角度算出手段と、
前記角度をソートし、グループ内始点ノードから角度の順にグループ内始点側ノード群の各ノードを結んでグループ内始点側巡回路を生成するグループ内始点側巡回路生成手段と、
グループ内終点からグループ内終点側ノード群の各ノードまでの角度を求めるグループ内終点側ノード群角度算出手段と、
前記角度をソートし、グループ内終点ノードから角度の順にグループ内終点側ノード群の各ノードを結んでグループ内終点側巡回路を生成するグループ内終点側巡回路生成手段と、
グループ内始点とグループ内終点を結ぶ線分に対して前記グループ内中間ノード群の各ノードから垂線を下ろし、グループ内始点とグループ内終点を結ぶ線分と各垂線との交点がグループ内始点に近い方から順にグループ内中間ノード群の各ノードを結んでグループ内中間ノード群巡回路を生成するグループ内中間ノード群巡回路生成手段と、
前記グループ内始点側巡回路、グループ内中間ノード群巡回路およびグループ内終点側巡回路の順に巡回路を結んでグループ内始点からグループ内終点までの巡回路を生成するグループ内全巡回路生成手段とを有し、
前記始点側巡回路生成手段および前記終点側巡回路生成手段の前記グループ設定手段は、隣り合うノード間の角度が所定値より小さいノードをまとめて、グループを設定する手段を有し、
前記中間ノード群巡回路生成手段の前記グループ設定手段は、中間ノード群における各ノードから始点と終点を結ぶ線分に垂線を下ろした点の中で隣り合う点間の距離が所定値より小さいノードをまとめて、グループを設定する手段を有することを特徴とする請求項１記載の巡回路探索装置。The starting point traveling circuit generating means, the end point traveling circuit generating means, and the intermediate node group traveling circuit generating means,
A group setting unit configured to collectively set nodes satisfying a predetermined condition and set a group at each node configuring each traveling route generated by each of these units;
In each of the nodes constituting the group, a group start point / end point setting unit that sets a node having the smallest sort value as a group start point, and sets a node farthest from the start point as a group end point,
For the line segment connecting the start point in the group and the end point in the group , a perpendicular to the start node side passing through the start point in the group and orthogonal to the line segment, and a perpendicular to the end point node perpendicular to the line segment through the end point in the group. Each of the nodes is referred to as a group in which the nodes present on the opposite side to the end point in the group with respect to the perpendicular to the start node side are grouped. Grouped node grouping means for classifying the grouped end point group in the group, and the group start point, the group end point, the group start point node group, and the group intermediate node group other than the group end point node group,
An in-group start-point-side node group angle calculating means for obtaining an angle from the in-group start point to each node of the in-group start-point-side node group;
Sorting the angles, in-group start-point traveling circuit generating means for connecting each node of the group-in-start-side node group in order of angle from the in-group start-point node to generate an in-group start-point-side traveling circuit,
An intra-group end-point node group angle calculating means for obtaining an angle from the intra-group end point to each node of the intra-group end-point node group,
Sorting the angles, in-group end-point traveling circuit generating means for generating an intra-group end-point traveling circuit by connecting each node of the intra-group end-point node group in the order of the angle from the intra-group end-point node;
A perpendicular line is drawn from each node in the group of intermediate nodes in the group to a line segment connecting the start point in the group and the end point in the group, and the intersection of the line segment connecting the start point in the group and the end point in the group and each perpendicular line is set as the start point in the group. An intra-group intermediate node group traveling means for connecting each node of the intra-group intermediate node group in order from the closest to generate an intra-group intermediate node group traveling circuit;
Means for generating a whole circuit within a group for connecting a circuit from the start point in the group, the intermediate node group in the group, and the end point in the group in order to generate a circuit from the start point in the group to the end point in the group And having
Wherein said group setting means starting point side traveling route generation means and the end point traveling route generation means comprises means for angle between adjacent nodes is collectively less nodes than a predetermined value, sets a group,
The group setting means of the intermediate node group traveling circuit generating means includes a node having a distance between adjacent points smaller than a predetermined value among points drawn perpendicular to a line connecting the start point and the end point from each node in the intermediate node group. 2. The traveling route searching apparatus according to claim 1, further comprising means for setting a group by grouping.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP5500997A JP3596650B2 (en) | 1997-03-10 | 1997-03-10 | Tour search device |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP5500997A JP3596650B2 (en) | 1997-03-10 | 1997-03-10 | Tour search device |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH10253374A JPH10253374A (en) | 1998-09-25 |
| JP3596650B2 true JP3596650B2 (en) | 2004-12-02 |
Family
ID=12986667
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP5500997A Expired - Fee Related JP3596650B2 (en) | 1997-03-10 | 1997-03-10 | Tour search device |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3596650B2 (en) |
Families Citing this family (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP3534392B2 (en) * | 1999-12-28 | 2004-06-07 | 日立ソフトウエアエンジニアリング株式会社 | Optimal delivery planning method and system |
| US6587785B2 (en) * | 2001-09-21 | 2003-07-01 | General Motors Corporation | Method and system for mobile vehicle re-routing |
| JP2021148688A (en) * | 2020-03-23 | 2021-09-27 | 三菱電機株式会社 | Route searching device and route searching method |
| CN117928566B (en) * | 2024-03-21 | 2024-07-12 | 华南农业大学 | Agricultural machinery driving path planning method, agricultural machinery driving path planning equipment, agricultural machinery driving medium and agricultural machinery driving path planning product |
-
1997
- 1997-03-10 JP JP5500997A patent/JP3596650B2/en not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JPH10253374A (en) | 1998-09-25 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Jagadeesh et al. | Heuristic techniques for accelerating hierarchical routing on road networks | |
| US11320275B2 (en) | Method for producing alternative route suggestions | |
| US5893081A (en) | Using multiple levels of costs for a pathfinding computation | |
| JP5448827B2 (en) | Method and apparatus for generating a route | |
| EP2645063A1 (en) | Path searching method and path search device | |
| US20040088392A1 (en) | Population mobility generator and simulator | |
| JP5668380B2 (en) | Route search apparatus and program | |
| CN107063278A (en) | A kind of Vehicular navigation system, air navigation aid and its vehicle | |
| EP2639553A1 (en) | Path searching method and path search device | |
| Shafahi et al. | Solving the school bus routing problem by maximizing trip compatibility | |
| Aissat et al. | Dynamic ridesharing with intermediate locations | |
| JP3596650B2 (en) | Tour search device | |
| Kanoh et al. | Route guidance with unspecified staging posts using genetic algorithm for car navigation systems | |
| US5778155A (en) | Method and apparatus for selecting among competing facts to achieve the desired calculation | |
| Murakami | A generalized model and a heuristic algorithm for the large-scale covering tour problem | |
| CN112667925B (en) | Route recommendation method and device, computer equipment and storage medium | |
| CN112748452B (en) | GPS track cleaning method based on road network data | |
| JP2000193470A (en) | Route searching device and method and medium storing program for route searching | |
| D'Andrea et al. | Path clustering based on a novel dissimilarity function for ride-sharing recommenders | |
| JPH11118501A (en) | Optimum route searching method | |
| Li et al. | Hierarchical model of road network for route planning in vehicle navigation systems | |
| CN108204820B (en) | Quick navigation path conjecture method | |
| CN111414437A (en) | Method and device for generating line track | |
| JPH05107073A (en) | Guiding device of recomended route | |
| Kanoh et al. | Evaluation of GA-based dynamic route guidance for car navigation using cellular automata |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20040331 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20040420 |
|
| A521 | Written amendment |
Effective date: 20040610 Free format text: JAPANESE INTERMEDIATE CODE: A523 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Effective date: 20040803 Free format text: JAPANESE INTERMEDIATE CODE: A01 |
|
| RD01 | Notification of change of attorney |
Effective date: 20040901 Free format text: JAPANESE INTERMEDIATE CODE: A7426 |
|
| A61 | First payment of annual fees (during grant procedure) |
Effective date: 20040901 Free format text: JAPANESE INTERMEDIATE CODE: A61 |
|
| R150 | Certificate of patent (=grant) or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (prs date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080917 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (prs date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080917 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (prs date is renewal date of database) |
Year of fee payment: 5 Free format text: PAYMENT UNTIL: 20090917 |
|
| LAPS | Cancellation because of no payment of annual fees |