有时间限制的旅行推销员
本文关键字：旅行推销员 时间 | 更新日期: 2023-09-27 18:09:12
我正在尝试制作一个应用程序来计算访问我的客户的每日路线。到目前为止，我可以用遗传算法求解全程。但我需要用距离来限制解。当我在某个点"切断"解决方案路径时，它就变成了一个糟糕的解决方案。对于这种情况有没有特殊的算法?我想找一个合适的，但是运气不好。
有做过这个的人可以给我推荐一下吗?我可以用vb。. NET, c#， php或JAVA谢谢。
如果你限制旅行的距离，那么我假设你可以接受每天不去拜访所有的客户。如果你需要拜访所有的客户，并且你有一个你想要旅行的最大距离，那么你所能做的就是继续运行TSP算法，直到它(希望)产生一个你满意的解决方案。
如果您只想访问距离起始点一定距离内的客户，则确定每个点到起始点的欧氏距离，并过滤掉距离太远的客户。然后在剩下的点上运行TSP算法。
我假设你想通过旅行最大距离d来访问尽可能多的客户。我建议使用爬山的方法。从一个有效的解决方案开始(例如，只是使用贪婪的方法，采取下一个最近的未访问客户端，并在总距离为d时停止)，然后随机修改解决方案中的n节点(这可能意味着重新排序它们，或者这可能意味着将节点交换为当前不在解决方案中的节点;在这里使用明智的启发式方法(您不想将节点交换到地图另一侧的节点)，一种可能的方法是使用加权算法，该算法倾向于使用较近的节点而不是较远的节点进行交换)，并测试新解决方案是否有效+比以前的解决方案更好。您总是可以通过从旅程中剥离最后几个客户端来强制新的解决方案是有效的。
也许你可以调整TSP或VRP的例子在OptaPlanner(开源，java)做你的投标?有一个视频展示了如何根据你的具体情况定制/定制约束。