JP2000048003A - 巡回セールスマン問題階層化処理方法およびそのプログラム記録媒体 - Google Patents

Abstract

(57)【要約】 【課題】 二次元平面上の問題領域に多数散在する都市
を一巡する経路のうち最短な経路を探索する大規模巡回
セールスマン問題を階層化して解く方法に関し，領域数
を削減し，開始／終了都市の設置可能な領域を拡大し
て，処理の高速化と，よい解を求めることを可能とす
る。 【解決手段】 領域分割部１はＴＳＰ問題領域を分割
し，領域修正部２は領域内の都市の偏りを検出し，都市
の偏りがある領域の一部を隣接する領域に含めるように
領域を修正する。ＴＳＰ処理部４は，分割された領域を
都市とみなして各階層ごとにＴＳＰ処理を行う。開始／
終了都市決定部３は，第２階層以降に，上位階層の経路
にもとづいて，各領域でＴＳＰ処理するときの開始／終
了都市を，あらかじめ定められた設置可能域から決定す
る。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は，計算機によって大
規模巡回セールスマン問題（以下，ＴＳＰという）を解
く方法であって，特に問題領域を階層的に分割して解く
処理方法に関する。

【０００２】ＴＳＰは，二次元平面上の問題領域に散在
する都市を一巡する経路のうち，最も短い経路（最小コ
ストの経路）を探索する問題である。一巡する経路の数
はＮ個の都市に対して（Ｎ−１）！だけ存在する。巡回
する都市数の増加に伴い，都市の組み合わせの計算量は
爆発的に増加してしまうため，この組み合わせの爆発的
増加を防ぎ，処理を高速化し，かつ最適解を求めること
が要求されている。

【０００３】

【従来の技術】従来のＴＳＰの階層化解法においては，
ＴＳＰの問題領域を，一定の数および一定の大きさの領
域で分割して処理を行っていた。しかし，従来の方法で
は，都市の配置に偏りがある領域も一領域とみなして処
理を行うため，都市の存在する領域数が多くなり，ま
た，小さい領域でもＴＳＰの処理を行う必要があった。

【０００４】図１０〜図１３を用いて，従来方法による
ＴＳＰの階層化解法を説明する。図１０は，従来技術に
おける都市空間（問題領域）の分割方法を示す。図１０
（Ａ）に示すようにＴＳＰの問題領域を，例えば４×４
分割し，１領域を１都市とする。この例では，図１０
（Ｂ）に示すように，１６の領域のうち都市が存在する
領域は１２であるから，ＴＳＰの問題領域上に１２都市
が存在するとみなして，１２都市のＴＳＰ問題を処理す
る。図１０（Ｃ）は，１２都市のＴＳＰ処理の１つの解
（経路）を示している。

【０００５】さらに，求まった経路を構成する各領域ご
とに，同様に４×４分割してＴＳＰ問題を解いていく。
このように階層化して処理していくことにより，探索し
なければならない経路の数を少なくすることができる。

【０００６】図１１は，従来方法における開始都市／終
了都市の設置可能域の例を示す。分割した領域におい
て，さらに階層的にＴＳＰ処理を進める場合，探索する
経路をどの都市から開始し，どの都市で終了するかを決
めなければならない。従来方法においては，図１１の斜
線で示すように，領域の四隅に位置する他の２つの領域
に隣接する４個の小領域のいずれかに開始都市と終了都
市とを配置していた。

【０００７】図１２は，従来方法における開始都市／終
了都市の決定方法の例を示す。従来技術では，開始都市
／終了都市は，図１１に示す開始都市／終了都市の設置
可能域の位置をもとに，１つ前に処理した領域の位置と
次に処理する領域の位置との位置関係により決定する。
四隅の設置可能域のうち，最も近い設置可能域に都市が
存在した場合には，その設置可能域を開始都市／終了都
市とする。

【０００８】図１２（Ａ）は１つ前に処理した領域およ
び次に処理する領域が上方向にある場合，図１２（Ｂ）
は１つ前に処理した領域および次に処理する領域が右方
向にある場合，図１２（Ｃ）は１つ前に処理した領域お
よび次に処理する領域が下方向にある場合，図１２
（Ｄ）は１つ前に処理した領域および次に処理する領域
が左方向にある場合の，開始都市／終了都市の設置可能
域を示す。これらの場合には，一方の設置可能域が開始
都市，他方が終了都市となる。

【０００９】図１２（Ｅ）は１つ前に処理した領域およ
び次に処理する領域が斜め上方向にである場合の開始都
市，終了都市の位置を示している。例えば１つ前に処理
した領域が左上方向である場合，開始都市の位置は左上
隅の小領域となる。

【００１０】また，１つ前に処理した領域と次に処理す
る領域とが斜めの同じ方向にある場合には，終了都市と
開始都市の設置可能域が同じ位置となるが，この場合に
は，残りの３つの設置可能域の１つを終了都市の設置可
能域とする。

【００１１】以上のような開始都市および終了都市の設
置可能域に都市が存在しなかった場合には，処理の都合
上，設置可能域にダミーの都市を配置していた。図１３
は，従来方法による開始都市／終了都市の配置および階
層化したＴＳＰ処理を説明する図である。

【００１２】図１０（Ｃ）に示す経路上の各領域をさら
に４×４分割して，ＴＳＰ処理を行う。ここで，巡回経
路上で連続する都市Ｘ，都市Ｙに対応する領域Ｘと領域
Ｙとに着目する。領域Ｘと領域Ｙでは，それぞれ，さら
に４×４分割してＴＳＰ処理を行う。

【００１３】領域Ｘでは，１つ前に処理した領域が上方
向にある領域であるから，開始都市の設置位置は左上ま
たは右上のいずれかの設置可能域となる。また，終了都
市の設置位置は，次に処理する領域が右上方向にある領
域であるから，右上の設置可能域のみが該当する。した
がって，領域Ｘにおいては，開始都市は左上の設置可能
域，終了都市は右上の設置可能域に配置されることとな
るが，左上および右上のいずれの設置可能域にも都市が
存在しない。そこで，左上および右上の設置可能域に，
それぞれダミーの開始都市およびダミーの終了都市を設
置する。

【００１４】また，領域Ｙでは，１つ前に処理した領域
が左下方向にあるため，開始都市の設置できる位置は左
下の設置可能域のみとなる。さらに，領域Ｙの次に処理
する領域は下方向にある領域であることから，終了都市
の設置できる位置は右下の設置可能領域ということにな
る。しかし，右下の設置可能域には都市が存在しないた
め，右下隅にダミーの都市を設置し，それを終了都市と
する。

【００１５】

【発明が解決しようとする課題】ＴＳＰの問題領域を分
割したとき，領域によっては都市の配置に偏りのあるも
のが存在し，１領域内に均等に都市が配置されているも
のと，都市が偏在しているものとを比較すると，一般に
都市が偏在しているものは都市数が少ない。このような
領域を１領域（１都市）と認定して処理を進めると，偏
りのある領域が，近隣の領域と直接結ばれる経路ができ
るとは限らないために，従来技術では，結果的に解（＝
経路）が悪いものとなってしまうという問題があった。

【００１６】また，開始都市／終了都市としてダミーの
都市を配置すると，都市数が実際の都市数より多くなる
ことから，都市の組み合わせ数も多くなり，高速に解を
求めにくいという問題があった。

【００１７】また，開始都市と終了都市との設置可能域
を，領域の四隅の小領域だけに限定した場合には，同じ
小領域に開始都市と終了都市とが配置される場合があ
り，終了都市の決定が開始都市の後になるため，終了都
市をよい位置に配置できないことがあるという問題があ
った。

【００１８】本発明は，上記問題点の解決を図り，計算
機を用いて高速に効率よく大規模巡回セールスマン問題
を解く手段を提供することを目的とする。特に都市の散
在する傾向を考慮して，都市が領域内で偏在する場合に
は，従来の２領域を１領域として分割して処理すること
により，領域数の増加を抑制して処理の高速化を図ると
ともに，開始都市と終了都市の決定において設置可能域
を従来のものより拡大することにより，ダミー都市を設
置しなければならないケースを少なくし，処理量の削減
および解の向上を図ることを目的とする。

【００１９】

【課題を解決するための手段】本発明は，上記の目的を
達成するため，図１に示すような各手段を持つ。図１
は，本発明を実現するための装置の構成例を示す。

【００２０】本発明を実現するＴＳＰ階層化解析装置１
０は，領域分割部１，領域修正部２，開始／終了都市決
定部３，ＴＳＰ処理部４からなる。これらは，ＣＰＵお
よびメモリを備えた計算機と，ＣＰＵが実行するプログ
ラムとから構成される。

【００２１】領域分割部１は，ＴＳＰの問題領域をＭ×
Ｎに分割する手段である。領域修正部２は，領域分割部
１により分割した各領域の都市の偏りを，領域内におけ
る都市の配置が所定のパターンに該当するかどうかによ
って調べ，都市の偏りが認められる領域があった場合，
それを隣接する領域に組み込んで１つの領域とする手段
である。

【００２２】開始／終了都市決定部３は，開始都市また
は終了都市の位置を決定する手段でであり，領域の四隅
に位置する小領域とその小領域に辺を接する小領域を設
置可能域として，その中に存在する都市を開始都市また
は終了都市とする。

【００２３】ＴＳＰ処理部４は，分割した領域を１の都
市とみなして，その領域（都市）についてのＴＳＰ処理
を行う手段である。以上の各処理手段を計算機によって
実現するためのプログラムは，計算機が読み取り可能な
可搬媒体メモリ，半導体メモリ，ハードディスクなどの
適当な記録媒体に格納することができる。

【００２４】本発明は，以下のように作用する。領域分
割部１は，ＴＳＰの問題領域をＭ×Ｎに分割する。領域
修正部２は，領域分割部１が分割した各領域ごとに都市
が存在するかどうかを調べ，領域内に都市が存在するも
のは，その領域にフラグを立てる。そのフラグのパター
ンが，所定のパターンと一致するかどうかにより，領域
内の都市に偏りがあるかどうかを判断し，領域内の都市
に偏りがある場合には，その都市が存在する領域の一部
を隣接する領域に含める。

【００２５】このように都市が偏在する領域を隣接する
領域に含め，領域を拡大する修正によって，領域数が減
少することになるので，都市の組み合わせ数が減少し，
ＴＳＰ処理部４における処理の高速化が可能になるとと
もに，近隣の都市の巡回領域が拡がるので，解も向上す
る。

【００２６】また，開始／終了都市決定部３は，領域の
四隅に位置する小領域を開始／終了都市の選択候補とす
るだけなく，それらに隣接する小領域も開始／終了都市
の選択候補とする。したがって，ダミーの都市が配置さ
れる確率が小さくなり，処理量の削減と良好な解を求め
ることが可能になる。

【００２７】

【発明の実施の形態】以下では，図１０（Ａ）に示すＴ
ＳＰの問題領域について，４×４分割で階層的にＴＳＰ
処理を行う例について説明する。

【００２８】図２は，本発明の処理の流れの概要を示す
図である。領域分割部１により，ＴＳＰの問題領域をＭ
×Ｎ分割する（ステップＳ１）。本例では，４×４分割
で，領域は正方形とする。分割の結果は，図１０（Ａ）
に示すものと同様である。

【００２９】次に，領域修正部２により，領域分割部１
により分割した各領域について，領域内の都市が偏在し
ているかどうかを調べる（ステップＳ２）。都市の偏り
がある場合には，ステップＳ４へ進み，偏りがない場合
には，ステップＳ５へ進む（ステップＳ３）。

【００３０】都市の偏りがある場合，所定の規則にした
がって，都市が存在する領域の一部を，隣接する領域に
組み込み，新たな領域とする（ステップＳ４）。具体的
には，次のような処理を行う。領域内に都市が存在する
場合には，その領域に都市の存在を示すフラグを立て，
フラグのパターンを得る。各領域のパターンを，予め用
意した都市の偏りを表すパターンと比較し，都市の偏り
の有無を判断する。

【００３１】図３に示すように，領域をＭ×Ｎ分割し，
個々の領域を（１，１），（１，２），…，（１，
Ｎ），…，（Ｍ，１），…，（Ｍ，Ｎ）とするとき，都
市が以下のように偏って存在する場合には，都市が存在
する領域部分が，隣接する領域に組み込まれるように領
域の分割を修正する。

【００３２】１）都市が（１，ｉ）（ｉ＝１〜Ｎ）にの
み存在する場合には，左の領域に含める（図４（Ａ）参
照）。 ２）都市が（ｉ，１）（ｉ＝１〜Ｍ）にのみ存在する場
合には，上の領域に含める（図４（Ｂ）参照）。

【００３３】３）都市が（Ｍ，ｉ）（ｉ＝１〜Ｎ）にの
み存在する場合には，右の領域に含める（図４（Ｃ）参
照）。 ４）都市が（ｉ，Ｎ）（ｉ＝１〜Ｍ) にのみ存在する場
合には，左の領域に含める（図４（Ｄ）参照）。

【００３４】５）都市が（１，１），（２，１），
（１，２）にのみ存在する場合には，上または左の領域
に含める（図４（Ｅ）参照）。 ６）都市が（Ｍ，１），（Ｍ−１，１），（Ｍ，２）に
のみ存在する場合には，上または右の領域に含める（図
４（Ｆ）参照）。

【００３５】７）都市が（１，Ｎ），（１，Ｎ−１），
（２，Ｎ）にのみ存在する場合には，左または下の領域
に含める（図４（Ｇ）参照）。 ８）都市が（Ｍ，Ｎ），（Ｍ−１，Ｎ），（Ｍ，Ｎ−
１）にのみ存在する場合には，下または右の領域に含め
る（図４（Ｈ）参照）。

【００３６】９）都市が，これら以外の領域にある場合
には，その領域を，隣接する領域に含めないようにす
る。図４は，都市の偏りを判断するためのパターンの例
を示す。

【００３７】図４中，斜線で示す小領域は都市が存在す
る領域である。領域における都市の偏りを上述したよう
な８パターンとして想定する。都市の存在を示すフラグ
のパターンがこれらの８つのパターンに当てはまる場合
には，その領域において都市が偏在しているとする。

【００３８】図５は，領域修正処理後の領域の例を示す
図である。図５に示すように，第１の階層における都市
が存在する領域の数は８となり，従来方法であれば，図
１０（Ｂ）に示すように領域数＝１２についてするＴＳ
Ｐ処理が，８都市に対する処理で済むことになる。この
ようにして，領域数が減少することにより，都市の組み
合わせ数が少なくなり処理が高速化し，また，近接する
都市の巡回領域が広がるために良好な解が得られるよう
になる。

【００３９】次に，図２のステップＳ５において，最初
の処理，すなわち第１階層の処理であるかどうかを調べ
る。最初の処理の場合，開始都市と終了都市は，あらか
じめ決まっているため，次のステップＳ６をスキップす
る。第２階層以降の処理の場合，ステップＳ６によっ
て，開始都市と終了都市とを後述する処理により決定す
る。

【００４０】その後，領域を都市とみなして，ＴＳＰ処
理を行い，開始都市から終了都市までの経路を求める
（ステップＳ７）。以上のステップＳ１からＳ７までの
処理を，領域内の都市が１個となり領域が分割できなく
なるまで，または所定の階層数だけ繰り返す（ステップ
Ｓ８）。

【００４１】次に，本実施の形態における開始都市，終
了都市の決定方法について説明する。図６は，開始都市
または終了都市の設置可能域の例を示す。従来技術で
は，図１１に示すような領域四隅の小領域のみを設置可
能域としていた。本実施の形態では，設置可能域を，四
隅の小領域とその小領域に辺を接する小領域にまで拡大
する。開始都市／終了都市の設置可能域となる小領域に
は，開始都市と終了都市の設置可能を示すフラグを立て
ておく。図６に示す５×５（４×４の場合も同様）の小
領域からなる領域において，斜線が付けられている小領
域が，開始都市と終了都市の設置可能を示すフラグが立
てられた小領域である。また，各領域は，前に処理した
領域の方向と，次に処理する領域の方向の情報も保持す
る。

【００４２】開始都市は，１つ前に処理した領域の方向
にもとづいて，４つの設置可能域から１つを選択して設
置し，終了都市についても，同様に次に処理する領域の
方向にもとづいて，４つの設置可能域から１つを選択し
て設置する。

【００４３】開始都市の選択方法としては，処理領域を
２×２分割し，１つ前の終了都市の位置から一番近い領
域を選択し，その領域内の設置可能域を選択する。ま
た，終了都市の選択方法としては，次に処理する領域を
２×２分割し，境界に一番近い領域内の設置可能域を選
択する。

【００４４】選択された設置可能域内に都市が存在する
小領域があれば，その小領域が開始都市または終了都市
となる。すなわち，「設置可能域を示すフラグ＆都市の
存在を示すフラグ＝＝１」である小領域が存在する場合
には，その小領域が，開始都市または終了都市となる。

【００４５】「設置可能域を示すフラグ＆都市の存在を
示すフラグ＝＝１」である小領域が，選択された設置可
能域内に存在しない場合には，ダミーの開始都市または
終了都市を設定する。

【００４６】設置可能域のうちの１つに着目した場合
に，開始都市／終了都市の設置可能域が多数（例えば，
３個以上の小領域）存在するときには，一番近いものを
選択する。また，開始都市と終了都市とが同じ設置可能
域にある場合（例えば，１つ前に処理した領域と次に処
理する領域がどちらも左下にある場合）には，設置可能
域の３つの小領域からそれぞれ別の小領域を開始都市ま
たは終了都市として選択する。

【００４７】開始都市の設置可能域と終了都市の設置可
能域が一致する場合としては，以下のような８通りの場
合がある。 １）前に処理した領域が上方向にある領域であって，次
に処理する領域が左上または右上方向にある領域である
場合。

【００４８】２）前に処理した領域が右方向にある領域
であって，次に処理する領域が右上または右下方向にあ
る領域である場合。 ３）前に処理した領域が下方向にある領域であって，次
に処理する領域が右下または左下方向にある領域である
場合。

【００４９】４）前に処理した領域が左方向にある領域
であって，次に処理する領域が左上または左下方向にあ
る領域である場合。 ５）前に処理した領域が左上方向にある領域であって，
次に処理する領域が上または左方向にある領域である場
合。

【００５０】６）前に処理した領域が右上方向にある領
域であって，次に処理する領域が右または下方向にある
領域である場合。 ７）前に処理した領域が右下方向にある領域であって，
次に処理する領域が右または下方向にある領域である場
合。

【００５１】８）前に処理した領域が左下方向にある領
域であって，次に処理する領域が左または下方向にある
領域である場合。このように，開始都市と終了都市とを
設置する設置可能域が一致する場合には，次のように開
始都市と終了都市とを決定する。

【００５２】１）開始都市および終了都市の設置可能域
に２つ以上の都市があるときには，開始都市と終了都市
はその設置可能域から選ぶ。 ２）開始都市および終了都市の設置可能域に１つの都市
だけがあるときには，開始都市または終了都市のいずれ
かをその設置可能域から選び，残りの開始都市または終
了都市をダミーの都市とする。

【００５３】３）開始都市および終了都市の設置可能域
に１つも都市がないときには，開始都市および終了都市
としてダミーの都市を設置する。なお，開始都市／終了
都市を設定する設置可能域が一致しない場合には，それ
ぞれの設置可能域から開始都市または終了都市を選ぶ。

【００５４】図７は，開始都市と終了都市の配置の例を
説明する図である。なお，図７では，開始都市／終了都
市の決定処理を把握しやすくするために，領域修正処理
は省略している。

【００５５】図７に示すように，領域ａでは，前に処理
した領域が上方向に位置する領域であり，次に処理する
領域は右上方向に位置する領域であるから，開始都市の
設置可能域は左上のものとなり，終了都市の設置可能域
は右上のものとなる。この領域ａについては，開始都市
／終了都市の設定可能域内に都市が存在し，また，この
設定可能域内に都市が存在する小領域が１つ存在するた
めに，その小領域が開始都市または終了都市となり，ダ
ミーの開始都市／終了都市を設定しなくてもＴＳＰ処理
することができる。

【００５６】また，領域ｂについては，１つ前に処理し
た領域が左下方向に位置する領域であり，次に処理する
領域が下方向に位置する領域である。したがって，開始
都市の設置可能域は左下のもの，終了都市の設置可能域
は左下もしくは右下のものから選択される。この終了都
市の設置可能域の選択では，境界から一番近い都市が左
下にあることから左下のものが選ばれる。この場合に
は，開始都市も終了都市も左下隅の小領域とその隣接小
領域の３つの小領域から選択することになる。ここで，
経路が交差すると，階層化において解が悪いものになっ
てしまうため，経路が交差しないように，開始都市を左
下隅の上に隣接する小領域に設置し，終了都市を左下隅
の小領域に設置する。

【００５７】図８は，領域修正処理後の開始都市と終了
都市の配置および階層化したＴＳＰ処理を説明する図で
ある。都市が偏在する領域を調べて，図５に示すように
領域を修正すると，第１階層のＴＳＰ処理では，８個の
領域を都市とみなして経路を探索することになる。この
結果，図８（Ａ）に示すような領域間の経路が決定され
る。次に，この経路上の各領域内で，さらに領域分割を
行い，階層的にＴＳＰ処理を実行していく。

【００５８】分割された領域は，できるだけ正方形に近
いほうが良い解が求まる。しかし，すでに領域修正処理
が行われているときには，領域ｃのように，都市の偏り
により修正した領域は正方形でなくなっている。ここ
で，他の修正しない領域ｄなどと同様に，４×４分割に
より小領域を作るとすれば，領域修正処理で隣接する領
域の一部を組み込んだ方向の辺が長くなってしまい，領
域の形は階層化に伴い次第に正方形から離れていってし
まう。一方，小領域の形状を正方形のままに保とうとす
れば，領域数すなわち都市数が増加してしまい，処理の
速度が低下することになる。

【００５９】そこで，すでに修正された領域について，
さらに分割処理して小領域を生成する場合には，矩形の
長辺を基準に分割し，かつ分割した領域ができるだけ正
方形に近い矩形となるように分割する。本例の場合，分
割後の小領域の大きさが，領域ｄの小領域と同じになる
ように分割すれば，５×４分割となるが，小領域数が２
０個となって増加してしまうため，図８（Ｂ）に示すよ
うに，領域の矩形の長辺を４分割し矩形の短辺を３分割
して，４×３分割とし，領域数が１６を超えないように
している。

【００６０】図９は，領域テーブルの構成例を示す図で
ある。領域テーブルは，同一階層において分割した領域
ごとに，その領域の位置，その領域が含む実際の都市
数，次の都市へのポインタ，次の領域へのポインタ等の
情報を保持する。

【００６１】例えば，第１階層の領域では，ＴＳＰ処理
で求めた経路の順序にしたがって，次の領域へのポイン
タ情報を用いてリンクする。経路が変更になるたびにポ
インタを変更してリンクを修正する。

【００６２】また，その領域ごとに，１つ下の階層でＴ
ＳＰ処理した領域（都市）の経路の開始都市から終了都
市への順序をポインタ等により保存する。さらに，下の
階層でＴＳＰ処理をした場合には，同様にしてさらにそ
の領域ごとに下位階層における都市の経路情報をポイン
タにより保存する。これにより，処理の階層化が進んで
も，各領域のポインタを順にたどることによって，全て
の都市についての経路，すなわち解を得ることができ
る。なお，図９の領域テーブルの構成は一例であり，他
の形式で領域および都市情報を管理してもよい。

【００６３】

【発明の効果】以上説明したように，本発明によれば，
大規模巡回セールスマン問題（ＴＳＰ）において，領域
分割による都市の偏りの考慮とＴＳＰの階層化処理にお
ける開始都市と終了都市の決定パターンの改善により，
巡回セールスマン問題を高速に解くことができ，かつ良
好な解を求めることができるようになる。

【図面の簡単な説明】

【図１】本発明を実現する装置の構成例を示す図であ
る。

【図２】本発明の処理の流れの概要を示す図である。

【図３】都市の偏りによる分割した領域の修正処理を説
明するための図である。

【図４】都市の偏りを判断するためのパターンの例を示
す図である。

【図５】領域修正処理後の領域の例を示す図である。

【図６】開始都市／終了都市の設置可能域の例を示す図
である。

【図７】開始都市と終了都市の配置の例を説明する図で
ある。

【図８】領域修正処理後の開始都市と終了都市の配置お
よび階層化したＴＳＰ処理を説明する図である。

【図９】領域テーブルの構成例を示す図である。

【図１０】従来方法における都市空間（問題領域）の分
割方法を説明する図である。

【図１１】従来方法における開始都市／終了都市の設置
可能域を示す図である。

【図１２】従来方法における開始都市／終了都市の決定
方法の例を示す図である。

【図１３】従来方法による開始都市／終了都市の配置お
よび階層化したＴＳＰ処理を説明する図である。

【符号の説明】

１ 領域分割部 ２ 領域修正部 ３ 開始／終了都市決定部 ４ ＴＳＰ処理部 １０ ＴＳＰ階層化解析装置

Claims (4)

【特許請求の範囲】
1. 【請求項１】 計算機により，二次元平面上の問題領域
   に多数散在する都市を一巡する経路のうち最短な経路を
   探索する巡回セールスマン問題を階層化して解く処理方
   法であって，前記問題領域を複数の領域に分割する第１
   の過程と，前記複数の領域に分割した各領域における都
   市の偏りを調べ，領域内の都市が偏在する場合には，偏
   在側の隣接領域にそれらの都市が含まれるように領域の
   分割を修正する第２の過程と，前記分割された領域を都
   市とみなして，その都市を一巡する経路のうち最短な経
   路を探索する処理を行う第３の過程とを有し，前記第１
   ないし第３の過程を，分割した領域について階層的に繰
   り返して実行することを特徴とする巡回セールスマン問
   題階層化処理方法。
2. 【請求項２】 請求項１に記載の巡回セールスマン問題
   階層化処理方法において，前記第３の過程における探索
   のために開始都市および終了都市の位置を決定する場合
   に，その探索しようとする領域をさらに分割した小領域
   のうち，四隅に位置する小領域とその小領域に辺を接す
   る小領域中に存在する都市から開始都市および終了都市
   を選択し，それらの小領域に都市が存在しない場合に
   は，それらの小領域にダミーの都市を配置して開始都市
   または終了都市とすることを特徴とする巡回セールスマ
   ン問題階層化処理方法。
3. 【請求項３】 二次元平面上の問題領域に多数散在する
   都市を一巡する経路のうち最短な経路を探索する巡回セ
   ールスマン問題を階層化して解く処理を計算機に実行さ
   せるためのプログラムを記録した媒体であって，前記問
   題領域を複数の領域に分割する第１の処理と，前記複数
   の領域に分割した各領域における都市の偏りを調べ，領
   域内の都市が偏在する場合には，偏在側の隣接領域にそ
   れらの都市が含まれるように領域の分割を修正する第２
   の処理と，前記分割された領域を都市とみなして，その
   都市を一巡する経路のうち最短な経路を探索する処理を
   行う第３の処理と，前記第１ないし第３の処理を，分割
   した領域について階層的に繰り返して実行する処理と
   を，計算機に実行させるプログラムを記録したことを特
   徴とする巡回セールスマン問題階層化処理プログラム記
   録媒体。
4. 【請求項４】 請求項３に記載の巡回セールスマン問題
   階層化処理プログラム記録媒体であって，前記第３の処
   理における探索のために開始都市および終了都市の位置
   を決定する場合に，その探索しようとする領域をさらに
   分割した小領域のうち，四隅に位置する小領域とその小
   領域に辺を接する小領域中に存在する都市から開始都市
   および終了都市を選択し，それらの小領域に都市が存在
   しない場合には，それらの小領域にダミーの都市を配置
   して開始都市または終了都市とする処理を，計算機に実
   行させるプログラムを記録したことを特徴とする巡回セ
   ールスマン問題階層化処理プログラム記録媒体。