图的优化算法

Question

我有一个图，我需要从选择的节点开始访问图中的每个节点ni。存在不访问节点的成本，这对于不同的节点ci是不同的，并且对于成本ci存在时间梯度。换句话说，不访问ci的成本是时间的函数。存在运输成本，即对于两个相邻节点i和j，两个节点dij之间的距离是线性的。

问题是确定以最小成本到达所有节点的最优路由。

我唯一的想法就是暴力破解它，选择所有可能的路线并计算成本。我想知道是否有人可以提供一些一般性的见解来解决这个问题。我不是在寻找代码/整个解决方案，只是一些指向这个问题的指针或一些论文。请注意，这不同于旅行商问题。

Answer 1

正如您在上面回答的Draco18s，这是“经典TSP”的一个变体。

让我们将经典版本表示为cTSP；描述访问图中的所有节点(以及最终返回到起始节点)的问题，其中成本函数仅包含不同节点之间旅行的运输成本之和-在距离中线性。

让我们将您的cTSP变体表示为vTSP。在解决这个问题之前，我们应该确定cTSP和vTSP之间的一些重要区别。对于n个节点的cTSP实例，存在(n-1)!/2个不同的路径；对于任何特定的路径，方向和起始节点都不会影响路径开销。对于vTSP的实例，问题更为复杂，因为起始节点的选择以及路径方向都将影响路径成本，这是由于(尚未)访问节点的时间相关成本。从这里开始，我将假设“自旅行开始以来花费的时间”被定义为与“自旅行开始以来所走的距离”的某种关系，特别是恒定的旅行速度。此外，我假设这些依赖于时间的成本函数是单调递增的。

我在文献中没有遇到过这种特定的变体，所以我不能在这个方向上给你任何指导。然而，与蛮力(对于vTSP来说，随着问题规模的增加，暴力应该会变得非常棘手)相比，我建议使用蚁群优化来解决问题。抛开证明最优性不谈，你至少可以将其结果与蛮力方法进行比较，在一段时间内限制算法的运行时间。使用蚁群算法，为了确保信息素水平即使在更复杂的vTSP中仍然是良好路径的定量度量，该问题可能应该分为n个子问题，每个子问题都有一个固定的起始城市。最初，让这些子问题相互独立，也许在以后研究让它们相互作用的可能性。

对于每个子问题，只需应用(标准)蚁群算法，这非常简单，参见例如https://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms#Example_pseudo-code_and_formula

不同边缘的信息素水平将-就像ACO应用于cTSP一样-仍然只反映出它是否是在蚂蚁中“流行”的边缘。由于起始节点是固定的，并且时间相对于行进的距离，蚂蚁应该倾向于及早访问那些对迟到的惩罚更大的节点。从蚂蚁的角度来看，vTSP w.r.t.中的附加约束类型。cTSP只会导致有利优势的不同评分(本身就是一种蛮力方式...)。

无论如何，可能不是您想要的答案(如果更喜欢经典的优化方法？)，但祝您好运！