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

Question

我正在尝试为我的最短路径问题找到解决方案。我在一个小型 9 节点系统中有两辆车 (AGV)。 AGV 需要从开始位置到结束位置，而不会互相妨碍。

Picture of 9-node-system

有没有一种很容易用python实现的算法来找到两辆车的最短路径(系统最短路径)？路径需要不相交以避免串通。

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

感谢您的帮助!

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

• 关于边缘:我应该将边缘添加到哪里？我猜是 E'(e_new) 但我不知道是什么形式。
• 如何包含“每个邻居”？我不知道如何让邻居离开 map_sparse。
• 我努力正确构建代码并将计算出的边用于 dijikstra 算法。代码写在下面的方式，我什至不使用最短距离的边缘。
• 而且我只计算其中一个 AGV 的最短路径，但它应该同时为两个 AGV 计算，对吗？

非常感谢，非常感谢您的帮助!

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]

Answer 1

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

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

• V'包含所有对 (u,v) V 中的顶点数(如果需要，您可以省略 (u,u) 形式的对，因为它们无论如何都无法访问)。
• 现在对于边缘，看看从位置 (u,v) 会发生什么.第一辆车移动到某个位置a != v u 之间有一条边和 a在 E ，或者第二辆车移动到某个位置b != u v 之间有一条边和 b在 E , 或者他们都可以移动到 a和 b分别如果a != 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是目标顶点。如果你想让两辆车在同一个顶点开始或结束，你必须添加必要的边来制作 (t,t) .

你在 G' 中得到了一些顶点这是G中顶点数的平方所以你可以期望大实例的运行时间也近似平方(大多数算法用于寻找最短路径)。然而，9 个顶点很小，所以不用担心。

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