有时限的旅行推销员

Question

我正在尝试制作一个应用程序来计算每天拜访客户的路线。到目前为止，我可以通过使用遗传算法来解决整个问题。但我需要用距离来限制解。当我只是在某个点“切割”解决方案路径时，它就变成了一个糟糕的解决方案。这个例子有特殊的算法吗？我想找一个合适的，但运气不好

以前做过这个的人能给我一个推荐吗？我会用vb。NET、c#、php或JAVA

谢谢

Answer 1

也许你可以调整OptaPlanner（开源，java）中的TSP或VRP示例来完成你的出价？有a video that shows how to customize/tailor the constraints to your specific case

Answer 2

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

如果您只想访问距起点一定距离内的客户，则确定距起点的每个点的Euclidean distance，并过滤掉那些距离太远的客户。然后在剩下的点上运行TSP算法

我假设您希望通过旅行最大距离d访问尽可能多的客户。我建议使用Hill-climbing方法。从一个有效的解决方案开始（例如，只需使用贪婪的方法，获取下一个最近的未访问客户端，并在总距离为d时停止），然后随机修改解决方案中的n节点（这可能意味着对它们进行重新排序，或者这可能意味着将一个节点替换为当前不在解决方案中的节点；在这里使用合理的启发式方法，您不想将一个节点替换为位于地图另一侧的节点，一种可能的方法是使用加权算法，该算法倾向于与较近的节点交换，而不是与较远的节点交换）并测试看看新的解决方案是否有效+比以前的解决方案更好。你总是可以通过从旅行中剥离最后几个客户来强制新的解决方案有效