必須訪問を伴うセットオリエンテーリング問題にシミュレーテッドアニーリングアルゴリズムを適用する

本研究は、チームオリエンテーリング問題 (SOP) の変種である必須訪問を伴うセットオリエンテーリング問題 (SOPMV) に取り組んでいます。SOPMVでは、特定の重要なセットを訪問する必要があります。研究はSOPMVの数学モデルを定式化することから始まりました。オリジナルのMILPアプローチを用いて時間制約の中で実行可能なルートを取得する課題に対処するために、二段階混合整数線形計画 (MILP) モデルを提案しました。その後、最適なルートを特定するために、シミュレーテッドアニーリング (SA) アルゴリズムと動的計画法が採用されました。提案されたSAアルゴリズムはSOPを解くために使用され、他のアルゴリズムと比較され、その効果が示されました。次に、SAはSOPMV問題を解くために適用されました。結果は、SAを使用して得られた解が、オリジナルのMILPや二段階MILPから導き出されたものに比べて優れており、より効率的であることを示しています。さらに、必須訪問セットの比率が増加したり、最大許容移動時間が減少するにつれて、解の質が悪化することが明らかになりました。本研究は、SOPに必須訪問を統合する初めての試みであり、この分野における新しい研究方向を確立しています。この研究の潜在的な影響は重要であり、複雑な組合せ最適化問題に対処するための新しい可能性を導入します。