帶扭曲的多個TSP

Question

幾個星期前，我遇到了一個問題，我幾乎打破了旅行商問題的變化。曲折是：

有多個銷售員。 城市列表正在動態增加（如在現場輸入） 每個城市只在有限的時間內完全盈利，因爲在一段時間之後城市將返回較少的獎勵 而且總時間限制

顯然，這個問題是NP。我想知道是否有任何可以修改以適應此問題的良好TSP近似值？

Answer 1

您可能可以使用一些操作研究軟件來解決您的問題，例如， Coin-OR，原因在於向OR約束/線性/整數/等編程求解器添加新的約束/目標通常比向一個用C或Fortran編寫的專門的TSP求解程序或者其他任何東西（而且你不可能找到一些C/Fortran代碼來解決你的問題）。 Here is a tutorial on how to code a Tabu search to solve the basic TSP using Coin-OR。此外，here is an article on modeling the time-dependent TSP（本文使用分支定界來解決可能不適合您的問題的問題，因爲它不會擴展到超過一百個城市的範圍，但該模型應該延續到近似求解器投幣-OR）。

爲了說明有多個銷售人員，您可能需要查看圖分區來區分不同銷售人員之間的城市，例如here is a fast online graph partitioning algorithm。好處是，一旦你分割了圖表，你可以減少甚至消除不同銷售人員之間的同步。