JPH0457147A - 巡回経路決定法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （＃ｉ−菓ｌ−の利用分野） この発明は、空間内に製置された多数の声を巡する経路
を決定するとき、距離　時間　経費消費燃料を出来るた
け少なくする道順を短時間に効果的に求める方法に関す
る。

（従来の技（ホｉ） 多数の点を一巡する最短経路を求める問題は巡回セール
スマン問題としてよく知られている。

この場合、完全な最短距離を求めるためには全ての可能
性の組合せを試みれば解けるが、点の数をＮとしたとき
Ｎ−１の階乗回の試みが必要になる。したがって、Ｎが
大きくなるとお激に故が増え、カフ士以十になると言１
算磯を使っても計算時間か掛かり過き、実際上は解ｉ−
４なくなる。

そのため、理が的な最短距離は分がらないが出来るだ＋
１それに近い巡回経路の距離を持つ解を得ることか問題
となり、これについて多くの試みが研究者によりなされ
ている（文献、Ｍ、Ｂｅｌｌｍｏｒｅａｎｄ　Ｇ、Ｌ、
Ｎｅｍｈａｕｓｅｒ　１９Ｂ８．０ｐｍｓ、Ｒｅｓ、１
６）。

また、点数が大きくなると問題が複雑になり過き、決ま
った解決法が見出されていないが、比較的成功した例と
して第６図（ａ）のように今得られた巡回経路を観察し
て交差して不合理な経路がある場合、第６図（ｂ）のよ
うに交差した点の集まりの順番を入れ換えて交差をなく
する訂正をすることで解決を図ろうとする方法がある（
文献、Ｓ、Ｌｉｎ　ａｎｄ　Ｂ、Ｗ、Ｋｅｒｎｉｇ　ｈ
ａｎ　１９７３．０ｐｎｓ、Ｒｅｓ、２１）。

方、士数点までの場合にはニューラル・ネタ１〜ワーク
を用いた方法も提案されている。このうち、令名に知ら
れたもので最も優れていると思われる方法は、輪ゴムの
ようなものでたどって行（方と去がある（Ｒ，Ｄｕｒｂ
ｉｎ　ａｎｄ　Ｄ、Ｗｉｌｌｓｈｅｒ　１９８７．Ｎａ
Ｌｕ口、　３２６）。その方法はランダムに西装置され
た１００点の中心イ」近に小さい輪ゴムを置き、点の引
力に引かれながら輪ゴムが延びていき最後に全ての点に
たどり着いたときの輪ゴムが求める巡回経路てあろとし
て問題を解している。

（発明が解決しようとする間顕点） 辺、上の従来の方法を見ると、第６図にボしたような交
差を訂正する方法は、全体的に交差点を調へなしすれは
ならず、またどの位の政の交差点について入れ替え操作
を行なえば、高定な値が得られるかについて明確な指標
がない。

また、上記方法では達すきる点を結んだ結果、ｆｉｌ＋
または角のような経路が形成されるような場合について
、これについての対応策がない。

力、輪ゴムの方法では、輪ゴムを少しづつ変ＩＴεする
ための泪算には指数計算を含む複雑な；、＋　′ｒＩ＞
が必要で、更にゴムの弾性に関係するパラメータな考Ｈ
，，’、ｊ、しながら適切な値を選び計算を進めるなど
の配ｔ、、ｉ：ｊをしなければならない。そのため言１
算時間が掛かり、途中で経路のパターンを変えることも
てきない。

そこで、この巡回セールスマン問題の困難な、屯を１７
理すると （１）　　巡回する点数が大きくなると急散に可能性の
数が増えて計算時間が掛かりすぎること。

■　部分的に適正な順番の経路であっても全体の改良の
ためには、それを敢えて崩さなければならないこともあ
ることが、従来法では部分的に適正な順番の経路が求め
られると、これに拘束されて全体的な改良が困難であっ
た。

■　最適な解が分かっていない場合が普通で、つの解の
経路パターンと全（異なるけれどもこれに非常に近い別
の解の経路パターンがあることが多く、この場合従来の
方法では一つの解を見出すと、この極小値のパターンに
拘束されて別の最小値をもつ解を見出すのが困難である
などが挙げられる。

これらの困難な点を有効に解決する方法はまだ知られて
いなかった。

（問題点を解決するための手段） この発明は、簡単な計算で計算時間を速くし、自動的に
部分改良もすると同時に、全体的な思い切った改良もす
る方法を見イ」けて上記の問題点を解決しようとするも
のである。

そして、本願の第１発明は多数の点を全て巡回する出来
るだけ短（巡回経路を決定する方法において、先ず近接
した任意の２点を結ぶ最先の距離要素を定め、次に上記
２点と他の点を取り込んで形成される三角形における距
離要素の増加分を上記各点で計算してその増加分が最小
値となる最適角形を見付けて巡回経路を求め、次にこの
巡回経路のそれぞれの経路から未だ取り込まれていない
点に経路を延はしたときの距離要素の増加分が最小値と
なる各経路毎の最適三角形を求め、このうち距離要素の
増加分が最小値を示す最適三角形の１口点の点に新しい
経路を延ばす操作を繰り返して全ての点を含む巡回経路
を求めるようにしたものである。

また、本願の第２発明は、先ず上記第１発明の方法で全
ての点を含むＪ＾７＜＋巡回経路を求め、次にこの基糸
巡回経路を改善するために基準巡回経路に取り込まれた
点のうち１つ又は２以上を統計的に切りｈりし、残りの
点で経路を決め、上記同様の操作でこの経路に切り放さ
れた点を再び取り込んて、巡回経路を再編成し、この再
編成された巡回経路と上記基準巡回経路とを比較して距
離の短い方を選ぶようにしたものである。

ここで、距離要素としては、実際の２点間の距離のほか
、２点間の所要時間、運賃、消費燃料など２点間の関係
によって意味を持つ数値を距離要素として扱うことがで
き、更に複数の価値を距離に置き換えたものを距離要素
として扱うこともできる。

また、本願の第２発明において本願の第１発明で得られ
た基準巡回経路を改善するために、基準巡回経路の点の
うち１又は２以上を統計的に切り１ｉりずようにしてい
るが、切り放すべき点の数及び位置についてはランダム
に定められ、例えばその数は１つでもよいが、最適三角
形を構成する３点を残して他を全て切りｈ々すようにし
てもよい。

第２図はこの発明の方法のフローチャートを示すもので
ある。

このフローチャートに従えば、先ず最初に各点の入力さ
れたデータを基に、それぞれの点の間の距離りを計算し
、縦に点の番号順を取り、横にその点からの行き先の点
の番号順を取って先の距離を行列式の要素として配置し
た距離行列を作る。

ここで距離行列は距離のような可逆要素を扱う場合には
対称行列となるが、２，６間の所要時間、運賃、消費燃
料など２点間の関係によって意味を持つ数値を距離要素
として扱う場合には、必ずしも対称行列とならない場合
もある。

次に距離行列を用いて本願の第１発明により巡回経路を
求める方法を第１図で説明する。

第１図（ａ）のように任意のＡ点とそれに近接する１３
点をとり最初の経路ＡＢとしその２声、から経路を延ば
したときの距離の増加分△Ｄｃ＝Ｄ、ｃ＋Ｄｃｄを残り
の全ての点で計算し、その最小値をもつＣ１占を次の訪
問、占と決め、最初の最適三角形とする。

次に取り込も点は、それぞれの経路（辺）１４Ｊからま
だ取り込まれていない声Ｋに経路を延ばしたときの距離
の増加分△Ｄ　ｉ＝　＝　Ｄ　、に＋　Ｄ　ｋ７　　Ｄ
　：、、が最小値になる点ｋを求め各経路毎の最適三角
形とし、川に全ての辺で求めた点にの内の最小値を示す
三角形の頂点の点に新しい経路を延ばす。このＩ＆適適
用角形よる構築操作を第１区（ｌ〕）のように次々の繰
り退して全ての、屯を取り込み巡回経路とする。

したがって、本願の第１発明によれば距離行列を作った
後の操作は加減算と大小の比較のみて訓ｐは速くてき、
Ｌ記■の問題点を解決することができる。

ここで出来上がった巡回経路は局所的には最適であるが
、中には巡回経路内に刺・角があったり、或は交差部分
があったりして全体的に見て敵情の余地が残されている
場合もある。

その解決のために、一部を統計的に切り放し再び巡回経
路を１１１編成する操作をして不合理な、ｔ、′ｊを改
善するのが本願の第２発明である。

この原理を第３図、第４図に従って説明すると、第３図
はト訳方法で経路を構築した場合、刺がある経路が形成
されたとすると［第３図（ａ）］、経路に取り込まれた
点のうち１又は２以４−をランダムに切りｈ９．ずこと
がてきるが、今Ｐ点が切り７＋ダされ、Ｉ）、ｒ！−ｉ
、を孜すこと（こより経路は短縮されてＯＱとなって第
３図（ｂ）のようになり、ここで先の最適正角バａの方
法を取り、Ｐ点が再び取り込まれると第３図（Ｃ）のよ
うに改善される。

第４図は、交差する経路が求められた例を示すもので、
この場合も経路に取り込まれた点のうち１又は２以十を
ランダムに切り放すことができるが、今１）、τ′１が
切り１ｊ９．された経路は第４図（ｌ〕）のよう番こ短
縮され、ここで先の最適三角形の方法を取り、ｐ　、＋
４１が再び取り込まれると第４図（Ｃ）のように改占さ
れる。

なお、す？すや交差の部分が多くの芦を含も経路に一つ
いては経路より切り放す声、の数を統言］的に多くずろ
とともに、切り放された。占を再び取り込も再編成操作
を繰り返し、巡回経路の全体の距離が次第に小さくなる
ＳＹ路をり／ｖて行けＩＪ′ｉｆｌ適に近い解か求めら
れる。

（作用） 上述のＪ二うに、巡回セールスマン問題では巡回する点
数が大きくなると急激に可能性の数が増えて計算時間が
掛かりすぎるという問題があったが、本願の第１発明に
よれば距離行列を作った後の操作は加減算と大小の比較
のみて計算は速＜　−Ｃきるので、これらの問題を解決
することができる。

また、本願の第２発明では上述のように求められた巡回
経路が局所的には最適なものであっても、全体的に見て
改良すべき点がある場合には、光に求めた巡回経路より
切り１ｊ々ず方法により繰り返して改〆９することがて
き、極小値に拘束されてしま一〕だときても切り放す点
を思い切って多くして再編成操作を行なえば、先に求め
た巡回経路パターンの拘束から簡単に逃れることができ
、これとは全く異なる改良された最小値をもつ巡回経路
のパターンを得ることができる。

よＬ−１この発明による最適三角形による経路決定法は
、相当大きな割合の切り放しをされても最低３．占が残
れば経路を自分で再生できる強力な能力を持っているた
Ｎ）、どんな大がかりな不合理な経路であっても改善す
ることができる。更に、ランダムに切り７］９．した点
を再編成するとき今ある巡回経路のパターンから考えて
最適なように各点を取り込んで行くために全体的に見た
不合理を自然に改善する能力をもつ特徴がある。

（実施例） 以下、この発明の実施例を示す。

２次元−１−の都市間の巡回経路決定の問題をパソコン
を使い、先ず１０．占、３０．占　１００点で試みた。

位置のＸ、Ｙ座標値から距離を計算し、距離行列を作っ
た。

仔・υ、の、占から始めて最適三角形から経路を求める
方法を用いると、１０声の場合は最初に求めた巡回経路
でほぼ半２々が最短距離の経路が求まり、使の゛ト故も
数回の再編成操作で解が求まった。

３０貞の場合ち最初の巡回経路で合計距離が最小値の１
５％くらい大きいものか得られ、再編成操作（によりｌ
Ｏ砂から１分の内に第５区（ａ　）のような最小値をも
つ解が求まっｌｌ。

１００、占の場合は最初の巡回経路で合計距離が最小値
の平均１３％くらい大きいものが得られ、更に再編成処
理により理想的と思われる最小値にまで合計距離を近付
けた巡回経路を得ることができた。また、最小値から２
％以内の合計距離の巡回経路は数分からｌＯ分位で得る
ことができた。

このようにこの発明による方法は巡回セールスマン問題
を従来の方法よりかなり速く簡単に解くことができる。

点の数が更に増えた場合は、この発明では幾つかの部分
に分しってそれぞれの部分て最適な巡回経路を求めた後
、それぞれを結合することも容易に−Ｃき、その後部分
を結合したことによる不合理を全体の再編成操作を行な
うことにより改善することができた。

令名距離行列の要素を２点間の平面上の距離に関しての
み扱ってきた力釈必ずしも２次元平面」二に限定されず
、３次元、Ｎ次元ユークリッド空間の距離ても距離が定
義できれば距離行列は作れ、この発明の方法を解くこと
ができた。

更に、地球のような球面の大円コースや、ドナッ型物体
上の２点の曲面に沿った曲線で定義される距離などても
同様に扱うことができた。

また、距離に限らず、２．屯間の所要時間、道のり、消
費燃料など２つのものの関係により意味を持つ数値を扱
うことができ、更に複数の価値を距離に置き換えて計算
することもてきる。その時ににｉ例えば、所要時間と運
賃を変数とする関数を距離の関数と定義して扱うことが
できた。

なお、この発明によればループ状の巡回経路だけでなく
、第５図（ｂ）のようにＡ点から別のＢ点へ行く最短の
巡回経路を求めることができる。

この場合、Ａ、Ｂ間の距離要素をり、、、−〇と置くた
けて全く同し操作をすると自動的に最適な巡回経路を求
めることができた。

また、２点間を連絡できない場合や、連絡したくない場
合があっても、その２点間の距離行列の四ＫＳ　ｒ）　
、ｈを非常１こ大きい値にしておけば、全く同し方法で
解ける。

ある点を複数回訪れる巡回経路を考える場合でも、訪れ
る回数がＮならばその点をＮ個の独立した点と見なして
それぞれの間では連絡できないように距離行列要素を無
限大に決めれば、令名と同し方法で解くことができる。

以上のように、この発明によれば地球上を飛び回るセー
ルスマンに関する問題のように非常に融通性をもって扱
うことを可能にした。

また、郵便配達、ヂエーンストアの配送のように、日に
よりまたは巡回の途中で顧客の訪問先が変わる場合でも
、この発明によれば柔軟に対応できる。即ち、丁度ラン
ダムに点を取り除き、再編成操作で取り込むことと同し
操作であるため、計算の時点でも訪問先の変更が可能と
なる。

更に、次のようなダイナミック・プログラミングが可能
となった。即ち、訪問する点が移動して相対的な距離を
逐次変える場合においても、距離行列の要素が時間的に
変化することとしてとらえて、移動する部分の点に注目
して切り放し再編成の操作をすれば巡回経路を得ること
が可能となっ！≧。

（発明の効果） 以上説明したように、この発明によれば最適角形による
経路の決定法は非常に融通性のある方法であり、したが
って一つの解に拘束されず、これから脱出して全く新し
い解を見出すこともてきる。また距離行列の要素の定義
も非常に自由に取ることができて、従来の方法では不可
能であった所要時間と運賃との関係等を扱うことができ
る。

また、再編成操作により全体としての最適化が自然に出
来ることや、計算の途中で５屯の位置が変化するような
ダイナミック　プログラミングも作大し、従来の方法で
は不可能であったことを可能にした。

【図面の簡単な説明】

第１図はこの発明の概念図で、第１図（ａ）は経路ΔＢ
から最適三角形ＡＢＣを求め、第１図（１））は巡回経
路を求める操作の図、第２図はこの発明のス］算処理の
フローチャート、第３図はこの発明による切り放し、再
編成操作による刺・角の改り法を示し、第３図（ａ）は
改善すべき刺・角のある経路を示し、第３図（ｂ）：よ
切り放し操作を示し、第３図（ｃ）は再編成操作を示す
図、第４図はこの発明による切り放し、再編成操作によ
る交差の改善法を示し、第４区（ａ）は改善すべき交差
のある経路を示し、第４図（ｂ）は切り放し操作を示し
、第４図（ｃ）は再編成操作を示す図、第５図は３（１
点の巡回経路を求めた図で、第５図（ａ）はループ巡回
経路、第５図（ｂ）はＡからＢへの経路を示す図、第６
図は従来の方法による交差部分の改善法を示すもので、
第６図（ａ）は改善すべき交差部分のある経路を示し、
第６図（ｂ）は訪問１１１１ｍ序を逆にして改善する方
法を示す。 （ａ、） ＼ 第６図

Claims (7)

【特許請求の範囲】
1. （１）多数の点を全て巡回する出来るだけ短い巡回経路
   を決定する方法において、先ず近接した任意の２点を経
   路として結び、次に上記２点から残りの点とでつくられ
   る三角形の経路を考えその距離要素の増加分を各点で計
   算してその増加分が最小値となる最適三角形を見付けて
   巡回経路を求め、次にこの巡回経路のそれぞれの経路か
   ら未だ取り込まれていない点に経路を延ばしたときの距
   離要素の増加分が最小値となる各経路毎の最適三角形を
   求め、このうち距離要素の増加分が最小値を示す最適三
   角形の頂点の点に新しい経路を延ばす操作を繰り返して
   全ての点を含む巡回経路を求めるようにしたことを特徴
   とする巡回経路決定法。
2. （２）多数の点を全て巡回する出来るだけ短い巡回経路
   を決定する方法において、先ず近接した任意の２点を経
   路として結び、次に上記２点から残りの点とでつくられ
   る三角形の経路を考えその距離要素の増加分を各点で計
   算してその増加分が最小値となる最適三角形を見付けて
   巡回経路を求め、次にこの巡回経路のそれぞれの経路か
   ら未だ取り込まれていない点に経路を延ばしたときの距
   離要素の増加分が最小値となる各経路毎の最適三角形を
   求め、このうち距離要素の増加分が最小値を示す最適三
   角形の頂点の点に新しい経路を延ばす操作を繰り返して
   全ての点を含む基準巡回経路を求め、 次に、上記基準巡回経路を改善するために上記基準巡回
   経路に取り込まれた点のうち１つ又は２以上を統計的に
   切り放し、残りの点で経路を決め、それぞれの経路から
   切り放した点に経路を延ばしたときの距離要素の増加分
   が最小値となる各経路毎の最適三角形を求め、このうち
   距離要素の増加分が最小値を示す最適三角形の頂点の点
   に新しい経路を延ばす操作を繰り返して切り放された点
   を再び取り込んで、巡回経路を再編成し、この再編成さ
   れた巡回経路と上記基準巡回経路とを比較して距離の短
   い方を選ぶようにしたことを特徴とする巡回経路決定法
   。
3. （３）最初の距離要素を零として出発点から終着点まで
   巡回経路を求める、特許請求の範囲第１項又は第２項記
   載の巡回経路決定法。
4. （４）連絡できない場合や連絡したくない場合の２点間
   の距離要素を非常に大きな値としておく、特許請求の範
   囲第１項又は第２項記載の巡回経路決定法。
5. （５）同一の点にＮ回訪れる場合、その点をＮ個の独立
   点と見なし、それぞれの間の距離要素を無限大に決める
   ようにした、特許請求の範囲第１項又は第２項記載の巡
   回経路決定法。
6. （６）点が移動して相対的な距離要素が逐次変わる場合
   において、移動する点を切り放して再編成操作するよう
   にした、特許請求の範囲第２項記載の巡回経路決定法。
7. （７）距離要素として、実際の距離の他に、２点間の所
   要時間、運賃、消費燃料など２つのものの関係により意
   味を持つ数値を扱うようにした、特許請求の範囲第１項
   又は特許請求の範囲第２項記載の巡回経路決定法。