不限制访问次数的旅行商问题

Question

我有一个类似于旅行商 (TSP) 的问题。我找到了一些库来解决旅行商问题。但是，我想取消每个城市只能访问一次的限制。如何找到访问每个城市 至少 一次的最短路径？

Answer 1

一种简单的方法是通过预处理。将每个 c(i,j) 替换为 i 和 j 之间最短路径的 length/cost 。现在应用标准茶匙。报告时，将这些最短路径插入解决方案中。这可能会导致多次访问城市。