时间戳

首页 > 解决方案 > python中多个AGV的最短路径算法

python-3.x - python中多个AGV的最短路径算法

问题描述

我正在尝试为我的最短路径问题找到解决方案。我在一个小型 9 节点系统中有两辆车（AGV）。AGV 需要从起点到达终点，而不会相互妨碍。

9节点系统图片

是否有一种易于在 python 中实现的算法来找到两辆车的最短路径（系统的最短路径）？路径需要不相交以避免串通。

当只使用一辆车时，我使用了 Dijikstra 算法。现在有了两个，我显然可以让其中一个选择最短路径并阻止另一个路径。但在这么小的系统中，另一台 AGV 可能最终会等到第一台完成。我相信一定有更好的解决方案。在我的研究中，我找不到解决它的算法，而且实现起来并不复杂。

谢谢您的帮助！

更新#1：我尝试将 Tassles 建议放入代码中。但是由于我对编程还很陌生，所以我很挣扎，而且我确信我还有很长的路要走。所以我有很多问题，希望你能一路帮助我。

非常感谢你，我真的很感谢你的帮助！

import numpy as np
from itertools import combinations
import itertools
from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import dijkstra


class NavigationSystem:
    def __init__(self):
        self.map_sparse = csgraph_from_dense(
            np.genfromtxt('karte.csv', delimiter=',')[2:, 2:])
        self.coordinates = np.genfromtxt(
            'koordinaten.csv', delimiter=',')[1:, 1:]
        self._shortest_distances, self._predecessors = dijkstra(
            self.map_sparse, return_predecessors=True)

    def get_shortest_distance(start, end):
        v_old = [1, 2, 3, 4, 5, 6, 7, 8, 9]
        e_old = [map_sparse]
        g_old = (v_old, e_old)

        v_new = list(itertools.permutations(v_old, 2))
        e_new = []
        g_new = (v_new, e_new)

        for x in v_new:
            for every neighbour a of x[0]:
                if a != x[1]:
                    e_new.append((a, x[0]))

            for every neighbour b of x[1]:
                if b != x[0]:
                    e_new.append((b, x[1]))

            for every neighbour a of x[0]:
                for every neighbour b of x[1]:
                    if a != b:
                        e_new.append((x[0], x[1]), (a, b))
        return self._shortest_distances[start][end]

标签： python-3.xalgorithmshortest-path

解决方案

我想“不碍事”意味着两辆车不能同时在同一个节点。

在这种情况下，您可以再次将其建模为最短路径问题，但这次是在一个新图中，其中每个顶点代表原始图中的一对顶点，即两辆车的位置。因此，让我们G = (V,E)表示您的原始图，并以G' = (V',E')这种方式构建一个新图：

  • V'包含所有(u,v)顶点对V（如果需要，您可以省略表格对(u,u)，因为无论如何这些都无法访问）。
  • 现在对于边缘，看看从一个位置会发生什么(u,v)。要么第一辆车移动到在和a != v之间有边的某个位置，要么第二辆车移动到在和之间有边的某个位置，或者它们都可以分别移动到和if 。uaEb != uvbEaba != b

在伪代码中你得到：（你对每一对都这样做(u,v)）

For every neighbour a of u:
  If a != v: 
    Add an edge between (u,v) and (a,v)

For every neighbour b of v:
  If b != u: 
    Add an edge between (u,v) and (u,b)

For every neighbour a of u:
  For every neighbour b of v:
    If a != b: 
      Add an edge between (u,v) and (a,b)

然后，您可以寻找 和 之间的最短路径(s1,s2)，(t1,t2)其中s1和s2是两个起始顶点，并且e1, e2是目标顶点。如果你想让两辆车在同一个顶点开始或结束，你必须在 make 中添加必要的边(t,t)。

您得到的顶点数量是其中顶点G'数量的平方，G因此您可以期望大型实例上的运行时间也近似平方（大多数算法用于查找最短路径）。但是，9 个顶点很小，所以这里不用担心。

作为旁注，当在方形网格（或任何只有相同长度的边的图形上）工作时，Dijkstra 有点矫枉过正。您可以通过从您的起始位置执行简单的 BFS（广度优先搜索）来加快速度，记录您沿途的位置。

推荐阅读