TSP的一种变体：限制时间，访问尽可能多的节点

让我们再次使用推销员上下文：

如果销售员不需要拜访所有客户，但有时间限制，他必须拜访尽可能多的客户。我们怎样才能找到最佳路线？

一个更高级的版本是，假设每个客户都被标记为货币收益，因此我们的销售人员希望最大化他实际访问的那些客户的总货币收益，只要他在时间限制内完成访问即可

我试图搜索一些研究论文。但我发现的最接近的是 k-TSP 的工作，其中要求推销员在小于 k 跳长的路径上最大化总增益。这是完全不同的，因为边缘时间成本不存在，或者只是 1。

有人知道关于这个问题的现有研究工作吗？

谢谢 杨

Look at jsprit http://jsprit.github.io/。它可以让您定义：

• 一个有时间限制的旅行推销员，即最早出发和最晚到达出发/站点位置，
• 为每位顾客带来的利润
• 考虑这些利润的目标函数。

因此 jsprit 确定您需要访问的最多客户。考虑到运输成本和时间限制，您的利润。所有其他客户最终都会出现在未分配的工作列表中。请注意，jsprit 使用启发式方法来解决此类问题。