一個求解旅行商問題的松弛算法

摘要：在旅行商問題(TSP)的傳統模型中,子回路消除約束的數量隨著問題規模的增大具有指數增長的特性,極大地限制了TSP的求解效率?；赥SP的松弛問題,本文提出一種有效生成子回路消除約束的方法。該方法通過求解一系列線性整數規劃,來實現TSP的精確快速求解。數值結果表明,本方法相比于采用Cplex直接求解,能夠更快地找到TSP的最優解。