c# - 有时间限制的旅行推销员

Question

我正在尝试制作一个应用程序来计算每天拜访客户的路线。到目前为止，我可以使用遗传算法全程解决问题。但我需要通过距离来限制解决方案。当我在某个时刻“切断”解决方案路径时，它就变成了一个糟糕的解决方案。这个例子有特殊的算法吗？我正在尝试寻找并安装一个，但没有成功。

有人做过这个可以给我推荐吗？我可以使用 vb.NET、c#、php 或 JAVA。

谢谢。

Answer 1

如果您限制行驶距离，那么我假设您可以不每天拜访所有客户。如果您需要拜访所有客户并且您有一个想要旅行的最大距离，那么您所能做的就是继续运行您的 TSP 算法，直到它(希望)产生您满意的解决方案。

如果只想访问距起点一定距离内的客户端，则确定 Euclidean distance从起点开始计算每个点，并过滤掉那些距离太远的点。然后对剩余点运行 TSP 算法。

我假设您希望能够通过最大距离 d 拜访尽可能多的客户。我建议使用Hill-climbing方法。从有效的解决方案开始(例如，仅使用贪婪方法获取下一个最近的未访问客户端，并在总距离为 d 时停止)，然后随机修改解决方案中的 n 个节点(这可能意味着对它们重新排序，或者这可能意味着将节点交换为当前不在解决方案中的节点；此处使用明智的启发式方法，您不想将节点交换为 map 另一侧的节点，一种可能的方法是使用加权算法，该算法有利于与较近的节点进行交换，而不是较远的节点)并测试新的解决方案是否有效+是否比以前的解决方案更好。您始终可以通过从行程中删除最后几个客户来强制新解决方案有效。