JPH02304587A - 最短距離、最短時間または最低交通費算出装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 λ胛夏亘狗 ［産業上の利用分野］ 本発明は最短距離、　最短時間または最低交通費算出装
置に関し、特にニューラルネットワークを利用した最短
距離、　最短時間または最低交通費算出装置に関する。

［従来の技術］ 従来、いわゆるセールスマンの巡回問題としてコンピュ
ータ上の処理の限界を示す課題が存在する。例えＩｆ、
　　−人のセールスマンが１０都市を巡回するものとし
て、その最短経路を捜す場合、単純゛に順列組合を実施
すると、全ての組合せは１０！／２：１，８１４，４０
０通り有り、それらの経路をすべてチェックし記憶して
おくことは膨大な時間とメモリとを必要とし実際的では
ない。このような装置は携帯してこそ役に立つのである
が、上記のような理由から小型化・軽量化することが　
　′出来ず、また解を得るまでに時間がかかり即応性に
欠けるので、その必要性は認めつつもほとんど利用され
ていない。従って、セールスマンに限らず、各種の地域
調先　選挙演説会場巡回、選挙カーの巡回等の各種の巡
回訪問において、無駄な時間・費用・労力・エネルギー
を費やすこととなつこの巡回問題を小型のコンピュータ
にて迅速に解を求めることが出来るものとして、ニュー
ラルネットワークを利用したものが提案されている（宮
沢丈夫：実践！ニューラルネット、ＡＳＣＩＩ　ＶＯＬ
、１３、Ｎｏ、　１．１９８９、合原−幸二二ューラル
コンピュータ。

東京電機大学出版局、１９８８、その他）。

これらはノイマン型デジタルコンピュータによるシミュ
レーションにて実施している。即ち、各都市と訪問順序
とに基づいて設定されたニューロンにシナプス荷重を設
定し、ニューラルネットの結合に基づいて各ニューロン
の状態を変化させてゆき、最後に収束した状態から発火
しているニューロンを求めて、最適な巡回順序を得ると
いうものであっｈ　この様なニューラルネットはホップ
フィールド、ボルツマンマシンあるいはガウシアンマシ
ンのモデルとして知られているものである。

このモデルによれ（戯　膨大な組合を検討する必要はな
く時間的にもきわめて短い時間で、最適な解を出力でき
る。従って、このモデルを小型のコンピュータに適用す
れ（ｆ−、重量、大きさ及び処理時間の点で実際に利用
可能な装置となると考えられる。

［発明が解決しよ−うとする課題］ しかし、実際の巡回に利用するために（上　更に次なる
課題を解決する必要があった　即ち、実際には、各巡回
地点間は直線で移動可能とは限らないので、巡回地点の
位置ばかりでなく、地点間の距離を入力しなくてはない
。しかもその経路は１つとは限らない。この作業は実際
の地図から曲線である道路の距離を測定してからその値
を入力することを意味し、きわめて煩雑な時間のかかる
作業を使用者に要求することになる。　地点間のデータ
が距離でなく、移動時間や交通費であっても同様である
。これではニューラルネットワークを利用する意味がな
くなる。

ｌ用立逍威 本発明はこの課題を解決し、訪問位置とその間の距離、
　時間または交通費データの入力の困難性を解消して、
ニューラルネットワークの有用性・迅速性を発揮させる
最短距既　最短時間または最低交通費算出装置を提供す
ることを目的とするものである。

［課題を解決するための手段］ 上記課題を解決するために採用された本発明の構成は次
のごとくである。即ち、第１図に例示するごとく、 地図Ｍ１と、 地図Ｍ１上をタッチすることにより任意の地点の位置デ
ータを入力できる位置入力手段Ｍ２と、地図Ｍ１上の経
路データとその距離、　時間または交通費データとを記
憶する記憶手段Ｍ３と、記憶手段Ｍ３に記憶されたデー
タから、入力された各地点間の最短距離、　最短時間ま
たは最低交通費データを選択する選択手段Ｍ４と、選択
手段Ｍ４にて選択された各地点間の距既時間または交通
費データを用いて、ニューラルネットワークの手法に基
づき、全地点を訪問した場合に最短路１　最短時間また
は最低交通費となる地点訪問順序の最適解を求める演算
手段Ｍ５と、この最適解として求められた地点訪問順序
をその実際の道路に適合させた経路と共に地図Ｍ１上に
表示する表示手段Ｍ６と、 を備えたことを特徴とする。

［作用〕 本発明（飄　特に選択手段Ｍ４が、記憶手段Ｍ３に記憶
されたデータから、入力された各地点間の最短距離、　
最短時間または最低交通費データを選択している。従っ
て、本装置の利用者（友　単に地図上の訪問地点をタッ
チして指示するだけで、実際の経路に即したデータが自
動的に用意さ札　その後は演算手段Ｍ５がニューラルネ
ットワークの手法に基づいて、最短距既　最短時間また
は最低交通費となる地点訪問順序の最適解を迅速に求め
二のように利用者は各地点間の実際の距既　時間または
交通費を調べて最短・最低のものを見つけなくとも、自
動的に実際に即した経済的省力的な経路が得ら札　その
データを用いて適切な訪問順序色得ることが出来る。

［実施例］ 第２図に本発明の最短距既　最短時間または最低交通費
算出装置の第１実施例を示す。本装置は携帯用にカード
型として構成されたものである。

この最短距既　最短時間または最低交通費算出装置１（
よ　いわゆるシステム手帳にファイルできるように柔軟
なシート３をその一辺に備えている。

このシート３がバインダ用の係合孔３ａを有しているた
め、システム手帳に綴じ込むことが可能であり、携帯性
永発揮する。

本算出装置１（よ　その−面１：、表示用の液晶パネル
（ＬＣＤ）５、指示入力用キー７８〜７ｍ及び電源スィ
ッチ９が配置されている。また、ＬＣＤ５の表面には透
明なタッチパネル１１が配置されている。

この内部構成は第３図のブロック図に示すごとく、マイ
クロコンピュータ１２として構成さ札主要部はＣＰＵ１
３．ＲＯＭ１５．ＲＡＭ１７゜及びＲＯＭカード１９を
備えると共ｌ：、指示入力用キー７ａ〜７ｍ、ＬＣＤ５
及びタッチパネル１１の入出力回路２］を備えている。

これらの構成はバス２３にて送受信可能に接続されてい
る。

第４図のフローチャートに第１実施例の処理在来す０本
処理は電源スィッチ９がオンされた以後に繰り返し実行
される。

処理が開始されると、まず初期設定がなさ札各種変数や
フラグの初期値が設定される（ステップ１１０）。次に
キー入力待となる（ステップ１２０）。ここで地図選択
キー７ノが押されると、ＬＣＤ５に地域のメニューが表
示される（ステップ１３０）。メニューに基づいて所定
の地域を選択すると、その地域の地図がＬＣＤ５に表示
される（ステップ１４０）、　　次にキー入力待となる
（ステップ１５０）。ここでスクロールキー７　ｃ。

７ｆ、　　７ｉ、７ｍが押されれ（戴　キーに表示され
た矢印方向にＬＣＤ５に表示された地図がスクロールす
る（ステップ１６０）。従って、ＬＣＤ５自体は一度に
は限られた地域しか表示できないが、スクロールすれば
幾らでも広い地域の地図を確認でき、正確な指示入力を
することが出来る。

次に訪問他人カキ−７ａが押されると、タッチパネル１
１からの地点の読込が開始される（ステップ１７０）。

ＬＣＤ５による地図の表示位置とタッチパネル１１の検
出地域範囲とは連動して常に一致するように演算されて
いるので、地図を見ながら該当位置をペンで押圧すれ（
ヱ　地図上の地点が訪問地点として入力されることにな
る。勿詭このステップ１７０の処理中もスクロールキー
７ｃ、７ｆ、７ｉ、７ｍで地図のスクロールは可能であ
る。

終了キー７ｇが押されるまで、訪問地点が入力可能とさ
札　終了キー７ｇが押されると（ステップ１８０）、入
力した地点を確認するための表示がなされる（ステップ
１９０）。訂正が有れば訂正キー７ｈを押せば（ステッ
プ２００）再度タッチパネル１１からの地点の読込が開
始される（ステップ１７０）。

次に、処理の種類の指示が求められる（ステップ２１０
）。即ち、最短距飄　最短時間または最低交通費のいず
れを求めるかがメニューでＬＣＤ５に表示される。最短
距離キー７ｂを押せ（戯　ステップ１７０にて入力した
各地点間の移動のための最短距離がＲＯＭ１５あるいは
ＲＯＭカード１９に記憶されている経路データから、各
地点間を結ぶ実際の道路をチェックして、最短距離の経
路を検索して記憶する。この検索の仕方は例えば次の様
に実施される。

即ち経路が実線と破線で表される第８図の２地点　Ｐ、
、　　Ｐ２間の最短距離の経路を求める場合、Ｐ、が存
在する経路Ｔ、−Ｔ２をＰ、で２つに分割し、いずれの
経路が地点Ｐ、がらみてＰ２に近付くことになるのかを
判定する０図ではＰ　＋　−Ｔ　＋もＰ、−Ｔ２も近付
くか離れるかについては大きな差はないので、両方が選
択される。次に経路の末端Ｔ、、Ｔａから出ている経路
のべ　いずれがＰ２に近付くかを判定する。こうして選
択して行くと、実線で示したごとく、　■ｐ　、−Ｔ　
、−Ｔ　３−Ｔ　ａ　−Ｔ、−Ｐ２．　　■Ｐ＋−Ｔ＋
＝Ｔ３−Ｔｓ−Ｔ、　Ｔａ−Ｐ　２＋　　■　Ｐ　＋−
Ｔ　ｅ−Ｔ　ｖ−Ｔ　ｓ−Ｔ　ｏ−Ｐ　２の３つ経路が
選び出される。このうち最短距離１よ　■Ｐ、−Ｔ＋−
Ｔ３＝Ｔ４　Ｔａ　　Ｐ２であることが各経路の距離を
加算することにより判明する。

同様に最短時間キー７ｄまたは最低交通費７ｅを押せ（
戯　それぞれ各地点間の移動のための経路を１つまたは
２つ以上求めて、その内で、最短時間または最低交通費
となる経路を見つけ記憶する（ステップ２３０，２４０
）。この２地点間の組合せＩＬ　　例えば１０地点であ
れば１０Ｘ９／２＝４５通りであり、４５回の検索処理
でよいことになるので処理も短い時間で済む。またメモ
リに４５個のデータを記憶しておくだけでよく、メモリ
容量も少なくて済む。

次にこれらのデータに基づいて、ニューラルネットが構
成される（ステップ２５０）、　　ホップフィールドの
モデルに基づくと次のようになされる。

勿＾　他のモデルであるボルツマンマシンあるいはガウ
シアンマシンを適用してもよい、尚、このモデルによる
演算式の導出は良く知られているので、以下の説明では
式を導くための詳細な計算は省略する。ただし演算式自
体は予め求めてＲ２Ｍ１７またはＲＯＭカード１９中に
格納されているので、ニューラルネットの構成にあたっ
てはニューロンの数及び必要に応じて各定数を決定すれ
ばよい。

ｉ１目のニューロンの出力Ｖｉは次のように表される。

Ｖ＋＝　（１／２）　　・（１＋　ｔａｎｈ　（ｘ／　
μｓ）　ｌ　−（１）ただし、　Ｘ＝ΣＴ　＋、ｉＶ　
４＋１　＋Ｉ寥ｉ Ｎ：ニューロンの故　例えば１０地点であれば１０地点
を行に対応させ、訪問順位を列に対応させた１０×１０
のマトリックスで表される１００個のニューロンを用い
る。

王、９．：　　ｊ番目のニューロンからｊ番目のニュー
ロンへのシナプス荷Ｌ　ただしＴ、、、＝Ｏ０ｌ、：　
　ｊ番目のニューロン固有の閾（ＬＬμａ：ニューロン
の入出力関係を決める定仇更にシナプス荷重が対称性を
有すると、Ｔ、、、＝■４，１であり、各ニューロンは
非同期に状態を替え得るとすると、エネルギーＥが次の
ように定義される。

このエネルギーＥはニューロンの状態変化にともなって
、自発的に減少して行く性質を有することが耽にホップ
フィールドにより証明されている。

式（２）をＸ成分とＹ成分とを有するニューロンの２次
元配列に表すと、エネルギーＥは次のように表される。

次に［各地点は１度だけ訪問する」、　「同時に２地点
を訪問することはない」との条件から、次なる評価関数
が求められる。

２　　　　Ｘ＋ ここでＡ、　　Ｂ、　　Ｃは定数である。

更に巡回経路の総和は下式で表される。

２　　×　Ｉ　Ｙ ・・・（５） ただし、　ｄｘｘ＝ｏ、Ｄは定数である。

従って、Ｅ　ＥＥ　Ｅ　Ｉ十Ｅ　２とすると、中間の処
理は省略するが、下式のごとく整理される。

”ｘ＋、ｖｌ＝Ａδｘｙ（１−δ１ｊ）−Ｂδ１．（１
−δ８．） Ｃ Ｄｄｘｖ（δｊ、＋４１＋δＪ、１−１）・・・　（６
） ｌ　Ｘ、：Ｃｎ　　　　　　　　　　−（７）ただし−
≠ｊのときδ、、＝＝Ｑ、　　ｉ＝ｊのときδ１ｊ＝１
である。

次にデジタルコンピュータに適用するため１：。

時間的に離散化し、デジタル的なモデルを求めると、前
記式（１）は次のようになる。

Ｖｘ＋（ｋ）＝　（１／２）　・（１＋ｔａｎｈ　（Ｕ
ｘ＋（ｋ）／　ｕｓ）　１・・・（９） 前記（６）、　　（７）式を上記（８）、　　（９）式
に代入することにより、下式が求められる。

−ＤΣｄｘ”ｖ　（ＶＹ、ｌ−１（ｋ　　１）　　＋Ｖ
ｙ、１−＋　（ｋ　　Ｉ）　　１・・・　（１０） Ｖｘ＋（ｋ）＝　　（１／２）　　・（１＋ｔａｎｈ　
（ｔＪｘ＋（ｋ）／　ｕｓ）　１・・・　（１１） こうして巡回用のニューラルネット入出力関数が完成す
る。

このｎ　　ｖｘ＋（ｋ）、　　Ｕｘ＋（ｋ）（７）初期
値ＶＸ＋（Ｏ）。

Ｕ　ｘ＋（０）について１上　手法が確立されていない
ので、適当と思われる値を設定しても良いし、実際に演
算させてみて、予め適当と考えられる値を決定しておい
てもよい。定数ｎ、　　Ａ、　　Ｂ、　　Ｃ，Ｄ。

μ９についても同様である。

そして、二〇ニューラルネット入出力関数（１０）、　
　（１１）のｋをインクリメントしながら、順次計算し
て各ニューロンの状態Ｖ□（ｋ）が収束するのを検出す
る（ステップ２６０）。ｋの所定回数のインクリメント
及び計算の後、各列・各行に発火したニュＯ’／　（Ｖ
ｘ＋（ｋ）　＞０．　８）が各１つになった場合に収束
したものと判断する（ステップ２７０）。収束していな
けれ（Ｌ　ニューロンの発火状況に合わせて各定数を適
当に変更して（ステップ２８０）、再度計算しなおす。

収束した場合、各列１を順番に読んで行き、各列１ぞ発
火している訪問地番号Ｘを順にＲＡＭｌ１中の配列、に
格納し、訪問地の訪問順序を得る（ステップ２９０）。

次にＬＣＤ５に表示した地図上の訪問地に識別できるマ
ークを表示する。例えば訪問順に■■■・・・といった
表示を行う。更にその訪問地間にステップ２２０〜２４
０にて検索しておいた最短距離、　最短時間または最低
交通費の経路のへ　訪問の順序に治ったものだけが表示
される（ステップ）。

次いで、キー入力待となり（ステップ３１０）、１次の
処理」のキー７ｋが押されれ１ｆＳ　　ステップ１２０
の処理に戻る。　「終了」のキー７ｇが押されれば処理
は終了する。

この様にして最適な経路が判明し、時は　労力、エネル
ギー、経費の無駄なく経路を巡回することが可能となる
。

第２実施例として交通手段を選択するステップを備え、
その交通手段での各地点間の最短距限最短時間または最
低交通費データを選択するようにしてもよい。

例え（戯　第４図のフローチャートのステップ２００と
ステップ２１０との間１：、第５図に示す処理を実施す
ることにより、交通手段を選択することが８来る。即ち
、■徒歩■自動車■公共交通機関（バス、電車等）とい
ったメニューをＬＣＤ５に表示し、スクロールキー７ｃ
、　　７ｆ、　　７ｉ、　　７ｍにてカーソルを移動さ
せていずれかを選択させる（ステップ５１０）、　　そ
の結果により、ステップ２２０〜２４０にて用いられる
ＲＯＭ１５またはＲＯＭカード１９内のデータ群のポイ
ンタを切替る（ステップ５２０〜５４０）、　　このこ
とにより以後のステップ２２０〜２４０にて１表　ポイ
ンタの設定に応じて、徒歩、自動車あるいは公共交通機
関による移動の際の各地点間の距離１時ｒ８１交通費（
徒歩は通常無料）データが用いら札　その最短・最低の
値が選択される。

この様にして第２実施例によれば種々の交通手段にも対
応でき、単に選択するだけで自動車ばかりでなく徒歩、
電束　バスによる移動にても最適な解を得ることが出来
る。

第３実施例として、距離、　時間または金額データを入
力する制限データ入力ステップを備え、この制限データ
以内に到達できる地点も表示するようにしてもよい。例
え（戯　第４図のフローチャートのステップ２９０とス
テップ３００との１８１　　あるいはステップ３００の
直後に、第６図に示す処理を実施することにより、制限
データ以内に到達できる地点も表示することが出来る。

即ち、メニューにより制限データが距飄　時は　交通費
のいずれであるかということと、その値がいくつかとい
うことを入力させる（ステップ６１０）。それが［距離
Ｊで有れば出発点から現在の訪問地までの距離が、ステ
ップ２９０で求められた順番をたどって積算されていく
　（ステップ６２０）。現時点の積算距離が制限距離以
内と判定されれば（ステップ６３０）、次の訪問地の有
無が判定される（ステップ６４０）。有れば今の訪問地
と次の訪問地との間の距離が今までの積算値に加算され
る（ステップ６２０）。こうして制限距離以上の地点に
達するかあるいはその前に訪問地が終了すると、制限内
地点の表示がなされる（ステップ６５０）。この表示は
制限距離内と外とで、経路の表示パターンや色を変更し
てもよく。制限距離内に到達できない訪問地については
点滅表示として識別できるようにしてもよい。

他の制限データを設定した場合も同様であり、時間的制
限が有ればステップ６６０〜６８０の処理により、時間
的に巡回できない訪問地が判明する。また交通費的に制
限がある場合はステップ６９０〜７１０の処理により、
費用的に巡回できない訪問地が判明する。この制限デー
タの選択と、前に実行されているステップ２１０〜２４
０の選択とは別個のものであり、最短距離の経路を求め
から（ステップ２２０）その経路にて費用に合わせて到
達できる地点を確認できるしくステップ６９０〜７１０
，６５０）、最低の交通費となる経路を求めてから（ス
テップ２４０）その経路にて所定時間内に到達できる地
点が確認できる（ステップ６６０〜６８０．　６５０）
。勿浪　その他の組合せを選ぶこともできる。

このことにより、自分の持ち時ｒ８１　　自動車の修理
特販　あるいは所持金等の自己の能力にあわせて、計画
を立てて訪問することが可能となる。

第４実施例として、一部の経路を選択するステップを備
え、特定の経路は必ず通過するようにししたり、あるい
は逆に通過しないようにしてもよい。例えＩｔ　　第７
図に示すような処理（ステップ７５０〜７７０）をステ
ップ２００とステップ２１０との間に設けて、強制的に
排除あるいは通過する経路を指定する。即ち、経路に対
する指示が有るか否かとそれはどの地点間であるのかを
メニューにより入力させる（ステップ７５０）。有れ１
ｉ　　その地点間の経路を表示してスクロールキー７ｃ
、７ｆ、７ｉ、７ｍにてカーソルを移動させて経路を選
択させ、同時に排除か通過かを指示させる（ステップ７
６０）。更に他の地点間で指示する必要が有れば（ステ
ップ７７０）、ステップ７６０の処理に戻る。無ければ
次の「処理の種類」の選択（ステップ２１０）に移る。

この様に、経路に対して排除あるいは通過を指示できる
ので、工事中等で通行止めであったりする経路を避けた
適切な経路を得ることが出来き、臨機応変に対処できる
。また宣伝カーを兼ねている場合、宣伝が効果的である
経路を必ず通過するように出来る。

上記ステップ１７０にて地点の指示を実施したが指示点
が経路上の位置でなけれｌｆ、　　指示地点から一番近
い経路上の一番近い地点を用いて以後の処理を実施すれ
ばよい。

上記各実施例で、更に各地点間または全地点巡回に要す
る最短距飄　最短時間または最低交通費の数値そのもの
を地図上の経路表示とは別に表示してもよい。

また上記各実施例は矛盾のない限り、種々組み合わせて
実施することが出来る。

更に本実施例で１上　ニューラルネットをノイマン型デ
ジタルコンピュータによるシミュレーションにて実施し
ているが、ニューラルネットをアナログ的にハードウェ
ア化したＬＳＩ等を使用することも可能である。

上記各実施例において、ＬＣＤ５が地図Ｍ］及び表示手
段Ｍ６に該当し、タッチパネル１１が位置入力手段Ｍ２
に該当し、マイクロコンピュータ１２が選択手段Ｍ４及
び演算手段Ｍ５に該当し、ＲＯＭ１５またはＲＯＭカー
ド１９が記憶手段Ｍ３に該当する。

１吋辺力１ 本発明によれｌｆ、　　単に地図上の位置を入力するだ
けで実際の経路に照らして、最短距離、　最短時間また
は最低交通費を簡便、迅速に算出することが出来る。

【図面の簡単な説明】

第１図は本発明の基本的構成例示医　第２図は実施例装
置の外観斜視は　第３図はそのブロック文　第４図は第
１実施例の処理内容のフローチャート、第５図は第２実
施例の処理内容の一部を示すフローチャート、第６図は
第３実施例の処理内容の一部を示すフローチャート、第
７図は第４実施例の処理内容の一部を示すフローチャー
ト、第８図は最短経路検索の説明図を表す。 Ｍｌ・・・地図　　　　　　　Ｍ２・・・位置入力手段
Ｍ３・・・記憶手段　　　　　Ｍ４・・・選択手段Ｍ５
・・・演算手段　　　　　Ｍ６・・・表示手段５・・・
液晶パネル（ＬＣＤ）　　１１・・・タッチパネル１２
・・・マイクロコンピュータ　１５・・・ＲＯＭ１９・
−・ＲＯＭカード

Claims (1)

1. 【特許請求の範囲】 １　地図と、 地図上をタッチすることにより任意の地点の位置データ
   を入力できる位置入力手段と、 地図上の経路データとその距離、時間または交通費デー
   タとを記憶する記憶手段と、 記憶手段に記憶されたデータから、入力された各地点間
   の最短距離、最短時間または最低交通費データを選択す
   る選択手段と、 選択手段にて選択された各地点間の距離、時間または交
   通費データを用いて、ニューラルネットワークの手法に
   基づき、全地点を訪問した場合に最短距離、最短時間ま
   たは最低交通費となる地点訪問順序の最適解を求める演
   算手段と、 この最適解として求められた地点訪問順序をその実際の
   道路に適合させた経路と共に地図上に表示する表示手段
   と、 を備えたことを特徴とする最短距離、最短時間または最
   低交通費算出装置。