TSP的变化：限制时间，请尽可能多的节点作为可能的 [英] a variation of TSP : limit time, visit as many nodes as possible

问题描述

再一次让我们使用业务员背景：

again let's use the salesman context:

如果不要求业务员拜访所有的客户，而是被赋予了时间限制，其中他必须访问次数尽可能多的客户尽可能。我们怎样才能找到最佳路线？

if the salesman is not required to visit ALL customers, but is given a time constraint, in which he must vist as many customers as possible. how can we find the best route?

更稍微高级的版本，说每个客户都标有一个获取金钱，所以我们的销售员要最大限度地从这些客户的总金钱利益，他居然参观，只要他完成的时间限制内探访他们

an even more slightly advanced version is, say each customer is marked with a monetary gain, so our salesman wants to maximize the total monetary gain from those customers that he actually visits, as long as he finishes visiting them within the time constraint

我试图寻找一些研究论文。但我发现最接近的是K-TSP的工作，其中业务员被要求最大化路径上的总增益少于k个跳长。这是因为边缘时间成本并不存在很大的不同，或仅仅是1。

I tried to search for some research papers. but the closest I found is the work on k-TSP, in which the salesman is asked to maximize the total gain on a path less than k hops long. this is quite different since the edge time cost does not exist, or is just 1.

有人知道了在这个问题上的任何现有的研究工作？

anybody knows of any existing research work on this problem?

谢谢 杨

推荐答案

看 jsprit 。它允许您定义：

• 在一个旅行商具有时间限制，即earliestStart和latestArrival在启动/仓库的位置，
• 利润为每一位客户参观和
• 的目标函数考虑这些利润。

因此​​jsprit决定你需要访问到最大的客户。你的利润考虑运输成本和时间的限制。所有其他客户端在未分配的任务列表。需要注意的是jsprit使用启发式方法来解决这样的问题。

Thus jsprit determines the customers you need to visit to max. your profits considering transport costs and time constraints. All other customers end up in an unassigned job list. Note that jsprit uses an heuristic approach to solve such a problem.

这篇关于TSP的变化：限制时间，请尽可能多的节点作为可能的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！