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

Question

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

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

谢谢。

Answer 1

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

如果只想访问距离起点一定距离内的客户，那么确定每个点到起点的欧式距离，过滤掉距离太远的。然后在剩余点上运行您的 TSP 算法。

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

Answer 2

也许您可以调整OptaPlanner（开源、Java）中的 TSP 或 VRP 示例来进行投标？有一个视频展示了如何根据您的具体情况自定义/调整约束。