(57)【要約】【課題】与えられたＮ個の都市の都市数Ｎや都市配置の依存性が小さく、計算の並列化を自然に行うことが可能な巡回路の作成方法を提供する。【解決手段】与えられた相異なる複数の点を結ぶ巡回路を作成する方法であって、与えられた相異なる複数の点等をデータ入力する手段（１０００）と、与えられた相異なる複数の点を含む領域を分割して格子を作成する手段（２０００）と、前記格子に格子基準点を付与する手段（３０００）と、最隣接する格子の前記格子基準点を、直線で結んで多角形を作成する手段（４０００）と、与えられた相異なる複数の点のそれぞれに最も近い多角形の辺上の格子基準点を特定する手段（５０００）と、与えられた相異なる複数の点を前記特定された格子基準点の当該多角形が定める順序により直線で結ぶ手段（６０００）とを備えたことを特徴とする巡回路の作成方法。【選択図】図１
2007207215.tif 000002
【特許請求の範囲】
【請求項１】
与えられた相異なる複数の点を結ぶ巡回路を作成する方法であって、
与えられた相異なる複数の点を含む領域を分割して格子を作成する手段と、
前記格子に格子基準点を付与する手段と、
最隣接する格子の前記格子基準点を、直線で結んで多角形を作成する手段と、
与えられた相異なる複数の点のそれぞれに最も近い多角形の辺上の格子基準点を特定する手段と、
与えられた相異なる複数の点を前記特定された格子基準点の当該多角形が定める順序により直線で結ぶ手段と
を備えたことを特徴とする巡回路の作成方法。
【請求項２】
請求項１記載の多角形は、
格子の初期形状と格子の分割次数から再帰的に構成され、
格子の分割次数を無限大にした極限でフラクタル図形と
なることを特徴とする巡回路の作成方法。
【請求項３】
請求項１記載の、最隣接する格子の前記格子基準点を、前記格子基準点を
直線で結んで多角形を作成する手段は、
格子の初期形状に対応した記号列と、記号列中の各記号に
再帰的に新たな記号列を代入する操作により得られる記号列により、
前記格子基準点を直線で結ぶ順序を
与えることを特徴とする巡回路の作成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、配送スケジュールの策定やLSIの回路設計等で必要とされる、相異なる複数の点を結ぶ巡回路の作成方法のうち、準最適解としての巡回路の探索のための初期巡回路を設定する、設定法に関するものである。
【背景技術】
【０００２】
相異なる複数の点を結ぶ巡回路の作成方法は、準最適解としての巡回路を見つけるため初期条件としての巡回路を設定する「設定法」と、初期条件としての巡回路を改善して準最適解を探索する「改善法」のふたつがあり、本発明は前者に属するものである。なお、以下の記述においては、慣例に従って相異なる複数の点を「都市」という言葉で代表するものとする。
【０００３】
従来の技術の第１の例としては、最も素朴な方法として「ランダム設定法」が挙げられる。ランダム設定法は、ある都市を出発点として次の都市をランダムに過不足なく結んだ後、最後の都市と出発点を直線で結ぶ方法である。
【０００４】
従来技術の第２の例として、伊理の方法（非特許文献１参照）を取り上げる。伊理の方法は、正方格子を作成してその格子上に順序を与える図形を与えて、その順序に従って都市を結ぶ、都市数Ｎに対してオーダＮの高速解法である。与える図形の例として、正方格子中の渦巻き模様、開いたHilbert線が例示されている。このとき、与える図形が多角形である場合を含め、多角形の座標は予め計算しておく必要がある。なお、都市数Ｎが増大した場合に、オーダＮで多角形を作成する手段は示されていない。
【０００５】
従来の技術の第３の例として、BARTHOLDI. III  ＆ PLATZMANの方法（非特許文献２参照）を取り上げる。彼らは、順序を与える図形として、再帰的な操作の極限でフラクタル図形となる多角形を選び、その周方向の順序に都市座標を射影して巡回路を作成する方法を示した。本方法では、周方向の順序に従って、各都市をソートする処理が入るため、計算量は都市数をＮとするとＮ・ｌｏｇ（Ｎ）となる。
【非特許文献１】伊理雅夫・今井浩・刀根薫  監訳：最適化ハンドブック、朝倉書店(1997)
【非特許文献２】J.J.BARTHOLDI. III  and L.K.PLATZMAN：An O(NlogN) Planar Traveling Salesman Heuristic Based on Spacefilling Curves,  OPERATIONS RESEARCH LETTERS,  Volume1,Number4  (1982)  121-125
【発明の開示】
【発明が解決しようとする課題】
【０００６】
従来の技術の第３の例では、巡回路を求める際に都市数Ｎに対してＮ・ｌｏｇ（Ｎ）のオーダの計算量が必要になる。
【０００７】
また、従来の技術の第１，２の例のように、都市数Ｎのオーダで計算できる設定法は存在するが、必ずしも精度の良い初期値設定が行われていない。これは、たとえば順序を与える図形が巡回路が交差しやすい図形であったり、順序を与える図形が最隣接格子同士を結び付けられないため局所的に不適当な巡回路が発生していることによる。
【０００８】
同様に、従来の技術では、都市数Ｎの増加に伴って、精度が悪化しやすいという傾向があった。これは、都市配置の小さな領域の構造と、都市配置の大きな領域の構造の間での、順序を与える図形による巡回路のトレードオフが、うまく行われていないことに起因する。
【０００９】
同様に従来技術では、精度が都市配置に依存しやすいという傾向があった。これも、都市配置の小さな領域の構造と、都市配置の大きな領域の構造の間での、順序を与える図形による巡回路のトレードオフが、うまく行われていないことに起因する。
【００１０】
最後に、従来技術では、並列計算を行うことは、原理的に可能ではあるが、並列計算用に本質的にコードを書き直す必要がある。
【００１１】
本発明の目的は、都市数Ｎのオーダの計算量で、準最適巡回路を設定する方法を提供することにある。
【００１２】
本発明の他の目的は、準最適巡回路の精度（最適巡回路からの偏差）がより小さい準最適巡回路の設定方法を提供することにある。
【００１３】
本発明の他の目的は、準最適巡回路の精度が都市数Ｎに依存しない、準最適巡回路の設定方法を提供することにある。
【００１４】
本発明の他の目的は、準最適巡回路の精度が都市の配置に依存しない、準最適巡回路の設定方法を提供することにある。
【００１５】
本発明の他の目的は、自然に並列計算が可能な、準最適巡回路の設定方法を提供することにある。
【課題を解決するための手段】
【００１６】
上記目的を達成するために、本発明による巡回路の作成方法は、与えられた相異なる複数の点を含む領域を分割して格子を作成する手段と、前記格子に格子基準点を付与する手段と、最隣接する格子の前記格子基準点を、直線で結んで多角形を作成する手段と、与えられた相異なる複数の点のそれぞれに最も近い多角形の辺上の格子基準点を特定する手段と、与えられた相異なる複数の点を前記特定された格子基準点の当該多角形が定める順序により直線で結ぶ手段を備える。
【００１７】
与えられた相異なる複数の点を前記特定された格子基準点の当該多角形が定める順序により直線で結ぶ手段において、順序を与える図形として多角形を用いていることは、自然に巡回路の交差が多発することを防ぎ、また、精度が悪くなることを防ぐ。
【００１８】
また、与えられた相異なる複数の点を含む領域を分割して格子を作成する手段、ならびに、前記格子に格子基準点を付与する手段、およびに、最隣接する格子の前記格子基準点を直線で結んで多角形を作成する手段によって、順序を与える図形は、単位格子のレベルにおいて、最も緻密な巡回路を与える道具になる。これに加え、これらの手段によって、全ての格子基準点を都市とした場合、その都市数Ｎが増えても、巡回路の厳密な意味での最適巡回路を提供する。
【００１９】
また、前記多角形は、格子の初期形状と格子の分割次数から再帰的に構成され、格子の分割次数を無限大にした極限でフラクタル図形となることを特徴とする。
【００２０】
順序を与える多角形を作成する手段は、格子の初期形状と格子の分割次数から再帰的に構成され、格子の分割次数を無限大にした極限で平面を埋め尽くすフラクタル図形となることを特徴とする。そのため、多角形は自己相似性（部分を拡大すると同じような構造が現れること）をもち、さまざまなスケールにおける精度のトレードオフが、自然に取り込まれている。このことが、準最適巡回路の精度（最適巡回路からの総距離の偏差）が、都市配置に比較的依存しない理由となっている。
【００２１】
さらに、最隣接する格子の前記格子基準点を前記格子基準点を直線で結んで多角形を作成する手段は、格子の初期形状に対応した記号列と、記号列中の各記号に再帰的に新たな記号列を代入する操作により得られる記号列により、前記格子基準点を直線で結ぶ順序を与えることを特徴とする。
【００２２】
最隣接する格子の前記格子基準点を前記格子基準点を直線で結んで多角形を作成する手段は、一言で言えば記号列の代入操作結果を翻訳して行われる。つまり、格子の初期形状に対応した記号列と、記号列中の各記号に再帰的に新たな記号列を代入する操作により得られる記号列により、前記格子基準点を直線で結ぶ順序を与える格子の初期形状に対応した記号列と、記号列中の各記号に再帰的に新たな記号列を代入する手段により、その記号列を解釈して前記格子基準点を直線で結ぶ順序を与えている。このことにより、順序を与える多角形の作成は、都市数Ｎのオーダの計算量で行うことが可能となり、その結果、巡回路の作成も都市数Ｎのオーダで可能となる。
【００２３】
さらに、格子の初期形状に対応した記号列と、記号列中の各記号に再帰的に新たな記号列を代入する操作により得られる記号列により、前記格子基準点を直線で結ぶ順序を与えることによって、巡回路の作成の手順を並列化することは自然にできて、将来並列計算機に搭載することは容易に行える。
【発明の効果】
【００２４】
本発明は、以上のように説明した機能があるので、以下に記載されるような効果がある。
（１）  都市数Ｎのオーダの計算量で、多角形を作成でき、かつ、巡回路の作成においても、都市数Ｎのオーダの計算量で処理ができるため、都市数Ｎのオーダの計算量という高速の準最適解設定法になっている。実績として，１億７６００万点の計算が、市販のＰＣで約３０ｓｅｃで完了することを確認している。
（２）  都市の巡回路の順序を与えている図形が、多角形であるため、得られる巡回路は、巡回路の交差が少ない準最適解になっている。
（３）  最隣接する格子の前記格子基準点を直線で結んで多角形を作成する手段により、都市数の増加による精度低下が経験的に起こらない。これは、全ての格子基準点を都市とした都市配列に対しては、厳密な最適解を与えることがひとつの根拠となっている。
（４）  再帰的に単位格子を細かくして、より細密な多角形を作成するため、経験的に準最適解の精度が、都市配置の依存しにくい。これは、多角形の自己相似性による異なるスケール間の精度の自然なトレードオフによる。実績として、経験的に、最適解のＣ＝１．３〜１．４倍程度の準最適解が得られる。Ｃは何らかの普遍定数と予想されている。
（５）  記号列の代入操作により、巡回路の作成の手順を並列化することは自然にできて、将来並列計算機に搭載することは容易に行える。
【発明を実施するための最良の形態】
【００２５】
以下、本発明の実施例を、簡単なデータを用いて説明する。実施例の説明においては、「与えられた相異なる複数の点」を慣例に従って「都市」という言葉で表現し、その座標を「都市座標」と称する。
【００２６】
図１に、巡回路作成の概略手順を示す。手順は、大きく６つのステップに分かれる。
（１）  データ入力ステップ  １０００
（２）  格子の作成ステップ  ２０００
（３）  格子基準点の付与ステップ  ３０００
（４）  多角形の作成ステップ  ４０００
（５）  最近接格子基準点の特定ステップ  ５０００
（６）  巡回路の作成ステップ  ６０００
データ入力ステップ１０００では、都市番号の入力１１００と都市座標の入力１２００、  ならびに格子の分割次数１３００を入力する。本明細書で扱うデータを、図２に示す。都市番号１１１０は１から始まる整数を割り付け、最大の都市番号が与えた都市数になるように設定する。また、それぞれの都市のｘ座標とｙ座標１２１０を設定する。また、図２に都市１を２１０１で、都市番号順に都市を結んだ折れ線を２１０２で、都市を含む領域を２１０３で示す。格子の分割次数とは、都市を含む領域２１０３を、ｘ座標ならびにｙ座標方向に２のｒ乗分割したときの自然数ｒと定義する。すなわち、１辺１００００の正方形を、一辺１２５０の正方形に分割した場合には、合計６４個＝２2r個となるので、分割次数はｒ＝３となる。
【００２７】
格子の作成ステップ２０００では、都市を含む領域の設定２１００と、領域の分割による格子作成２２００を行う。本実施例では、巡回路の作成を図３中の[０，１００００]×[０，１００００]の正方形の標準的領域２１０５で実施する。都市の座標は、任意に与えられる。そのため、図２に示した都市の座標に、適切なスケール変換と適切な平行移動を施して、標準的領域に変数変換する。変数変換は次の手順で行われる。
【００２８】
ａ）都市｛（ｘｉ、ｙｉ）｜１≦ｉ≦１０、ｉは自然数｝の重心座標を求める。これを，（ｘｃ、ｙｃ）とおく。
【００２９】
ｂ）都市の重心を標準的正方形の重心（（５０００．０、５０００．０）に平行移動して、適当なスケール変換（本実施例では、１０．０倍）を施す。式で表すと
Ｘｉ＝１０．０＊（ｘｉ−ｘｃ）＋５０００．０      ・・・（１−ａ）
Ｙｉ＝１０．０＊（ｙｉ−ｙｃ）＋５０００．０      ・・・（１−ｂ）
このようにして得られた新しい都市座標｛（Ｘｉ，Ｙｉ）｜１≦ｉ≦１０、ｉは自然数｝が、図２の新ｘ座標、新ｙ座標２１１０である。本実施例では、領域の設定２１００における領域とは、図３中の[０，１００００]×[０，１００００]の正方形の標準的領域２１０５である。また、領域の設定とは、各都市座標を（１−ａ）、（１−ｂ）のように座標変換することを指す。このとき、各都市は、可能な限り標準的領域に均等に分布させる。図３に、座標変換後の都市２１０６を含む領域の設定を示す。
【００３０】
次に、領域の分割による格子の作成２２００について説明する。図４の領域の分割による格子作成の中の、正方形２２７０が変数変換後の標準的領域である。本実施例では、標準的領域が正方形であり、かつ、分割次数をｒ＝３と決めるので、２2r＝６４個の正方格子を作成することになる。図４の領域の分割による格子作成に、その手順を表した。分割次数ｒ＝１の場合には、太い実線２２１６、２２４８によって、４個の正方形の格子ができる。さらに、分割次数がｒ＝２の場合には、細い実線２２０８、２２２４、２２４０、２２５６によって、１６個の正方形の格子ができる。以下同様に、分割次数がｒ＝３の場合には、一点鎖線２２０４，２２１２，２２２０，２２２８，２２３６，２２４４，２２５２，２２６０によって６４個の正方形の格子ができる。このように作成された６４個の正方形の格子２２８０等を、以下「単位格子」と称する。
【００３１】
格子基準点の付与ステップ３０００では、作成された各々の格子に基準点を付与する。図５の標準的領域３１００にその様子を示す。格子基準点３２００は、都市が属する格子を表す指標であり、これから作成する多角形（都市を直線で結ぶための順序を与える役割を持つ）を誘導する（頂点あるいは辺上の一点となる）役割を持つ。本実施例の場合には、作成された正方格子の重心を格子基準点とする。すなわち、格子基準点を座標で表現すれば、
｛（Ｓi、Ｔj）｜１≦ｉ，ｊ≦２r＋１、ｉ、ｊは自然数、
Ｓi＝（Ｘi＋Ｘi+1）／２                  ・・・（２−ａ）
Ｔj＝（Ｙj＋Ｙj+1）／２                  ・・・（２−ｂ）
Ｘi＝１００００・（ｉ−１）／２r、
Ｙj＝１００００・（ｊ−１）／２r            ・・・（２−ｃ）｝
となる。
【００３２】
多角形の作成ステップ４０００では、ある記号列を作成して、その記号列と格子基準点を基に、多角形を作成する。記号列の作成ステップ４１００では、分割次数ｒに応じて再帰的に記号列を作成する。本実施例では、記号列の最小単位である記号は、以下の５種類を用いる。
【００３３】
ａ）ｘ：代入変数記号１                                ・・・（３−１ａ）
ｂ）ｙ：代入変数記号２                        ・・・（３−１ｂ）
ｃ）Ｆ：単位格子の１辺のみ進む操作            ・・・（３−１ｃ）
ｄ）＋：時計回りに９０度回転する操作            ・・・（３−１ｄ）
ｅ）−：反時計回りに９０度回転する操作            ・・・（３−１ｅ）
次に、上記５種類の記号を用いた任意の記号列Ｚ（ｒ）から、再帰的に記号列Ｚ（ｒ+１）を求める操作をＰで表す。本実施例では、Ｐは次のような演算となる。
【００３４】
Ｐ（ｘ）＝＋ｙＦ−ｘＦｘ−Ｆｙ＋            ・・・（３−２ａ）
Ｐ（ｙ）＝−ｘＦ＋ｙＦｙ＋Ｆｘ−            ・・・（３−２ｂ）
Ｐ（Ｆ）＝Ｆ                              ・・・（３−２ｃ）
Ｐ（＋）＝＋                              ・・・（３−２ｄ）
Ｐ（−）＝−                              ・・・（３−２ｅ）
複数の記号列の場合には、記号の順番はそのままで、（３−ａ）〜（３−ｅ）により変換された記号列が引数としての記号に代入される。たとえば、
Ｐ（＋Ｆｙ）＝Ｐ（＋）Ｐ（Ｆ）Ｐ（ｙ）
＝＋ＦＰ（ｙ）＝＋Ｆ−ｘＦ＋ｙＦｙ＋Ｆｘ−  ・・・（３−ｆ）
本実施例では、初期記号列Ｚ（１）を次のように設定する。
【００３５】
Ｚ（１）＝ｘＦｘ−Ｆ−ｘＦｘ−Ｆ            ・・・（３−ｇ）
これは、分割次数ｒ＝１の場合の記号列に相当する。本実施例では、分割次数がｒ＝３なので、作成する記号列は、
Ｚ（３）＝Ｐ2（Ｚ（１））
＝−ｘＦ＋ｙＦｙ＋Ｆｘ−Ｆ−
・・・・・・
−ｘＦ＋ｙＦｙ＋Ｆｘ−＋−Ｆ      ・・・（３−ｈ）
となる。
【００３６】
格子基準点と記号列による多角形の作成ステップ４２００では、格子基準点間を移動する、向きが可変の単位ベクトルを想定し、ステップ４１００で作成した記号列Ｚ（３）を向きが可変の単位ベクトルの状態遷移命令として解釈することで、多角形を作成する。図６に多角形の作成を、概念的に示した。向きが可変の単位ベクトル４２０１は、本実施例における初期座標４２０５に、−π／２の向きに設定される。記号列（３−ｈ）は、記号列の終わりから順に、（３−１ａ）〜（３−１ｅ）の操作を、向きが可変の単位ベクトル４２０１に施すように解釈される。たとえば、単位ベクトル４２０１は、記号Ｆ  ４１１０によって、単位格子の１辺４２１０のみ進む。次に、記号列−＋−  ４１２０は、単位ベクトルの向きを反時計回りにπ／２回転させ、記号列ＦＸ  ４１３０で、単位格子の１辺４２３０のみ進む。このとき、記号Ｘは、再帰的に記号列を作成する際の代入変数記号１であるため、単位ベクトル４２０１に対しては、何も作用しない。同様に、記号列４１４０、４１５０に対しては、単位格子の１辺４２５０のみ進ませ、記号列４１６０、４１７０に対しては、単位格子の１辺４２７０のみ進ませる。以下同様にして、単位ベクトル４２０１の辿った跡が一巡して、多角形４２８０が作成される。
【００３７】
最近接格子基準点の特定ステップ５０００では、各都市座標に一番近い格子基準点を特定する。図７に本実施例の都市座標による最近接格子基準点の特定の例を示す。第１番目の都市５１１０が含まれる単位格子５２１０の格子基準点５３１０が、第１番目の都市５１１０の最近接格子基準点である。以下同様に、第２番目の都市５１２０が含まれる単位格子５２２０の格子基準点５３２０が、第２番目の都市５１２０の最近接格子基準点であり、第１０番目の都市５２００が含まれる単位格子５３００の格子基準点５４００が、第１０番目の都市５２００の最近接格子基準点である。一般には、各都市が、単位格子の中（境界線を除く）に複数の都市が存在し、かつ、単位格子の境界線上に都市が存在する場合を扱う必要がある。単位格子の中（境界線を除く）に複数の都市が存在する場合には、最近接格子基準点は一意的に決まるが、単位格子の境界線上に都市が存在する場合には一意的に決まらないため、次の巡回路作成ステップ６０００ではそのような状況を加味した処理を行う。
【００３８】
巡回路の作成ステップ６０００では、多角形の作成ステップ４０００で作成された多角形の外周順序に従って、各都市の最近接格子基準点を順序付けて、当該順序で各都市を直線で結び、所望の巡回路を作成する。図８の巡回路の作成に、本実施例における巡回路の作成手順を示す。まず、多角形の作成ステップ４０００で作成された多角形８２８０の反時計回りの外周順序に従って、各都市の最近接格子基準点を順序付ける。第１都市８０１０を起点とすると、各都市の最近接格子基準点は、８１１０、８１８０、８１２０、８１４０、８２００、８１７０、８１３０、８１９０、８１５０、８１６０と順序付けられる。次に、各都市の最近接格子基準点の順序に対応させて、各都市を、８０１０、８０８０、８０２０、８０４０、８１００、８０７０、８０３０、８０９０、８０５０、８０６０と順序づける。最後に、各都市の順序付けに従って、都市間に直線を引いて、巡回路８３００を得る。なお、単位格子中に複数の点がある場合には、「最近接法」、すなわち当該単位格子中の都市の中で、最も近い都市から順に直線で結んで、次の単位格子に向かう方法を採用する。合い隣り合う単位格子の境界上に都市が存在する場合も、順序が先の単位格子の中で、「最近接法」の処理を行うことで、巡回路の作成が完遂可能となる。また、あまりにも単位格子中の都市数が多い場合には、当該単位格子の中で、本実施例で述べている方法で巡回路を作成しておき、後で適切につなげるという、再帰的な処理も可能である。
【００３９】
図９の初期巡回路作成比較で、「ランダム設定法」、「伊理の方法」、「当該巡回路の作成方法」の３手法で、初期巡回路を作成した例を示す。選んだ問題は、ＰＬＡ７３９７と呼ばれる都市数７３９７の問題である。９１００は、ランダム設定法で得られた巡回路、９２００は、伊理の方法で得られた巡回路、９３００は、当該巡回路の作成方法で得られた巡回路であり、９３００の巡回路の総距離は、最適解の約１．４１倍である。以上で、与えられた相異なる複数の点を結ぶ巡回路の作成の実施例の説明を終える。
【図面の簡単な説明】
【００４０】
【図１】巡回路の作成の概略手順
【図２】初期都市座標と座標変換の実施例
【図３】座標変換後の都市を含む領域の設定
【図４】領域の分割による格子作成の実施例
【図５】格子基準点の付与の実施例
【図６】多角形の作成の実施例
【図７】最近接格子基準点の特定の実施例
【図８】巡回路の作成の実施例
【図９】初期巡回路作成比較の実施例
【符号の説明】
【００４１】
１０００  データ入力ステップ
２０００  格子の作成ステップ
３０００  格子基準点の付与ステップ
４０００  多角形の作成ステップ
５０００  最近接格子基準点の特定ステップ
６０００  巡回路の作成ステップ
【図１】
2007207215.tif 000003
【図２】
2007207215.tif 000004
【図３】
2007207215.tif 000005
【図４】
2007207215.tif 000006
【図５】
2007207215.tif 000007
【図６】
2007207215.tif 000008
【図７】
2007207215.tif 000009
【図８】
2007207215.tif 000010
【図９】
2007207215.tif 000011