(57)【要約】【課題】最適巡回路解を効率的に精度良く探索する。【解決手段】評価基準を選択し、その選択した評価基準に応じたマトリクス情報を作成し、巡回対象となる巡回点の中から巡回開始点（初期点）を決定する。続いて、作成したマトリクス情報に基づいて、決定した巡回開始点を含む第１の部分最適巡回路に該第１の部分巡回路上の巡回点以外の巡回点を１つ加えた第２の部分最適巡回路（部分最適巡回路の初期解）を作成し、この作成した第２の部分最適巡回路に対し再最適化調整を行う、という処理を、再最適化調整を行った第２の部分最適巡回路上の巡回点が巡回対象となる全ての巡回点になるまで繰り返し行う。【選択図】      図２
2004302896.tif 000002
【特許請求の範囲】
【請求項１】
評価基準を選択し、
該選択した評価基準に応じたマトリクス情報を作成し、
巡回対象となる巡回点の中から巡回開始点を決定し、
前記作成したマトリクス情報に基づいて、前記決定した巡回開始点を含む第１の部分最適巡回路に該第１の部分巡回路上の巡回点以外の巡回点を１つ加えた第２の部分最適巡回路を作成するという処理を、該第２の部分最適巡回路上の巡回点が前記巡回対象となる全ての巡回点になるまで繰り返し行う、
ことを特徴とする最適巡回路探索方法。
【請求項２】
評価基準を選択し、
該選択した評価基準に応じたマトリクス情報を作成し、
巡回対象となる巡回点の中から巡回開始点を決定し、
前記作成したマトリクス情報に基づいて、前記決定した巡回開始点を含む第１の部分最適巡回路に該第１の部分巡回路上の巡回点以外の巡回点を１つ加えた第２の部分最適巡回路を作成し、該作成した第２の部分最適巡回路に対し再最適化調整を行うという処理を、前記再最適化調整を行った前記第２の部分最適巡回路上の巡回点が前記巡回対象となる全ての巡回点になるまで繰り返し行う、
ことを特徴とする最適巡回路探索方法。
【請求項３】
前記評価基準は、
少なくとも、距離、時間、及びコストのうちの何れか一つ又は複数を含む、
ことを特徴とする請求項１又は２記載の最適巡回路探索方法。
【請求項４】
前記マトリクス情報の作成では、
前記選択した評価基準に応じて、少なくとも、巡回対象となる巡回点の座標情報又は前記巡回対象となる巡回点の各巡回点間の距離情報、前記巡回対象となる巡回点の各巡回点間の移動方式、該移動方式下の所要時間情報、前記移動方式下の所要コスト情報、及び移動主体の単位時間でのコスト情報、のうちの何れか一つ又は複数の情報に基づいて、少なくとも、前記巡回対象となる巡回点の各巡回点間の距離、前記巡回対象となる巡回点の各巡回点間の最短所要時間、前記巡回対象となる巡回点の各巡回点間の最小総コスト、及び前記巡回対象となる巡回点の各巡回点の距離と最短所要時間と最小総コストのうちの何れか一つ或いは複数の積からなるもの、のうちの何れか一つに係るマトリクス情報を作成する、
ことを特徴とする請求項１乃至３の何れか一項記載の最適巡回路探索方法。
【請求項５】
前記第２の部分最適巡回路の作成では、
各巡回点間の枝の内容を前記作成したマトリクス情報に応じた値とし、前記第１の部分最適巡回路上の各巡回点間の各枝に対し、当該枝をＢ１とし、該枝Ｂ１の両端点となる２つの巡回点をＰｂ  ，Ｐｃ  とし、前記第１の部分最適巡回路上の巡回点以外の１つの巡回点をＰｄ  とし、前記巡回点Ｐｂ  と前記巡回点Ｐｄ  を結ぶ枝をＢ２とし、前記巡回点Ｐｃ  と前記巡回点Ｐｄ  を結ぶ枝をＢ３としたときに、Ｂ２＋Ｂ３−Ｂ１の値が最小となるような前記枝Ｂ１と前記巡回点Ｐｄ  を求め、このときの前記枝Ｂ１と前記巡回点Ｐｄ  とから、前記巡回点Ｐｄ  と前記枝Ｂ１の両端点となる前記巡回点Ｐｂ  ，Ｐｃ  を結ぶ前記枝Ｂ２，Ｂ３を新たに設けると共に、前記枝Ｂ１を削除することにより、前記第２の部分最適巡回路を作成する、
ことを特徴とする請求項１乃至４の何れか一項記載の最適巡回路探索方法。
【請求項６】
前記再最適化調整では、
各巡回点間の枝の内容を前記作成したマトリクス情報に応じた値とし、前記第２の部分最適巡回路上の各巡回点に対し、当該巡回点をＰｅ  とし、該巡回点Ｐｅ  に接続される２つの枝をＢ４，Ｂ５とし、前記巡回点Ｐｅ  に枝Ｂ４，Ｂ５を介して接続される巡回点をＰｆ  ，Ｐｇ  とし、該巡回点Ｐｆ  ，Ｐｇ  を結ぶ枝をＢ６とし、前記巡回点Ｐｅ  に接続されてない前記枝Ｂ６以外の１つの枝をＢ７とし、該枝Ｂ７の両端点となる両巡回点をＰｈ  ，Ｐｉ  とし、前記巡回点Ｐｅ  と前記巡回点Ｐｈ  を結ぶ枝をＢ８とし、前記巡回点Ｐｅ  と前記巡回点Ｐｉ  を結ぶ枝をＢ９としたときに、Ｂ６−Ｂ４−Ｂ５＋Ｂ８＋Ｂ９−Ｂ７＜０となるものがあったときには、そのときの前記枝Ｂ４，Ｂ５，Ｂ７を削除すると共に、前記枝Ｂ６，Ｂ８，Ｂ９を新たに設けることにより、前記第２の部分最適巡回路に対し再最適化調整を行う、
ことを特徴とする請求項２記載の最適巡回路探索方法。
【請求項７】
コンピュータに、
評価基準を選択する機能と、
該選択した評価基準に応じたマトリクス情報を作成する機能と、
巡回対象となる巡回点の中から巡回開始点を決定する機能と、
前記作成したマトリクス情報に基づいて、前記決定した巡回開始点を含む第１の部分最適巡回路に該第１の部分巡回路上の巡回点以外の巡回点を１つ加えた第２の部分最適巡回路を作成するという処理を、該第２の部分最適巡回路上の巡回点が前記巡回対象となる全ての巡回点になるまで繰り返し行う機能と、
を実現させるための最適巡回路探索プログラム。
【請求項８】
コンピュータに、
評価基準を選択する機能と、
該選択した評価基準に応じたマトリクス情報を作成する機能と、
巡回対象となる巡回点の中から巡回開始点を決定する機能と、
前記作成したマトリクス情報に基づいて、前記決定した巡回開始点を含む第１の部分最適巡回路に該第１の部分巡回路上の巡回点以外の巡回点を１つ加えた第２の部分最適巡回路を作成し、該作成した第２の部分最適巡回路に対し再最適化調整を行うという処理を、前記再最適化調整を行った前記第２の部分最適巡回路上の巡回点が前記巡回対象となる全ての巡回点になるまで繰り返し行う機能と、
を実現させるための最適巡回路探索プログラム。
【請求項９】
前記第２の部分最適巡回路の作成では、
各巡回点間の枝の内容を前記作成したマトリクス情報に応じた値とし、前記第１の部分最適巡回路上の各巡回点間の各枝に対し、当該枝をＢ１とし、該枝Ｂ１の両端点となる２つの巡回点をＰｂ  ，Ｐｃ  とし、前記第１の部分最適巡回路上の巡回点以外の１つの巡回点をＰｄ  とし、前記巡回点Ｐｂ  と前記巡回点Ｐｄ  を結ぶ枝をＢ２とし、前記巡回点Ｐｃ  と前記巡回点Ｐｄ  を結ぶ枝をＢ３としたときに、Ｂ２＋Ｂ３−Ｂ１の値が最小となるような前記枝Ｂ１と前記巡回点Ｐｄ  を求め、このときの前記枝Ｂ１と前記巡回点Ｐｄ  とから、前記巡回点Ｐｄ  と前記枝Ｂ１の両端点となる前記巡回点Ｐｂ  ，Ｐｃ  を結ぶ前記枝Ｂ２，Ｂ３を新たに設けると共に、前記枝Ｂ１を削除することにより、前記第２の部分最適巡回路を作成する、
ことを特徴とする請求項７又は８記載の最適巡回路探索プログラム。
【請求項１０】
前記再最適化調整では、
各巡回点間の枝の内容を前記作成したマトリクス情報に応じた値とし、前記第２の部分最適巡回路上の各巡回点に対し、当該巡回点をＰｅ  とし、該巡回点Ｐｅ  に接続される２つの枝をＢ４，Ｂ５とし、前記巡回点Ｐｅ  に枝Ｂ４，Ｂ５を介して接続される巡回点をＰｆ  ，Ｐｇ  とし、該巡回点Ｐｆ  ，Ｐｇ  を結ぶ枝をＢ６とし、前記巡回点Ｐｅ  に接続されてない前記枝Ｂ６以外の１つの枝をＢ７とし、該枝Ｂ７の両端点となる両巡回点をＰｈ  ，Ｐｉ  とし、前記巡回点Ｐｅ  と前記巡回点Ｐｈ  を結ぶ枝をＢ８とし、前記巡回点Ｐｅ  と前記巡回点Ｐｉ  を結ぶ枝をＢ９としたときに、Ｂ６−Ｂ４−Ｂ５＋Ｂ８＋Ｂ９−Ｂ７＜０となるものがあったときには、そのときの前記枝Ｂ４，Ｂ５，Ｂ７を削除すると共に、前記枝Ｂ６，Ｂ８，Ｂ９を新たに設けることにより、前記第２の部分最適巡回路に対し再最適化調整を行う、
ことを特徴とする請求項８記載の最適巡回路探索プログラム。
【請求項１１】
評価基準を選択する選択手段と、
該選択手段により選択された評価基準に応じたマトリクス情報を作成する作成手段と、
巡回対象となる巡回点の中から巡回開始点を決定する決定手段と、
前記作成手段により作成されたマトリクス情報に基づいて、前記決定手段により決定された巡回開始点を含む第１の部分最適巡回路に該第１の部分巡回路上の巡回点以外の巡回点を１つ加えた第２の部分最適巡回路を作成するという処理を、該第２の部分最適巡回路上の巡回点が前記巡回対象となる全ての巡回点になるまで繰り返し行う制御手段と、
を有することを特徴とする最適巡回路探索装置。
【請求項１２】
評価基準を選択する選択手段と、
該選択手段により選択された評価基準に応じたマトリクス情報を作成する作成手段と、
巡回対象となる巡回点の中から巡回開始点を決定する決定手段と、
前記作成手段により作成されたマトリクス情報に基づいて、前記決定手段により決定された巡回開始点を含む第１の部分最適巡回路に該第１の部分巡回路上の巡回点以外の巡回点を１つ加えた第２の部分最適巡回路を作成し、該作成した第２の部分最適巡回路に対し再最適化調整を行うという処理を、前記再最適化調整を行った前記第２の部分最適巡回路上の巡回点が前記巡回対象となる全ての巡回点になるまで繰り返し行う制御手段と、
を有することを特徴とする最適巡回路探索装置。
【請求項１３】
前記第２の部分最適巡回路の作成では、前記制御手段は、
各巡回点間の枝の内容を前記作成したマトリクス情報に応じた値とし、前記第１の部分最適巡回路上の各巡回点間の各枝に対し、当該枝をＢ１とし、該枝Ｂ１の両端点となる２つの巡回点をＰｂ  ，Ｐｃ  とし、前記第１の部分最適巡回路上の巡回点以外の１つの巡回点をＰｄ  とし、前記巡回点Ｐｂ  と前記巡回点Ｐｄ  を結ぶ枝をＢ２とし、前記巡回点Ｐｃ  と前記巡回点Ｐｄ  を結ぶ枝をＢ３としたときに、Ｂ２＋Ｂ３−Ｂ１の値が最小となるような前記枝Ｂ１と前記巡回点Ｐｄ  を求め、このときの前記枝Ｂ１と前記巡回点Ｐｄ  とから、前記巡回点Ｐｄ  と前記枝Ｂ１の両端点となる前記巡回点Ｐｂ  ，Ｐｃ  を結ぶ前記枝Ｂ２，Ｂ３を新たに設けると共に、前記枝Ｂ１を削除することにより、前記第２の部分最適巡回路を作成する、
ことを特徴とする請求項１１又は１２記載の最適巡回路探索装置。
【請求項１４】
前記制御手段による前記再最適化調整では、
各巡回点間の枝の内容を前記作成したマトリクス情報に応じた値とし、前記第２の部分最適巡回路上の各巡回点に対し、当該巡回点をＰｅ  とし、該巡回点Ｐｅ  に接続される２つの枝をＢ４，Ｂ５とし、前記巡回点Ｐｅ  に枝Ｂ４，Ｂ５を介して接続される巡回点をＰｆ  ，Ｐｇ  とし、該巡回点Ｐｆ  ，Ｐｇ  を結ぶ枝をＢ６とし、前記巡回点Ｐｅ  に接続されてない前記枝Ｂ６以外の１つの枝をＢ７とし、該枝Ｂ７の両端点となる両巡回点をＰｈ  ，Ｐｉ  とし、前記巡回点Ｐｅ  と前記巡回点Ｐｈ  を結ぶ枝をＢ８とし、前記巡回点Ｐｅ  と前記巡回点Ｐｉ  を結ぶ枝をＢ９としたときに、Ｂ６−Ｂ４−Ｂ５＋Ｂ８＋Ｂ９−Ｂ７＜０となるものがあったときには、そのときの前記枝Ｂ４，Ｂ５，Ｂ７を削除すると共に、前記枝Ｂ６，Ｂ８，Ｂ９を新たに設けることにより、前記第２の部分最適巡回路に対し再最適化調整を行う、
ことを特徴とする請求項１２記載の最適巡回路探索装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、複数の巡回点を重複なしに全て巡回する場合に、その最適な巡回路を探索する方法、プログラム、及び装置に関する。
【０００２】
【従来の技術】
従来、２点間の最適経路（最短経路等）や、いわゆる巡回セールスマン問題のように複数の巡回点を重複なしに全て巡回する場合の最適巡回路（最短巡回路等）をコンピュータを用いて探索する、といったことが行われている。
【０００３】
例えば、２点間の最適経路の探索を行うものとして、特許文献１には、道路地図データにもとづいて、その道路地図上に設定された２点間を結ぶ各経路における距離，走行時間，道幅，右左折回数などの複数のコストをパラメータにとった予め設定された総合評価関数を用いて、その数値を最小にする経路を探索する際に、所定の処理を行うことによって、次第に運転者の好みを反映した最適経路を優先的に探索できるようにした装置が提案されている。
【０００４】
一方で、巡回セールスマン問題においては、有限時間で理論的最適巡回路解（理論的最短巡回路解等）を求めることができないことが証明されており、この場合には近似解を求めることになる。その解法の評価の基準は、探索時間と求まった巡回路解の精度になる。尚、巡回路解の精度とは、例えば最短巡回路解を求めた場合には、その巡回路解が理論的最短巡回路解と比べてどの程度長いかを表すものであり、精度が０％の場合は理論的最短巡回路と同一長さの巡回路ということになり、精度が１０％の場合は理論的最短巡回路に比べて１０％長い巡回路ということになる。通常、探索時間と求まった巡回路解の精度には対立関係があり、探索時間を短くすれば精度が低くなり、精度を高くすれば探索時間が長くなるという関係にある。
【０００５】
例えば、最新の研究成果で探索時間が短く、かつ精度も高い、リアルタイム性が最も高いといわれるポップフィールド型ニューラルネットモデルによる方式により最短巡回路解を求めた場合、探索に要する処理時間はワークステーションで０．１秒以下だが、求まった巡回路解の精度は理論的最短巡回路解に対して平均３７％となっている。また、一方で、０％に近い平均精度を得られる方式もあるが、ワークステーションでの探索に数時間の処理時間を要している。
【０００６】
このように、従来の最適巡回路探索においては、探索に要する処理時間が短いものでは精度が１０〜４０％となり、精度の高いものでは探索に長時間（中には数十時間というものもある）の処理時間を要している。
【０００７】
【特許文献１】
特開平５−２２４６０１号公報
【０００８】
【発明が解決しようとする課題】
このようなことから、前述のポップフィールド型ニューラルネットモデル等の従来の方式に比べ、より巡回路（巡回路解）の精度が高く且つ探索時間が短い巡回路を探索する手法が望まれていた。
【０００９】
本発明は、上記実情に鑑み、最適巡回路解を効率的に精度良く探索し得る、最適巡回路探索方法、最適巡回路探索プログラム、及び最適巡回路探索装置を提供することを目的とする。
【００１０】
【課題を解決するための手段】
本発明の第１の態様は、評価基準を選択し、該選択した評価基準に応じたマトリクス情報を作成し、巡回対象となる巡回点の中から巡回開始点を決定し、前記作成したマトリクス情報に基づいて、前記決定した巡回開始点を含む第１の部分最適巡回路に該第１の部分巡回路上の巡回点以外の巡回点を１つ加えた第２の部分最適巡回路を作成するという処理を、該第２の部分最適巡回路上の巡回点が前記巡回対象となる全ての巡回点になるまで繰り返し行う、ようにした最適巡回路探索方法である。
【００１１】
上記の方法によれば、選択された評価基準に応じて作成されたマトリクス情報に基づいて、第１の部分最適巡回路から巡回点の一つ多い第２の部分最適巡回路を作成する、といった処理が繰り返し行われることによって、巡回対象となる全ての巡回点を巡回する最適巡回路の探索が行われるようになり、最適巡回路を効率的に精度良く探索することができる。
【００１２】
本発明の第２の態様は、評価基準を選択し、該選択した評価基準に応じたマトリクス情報を作成し、巡回対象となる巡回点の中から巡回開始点を決定し、前記作成したマトリクス情報に基づいて、前記決定した巡回開始点を含む第１の部分最適巡回路に該第１の部分巡回路上の巡回点以外の巡回点を１つ加えた第２の部分最適巡回路を作成し、該作成した第２の部分最適巡回路に対し再最適化調整を行うという処理を、前記再最適化調整を行った前記第２の部分最適巡回路上の巡回点が前記巡回対象となる全ての巡回点になるまで繰り返し行う、ようにした最適巡回路探索方法である。
【００１３】
上記の方法によれば、選択された評価基準に応じて作成されたマトリクス情報に基づいて、第１の部分最適巡回路から巡回点の一つ多い第２の部分最適巡回路を作成して再最適化調整を行う、といった処理が繰り返し行われることによって、巡回対象となる全ての巡回点を巡回する最適巡回路の探索が行われるようになる。本方法では、第２の部分最適巡回路の作成後に再最適化調整が行われているので、より精度の高い最適巡回路を得ることができる。
【００１４】
本発明の第３の態様は、上記第１又は第２の態様において、前記評価基準は、少なくとも、距離、時間、及びコストのうちの何れか一つ又は複数を含む、ようにした方法である。
【００１５】
この方法によれば、少なくとも、距離が最短となる巡回路、時間が最短となる巡回路、コストが最安となる巡回路、距離が短く且つ時間が短い巡回路、距離が短く且つコストが安い巡回路、時間が短く且つコストが安い巡回路、又は距離が短く且つ時間が短く且つコストが安い巡回路、の何れかの巡回路の探索が行われるようになり、これら各種の最適巡回路の作成が可能になる。
【００１６】
本発明の第４の態様は、上記第１乃至第３の何れか一つの態様において、前記マトリクス情報の作成では、前記選択した評価基準に応じて、少なくとも、巡回対象となる巡回点の座標情報又は前記巡回対象となる巡回点の各巡回点間の距離情報、前記巡回対象となる巡回点の各巡回点間の移動方式、該移動方式下の所要時間情報、前記移動方式下の所要コスト情報、及び移動主体の単位時間でのコスト情報、のうちの何れか一つ又は複数の情報に基づいて、少なくとも、前記巡回対象となる巡回点の各巡回点間の距離、前記巡回対象となる巡回点の各巡回点間の最短所要時間、前記巡回対象となる巡回点の各巡回点間の最小総コスト、及び前記巡回対象となる巡回点の距離と最短所要時間と最小総コストのうちの何れか一つ或いは複数の積からなるもの、のうちの何れか一つに係るマトリクス情報を作成する、ようにした方法である。
【００１７】
この方法によれば、選択された評価基準に応じて、前述の巡回対象となる巡回点の座標情報等の情報のうちの何れか一つ又は複数の情報に基づいて、前述の巡回対象となる巡回点の各巡回点間の距離等のうちの何れか一つに係るマトリクス情報が作成されるようになる。例えば、選択された評価基準が時間であるときには、巡回対象となる巡回点の各巡回点間の移動方式とその移動方式下の所要時間情報に基づいて、巡回対象となる巡回点の各巡回点間の最短所要時間に係るマトリクス情報が作成される。
【００１８】
本発明の第五の態様は、上記第１乃至第４の何れか一つの態様において、前記第２の部分最適巡回路の作成では、各巡回点間の枝の内容を前記作成したマトリクス情報に応じた値とし、前記第１の部分最適巡回路上の各巡回点間の各枝に対し、当該枝をＢ１とし、該枝Ｂ１の両端点となる２つの巡回点をＰｂ  ，Ｐｃ  とし、前記第１の部分最適巡回路上の巡回点以外の１つの巡回点をＰｄ  とし、前記巡回点Ｐｂ  と前記巡回点Ｐｄ  を結ぶ枝をＢ２とし、前記巡回点Ｐｃ  と前記巡回点Ｐｄ  を結ぶ枝をＢ３としたときに、Ｂ２＋Ｂ３−Ｂ１の値が最小となるような前記枝Ｂ１と前記巡回点Ｐｄ  を求め、このときの前記枝Ｂ１と前記巡回点Ｐｄ  とから、前記巡回点Ｐｄ  と前記枝Ｂ１の両端点となる前記巡回点Ｐｂ  ，Ｐｃ  を結ぶ前記枝Ｂ２，Ｂ３を新たに設けると共に、前記枝Ｂ１を削除することにより、前記第２の部分最適巡回路を作成する、ようにした方法である。
【００１９】
この方法によれば、このようにして第１の部分最適巡回路から巡回点が一つ多い第２の部分最適巡回路が作成されることによって、最適巡回路を効率的に精度良く探索することができる。
【００２０】
本発明の第６の態様は、上記第２の態様において、前記再最適化調整では、各巡回点間の枝の内容を前記作成したマトリクス情報に応じた値とし、前記第２の部分最適巡回路上の各巡回点に対し、当該巡回点をＰｅ  とし、該巡回点Ｐｅ  に接続される２つの枝をＢ４，Ｂ５とし、前記巡回点Ｐｅ  に枝Ｂ４，Ｂ５を介して接続される巡回点をＰｆ  ，Ｐｇ  とし、該巡回点Ｐｆ  ，Ｐｇ  を結ぶ枝をＢ６とし、前記巡回点Ｐｅ  に接続されてない前記枝Ｂ６以外の１つの枝をＢ７とし、該枝Ｂ７の両端点となる両巡回点をＰｈ  ，Ｐｉ  とし、前記巡回点Ｐｅ  と前記巡回点Ｐｈ  を結ぶ枝をＢ８とし、前記巡回点Ｐｅ  と前記巡回点Ｐｉ  を結ぶ枝をＢ９としたときに、Ｂ６−Ｂ４−Ｂ５＋Ｂ８＋Ｂ９−Ｂ７＜０となるものがあったときには、そのときの前記枝Ｂ４，Ｂ５，Ｂ７を削除すると共に、前記枝Ｂ６，Ｂ８，Ｂ９を新たに設けることにより、前記第２の部分最適巡回路に対し再最適化調整を行う、ようにした方法である。
【００２１】
この方法によれば、このようにして、作成された第２の部分最適巡回路に対し再最適化調整が行われることによって、より精度高い最適巡回路を探索することができる。
【００２２】
また、本発明は、上記最適巡回路探索方法に限らず、最適巡回路探索プログラム、或いは最適巡回路探索装置として構成することも可能である。
【００２３】
【発明の実施の形態】
以下、本発明の実施の形態を図面を参照しながら説明する。
図１は、本発明の一実施の形態に係る最適巡回路探索装置の構成例を示した図である。
【００２４】
同図に示したように、本装置は、ＣＰＵ（中央演算処理装置）１、メモリ２、入力部３、出力部４、記憶部５、記録媒体駆動部６、及びネットワーク接続部７等を備え、それらはバス８により互いに接続されている。
【００２５】
メモリ２は、例えば、ＲＯＭ（ｒｅａｄ  ｏｎｌｙ  ｍｅｍｏｒｙ），ＲＡＭ（ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ）等を含み、処理に用いられるプログラムとデータを格納する。ＣＰＵ１は、メモリ２を利用してプログラム（最適巡回路探索プログラムを含む）を実行することにより、本装置全体の動作を制御する。入力部３は、例えば、キーボード，ポインティングデバイス，タッチパネル等であり、ユーザからの指示や情報の入力に用いられる。出力部４は、例えば、ディスプレイ，プリンタ等であり、処理結果の出力に用いられる。記憶部５は、例えば、磁気ディスク装置，光ディスク装置，光磁気ディスク装置，テープ装置等であり、種々の情報が記憶される。また、この記憶部５には、前述のプログラムとデータが保存されており、本装置は、必要に応じて、それらをメモリ２にロードして使用するようになっている。
【００２６】
記録媒体駆動部６は、可搬記録媒体を駆動し、その記録内容にアクセスする。可搬記録媒体としては、メモリカード，フロッピー（登録商標）ディスク，ＣＤ−ＲＯＭ（ｃｏｍｐａｃｔ  ｄｉｓｋ  ｒｅａｄ  ｏｎｌｙ  ｍｅｍｏｒｙ  ），光ディスク，光磁気ディスク等、任意のコンピュータ読み取り可能な記録媒体が用いられる。また、ユーザが、この可搬記録媒体に前述のプログラムとデータを格納しておき、本装置が、必要に応じて、それらをメモリ２にロードして使用することも可能である。
【００２７】
ネットワーク接続部７は、ＬＡＮ（ｌｏｃａｌ  ａｒｅａ  ｎｅｔｗｏｒｋ）等の任意の通信ネットワークに接続され、通信に伴うデータ変換を行う。尚、本装置は、前述のプログラムとデータをこのネットワーク接続部７を介して、サーバ等の他の装置から受け取り、必要に応じて、それらをメモリ２にロードして使用することも可能である。このとき、サーバは、プログラムとデータを伝送する伝搬信号を生成し、ネットワーク上の任意の伝送媒体を介して、本装置に送信する。
【００２８】
次に、このような構成の最適巡回路探索装置によって行われる最適巡回路探索処理について説明する。尚、本処理は、ＣＰＵ１が前述の最適巡回路探索プログラムを実行することによって行われる処理である。
【００２９】
図２は、その最適巡回路探索処理の処理内容の一例を示すフローチャートである。
同図において、まず、Ｓ２０１では、入力部３を介して行われたユーザの指示に応じて、探索する最適巡回路の評価基準として、距離、時間、又はコストの何れかが選択される。例えば、ここで、距離が選択されたときには最短距離となる最適巡回路探索が行われるようになり、時間が選択されたときには最短時間となる最適巡回路探索が行われるようになり、コストが選択されたときには最小コストとなる最適巡回路探索が行われるようになる。
【００３０】
Ｓ２０２では、巡回対象となる各巡回点の座標情報若しくは各巡回点間の距離情報、又は各巡回点間の移動方式とその移動方式下の所要時間，所要コストの情報及び移動主体の単位時間でのコスト情報が、入力部３を介してユーザによって入力され、その入力された情報に基づいて、前ステップで選択された評価基準に応じて、各巡回点間の距離、時間、又はコストの何れかのマトリクス情報（以下単にマトリクスという）が作成される。尚、本ステップの処理については、図３を用いて詳しく後述するが、例えば、前ステップで距離が選択されたときには距離のマトリクスが作成され、時間が選択されたときには時間のマトリクスが作成され、コストが選択されたときにはコストのマトリクスが作成されるようになる。
【００３１】
Ｓ２０３では、全ての巡回点の中から、探索する巡回路の始点（或いは終点でもある）となる初期点となる巡回点が決定される。尚、本例においては、この初期点を、全ての巡回点の座標情報から求めた重心に最も近い巡回点に自動的に決定するものとするが、ユーザの指示に応じて決定するようにすることも可能である。
【００３２】
Ｓ２０４では、Ｓ２０２で作成された各巡回点間の距離，時間，又はコストのマトリクスに基づいて、このときに作成されている、Ｓ２０３で決定された初期点を含む部分最適巡回路に、その部分最適巡回路上の巡回点以外の１つの巡回点を加えた、新たな部分最適巡回路（これを部分最適巡回路の初期解ともいう）が作成される。但し、本ステップがＳ２０３の処理の直後に行われた場合には、初期点が決定されているだけで部分最適巡回路がまだ作成されていないので、この場合には、初期点に、選択されている評価基準に応じて決定された１つの巡回点を加えた２つの巡回点からなる巡回路を、本ステップで作成される新たな部分最適巡回路として処理が行われる。
【００３３】
Ｓ２０５では、前ステップで作成された部分最適巡回路に対し再最適化調整が行われる。
尚、これらのＳ２０４乃至Ｓ２０５の処理については、図５を用いて詳しく後述する。
【００３４】
Ｓ２０６では、前ステップで再最適化調整が行われた第２の部分最適巡回路上の巡回点が全ての巡回点を含むものであるか否か、すなわち、全ての巡回点を巡回する最適巡回路が作成されたか否かが判定され、その判定結果がＹｅｓの場合にはＳ２０７へ進み、Ｎｏの場合にはＳ２０４へ戻る。
【００３５】
続くＳ２０７では、作成された、全ての巡回点を巡回する最適巡回路（最適巡回路解）の情報が作成され、その最適巡回路解情報が記憶部５に出力され記憶される。
【００３６】
Ｓ２０８では、前ステップで作成された、最適巡回路解情報に基づいて、最適巡回路表示イメージ図が作成され、それが出力部４に出力されディスプレイに表示される。尚、本ステップの処理については、図７を用いて詳しく後述する。
【００３７】
以上、本フローが行われることによって、ユーザにより指示された、距離，時間，コストの何れかの評価基準に従って、ユーザが入力した巡回点及び巡回点間の情報に基づいて、全ての巡回点を重複なしに巡回する最適巡回路が探索されるようになる。
【００３８】
図３は、前述のＳ２０２の処理内容をより詳細に示したフローチャートである。
同図において、まず、Ｓ３０１では、距離が処理対象であるか否か、すなわち、選択されている評価基準（図２のＳ２０１参照）が距離であるか否かが判定され、その判定結果がＹｅｓの場合にはＳ３０２へ進み、Ｎｏの場合にはＳ３０４へ進む。
【００３９】
Ｓ３０２では、巡回対象となる各巡回点の座標情報又は各巡回点間の距離情報が、入力部３を介してユーザにより入力されることによって、各巡回点の座標情報又は各巡回点間の距離情報が取得される。
【００４０】
Ｓ３０３では、前ステップで取得された各巡回点の座標情報又は各巡回点間の距離情報から、各巡回点間の距離が示された、距離のマトリクスが作成され、その距離のマトリクスが記憶部５に記憶される。
【００４１】
Ｓ３０４では、距離以外の時間やコストについての処理を行うか否か、すなわち、選択されている評価基準（図２のＳ２０１参照）が距離以外の時間或いはコストであるか否かが判定され、その判定結果がＹｅｓの場合にはＳ３０５へ進み、Ｎｏの場合には本フローが終了する。
【００４２】
Ｓ３０５では、入力部３を介して、各巡回点間の移動方式とその移動方式下の所要時間（Ｔｍ  ），所要コスト（Ｃｓ  ）の情報、及び移動主体の単位時間でのコスト（Ｃｍｐｔ  ）情報が、ユーザにより入力されることによって、各巡回点間の移動方式とその移動方式下の所要時間（Ｔｍ  ），所要コスト（Ｃｓ  ）の情報、及び移動主体の単位時間でのコスト（Ｃｍｐｔ  ）情報が取得される。
【００４３】
ここで、移動方式とは、例えば、飛行機、電車、バス、徒歩等のことをいう。また、巡回点間の所要コスト（Ｃｓ  ）とは、巡回点間の移動方式による移動に要するコスト（費用）のことをいい、例えば、巡回点間を電車で移動したときには、その電車による移動に要するコストになる。また、移動主体の単位時間でのコストとは、例えば、移動する者の単位時間当りの人件費等である。
【００４４】
また、このＳ３０５において、同一巡回点間に移動方式が複数ある場合には、その巡回点間については、複数の移動方式と各移動方式についての所要時間（Ｔｍ  ），所要コスト（Ｃｍｐｔ  ）の情報がそれぞれ入力され、それらが取得されることになる。例えば、同一の巡回点間に移動方式として電車，バスがあるときには、その巡回点間については、移動方式を電車としたときの所要時間（Ｔｍ  ）と所要コスト（Ｃｓ  ）の情報と、移動方式をバスとしたときの所要時間（Ｔｍ  ）と所要コスト（Ｃｓ  ）の情報がそれぞれ入力され、それらが取得されることになる。
【００４５】
Ｓ３０６では、最短所要時間についての処理を行うか否か、すなわち、選択されている評価基準（図２のＳ２０１参照）が時間であるか否かが判定され、その判定結果がＹｅｓの場合にはＳ３０７へ進み、Ｎｏの場合にはＳ３０８へ進む。
【００４６】
Ｓ３０７では、Ｓ３０５で取得された各巡回点間の所要時間（Ｔｍ  ）又は各巡回点間の移動方式毎の所要時間（Ｔｍ  ）の情報から、各巡回点間を移動するのに要する時間の最短所要時間が計算され、その計算結果から、各巡回点間を移動するための最短所要時間とそのときの移動方式とが示された、時間のマトリクスが作成され、その時間のマトリクスが記憶部５に記憶される。
【００４７】
Ｓ３０８では、最小総コストの処理を行うか否か、すなわち、選択されている評価基準（図２のＳ２０１参照）がコストであるか否かが判定され、その判定結果がＹｅｓの場合にはＳ３０９へ進み、Ｎｏの場合には本フローが終了する。
【００４８】
Ｓ３０９では、各巡回点間において、巡回点間を移動するに当って各種移動方式の下で発生する総コストの最小値（ＴＣｉｊ  ）が算出される。尚、このＴＣｉｊ  は次式により求められる。
【００４９】
ＴＣｉｊ  ＝Ｍｉｎ  ｛（Ｃｓ  （ｋ）＋Ｔｍ  （ｋ）×Ｃｍｐｔ  ）｝
但し、ｋ＝１，２，・・・である。
例えば、同一巡回点間に複数の移動方式がある場合には、移動方式毎に、その移動方式の下で発生する総コストが求められ、その中から最小となる総コストＴＣｉｊ  が求められる。
【００５０】
Ｓ３１０では、前ステップで算出された各巡回点間の総コストの最小値（ＴＣｉｊ）から、各巡回点間を移動するのに発生する最小総コストとそのときの移動方式とが示された、コストのマトリクスが作成され、そのコストのマトリクスが記憶部５に記憶される。
【００５１】
以上、本フローが行われることによって、ユーザにより各巡回点の座標情報又は各巡回点間の距離情報が入力されることで距離のマトリクスが作成され、また各巡回点間の移動方式とその移動方式下の所要時間，所要コストの情報、及び移動主体の単位時間でのコスト情報が入力されることで時間のマトリクス又はコストのマトリクスが作成されるようになる。
【００５２】
図４は、前述のＳ３０３で作成された距離のマトリクスの一例を示した図である。
同図の例は、４８個の巡回点の座標情報又は４８個の巡回点の各巡回点間の距離情報が、入力部３を介してユーザによって入力され、その入力された情報に基づいて作成された距離のマトリクスを示している。但し、同図においては、その一部である、１０個の巡回点についてのみの情報を示している。
【００５３】
同図において、点名は巡回点を示し、Ｘ１，Ｘ２又はＸ２，Ｙ２は、各巡回点の座標を示している。また、各巡回点間の距離も示されている。同図の例によれば、例えば、巡回点１と巡回点３の距離は３１０６であることがわかる。
【００５４】
本実施形態に係る最適巡回路探索処理では、このような距離のマトリクスに基づいて、最短距離である最適巡回路の探索が行われる。
図５は、前述のＳ２０３乃至Ｓ２０８の処理内容をより詳細に示したフローチャートである。
【００５５】
尚、本実施形態において、１つの巡回点から次に移動する巡回点を結ぶ経路を枝という。また、枝の単位は、距離、時間、又はコストの何れかの単位であり、選択されている評価基準（図２のＳ２０１参照）に基づいて決定される。例えば、距離が選択されていたときには、枝の単位は距離の単位になる。これにより、枝長（経路長）は、距離、時間、又はコストの何れかであるともいえる。
【００５６】
図５において、まず、Ｓ５０１では、距離を基準で処理を行うか否か、すなわち、選択されている評価基準（図２のＳ２０１参照）が距離であるか否かが判定され、その判定結果がＹｅｓの場合にはＳ５０２へ進み、Ｎｏの場合にはＳ５０３へ進む。
【００５７】
Ｓ５０２では、図３のＳ３０３で記憶部５に記憶された、各巡回点間の距離が示された距離のマトリクスが読み出され、各巡回点の座標情報又は各巡回点間の距離情報が取得され、Ｓ５０６へ進む。
【００５８】
Ｓ５０３では、時間を基準で処理を行うか否か、すなわち、選択されている評価基準（図２のＳ２０１参照）が時間であるか否かが判定され、その判定結果がＹｅｓの場合にはＳ５０４へ進み、Ｎｏの場合にはＳ５０５へ進む。
【００５９】
Ｓ５０４では、図３のＳ３０７で記憶部５に記憶された、各巡回点間を移動するための最短所要時間とそのときの移動方式が示された時間のマトリクスが読み出され、各巡回点間の所要時間とそのときの移動方式が取得され、Ｓ５０６へ進む。
【００６０】
Ｓ５０５では、図３のＳ３１０で記憶部５に記憶された、各巡回点間を移動するのに発生する最小総コストが示されたコストのマトリクスが読み出され、各巡回点間を移動するために要するコストが取得される。
【００６１】
続いて、実際に、全ての巡回点を巡回する最適巡回路の探索（作成）が開始される。ここでは、一例として、選択されている評価基準（図２のＳ２０１参照）が距離であった場合について説明する。
【００６２】
まず、Ｓ５０６では、巡回対象となっている全ての巡回点の中から、探索する巡回路の始点（或いは終点でもある）となる巡回点Ｐｓ  が決定される。本例においては、前述の通り、その巡回点Ｐｓ  は、全ての巡回点の座標情報から求められた重心に最も近い巡回点に自動的に決定される。尚、重心は、例えば、全ての巡回点の座標の平均等により求められる。
【００６３】
続くＳ５０７乃至Ｓ５０８では、作成されている部分最適巡回路に、その部分最適巡回路上の巡回点以外の１つの巡回点を加えた新たな部分最適巡回路を作成する処理が行われる。
【００６４】
但し、Ｓ５０７の処理が開始される時点において、前述のＳ２０４の説明において述べたことと同じように、始点となる巡回点Ｐｓ  のみが決定されているだけで部分最適巡回路がまだ作成されていないとき（Ｓ５０６の処理の直後に本ステップが開始されるとき）には、このＳ５０７乃至Ｓ５０８では、巡回点Ｐｓ  と、選択されている評価基準に応じて決定された１つの巡回点Ｐａ  を加えた２つの巡回点Ｐｓ  ，Ｐａ  からなる巡回路が、新たな部分最適巡回路とされる。ここでは、選択されている評価基準が距離とされているので、その巡回点Ｐａ  として、巡回点Ｐｓ  からの移動距離が最小となる巡回点が決定され、巡回点Ｐｓ  とＰａ  の２つの巡回点からなる巡回路が、新たな部分最適巡回路とされる。
【００６５】
一方、Ｓ５０７の処理が開始される時点において、部分最適巡回路が作成されているときには、そのＳ５０７では、その部分最適巡回路上の各枝に対し、当該枝をＢ１とし、枝Ｂ１の両端点となる２つの巡回点をＰｂ  ，Ｐｃ  とし、その部分最適巡回路上の巡回点以外の１つの巡回点をＰｄ  とし、巡回点Ｐｂ  と巡回点Ｐｄ  を結ぶ枝をＢ２とし、巡回点Ｐｃ  と巡回点Ｐｄ  を結ぶ枝をＢ３としたときに、Ｂ２＋Ｂ３−Ｂ１の値が最小となるような、枝Ｂ１と巡回点Ｐｄ  が求められ、続くＳ５０８では、前ステップで求められた枝Ｂ１と巡回点Ｐｄ  とから、巡回点Ｐｄ  と枝Ｂ１の両端点となる両巡回点Ｐｂ  ，Ｐｃ  を結ぶ枝Ｂ２，Ｂ３が新たに設けられると共に、枝Ｂ１が削除され、１つの巡回点Ｐｄ  が加えられた新たな部分最適巡回路（部分最適巡回路の初期解）が作成される。
【００６６】
ここで、このＳ５０７乃至Ｓ５０８の処理について、より詳しく説明する。
図６は、そのＳ５０７乃至Ｓ５０８の処理を説明するための図である。
同図の例は、全ての巡回点をｉ，ｊ，ｅ，ｎ，ｍの５つとし、また現時点で作成されている部分最適巡回路を、巡回点をｉ，ｊ，ｅの３つとした枝Ｂ（ｉｊ）  ，Ｂ（ｊｅ）  ，Ｂ（ｅｉ）  からなる巡回路と仮定した場合の、Ｓ５０７乃至Ｓ５０８の処理を説明する図である。
【００６７】
このような場合に、現時点において作成されている部分最適巡回路上の各枝について前述のＢ２＋Ｂ３−Ｂ１の値：Ｄを求めると次のようになる。
まず、部分最適巡回路上の枝Ｂ（ｉｊ）  と巡回路上以外の巡回点ｎ，ｍに着目してＤの値を求めると、
巡回点ｎについては、Ｄ＝Ｂ（ｎｉ）  ＋Ｂ（ｊｎ）  −Ｂ（ｉｊ）  ，
巡回点ｍについては、Ｄ＝Ｂ（ｍｉ）  ＋Ｂ（ｊｍ）  −Ｂ（ｉｊ）
が得られる。
【００６８】
また、部分最適巡回路上の枝Ｂ（ｅｉ）  と巡回路上以外の巡回点ｎ，ｍに着目してＤの値を求めると、
巡回点ｎについては、Ｄ＝Ｂ（ｎｉ）  ＋Ｂ（ｅｎ）  −Ｂ（ｅｉ）  ，
巡回点ｍについては、Ｄ＝Ｂ（ｍｉ）  ＋Ｂ（ｅｍ）  −Ｂ（ｅｉ）
が得られる。
【００６９】
また、部分最適巡回路上の枝Ｂ（ｊｅ）  と巡回路上以外の巡回点ｎ，ｍに着目してＤの値を求めると、
巡回点ｎについては、Ｄ＝Ｂ（ｅｎ）  ＋Ｂ（ｊｎ）  −Ｂ（ｊｅ）  ，
巡回点ｍについては、Ｄ＝Ｂ（ｅｍ）  ＋Ｂ（ｊｍ）  −Ｂ（ｊｅ）
が得られる。
【００７０】
そして、このようにして求められたＤの値の中で、その値が最小となるような、部分最適巡回路上の枝とその部分最適巡回路上以外の巡回点が求められる。本例の場合には、それらが枝Ｂ（ｉｊ）  と巡回点ｎになる。
【００７１】
続いて、このようにして求められた枝Ｂ（ｉｊ）  と巡回点ｎとから、巡回点ｎから枝Ｂ（ｉｊ）  の両端点である両巡回点ｉ，ｊを結ぶ枝Ｂ（ｎｉ）  ，Ｂ（ｊｎ）  が新たに設けられると共に、枝Ｂ（ｉｊ）  が削除され、１つの巡回点ｎが加えられた新たな部分最適巡回路が作成される。すなわち、巡回点をｉ，ｊ，ｅ，ｎとした枝Ｂ（ｎｉ）  、枝Ｂ（ｎｊ）  、枝Ｂ（ｊｅ）  、枝Ｂ（ｅｉ）  からなる新たな部分最適巡回路が作成される。
【００７２】
前述のＳ５０７乃至Ｓ５０８の処理では、例えば、このようにして新たな部分最適巡回路が作成されるものである。
図５に戻り、続いて、Ｓ５０９では、前ステップで作成された部分最適巡回路の再最適調整が行われる。具体的には、前ステップで作成された部分最適巡回路上の各巡回点に対し、当該巡回点をＰｅ  とし、巡回点Ｐｅ  に接続される２つの枝をＢ４，Ｂ５とし、巡回点Ｐｅ  に枝Ｂ４，Ｂ５を介して接続される巡回点をＰｆ  ，Ｐｇ  とし、巡回点Ｐｆ  ，Ｐｇ  を結ぶ枝をＢ６とし、巡回点Ｐｅ  に接続されてない枝Ｂ６以外の１つの枝をＢ７とし、枝Ｂ７の両端点となる両巡回点をＰｈ  ，Ｐｉ  とし、巡回点Ｐｅ  と巡回点Ｐｈ  を結ぶ枝をＢ８とし、巡回点Ｐｅ  と巡回点Ｐｉ  を結ぶ枝をＢ９としたときに、Ｂ６−Ｂ４−Ｂ５＋Ｂ８＋Ｂ９−Ｂ７＜０となるものがあったときには、そのときの枝Ｂ４，Ｂ５，Ｂ７が削除されると共に、枝Ｂ６，Ｂ８，Ｂ９が新たに設けられて、新しい部分最適巡回路が作成される。但し、本ステップでは、前ステップで作成された部分最適巡回路上の巡回点が５つ以上ない場合には、このうような処理は行われず、本ステップがスキップする。
【００７３】
ここで、このＳ５０９の処理について、より詳しく説明する。
図７（ａ），（ｂ）  は、Ｓ５０９の処理を説明するための図である。
同図（ａ）  は、Ｓ５０９の処理が行われる前の部分最適巡回路の一例を示し、同図（ｂ）  は同図（ａ）  の部分最適巡回路にＳ５０９の処理が行われた後の部分最適巡回路を示している。
【００７４】
同図（ａ）  に示したように、本例では、Ｓ５０８で作成された部分最適巡回路を、巡回点をｉ，ｊ，ｅ，ｎ，ｍ，ｒの６つとした枝Ｂ（ｅｉ）  ，Ｂ（ｉｊ）  ，Ｂ（ｊｎ）  ，Ｂ（ｎｒ）  ，Ｂ（ｒｍ）  ，Ｂ（ｍｅ）  からなる巡回路と仮定する。
【００７５】
この場合、部分最適巡回路上の巡回点ｉ，ｊ，ｅ，ｎ，ｍ，ｒの各々に対して、前述のＳ５０９の説明で述べたような、Ｂ６−Ｂ４−Ｂ５＋Ｂ８＋Ｂ９−Ｂ７＜０となるものがあるか否かが判定され、それがあったときには、そのときの枝Ｂ４，Ｂ５，Ｂ７が削除されると共に、枝Ｂ６、Ｂ８、Ｂ９が新たに設けられて、新しい部分最適巡回路が作成される。
【００７６】
ここでは、その一例として、部分最適巡回路上の巡回点ｎに着目した場合の処理について説明する。この場合、巡回点ｎに接続される２つの枝はＢ（ｊｎ）  ，Ｂ（ｎｒ）  となり、巡回点ｎに枝Ｂ（ｊｎ），Ｂ（ｎｒ）  を介して接続される巡回点はｊ，ｒとなり、巡回点ｊ，ｒを結ぶ枝はＢ（ｊｒ）  となる。ここで、巡回点ｎに接続されてない枝Ｂ（ｊｒ）  以外の１つの枝をＢ（ｅｍ）  とすると、枝Ｂ（ｅｍ）  の両端点となる両巡回点はｅ，ｍとなり、巡回点ｎと巡回点ｅを結ぶ枝はＢ（ｅｎ）  となり、巡回点ｎと巡回点ｍを結ぶ枝はＢ（ｎｍ）  となる。このときに、前述のＢ６−Ｂ４−Ｂ５＋Ｂ８＋Ｂ９−Ｂ７である、Ｂ（ｊｒ）  −Ｂ（ｊｎ）  −Ｂ（ｎｒ）  ＋Ｂ（ｅｎ）  ＋Ｂ（ｎｍ）  −Ｂ（ｅｍ）  の値は０未満（＜０）となる。よって、このときの、枝Ｂ２，Ｂ３，Ｂ４である、枝Ｂ（ｊｎ）  ，Ｂ（ｎｒ）  ，Ｂ（ｅｍ）  を削除すると共に、枝Ｂ３，Ｂ５，Ｂ６である、枝Ｂ（ｊｒ）  ，Ｂ（ｅｎ）  ，Ｂ（ｎｍ）  を新たに設け、同図（ｂ）  に示したような、新たな部分最適巡回路が作成される。また、この場合において、巡回点ｎに接続されていない枝Ｂ（ｊｒ）  以外の１つの枝をＢ（ｅｉ）  とした場合には、前述のＢ６−Ｂ４−Ｂ５＋Ｂ８＋Ｂ９−Ｂ７である、Ｂ（ｊｒ）  −Ｂ（ｊｎ）  −Ｂ（ｎｒ）  ＋Ｂ（ｉｎ）  ＋Ｂ（ｅｎ）  −Ｂ（ｅｉ）  の値は０未満（＜０）とはならないため、新たな部分最適巡回路の作成は行われない。また、本例の場合には、巡回点ｎ以外の部分最適巡回路上の巡回点についても、前述のＢ６−Ｂ４−Ｂ５＋Ｂ８＋Ｂ９−Ｂ７の値は０未満（＜０）とはならないため、新たな部分最適巡回路は作成されない。よって、同図（ａ）  に示した部分最適巡回路に対してＳ５０９の処理が行われることによって新たに作成される部分最適巡回路は、同図（ｂ）  に示した部分最適巡回路となる。
【００７７】
前述のＳ５０９では、例えば、このようにして部分最適巡回路の再最適化調整が行われて、新たな部分最適巡回路が作成される。
図５に戻り、続いて、Ｓ５１０では、現時点において作成されている部分最適巡回路が全ての巡回点を含むものであるか否かが判定され、その判定結果がＹｅｓの場合にはＳ５１１へ進み、Ｎｏの場合にはＳ５０７へ戻る。
【００７８】
Ｓ５１１では、作成された部分最適巡回路、すなわち全ての巡回点を巡回する最適巡回路（最適巡回路解）の情報が作成され、その最適巡回路解情報が記憶部５に記憶される。
【００７９】
以上、本フローが行われることによって、ユーザの指示した評価基準に従って全ての巡回点を重複なしに巡回する最適巡回路が作成されるようになり、最適巡回路を効率的に精度良く探索することが可能になる。
【００８０】
尚、本フローのＳ５０９では、Ｓ５０８で作成された部分最適巡回路の再最適調整が行われているが、この再最適調整を行わないようにしても、充分な精度を確保できるのであれば、Ｓ５０９の処理を省くようにすることも可能である。このようにすることで、より探索時間の短縮化が可能になる。
【００８１】
また、本フローでは、選択された評価基準が距離であった場合を例に説明したが、それが時間又はコストであった場合にも同様にして処理が行われる。但し、選択された評価基準が時間であった場合には、前述の枝Ｂの単位が距離の単位ではなく時間の単位となって処理が行われる。この場合、枝Ｂの内容（枝長）は、時間のマトリクスから取得された巡回点間を移動するための最短所要時間を表すことになる。また、選択された評価基準がコストであった場合には、前述の枝Ｂの単位がコストの単位となって処理が行われる。この場合、枝Ｂの内容（枝長）は、コストのマトリクスから取得された巡回点間を移動するのに発生する最小総コストを表すことになる。また、選択された評価基準が時間又はコストであった場合には、各巡回点の座標情報（又は各巡回点間の距離情報）が入力されないことになるので、この場合には、巡回路の始点となる巡回点Ｐｓ  は、ユーザの指示に応じて決定されることになる。
【００８２】
図８は、Ｓ５１１で作成された最適巡回路解情報の一例を示した図である。
同図の例は、図４において説明した４８個の巡回点について作成された最適巡回路解情報を示している。
【００８３】
図８において、枝番は、作成された最適巡回路上の各巡回点間の枝に付された番号を示し、巡回開始点となる巡回点から順に番号が付されている。また、始点は、各枝の始点側の巡回点を示し、終点は、各枝の終点側の巡回点を示している。また、距離／時間／コストは、各枝の値（内容，枝長）を示すものであり、本例は距離を評価基準とした例であるので、各枝の距離を示している。
【００８４】
本実施形態に係る最適巡回路探索処理では、例えば、このような最適巡回路解情報が作成される。
図９は、前述のＳ２０８の処理内容をより詳細に示したフローチャートである。
【００８５】
同図において、まず、Ｓ９０１では、前述のＳ５１１で記憶部５に記憶された、最適巡回路解情報が読み出され、その最適巡回路解情報が取得される。
Ｓ９０２では、前ステップ取得された最適巡回路解情報に基づいて、最適巡回路表示イメージ図が作成され、それに基づく最適巡回路イメージ図がディスプレイに表示される。
【００８６】
例えば、前述の図８に示した最適巡回路解情報に基づいて表示が行われる場合には、後述する図１２に示したような最適巡回路イメージ図が表示されるようになる。
【００８７】
以上、本フローが行われることによって、作成された最適巡回路解情報に基づいて最適巡回路のイメージ図が表示されるようになる。
以上が、図１に示した最適巡回路探索装置によって行われる最適巡回路探索処理である。
【００８８】
尚、本処理では、ユーザの指示に応じて選択される評価基準を、距離，時間，又はコストの何れか１つとしたが、例えば、これらのうちの複数を選択できるようにすることも可能である。但し、この場合には、選択された複数の評価基準に応じた情報が入力され、その情報に基づいて、その複数の評価基準に応じたマトリクスが作成され、そのマトリクスに基づいて処理が行われるようになる。
【００８９】
例えば、評価基準として距離と時間が選択されたときには、巡回対象となる各巡回点の座標情報又は各巡回点間の距離情報、及び各巡回点間の移動方式とその移動方式下の所要時間の情報が入力される。そして、それらの情報に基づいて、距離と時間に応じたマトリクスが作成されるようになる。但し、この場合、作成されるマトリクスに示される各巡回点間の内容は、例えば、巡回点間の距離と最短所要時間の積（距離×最短所要時間）の値となる。
【００９０】
同様に、評価基準として、距離とコストが選択されたときには、巡回対象となる各巡回点の座標情報又は各巡回点間の距離情報、各巡回点間の移動方式とその移動方式下の所要コストの情報、及び移動主体の単位時間でのコスト情報が入力される。そして、それらの情報に基づいて、距離とコストに応じたマトリクスが作成されるようになる。但し、この場合、作成されるマトリクスに示される各巡回点間の内容は、例えば、巡回点間の距離と最小総コストの積（距離×最小総コスト）の値となる。
【００９１】
また、同様に、評価基準として、時間とコストが選択されたときには、各巡回点間の移動方式とその移動方式下の所要時間，所要コストの情報及び移動主体の単位時間でのコスト情報が入力される。そして、それらの情報に基づいて、時間とコストに応じたマトリクスが作成されるようになる。但し、この場合、作成されるマトリクスに示される各巡回点間の内容は、例えば、巡回点間の最短所要時間と最小総コストの積（最短所要時間×最小総コスト）の値となる。また、この場合には、各巡回点の座標情報（又は各巡回点間の距離情報）が入力されないことになるので、巡回路の始点となる巡回点Ｐｓ  は、ユーザの指示に応じて決定されることになる。
【００９２】
また、評価基準として、距離，時間，コストの全てが選択されたときには、巡回対象となる各巡回点の座標情報若しくは各巡回点間の距離情報、又は各巡回点間の移動方式とその移動方式下の所要時間，所要コストの情報及び移動主体の単位時間でのコスト情報が入力される。そして、それらの情報に基づいて、距離と時間とコストに応じたマトリクスが作成されるようになる。但し、この場合、作成されるマトリクスに示される各巡回点間の内容は、例えば、巡回点間の距離と最短所要時間と最小総コストの積（距離×最短所要時間×最小総コスト）の値となる。
【００９３】
そして、このようにして作成されたマトリクスに基づいて最適巡回路の作成を行う際には、前述の枝Ｂの値が、そのマトリクスに示された各巡回点間の内容の値として処理が行われるようになる。
【００９４】
これにより、評価基準を複数とした場合の処理が可能になり、評価基準として距離と時間が選択されたときには、距離が短く且つ時間が短い最適巡回路が作成され、評価基準として距離とコストが選択されたときには、距離が短く且つコストが安い最適巡回路が作成され、評価基準として時間とコストが選択されたときには、時間が短く且つコストが安い最適巡回路が作成され、評価基準として距離と時間とコストが選択されたときには、距離が短く且つ時間が短く且つコストが安い最適巡回路が作成されるようになる。
【００９５】
次に、上述の最適巡回路探索処理を適用した具体例について説明する。
まず、図１０乃至図１３を用いて具体例１について説明する。具体例１は、上述の最適巡回路探索処理を、米国４８都市について最短距離となる最適巡回路の探索に適用した例である。
【００９６】
図１０は、処理対象となる米国４８都市を示した図である。
同図上の４８個の点（巡回点）が、米国４８都市を示している。尚、縦軸及び横軸は座標を表している（図１１乃至図１３において同じ）。
【００９７】
図１１は、その米国４８都市について既に求められている理論的最適巡回路の解を示した図である。
同図に示したように、その理論的最適巡回路の解によれば、巡回路距離は、３３５２３．７０８５である。
【００９８】
一方、図１２は、上述の最適巡回路探索処理を適用して求めた最適巡回路の解を示した図である。
同図に示したように、本処理によって求められた最適巡回路の解によれば、巡回路距離は、３４１５３．１９であった。このことから、本処理による最適巡回路の解は、図１１に示した理論的最適巡回路の解に対して誤差率が＋１．８８％となって、高い精度が得られている。
【００９９】
また、この米国４８都市に本処理を適用した場合において、探索する巡回路の始点となる都市（巡回点）を何れの都市にするかによって、その誤差率が変わってくる。
【０１００】
図１３は、その始点となる都市と誤差率の関係を示した図である。
尚、このような関係は、各都市を始点として本処理による最適巡回路の解をそれぞれ求め、求めた各最適巡回路解と理論的巡回路解とをそれぞれ比較して、各都市を始点としたときの誤差率をそれぞれ求めることによって得られたものである。
【０１０１】
同図に示したように、各巡回点は、誤差率が１．８８％，２．５７％，２．８５％，３．６６％，５．５２％の５つのグループに分かれ、平均で誤差率が３．２６％、最高でも誤差率が５．５２％という結果が得られ、何れの都市を始点とした場合においても誤差率が低く、高い精度が得られている。尚、本例において、４８都市の重心の座標は、（６１９０．８２，３４５７．９３）であった。
【０１０２】
このように、上述の最適巡回路探索処理を、米国４８都市の最適巡回路探索に適用することによって、米国４８都市の最適巡回路解を効率的に精度良く探索することが可能になる。
【０１０３】
続いて、図１４を用いて具体例２について説明する。具体例２は、上述の最適巡回路探索処理を、格子上の６４点について最短距離となる最適巡回路の探索に適用した例である。
【０１０４】
図１４は、格子上の６４点について上述の最適巡回路探索処理を適用して求めた最適巡回路の解を示した図である。
同図に示したように、本処理によって求められた最適巡回路の解によれば、各格子間を１とすると、巡回路距離は６４であった。一方、この格子上の６４点についての理論的最適巡回路の解（不図示）によっても巡回路距離は６４であり、誤差率０．００％が得られ、理論的最適巡回路の解と同一の結果が得られている。
【０１０５】
このように、上述の最短巡回路探索処理を、格子上の６４点についての最適巡回路探索に適用することによって、その格子上の６４点の最適巡回路解を効率的に精度良く探索することが可能になる。
【０１０６】
続いて、図１５（ａ），（ｂ），（ｃ），（ｄ），（ｅ），（ｆ），（ｇ），（ｈ），（ｉ）  を用いて具体例３について説明する。具体例３は、上述の最適巡回路探索処理を、部品や部材等に複数箇所の加工（例えば切削加工等）を行う場合の最適加工順路（最適加工巡回路）の探索に適用した例である。
【０１０７】
図１５（ａ）  乃至（ｉ）  は、同一工具を用いてワーク（加工対象物）上の８箇所に点加工を行う際の最適加工順路を、上述の最適巡回路探索処理に従って作成したときの最適加工順路の作成過程を示した図である。但し、本例では、ワークから離れた点をリファレンス点とし、そのリファレンス点からワーク上の８つの加工点を切削加工し、再びそのリファレンス点に戻るまでの、最短距離となる最適加工順路を作成するものとする。
【０１０８】
まず、同図（ａ）  では、初期点となるリファレンス点から最短距離となる加工点▲３▼までの部分最適巡回路（同図（ａ）  の実線）が作成される。
続いて、作成された同図（ａ）  の部分最適巡回路に対し前述のＳ５０７乃至Ｓ５０８の処理が行われ、同図（ｂ）  に示したように、リファレンス点と加工点▲３▼間の枝が１つ削除され、リファレンス点と加工点▲１▼を結ぶ枝と、加工点▲３▼と▲１▼を結ぶ枝とが設けられ、新たな部分最適巡回路（同図（ｂ）  の実線）が作成される。
【０１０９】
尚、上述した最適巡回路探索処理（図５参照）においては、この後に、前述のＳ５０９の再最適化調整が行われるものであるが、本例においては、その再最適化調整を行わなくとも充分な精度が得られるため、そのＳ５０９の処理を省いて、更なる探索時間の短縮化を図っている。
【０１１０】
続いて、作成された同図（ｂ）  の部分最適巡回路に対し前述のＳ５０７乃至Ｓ５０８の処理が行われ、同図（ｃ）  に示したように、加工点▲１▼，▲３▼間の枝が削除され、加工点▲１▼と▲２▼を結ぶ枝と、加工点▲３▼と▲２▼を結ぶ枝とが設けられ、新たな部分最適巡回路（同図（ｃ）  の実線）が作成される。
【０１１１】
続いて、作成された同図（ｃ）  の部分最適巡回路に対し前述のＳ５０７乃至Ｓ５０８の処理が行われ、同図（ｄ）  に示したように、加工点▲３▼，▲２▼間の枝が削除され、加工点▲２▼と▲４▼を結ぶ枝と、加工点▲３▼と▲４▼を結ぶ枝とが設けられ、新たな部分最適巡回路（同図（ｄ）  の実線）が作成される。
【０１１２】
続いて、作成された同図（ｄ）  の部分最適巡回路に対し前述のＳ５０７乃至Ｓ５０８の処理が行われ、同図（ｅ）  に示したように、加工点▲１▼，▲２▼間の枝が削除され、加工点▲１▼と▲７▼を結ぶ枝と、加工点▲２▼と▲７▼を結ぶ枝とが設けられ、新たな部分最適巡回路（同図（ｅ）  の実線）が作成される。
【０１１３】
続いて、作成された同図（ｅ）  の部分最適巡回路に対し前述のＳ５０７乃至Ｓ５０８の処理が行われ、同図（ｆ）  に示したように、加工点▲１▼，▲７▼間の枝が削除され、加工点▲１▼と▲５▼を結ぶ枝と、加工点▲７▼と▲５▼を結ぶ枝とが設けられ、新たな部分最適巡回路（同図（ｆ）  の実線）が作成される。
【０１１４】
続いて、作成された同図（ｆ）  の部分最適巡回路に対し前述のＳ５０７乃至Ｓ５０８の処理が行われ、同図（ｇ）  に示したように、加工点▲５▼，▲７▼間の枝が削除され、加工点▲５▼と▲８▼を結ぶ枝と、加工点▲７▼と▲８▼を結ぶ枝とが設けられ、新たな部分最適巡回路（同図（ｇ）  の実線）が作成される。
【０１１５】
続いて、作成された同図（ｇ）  の部分最適巡回路に対し前述のＳ５０７乃至Ｓ５０８の処理が行われ、同図（ｈ）  に示したように、加工点▲５▼，▲８▼間の枝が削除され、加工点▲５▼と▲６▼を結ぶ枝と、加工点▲８▼と▲６▼を結ぶ枝とが設けられ、新たな部分最適巡回路（同図（ｈ）  の実線）が作成される。
【０１１６】
これにより、同図（ｉ）  の矢印に示したように、リファレンス点→加工点▲３▼→加工点▲４▼→加工点▲２▼→加工点▲７▼→加工点▲８▼→加工点▲６▼→加工点▲５▼→加工点▲１▼→リファレンス点といった順路の最適加工順路が作成される。尚、この順路は逆周りで良いのはもちろんである。
【０１１７】
このように、上述した最適巡回路探索処理を、部品等に加工を行う際の最適加工順路の探索に適用することによって、その加工点についての最適加工順路解を効率的に精度良く探索することが可能になる。
【０１１８】
以上、本発明の最適巡回路探索方法、最適巡回路探索プログラム、及び最適巡回路探索装置について詳細に説明したが、本発明は上記実施形態に限定されず、本発明の要旨を逸脱しない範囲において、各種の改良及び変更を行っても良いのはもちろんである。
【０１１９】
【発明の効果】
以上、詳細に説明したように、本発明によれば、複数の巡回点を重複なしに全て巡回する場合の最適巡回路を効率的に精度良く探索することが可能になる。
【図面の簡単な説明】
【図１】本発明の一実施の形態に係る最適巡回路探索装置の構成例を示した図である。
【図２】最適巡回路探索処理の処理内容の一例を示すフローチャートである。
【図３】Ｓ２０２の処理内容をより詳細に示したフローチャートである。
【図４】Ｓ３０３で作成された距離のマトリクスの一例を示した図である。
【図５】Ｓ２０３乃至Ｓ２０８の処理内容をより詳細に示したフローチャートである。
【図６】Ｓ５０７乃至Ｓ５０８の処理を説明するための図である。
【図７】（ａ），（ｂ）  はＳ５０９の処理を説明するための図である。
【図８】Ｓ５１１で作成された最適巡回路解情報の一例を示した図である。
【図９】Ｓ２０８の処理内容をより詳細に示したフローチャートである
【図１０】処理対象となる米国４８都市を示した図である。
【図１１】米国４８都市について既に求められている理論的最適巡回路の解を示した図である。
【図１２】最適巡回路探索処理を適用して求めた最適巡回路の解を示した図である。
【図１３】始点となる都市と誤差率の関係を示した図である。
【図１４】格子上の６４点について最適巡回路探索処理を適用して求めた最適巡回路の解を示した図である。
【図１５】（ａ）  乃至（ｉ）  は、同一工具を用いてワーク（加工対象物）上の８箇所に点加工を行う際の最適加工順路を最適巡回路探索処理に従って作成したときの作成過程を示した図である。
【符号の説明】
１      ＣＰＵ
２      メモリ
３      入力部
４      出力部
５      記憶部
６      記録媒体駆動部
７      ネットワーク接続部
８      バス
【図１】
2004302896.tif 000003
【図２】
2004302896.tif 000004
【図３】
2004302896.tif 000005
【図４】
2004302896.tif 000006
【図５】
2004302896.tif 000007
【図６】
2004302896.tif 000008
【図７】
2004302896.tif 000009
【図８】
2004302896.tif 000010
【図９】
2004302896.tif 000011
【図１０】
2004302896.tif 000012
【図１１】
2004302896.tif 000013
【図１２】
2004302896.tif 000014
【図１３】
2004302896.tif 000015
【図１４】
2004302896.tif 000016
【図１５】
2004302896.tif 000017