(57)【要約】【課題】  組合せ最適化問題は実社会でも応用範囲の広い問題であり、解決のための様々な算法が開発されてきた。算法には厳密に最適解を求める方法と、ある程度の精度内にある近似解を求めるものがある。近似解を求める場合、より最適解に近い解を得るためには精度を向上させる必要がある。本発明は精度を向上させることを課題とする。【解決手段】  本発明は、組合せ最適化問題を解く操作を行なうにあたり、最初に操作を始める始点となる点を任意に１選ぶことで近似解を求める算法に、始点となる点を複数選んで操作を行ない、複数の解の候補を作り、その中から最適解により近いものを選ぶ方法を適用することで精度をより向上させる。この近似解の精度を向上させる方法を適用できる組合せ最適化問題の少なくとも一つとして、複数の都市を一巡する最小コストのルートを求める巡回セールスマン問題がある。【選択図】図１
2015149049.tif 000002
【特許請求の範囲】
【請求項１】
組合せ最適化問題の解を求める算法には厳密に最適解を求める方法と、ある程度の精度内にある近似解を求めるものがある。本発明は近似解の精度を向上させる方法。
【請求項２】
少なくとも、そこから解を求める操作を始める始点となる点を任意に１決めることで組合せ最適化問題の近似解を求める算法ならどんな算法にも適用することができる、近似解の精度をより向上させる方法。
【請求項３】
少なくとも、始点となる点を次々と変えていくことで複数の解を得ることにより精度を向上させることで、精度がより向上することはあっても、最悪の場合でも従来と同じ精度は保証される方法。
【請求項４】
少なくとも、始点となる点を次々と変えていく算法の複数種類を組合せることにより精度を向上させる方法。
【請求項５】
少なくとも、精度を向上させながらも、問題を解く時間が指数関数的な増大を招かない方法。
【請求項６】
組合せ最適化問題の少なくとも一つに巡回セールスマン問題がある。これは複数の都市を一度だけ訪れながら巡回し、出発点に戻る場合の最小コストの巡回路を求める問題である。コストには時間や費用といったものが考えられるが、問題の条件が単純な場合、各都市間の距離に比例するとしてもよい。また、厳密に最小コストとなる最適な巡回路を求める場合と、実用上問題ない範囲の精度に納まる近似解を求める場合がある。なお、より一般的に、都市を点として表現する場合もある。
本発明は、少なくとも巡回セールスマン問題の近似解を求める算法に適用することが可能で、かつ、解の精度を向上させることが可能な方法。
【請求項７】
本発明が適用できる算法の少なくとも一つに巡回セールスマン問題の近似解を求める算法の一つの最近追加法がある。最近追加法では最初に部分巡回路を作り、その部分巡回路の近傍の都市を１選び出し、それを元の部分巡回路に加え、新たに部分巡回路を作る。これを全都市を加えるまで続けることで巡回路を得る。本発明は、少なくともこの最近追加法に適用でき、精度をより向上させることが可能な方法。
【請求項８】
本発明を少なくとも最近追加法に適用した場合、最初に作る部分巡回路の始点となる都市を次々と変えていくことで複数の巡回路を得、必要があれば、さらに複数の算法をこれら複数の巡回路に適用することで、解の候補を絞ることによって、精度をより向上させる方法。
【請求項９】
本発明を最近追加法に適用した場合、最初に作る部分巡回路の始点となる都市を次々と変えていくことで複数の巡回路が得られる。その中から、さらに解の候補となる巡回路を限定する必要がある場合、それを実行する方法の例の少なくとも一つとして、得られている複数の巡回路に最近隣人法を適用することで、解の候補を絞っていくことにより、解の精度をより向上させる方法。
【発明の詳細な説明】
【技術分野】
【０００１】  ２の値のいずれかをとるｎの変数の組合せに対して、ある制約条件を満足する組合せのうち、与えられた目的関数を最小とする組合せを見出す組合せ最適化問題に関する。
【背景技術】
【先行技術文献】
【非特許文献１】  「巡回セールスマン問題への招待」，朝倉書店１９９７年
【発明の概要】
【発明が解決しようとする課題】
【０００２】  組合せ最適化問題において、問題を解くための算法には、厳密に最適解を求めようとするものと、その精度が実用上問題ない範囲内にある近似解を求めるものがある。厳密に最適解を求めようとする場合、スーパーコンピュータを用いても実用にならないほど時間がかかる場合がしばしばある。そのため、近似解を求める算法が現実的である場合が多い。近似解を求める場合、最適解により近くなるように、その精度がよいほうが望ましい。本発明は、近似解の精度をより向上させることを課題とする。【０００３】  組合せ最適化問題に対し、近似解を求める算法はいくつもあるが、その中で、最初に算法を開始する始点となる点を任意に１選んで操作を開始する算法に適用することで、解の精度をより向上させることを課題とする。【０００４】  組合せ最適化問題の代表的な問題の一つに巡回セールスマン問題がある。複数の都市を一巡する巡回路で移動にかかるコストが最小のものを求めよという問題である。この移動コストが最小という意味での最短巡回路を求める従来の算法には、厳密解を求めるものと近似解を求めるものがある。最短巡回路そのものである厳密解を求める算法と異なり、近似解を求める算法はある程度、巡回路の距離が長くなっても、それが許容できる範囲であればよしとするより現実的な算法である。本発明は、少なくとも巡回セールスマン問題の従来の近似解を求める算法で、最初に算法を開始する始点となる都市を任意に１選んで操作を開始する算法に適用することにより、解の精度をより向上させる。【０００５】  組合せ最適化問題の少なくとも巡回セールスマン問題において、少なくとも、最近追加法や最近隣人法に適用することで、求められる解の精度をより向上させる。
【課題を解決するための手段】
【０００６】  組合せ最適化問題を解くための多数ある算法の中で、最初に算法を開始する始点となる点を任意に１選んで操作を開始する算法において、始点となる点を次々と変えて操作を行ない、複数の解の候補を得ることで、その中から、最も問題の条件に近いものを選び出すことで、解の精度を向上させる。【０００７】  組合せ最適化問題の代表的な問題の一つの巡回セールスマン問題において、近似解を求める算法の中で最初に算法を開始する始点となる点を任意に１選んで操作を開始する算法に最近追加法と最近隣人法がある。本発明の精度を向上させる方法は、少なくとも、最近追加法と最近隣人法に適用することで、始点となる点を次々と変えて操作を行ない、複数の解の候補を得、その中から、最も問題の条件に近いものを選び出すことで、近似解の精度をより向上させる【０００８】  精度を向上させる算法の具体例として、最近隣人法と最近追加法を挙げる。以下の説明のために、これらの算法を説明する。ここでは非特許文献「巡回セールスマン問題への招待」に載せられている説明を参考にする。まず、最近追加法を説明する。最短巡回路を求めたい都市の数をｎとし都市間の距離と移動にかかるコストは比例しているものとする。ｎある都市の中の１を任意に選び出し、その１のみからなる長さ０の部分巡回路を作る。この部分巡回路をＴとする。次に、このＴが全ての都市を含まないなら、Ｔ上の都市ｊとＴに含まれていない都市ｋの組合せのなかでｋ、ｊ間の距離を最小にする対を求める。
（ｉ，ｊ）をＴに含まれ都市ｊにつながっている本数２の路のいずれかとし、それを、本数２の路、（ｉ，ｋ）と（ｋ，ｊ）で置き換える。これを続けていき、ｎの都市全てを含めた時点で終了とする。【０００９】  次に最近隣人法を説明する。まず最短巡回路を求めたい複数の都市の中から都市を１選び、その都市と近傍の都市とを結ぶ。この操作を繰り返していって、最後に最初に選んだ都市と最後の都市を結ぶことで巡回路を作る。【００１０】  一般的な巡回セールスマン問題の条件をより狭めた問題に最近追加法を適用した場合、精度２、つまり最悪でも最短巡回路の２倍以内の長さの巡回路が得られることが保証されている。また、保証はないが、最近隣人法を巡回セールスマン問題の条件をより狭めた問題に適用した場合、巡回する都市の数をｎとすると、最短巡回路のｎを真数とする自然対数倍程度の長さにおさまることが経験的に知られている。本発明は、少なくとも最近追加法や最近隣人法それぞれに、または、これらの算法を併用した場合に本発明を適用した場合、この巡回路の距離の精度を向上させる。
【発明の効果】
【００１１】  始点を変えていくことにより得られる複数の結果の中から問題の条件を満たすのにより近いものを選び出す本発明の方法を、操作を始める始点を任意に１選んで問題を解決する算法に適用すれば、少なくとも、精度が向上することはあっても、その算法より悪くなることはない。例えば、本説明に用いた巡回セールスマン問題の最近追加法では、一般の巡回セールスマン問題の条件をより狭めた問題の場合、最短巡回路の距離の２倍以内の精度であることが保証されている。ということは、本発明の方法を適用した場合でも最も精度が悪い場合でも２倍以内ということはやはり保証されていることになり、それより精度がよくなることはあっても悪くなることはない。【００１２】  本発明の方法を、少なくとも巡回セールスマン問題解決のための算法に適用した場合、問題を解く時間は増加する。だが、その増加は、都市の数をｎとした場合、最大ｎ倍かｍ倍（２≦ｍ≦ｎ）程度であり計算時間の指数関数的増加はない。
【図面の簡単な説明】
【００１３】
【図１】番号▲１▼▲２▼▲３▼の各都市を始点として作った巡回路図
【図２】番号▲４▼▲５▼▲６▼▲７▼▲８▼▲９▼▲１０▼の各都市を始点として作った巡回路図
【図３】最近隣人法を用い番号▲１▼の都市を始点にして作った巡回路図
【図４】最近隣人法を用い番号▲２▼の都市を始点にして作った巡回路図
【図５】最近隣人法を用い番号▲３▼の都市を始点にして作った巡回路図
【発明を実施するための形態】
【００１４】  本発明の実施の形態の一つの例を［図１］〜［図５］を用いて説明する。ここでは最短巡回路を求めたい都市の数を１０とする。なお、条件を単純にして、移動のコストと都市間の距離が比例するものとする。つまり、コスト最小の巡回路が巡回の長さが最短の巡回路ということである。第一段階として最近追加法を用いることから始める。１０の都市の各々を▲１▼〜▲１０▼の番号で表すことにする。番号▲１▼の都市を始点とし▲１▼の都市だけを含んだ長さが０の最初の部分巡回路を作る。この部分巡回路の近傍の都市が例えば番号▲３▼の都市だったとすると、番号▲３▼の都市をこの最初の部分巡回路に加えて新たな部分巡回路を作る。さらに番号▲３▼の都市を含めた部分巡回路に近傍の都市、例えば番号▲２▼の都市を加えてさらに新たな部分巡回路を作る。これを続け、全都市を含め終わったら一度終了とする。
今度は番号▲２▼の都市を始点として▲２▼の都市だけを含んだ長さが０の最初の部分巡回路を作る。この部分巡回路の近傍の都市を▲３▼、▲１▼という具合にこの部分巡回路に加えていき部分巡回路を拡大していく。これを続けていき、全都市を含め終わったら、また一度終了とする。
以上の操作を全ての都市を始点として行ない続けることで、合計１０の巡回路が得られる。
【００１５】  上記の操作で１０の巡回路が得られた。この場合は都市の数が１０と少ないこともあり始点となる都市が番号▲１▼、▲２▼、▲３▼の場合の３が同じ巡回路となり、かつ、この算法で得られる最短距離の巡回路となった。これを示したのが［図１］である。始点となる都市が番号▲４▼、▲５▼、▲６▼、▲７▼、▲８▼、▲９▼、▲１０▼の場合の７が同じ巡回路となり、この場合、最長距離となった。これを示したのが［図２］である。この場合、解として選ぶのは［図１］に示した巡回路となる。
【００１６】  今回は、この算法で得られる最短距離の巡回路が複数であったが、同じ形の巡回路であったため［図１］に示した巡回路を選ぶことで問題なかった。しかし、今回とは異なる場合もありうる。つまり、長さとしては等しく最短であっても、形の異なる巡回路が複数得られる場合である。それら複数の解の候補から、より最適なものを選ぶ方法を説明するために、今回の問題に第二段階として、得られている複数の巡回路に最近隣人法を適用する方法を説明する。
【００１７】  今回の場合、複数の巡回路の中から解を選び出す必要はなかったが、必要が生じた場合の処理を説明するために、今回の問題の同じ巡回路となった番号▲１▼、▲２▼、▲３▼の都市を始点としている３の巡回路に、最近隣人法を適用して選び出す方法を説明する。
まず、番号▲１▼の都市を始点とし、番号▲１▼の都市と近傍の番号▲３▼の都市を結ぶ。次に番号▲３▼の都市と近傍の番号▲２▼の都市を結ぶ。これを続けていき、最後の都市と最初に選んだ番号▲１▼の都市とを結んで巡回路を作りおわる。次に番号▲２▼の都市を始点として同じ操作をする。終ったら、今度は、番号▲３▼の都市を始点として同じ操作を行なう。以上の結果、３の巡回路が得られる。番号▲１▼の都市を始点として最近隣人法を適用して作った巡回路を示したものが［図３］である。番号▲２▼の都市を始点として最近隣人法を適用して作った巡回路を示したものが［図４］である。番号▲３▼の都市を始点として最近隣人法を適用して作った巡回路を示したものが［図５］である。
【００１８】  上記の方法によって作成した巡回路の中から、長さが最短のものを選ぶ。この場合は［図４］に示す巡回路となった。
【００１９】  今回の場合は最近追加法において番号▲１▼、▲２▼、▲３▼の各都市を始点とした巡回路はどれも同じ形になっているため、その中から解を選び出す必要はないが、仮に異なる形だった場合は、上記に述べたように、番号▲２▼の都市を始点とした場合が最近隣人法でも最短であったため、番号▲２▼の都市を始点として最近追加法により作った巡回路を選ぶことになる。
【００２０】  上記で説明したように、本発明の精度改善法を適用した算法を第一段階として行ない、複数の異なる解候補が得られた場合は、第二段階として、やはり本発明の精度改善法を適用した別の算法を得られている複数の解候補に用いて、最も条件に近いものを選ぶことでより最適解に近い解を選び出す。
【００２１】  本説明では都市全てを始点の対象としたが、場合によってはそれより少なくてもよい。つまり、都市の数がｎの場合、２≦ｍ≦ｎのｍの都市を選ぶとしてもよい。また、複数の解の候補の中からより最適に近いものを選び出すために、複数の算法を用いるにあたり、用いる算法の数は特に限定する必要はない。
【実施例】
【産業上の利用可能性】
【００２２】  電子回路基板の穿孔制御、貨物の集配ルートの決定など。
【図１】
2015149049.tif 000003
【図２】
2015149049.tif 000004
【図３】
2015149049.tif 000005
【図４】
2015149049.tif 000006
【図５】
2015149049.tif 000007