optimization - 粒子群优化

Question

我对使用 PSO 算法解决交通问题有疑问。假设我们有 n 辆车（这里只限于四辆车）这些车辆有相同的目的地。他们有不同的起始城市。（假设我们知道他们的位置（x，y）） D：起始城市和目的地之间的距离。d：它在耗尽气体之前可以行驶的最大距离。D >> d : 每辆车必须加油 N 次 N=D/d 每辆车应该遵循的路径是不确定的。任务：我们正在寻找最少数量的加油站，这样每辆车都不会抛锚（当然是因为汽油）。加油站的数量是多少，它们的位置是什么。

Answer 1

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

首先将起点设置为硬编码位置。像往常一样进行 Dijkstra 搜索，记下您遇到的加油站，但暂时忽略它们。尝试在不停止加油的情况下到达目的地，但取消对所有可能会用完加油的节点的搜索。现在，如果您在没有用完油的情况下到达目的地，那是最短的路径，并且不涉及加油站。

但是，如果您确实用完了汽油，则将起点（和起点距离）设置为您在之前搜索中找到的加油站，这样现在您就有了多个潜在的起点。然后它只是重复。如果您再次未能到达目的地，请从您在上次搜索中找到的所有加油站开始搜索。

继续这样做，直到您从上一个查询中的所有起点到达目的地。计算距离并选择最短的路径。

现在，如果您到达加油站用完但未能到达最终目的地的阶段，那么就没有可能到达最终目的地的路线而不用完汽油。