标签: traveling-salesman

我正在建立一个遗传算法来解决旅行商问题.不幸的是,我发现可以持续超过一千代的峰值,然后突变它们并获得更好的结果.在这种情况下,交叉和变异算子通常做得好吗？

我正在解决这个问题：

TSP:
Input: A matrix of distances; a budget b
Output: A tour which passes through all the cities and has length <= b, 
if such a tour exists.

TSP-OPT
Input: A matrix of distances
Output: The shortest tour which passes through all the cities.

表明如果TSP可以在多项式时间内求解，那么TSP-OPT也可以。

现在，首先要想到的是，如果我知道最佳解决方案的成本，则可以将b设置为voila。而且，您会不会知道，在我书的其他地方也包含有关此问题的提示：

我们如何找到最佳成本？容易：通过二进制搜索。

我想我可能在这里误会了很严重的事情。二进制搜索旨在找到给定项目在排序列表中的位置。那到底如何帮助我找到最佳成本？我真的很困惑。不幸的是，作者没有进一步阐述。

解决这个问题，我唯一想到的另一件事就是证明它们都可以归结为NP-complete的另一个问题，我可能最终会解决，但这仍然使我感到困惑。

我正在学校开设一个数学课的项目,我选择在旅行商问题上做我的,我一直想调查一下.但是,我的蛮力求解算法存在问题.

*请转到底部的更新以查看最新版本的代码

跳过这一段,如果你知道旅行商问题是: 总结尽可能的TSP是这样的:你是谁想要访问每个城市在区(城市本质上是一个地图上的点)推销员.在有界x和y区域中有'n'个城市,每个城市与每个城市相连(通过直线道路).您需要在城市中找到允许您访问每个城市的最短路径.我想要使用的其中一种算法(我需要测试其他算法)是Brute Force,它检查每条可能的路线并返回最短的路线路线.这并不总是使用的原因是因为它需要我们检查(n-1)!可能的途径,而且这个数字得到巨大的"N" increases-事实上,只有50个城市,这将是608281864034267560872252163321295376887552831379210240000000000条路线检查.

将承担谈到这篇文章的所有例子,我们将要使用的一个任意区域有4个城市(即使该算法可以处理n个城市.我们也不在乎distances-我们想打畜生一切可能的途径力).

这是一个简单的图片演示我正在谈论的内容(4个城市是我开始检查过程是否正常工作)

与城市的地图的图片

这是Brute Force算法(假设所有其他被调用的方法都正常工作,因为它们可以):

(请在下方查看更多解释)

[码]

public void BruteForceFindBestRoute(Route r) //Must start r having 1 unflagged city to begin with
    {
        if(!r.allFlagged() && r.route.size() != m.cities.size())
        {
            /*STEP 1 Begin with last unflagged city*/
            City pivot = r.lastCityAdded();
            /*STEP 2: Flag city*/
            pivot.visited = true;
            /*STEP 3: Find cities "NOT IN ROUTE"*/
            ArrayList<City> citiesNotInRoute = new ArrayList<City>();
            for(int i = 0; i<m.cities.size(); i++)
            {
                if(!r.isCityInRoute(m.cities.get(i).name))
                {
                    citiesNotInRoute.add(m.cities.get(i));
                }
            }
            /*STEP 4: …

我正在尝试找到驾驶通过 A、B、C 和 D 点的最佳方式

有一些额外的限制 - 必须先达到某些点。说 D 必须在 B 之前到达。换句话说，对某些点进行排序。

如果没有额外的限制，Google Maps apis 可以帮助解决这个问题。是否有其他服务可以帮助解决此问题？有没有办法用我错过的谷歌地图 api 来做到这一点？

我正在寻找在Java中实现模拟退火算法以找到旅行商问题的最佳路线,到目前为止,我已经实施了暴力,并且我正在寻找修改该代码以便使用模拟退火.显然,强力和模拟退火是非常不同的,并且使用非常不同的功能.

我知道模拟退火使用一个称为温度的变量,然后在算法运行时冷却; 温度从高处开始逐渐冷却.虽然温度很高,但算法更可能选择比当前更差的解决方案,从而消除了类似爬山算法中的局部最大值.由于它冷却,算法更不可能接受更糟糕的解决方案,因此它可以专注于特定区域,并且可以快速找到最佳路线.

我相信我理解算法是如何工作的但是我把它放到Java中有困难,我有2个类; 一个叫城市,只是包含的方法制定出每个城市,如细节getIndex,getDistance等算法类从数组中输入文件并将其存储读取(int [][])

下面的代码是蛮力的算法,这是我想要修改的模拟退火,如果有人可以帮我这样做,我会非常感激它.

public static void doBF()
{
    int random1 = generateRand();

    if (towns2.size() > random1)
    {
        Town town = towns2.get(random1);
        visitedTowns[i] = town;
        towns2.remove(town);
        i++;
        if (lastTown != 1000)
        {
            journey += town.getDistance(lastTown);
        }
        lastTown = town.getIndex();
    }
    else 
    {
        doBF();
    }
}

我有一个地址列表,需要找到到达每个地址的最佳路线并回到起点使用谷歌地图API我可以用8个航路点来计算这个,但我认为8个不足够.

是否有人提供超过8个航路点的路线优化？我的意思是必须有,对吗？这是许多组织需要解决方案的问题.如果它花了很多钱,这是完全没问题的,计算非常重,所以我不希望任何免费服务.也许谷歌有这样的付费服务(针对中小企业)？

我会就如何解决这个问题采取任何想法!

它应该在应用程序内部工作,因此我不仅需要一个可以输入地址并返回路由的网页,我需要一些具有API的东西.

据我所知,3-Opt Heuristic涉及从图表中删除三条边,然后再添加三条边以重新完成游览.然而,我已经看到很多论文提到当三个边缘被移除时,仍然只有两种可能的方式重新组合巡回演出 - 这对我来说没有意义.

例如,该文件说:

3-opt算法以类似的方式工作,但不是删除两个边缘,而是删除三个.这意味着我们有两种方法可以将三个路径重新连接到有效的tour1中.3-opt移动实际上可以被视为两次或三次2-opt移动.

但是,我计算了8种不同的方式来重新连接游览(如果在删除边缘之前不计算顺序,则为7).我在这里错过了什么？

另外,有人可以将我链接到3-opt的算法吗？我只是想更好地理解它,但我还没有遇到任何问题.我找到的所有资源只是说"删除三条边,重新连接它们".而已.

在典型的 TSP 算法中，我们有多个点，并且希望以最佳的行进顺序行进。点是家庭、顾客等，基本上是地图上的一个点。

我用线代替点。扫雪就是一个很好的例子，你可以在多条街道上行驶。最大的区别是，对于每次旅行，结束点与起点不同。我的尝试是假设起点作为每次旅行的唯一节点。但显然，每当你的路线/线路很长时，你最终都会到达距离起点很远的地方。而且这个解决方案已经远非最佳了。

我查看了一些提供路线优化的公司。他们的解决方案就是将线分成接近的点；并将每条线视为彼此靠近的节点。我认为当你必须穿过街道的两侧，或者每当你靠近另一条街道时，这是行不通的。

我想知道是否有建模技巧或其他方法来解决这个问题？

我想在 Python 中使用动态编程算法解决 TSP 问题。问题是：

• 输入：表示为点列表的城市。例如，[(1,2), (0.3, 4.5), (9, 3)...]。城市之间的距离定义为欧几里得距离。
• 输出：此实例的旅行推销员旅行的最低成本，四舍五入到最接近的整数。

伪代码是：

Let A = 2-D array, indexed by subsets of {1, 2, ,3, ..., n} that contains 1 and destinations j belongs to {1, 2, 3,...n}
1. Base case:
2.          if S = {0}, then A[S, 1] = 0;
3.          else, A[S, 1] = Infinity.
4.for m = 2, 3, ..., n:   // m = subproblem size
5.    for each subset of {1, 2,...,n} of size m that contains …

我正在使用 R 中的 TSP 包解决旅行商问题，但试图实现预定的起点和终点。

该包显然允许设置旅程的起点，如下所述： 如何使用 R 中的 TSP 包指定起始城市

想知道是否有人知道设置终点的方法。我了解 TSP 本质上是开放式的，因此可能无法预设端点。在这种情况下，我对另一种最近邻方法持开放态度，该方法会产生类似的结果（按多元相似性/距离进行排序，并设置起点和终点）。

这是一个快速示例：

dat <- data.frame(X=sample(0:100,n)/100,Y=sample(0:100,n)/100,Z=sample(0:100,n)/100)
dat$SUM <- rowSums(dat)

startPoint <- which.min(dat$SUM) # Lowest sum
endPoint   <- which.max(dat$SUM) # Highest sum

tsp <- solve_TSP(TSP(ddat), method="nearest_insertion", start=startPoint)

tsp[1]==startPoint
> TRUE

tsp[n]==endPoint
> FALSE

不幸的是，“nearest_insertion”方法（和任何其他非随机方法）总是返回相同的路径，所以端点永远不会改变。因此，我可以删除 start= 选项，更改为随机起点方法，然后将其放入 while() 循环中，并希望它最终收敛于解决方案：

while(tsp[1]!=startPoint | tsp[n]!=endPoint){
  tsp <- solve_TSP(TSP(dist(dat[c("X","Y","Z")])), method="two_opt")
}

tsp[n]==endPoint
> TRUE

即使对于大数据，这似乎也能一致且非常快速地工作，而且我还没有遇到随机生成的数据集挂起循环。但是使用更优雅（更少蛮力）的方法会很好。有什么想法吗？