TSPヒューリスティックに方向性コストバイアスを追加すると、より良い局所最適解が明らかになる

巡回セールスマン問題（TSP）は、複数の都市を巡回し、すべての都市を一度だけ訪れて出発点に戻る最短経路を見つけるという、計算機科学における古典的な最適化問題です。TSPはNP困難問題であり、都市数が増加すると厳密な解を見つけることが計算量的に不可能になります。そのため、実用的な時間内に近似解を見つけるためのヒューリスティック手法が広く研究されています。 従来のTSPヒューリスティックは、近傍探索や局所探索アルゴリズムに依存することが多いですが、これらの手法はしばしば良好な局所最適解にトラップされ、大域的最適解からかけ離れた結果をもたらすことがあります。この問題に対処するため、本研究では、TSPヒューリスティックに「方向性コストバイアス」という概念を導入することを提案します。このバイアスは、経路の特定の方向への移動に対して、コストに偏りを与えるものです。例えば、ある都市から別の都市への移動コストを、その移動が全体的な経路の「進行方向」に沿っているかどうかに基づいて調整します。 この方向性コストバイアスをTSPヒューリスティックに組み込むことで、アルゴリズムは探索空間をより効果的にナビゲートし、従来のヒューリスティックが見逃していた可能性のある、より優れた局所最適解を発見できるようになります。実験的評価により、提案手法が既存の最先端手法と比較して、より高品質な解を生成できることが実証されています。このアプローチは、TSPだけでなく、他の組合せ最適化問題への応用も期待されます。