粒子群优化

Question

我在使用PSO算法解决流量问题时有一个问题。 假设我们有n辆车（这里仅限于四辆车），这些车辆具有相同的目的地。 （假设我们知道他们的位置（x，y）） D：起始城市和目的地之间的距离。 d：在气体用尽之前它可以行驶的最大距离。 D >> d：每辆车必须加油N次，N = D/d 每辆车应该遵循的路径是不确定的。 任务： 我们正在寻找最少的加油站数量，以便每辆车都不会发生故障（因为气体当然）。加油站的数量是多少？它们的位置是多少？

Answer 1

我相信你可以用你的标准Dijkstra搜索算法解决这个问题，只需稍微增加。

首先将您的起点设置为硬编码位置。像平常一样进行Dijkstra搜索，记下您遇到的加油站，但现在有点忽略它们。尽量到达目的地，不要停止使用天然气，但要取消搜索所有节点的燃气。现在，如果你到达目的地而没有用完天然气，那么这是最短的路径，并且它没有气体停止。但是，如果您确实用尽了气体，那么将起始点（和起始距离）设置为您在上一次搜索中找到的加油站，因此现在您有多个潜在起点。然后它只是重复。如果您再次未能到达目的地，则从您在上次搜索中找到的所有加油站开始搜索。

保持这样做直到您从上一个查询中的所有起点到达目的地。理清距离并选择最短路径。

现在，如果你到达一个停止加油站并未能到达最终目的地的阶段，那么在没有用完天然气的情况下，没有可能的路线通往最终目的地。