リングスター問題

リングスター問題( RSP ) は、組み合わせ最適化におけるNP 困難問題です^{[ 1 ]}。完全重み付き混合グラフにおいて、リングスター問題は、サイクル(リング部分) とアークの集合 (スター部分)から構成される最小コストのリングスター部分グラフを見つけることを目的とします。ただし、各アークの子ノードはサイクルに属し、各アークの親ノードはサイクルに属しません。アークのコストは通常​​、サイクルのコストとは異なります。サイクルには、少なくとも 1 つのデポまたはルートとして指定されたノードが含まれている必要があります。

RSPは巡回セールスマン問題の一般化である。^{[ 1 ]}弧のコストが無限で、リングがすべてのノードを含む場合、RSPはTSPに帰着する。RSPの応用例は、電気通信、^{[ 2 ]}輸送または物流の分野で発生する。

RSPは1998年に初めて定式化されました。^{[ 2 ]} RSPを解くための最初のMILPは、定式化を改善する有効な不等式とともに2004年に導入されました。 ^{[ 1 ]その後、グラフ層ベースのILP [ 3 ]}やstチェーン定式化^{[ 4 ]}など、リングスター問題を解くためのいくつかの厳密な定式化が導入されました。

2006年以降、環状星問題の多くの変種が研究されてきた。

• 容量付きmリングスター問題（2006）^{[ 5 ] [ 6 ]}
• マルチデポリングスター問題（2010）^{[ 7 ] [ 8 ]}
• 非分離mリングスター問題（2014）^{[ 9 ]}
• 生存可能なリングスター問題（2024）^{[ 10 ] [ 11 ]}

RSP の最初のヒューリスティックである一般変数近傍探索は、近似解をより迅速に得るために導入されました。^{[ 12 ]} 2013 年に、進化アルゴリズムも RSP を近似しました。2020 年に、アリコロニー最適化^{[ 13 ]}ヒューリスティックが進化アルゴリズムのヒューリスティックを上回りました。