gpt4 book ai didi

algorithm - TSP : limit time, 的变体访问尽可能多的节点

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:14:10 25 4
gpt4 key购买 nike

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

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

一个更高级的版本是,假设每个客户都标有货币 yield ,所以我们的销售人员希望最大化他实际拜访的那些客户的总货币 yield ,只要他在时间限制内完成访问他们

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

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

谢谢杨

最佳答案

jsprit .它允许您定义:

  • 有时间限制的旅行推销员,即 earliestStart 和 latestArrival 在起点/站点位置,
  • 每个来访的客户的利润和
  • 考虑这些利润的目标函数。

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

关于algorithm - TSP : limit time, 的变体访问尽可能多的节点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26927960/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com