TSP與

Question

我遇到問題的扭曲，這是非常相似的旅行商問題，除了與一些曲折：

1. 您可以訪問同一個節點多次
2. 的旅行邊緣，你之前已經走過無成本
3. 該圖是針對

當然，這個問題是NP完全的，因爲這是TSP的變化，但如果有任何ALGOR我想知道ithms是否被設計用於常規TSP，可以很容易地修改以適應這個特定的問題？

Answer 1

聽起來像你所描述的是圖形，不對稱TSP。爲了打破你描述的限制，

3是不對稱TSP（ATSP），即有向圖上的TSP。這總體上比TSP難得多，但這是一個相當充分研究的問題。在我的頭頂，Lin-Kernighan-Helsgaun（LKH）啓發式是一種TSP啓發式方法，它在ATSP方面也表現出色，我相信還有其他方法。

1是圖形化TSP，即可以多次訪問節點的TSP。我不完全稱這個問題研究得很好。它有一個很好的工作體系，但其中大部分都是針對標準TSP開採的結果。

約束條件2讓我困惑不已，但我認爲它是一條紅色的鯡魚，因爲它已經隱含在圖形化的TSP中。另一種考慮圖形化TSP的方法是，你需要一個原始圖的連通子圖，其中每個節點的度數至少爲2，而在TSP中度數等於2。因此我們只會花費一次訪問邊緣的成本。

所以要把這個與你的問題聯繫起來！如果我不得不使用TSP方法的「輕鬆修改」算法，我會：

- 使用LKH計算啓動的ATSP巡視，因爲這樣的巡視對於您的問題是可行的，所以它提供了一個上限。

- 在商業整數規劃解算器（如CPLEX或Gurobi）中編寫圖形ATSP的公式。我會用ATSP的Held-Karp放鬆度來改變度方程，以允許多次訪問一個給定的城市。

- 在返回斷開連接的解決方案的情況下，向IP解析器回寫添加連接性約束的回調。

- 通過IP解算器進行LKH巡視，作爲熱啓動/數值上限。

然後希望最好！基本上，這將是一個削減版的基於切割平面的TSP解算器，適合您的問題。我不會指望它解決大規模的實例，但我認爲這會給人一種可敬的嘗試。