genetic-algorithm - 具有时间窗口的 TSP 的交叉算子

Question

我正在研究 TSP 的一个变体，其中每个节点还有一个必须遵守的“时间窗口”。由于我使用遗传算法来解决 TSPTW，我想知道哪些交叉技术可能适用于 TSPTW。

谢谢。

Answer 1

这只是空想，但标准 TSP 往往会受益于试图在父巡视中保持节点邻接的运营商。因此，被认为重要的不是城市 X 出现在特定位置，而是它出现在城市 Y 和 Z 旁边，无论它们出现在字符串中的哪个位置。有像 Edge Assembly Crossover (EAX) 这样的算子专门设计用于尝试利用这种结构。

在您的情况下，时间窗口可能意味着，与 TSP 不同，01234567 之类的旅游不同于 56701234 之类的旅游，因此城市在旅游中的绝对位置也很重要。在像 QAP 这样绝对位置很重要的情况下，人们倾向于做诸如循环交叉 (CX) 之类的事情。

如果我致力于解决这个问题的 GA，我可能会先做一些显而易见的事情，比如同时实现 CX 和 EAX 并在它们之间随机选择。或者，您可能会尝试设计一个混合运算符来组合两者的元素，但这可能相当重要。

然而，我怀疑 GA 可能不是解决这个问题的方法，或者至少，黑盒 GA 可能会受到影响。尝试使用来自问题实例的语义信息的算子，例如，如果城市具有相似的时间窗口，则倾向于将彼此靠近的城市分组可能是有效的。我的 5 美元表示，一个好的本地搜索算法(禁忌搜索、可变邻域搜索等)在任何情况下都可能击败 GA，尽管这只是基于一种预感。