问题标签 [traveling-salesman]

我在 2d 平面上有 n 个点，n <= 12，我需要可用最短路径的距离，包括所有点，从其中任何点开始，但不形成闭合回路

我一直在尝试弗洛伊德元帅、旅行推销员问题和其他算法，但没有成功。

这个问题对我的老师来说很容易，所以我认为它不需要阿罗拉近似值左右，但我不知道解决这个问题的最佳方法是什么，但也许是一些动态算法之类的

有什么帮助吗？

鉴于城市列表和每个城市之间的飞行成本，我试图找到访问所有这些城市的最便宜的行程。我目前正在使用MATLAB 解决方案来寻找最便宜的路线，但我现在想修改算法以允许以下内容：

1. 重复节点- 应该允许重复节点，因为通过枢纽城市旅行通常会导致更便宜的路线
2. 动态边权重- 往返航班的成本与两个等效的单程航班不同（通常更低）

目前，我忽略了航班日期的问题，并假设可以从任何城市旅行到任何其他城市。

有谁知道如何解决这个问题？我的第一个想法是使用像GA或ACO这样的进化优化方法来解决第 2 点，并在根据行程是否包含往返航班来评估目标函数时简单地调整边缘权重，但也许其他人有更好的主意。

（注意：我使用的是 MATLAB，但我并不是专门寻找编码解决方案，更多的是关于可以使用哪些算法的高级想法。）

编辑 - 在考虑了更多之后，允许“重复节点”似乎过于宽松的约束。我们可以进一步约束这个问题，使得虽然节点可以被重复访问，但每个有向边最多只能被访问一次。忽略任何包含同一方向同一航班的行程不止一次似乎是合理的。

我正在尝试使用简单的爬山算法来解决旅行商问题。我想创建一个 Java 程序来做到这一点。我知道它不是最好用的，但我主要希望它看到结果，然后将结果与我还将创建的以下结果进行比较：

• 随机爬山者
• 随机重启爬山者
• 模拟退火。

无论如何回到简单的爬山算法，我已经有了这个：

这就是我所需要的吗？这段代码是否正确..？我希望程序从中读取并生成结果的文本文档中有一系列不同的数据集。

非常感谢您对此的任何帮助。

- - - 编辑 - -

我是个白痴，当我应该先在记事本中打开它时，直接在 Eclipse 中打开了 Java 文件。这是我现在得到的代码。

可能重复：
使用 A* 解决旅行商问题

我最近了解到A*算法可以应用于旅行商问题。Bot 我们如何在这里定义起点和目标，以及我们如何将权重应用于节点（什么是启发式）？

有人可以向我解释如何在这里应用 A* 吗？

是否有一种算法可以在多项式时间内准确地解决（时间无关的）TSP 问题（没有启发式方法，节点不是空间中的点并且成本是任意的）？

谢谢！

我正在尝试使用克隆选择算法来解决旅行商问题。我正在为我的一个班级项目做这件事，以比较克隆选择与传统遗传算法在这个问题上的比较。我找到了一篇以前做过这件事的人的论文，我正在尝试复制它。

http://www.dca.fee.unicamp.br/~vonzuben/research/lnunes_dout/artigos/gecco00.pdf

该算法在第 5 节中有详细解释。有人知道每一代的 Memory Set 和 Population 之间的关系吗？记忆集是否替换了每一代的种群？在每一代中，是被克隆和变异的记忆集还是种群？

任何帮助，将不胜感激！

我正在编写一个 C++ 项目来使用遗传算法解决旅行推销员问题。自然，我想在同一个局域网中使用一堆（大约 40 台）计算机来加快速度。计算机都在运行 Windows XP ......所以，问题是使用给定设备并行化它的方法是什么

更新：您帮助我将选择范围缩小到 mpich 一个 Open MPI，所以剩下的唯一问题是我应该为它们使用 boost MPI 包装器吗？另外，你能推荐一个 mpich/OpenMPI 的教程吗？

在http://www2.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/中是否有 TSPLIB 中包含的位置名称的来源。

出于说明目的，最好知道 Berlin52 实例上的第 31 点在哪里。

谢谢

Robert ps：是的，我用谷歌搜索了它-但是除了 ulysses 16 之外我找不到任何东西。非常令人沮丧

Let's assume food delivery for multiple restaurants (say 20). There are (say 10) drivers available. Further, let's say we get 100 orders over a 4 hour period to deliver food from these restaurants to homes.

So drivers have to be coordinated to pickup food at a location and deliver to customers at home.

Primary goal is to minimize time to delivery, i.e. time between order and arrival at homes. The secondary goal is to maximize driver capacity (i.e., least amount of time to deliver all orders).

Bear in mind that the orders come in over a four hour period, so let's say evenly, i.e. one very 3 minutes. Also, let's assume the orders are randomly to the 20 restaurants.

Assume that I can calculate time to travel from any location to a destination to the second.

I know the location of all drivers in realtime. I also know their statuses, i.e. are they currently on their way to pick up an order (to take to a known destination), have they already picked up an order and are enroute to a known destination.

Constraints are: 1) Must pick up an order after a given time (i.e. meal preparation time for restaurant) 2) Must deliver order in under 45 mins (otherwise alert thrown) 3) Must pad time with "x" minutes to accommodate for time spent walking to store to pickup order, etc. 4) Must pad time with "y" minutes to accommodate for time spent delivering order to customer and collecting payment. 5) Drivers have only a given set of payment methods (e.g. Cash, Visa, Amex, MasterCard). We must match customer request (cash, visa, etc) with driver capability (cash, visa, amex, etc).

So for example, if I get two orders with close by destination and close by pickup locations, even if there is another "Free" driver (not doing anything), it would be more efficient to use the same driver to pickup both orders and deliver both orders.

You can assume there will be delivery zones enforced for each restaurant, meaning, most people ordering from them will most likely be close to them. Therefore, this algorithm should manage to segment drivers automatically into city zones, and favor drivers within the zone already.

我想在 TSP 上尝试一些方法并且需要一些测试集。

我知道有一些关于 TSP 的精确和近似解决方案的比赛，我想测试我在这些比赛中使用的一些测试集上的一些想法。

但是我找不到任何好的竞争。

你知道任何好的 TSP 竞赛和/或 TSP 测试集吗？

我希望这是问的正确地方。