我正在使用Google Or-Tools通过this示例来解决一个旅行商问题(基本上我只是用我的距离矩阵代替了距离矩阵)。与示例中一样，我设置了data['depot'] = 0。对于我的应用程序，返回到路径末尾的第一个节点并不重要。我可以从解决方案中删除最后一条边，但我想知道，如果我可以完全删除这个限制，它可能会找到一条更好的整体路径。
浏览 73提问于2020-04-27得票数 2
回答已采纳
1回答
我正在寻找一个足够近的旅行商问题(CETSP)的解决方案，在这个问题中，我需要访问一组节点，所有节点都在某个最佳距离内。我已经为这个TSP变体的一些方法找到了几个来源，但无法找到我可以轻松使用的求解器或算法。
你有什么建议可以让我的CETSP问题得到一个解决方案，无论是我自己运行它的实现还是使用现有的求解器。
浏览 1提问于2016-02-19得票数 0
2回答
用线性表达式表示旅行推销员
、、、、
我在网上看到，人们可以将旅行推销员问题写成一个线性表达式，并使用CPLEX这样的软件来计算它。我的问题是，我如何准确地把它表示成一个线性表达式。所以我有100个城镇，我相信每个人都知道TSP是如何运作的。有
浏览 1提问于2015-04-28得票数 7
回答已采纳
有没有办法使用Google Maps API在给定一组路点的情况下返回“优化”的路径(换句话说，对旅行商问题有一个“足够好”的解决方案)，或者它总是以指定的顺序返回包含这些点的路径吗？
浏览 11提问于2008-12-03得票数 20
回答已采纳
我想知道TSP的问题名称是什么，考虑到回到起点的方式，以及解决这个问题的算法是什么。我也研究了哈密顿路径问题，但似乎没有解决我定义的<em
浏览 1提问于2011-07-18得票数 41
回答已采纳
2回答
如果用动态规划方法求解旅行商问题，它能给出比贪婪方法更好的可行解吗？
我知道，在最优解方面，贪婪算法被用来求解TSP，但是当顶点数(即城市)非常大时，它变得更加复杂，并且需要指数时间。
浏览 2提问于2019-02-05得票数 1
3回答
多路径旅行商优化
、、
我试图用不完全图来求解多路径旅行推销员的变型.更确切地说：
售货员只能访问每一个城市一次。我试过用pyconcorde解决这个问题。为此，我将同一节点的每一个平行边编码为一个新节点(A，A'，A'')，但我无法找到只访问一个A节点的限制。我看到了许多类似的TSP和多TSP<
浏览 1提问于2019-10-10得票数 0
1回答
所以我想解决输入完整的、加权的、有向图G和目标整数k1) visits every vertex exactly once通过以下方式：网格图是一个图，其中的顶点是从0,0到n，n的整数坐标(所以0,0，0, 1，0，2，...
浏览 4提问于2019-07-16得票数 0
我的问题是：什么是快速算法来做到这一点？这是一个众所周知的问题吗？相当快
浏览 3提问于2012-09-05得票数 4
1回答
TSP扭动一下
、、
我遇到了一个非常类似于旅行推销员问题的问题，除了一些曲折之外：
当然，这个问题是NP-完全的，因为这是TSP的一个变体，但我想知道是否有为常规TSP设计的算法可以很容易地修改以适应这个特定的问题？
浏览 0提问于2016-11-28得票数 0
回答已采纳
更确切地说，组合算法和线性算法的定义是什么？由于NP-hard问题是如此困难，有一个完整的领域试图找到近似的解决方案。例如，旅行商问题有几个近似解，它们以多项式时间运行，并产生一个在最佳解的
浏览 0提问于2009-06-16得票数 6
回答已采纳
6回答
将TSP归结为哈密顿回路
、、、、
我如何将旅行商问题(决策版本)转换为哈密顿回路问题(即如何将TSP简化为HCP，以便如果我有HCP的解决方案，则我将使用该解决方案来解决TSP问题)？
浏览 1提问于2012-11-14得票数 3
2回答
我在网上找到了许多资源，讨论这个和相关的主题，但我还没有找到任何真正帮助我知道从哪里开始实现这个解决方案的东西。C({0,4},4) = 1951S = {0,1,2}C(为了使这成为一个动态编程解决方案，我假设我应该保存任意n个节点之间的最短距离，我认为最好
浏览 2提问于2015-10-30得票数 2
2回答
可多次访问顶点的TSP
、、、
我想解决一个问题，我有一个加权有向图，我必须从原点开始，至少访问所有顶点一次，并在最短的路径上返回原点。本质上，这将是TSP的一个典型例子，但i不有一个约束，即每个顶点只能访问一次。在我的例子中，任何不包括原点的顶点都可以沿着路径访问任意次数，如果这使得路径更短。例如，在包含顶点V1, V2, V3的图中，这样的路径是有效的，因为它是最短路径：
ORIGIN -> V1 -> V2 -&
浏览 4提问于2016-10-03得票数 3
回答已采纳
2回答
TSP变种，可能的算法？
、、、、
经典的旅行商问题(TSP)定义之一是：在我的例子中，我不需要哈密顿路径，我需要两个已知顶点之间的路径。因此，公式将是：
给定一个加权完全无向图，其中三角形不等式成立，两个称为源和目的地的特殊顶点返回一条最小加权路径，该路径恰好访问所有节点一次，从源开始，结束于目的地。我记得哈密顿路径是无向图中的一条路径
浏览 4提问于2013-03-08得票数 0
这个问题已经被以类似的方式问了几次，但我找到的现有答案中没有一个对我有实际帮助。对于我必须解决的特定问题，我需要一个非常快速的解决方案。据我所知，我的问题与所有对最短路径问题有关。我也在想，
浏览 0提问于2013-11-26得票数 2
我阅读了关于这方面的各种材料，并理解了其中涉及的原理和概念，然而，没有一篇论文提到如何计算涉及相邻城市(在染色体中)而不是由(图中的)边直接连接的染色体(代表一条路线)的适合度的细节。例如，给出一条染色体1|3|2| 8 |4|5|6|7，其中每个基因代表一个城市在图形/地图上的指数，如果城市2和8之间没有直接的边/链路，我们如何计算它的适应度(即旅行距离的总和)。我们是否遵循某种贪婪算法来计算出2到8之间
浏览 1提问于2010-03-30得票数 5
回答已采纳
2回答
多起点、单终点的旅行推销员
、、、、
我试图制作一个谷歌地图应用程序，其中涉及从不同地点的车辆路线。例如，假设有三辆车，每辆都在不同的地点，它们必须覆盖10个地点，并到达一个共同的目的地。我需要找到最理想的方式，以涵盖所有10点与3辆车。我知道提供了一个解决旅行推销员问题的“方法点”功能，但是只有一辆车。我看了车辆路线问题，但未能找到一个算法来解决我的问题。如果有人能为我指出解决这个问题的正确方向，我将不胜感激。
浏览 0提问于2014-01-17得票数 1
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
云直播
对象存储
腾讯会议活动推荐
腾讯云开发者
