algorithm - 最佳(近似)路径算法(距离+优先级)

Question

我需要为以下场景编写一个算法:

Given a set of points (cities) on a map I have to visit. Each of these cities has a priority, from 1 (you need to go there ASAP) to 5 (no rush, but go there eventually). I have limited ressources so I can not visit all the priority-1 cities at first. (E.g if NY and SF have priority 1 and Washington has Priority 5, I'm looking for a path NY-Washington-SF not NY-SF-Washington).

我不知道这是否重要，但 n(城市数量)通常在 10-20 左右。

我找到了“分层旅行商问题”(Panchamgam、Xiong、Golden 和 Wasi)的演示文稿，这正是我正在寻找的内容，但相应的文章不可公开访问。

您能否推荐适用于此类场景的现有算法？或者指出我要搜索的正确方向？

一个近似值就可以了。我的情景并不像 Panchamgam 等人描述的那样危及生命。阿尔。重要的是要避免因优先级而导致的不必要的弯路，而不是完全忽略它们。

Answer 1

在标准 TSP 中，您希望最小化路线的总长度。在您的情况下，您基本上想优化两个指标:路线的长度，以及高优先级城市出现在路线上的时间。您需要将这两个指标放入一个指标中，您如何做可能会对算法选择产生影响。例如，将城市优先级映射到处罚，例如

1  ->  16
2  ->  8
3  ->  4
4  ->  2
5  ->  1

然后将 (city_penalty * distance_to_city_from_start_on_route) 的总和用作您想要最小化的指标。这通常会将高优先级城市推到路线的开头，但如果路线变得太长，则允许优先顺序遍历。显然，应该通过实验调整惩罚值。

有了这个指标，您就可以使用例如标准随机搜索方法 --- 从一条路线开始，然后交换路线上的城市或边缘以减少指标(使用模拟退火或禁忌搜索)。