基于改进遗传算法的AGVS单双向混合路径规划
                                                王江华，楼佩煌，钱晓明
                                    南京航空航天大学机电学院，江苏 南京210016
     针对自动导引车系统路径规划问题，首先提出了一种新的路径网络模型，即单双向混合路径网络布局。然后在仔细分析该种路径布局的特征和优势的基础上，使用改进的遗传算法实现其路径网络的规划，并详细描述了算法步骤。最后，通过对两个自动搬运系统进行路径规划、系统建模、系统仿真和对比分析，验证了单双向混合路径网络布局的优越性和可行性。

    多台自动导引车（Automated Guided Vehicle，AGV）在控制系统的统一指挥下，组成的柔性化的自动搬运系统称为自动导引车系统（Automated Guided Vehicle System，AGVS）。AGVS路径设计问题是AGVS设计首先需要考虑的问题，其布局极大地影响系统的性能。常用的路径布局包括单向路径网络布局、双向路径网络布局、单循环路径布局和基于串联配置的路径布局等，其中基于单向路径网络布局的AGVS由于控制简单可靠得到了普遍应用。单向路径网络的设计问题首先由Gaskins等运用0-1整数规划方法来处理，之后分支定界法、启发式算法、禁忌搜索算法、遗传算法等也被逐渐应用于单向路径网络的规划，然而由于单向路径网络中每条路径只允许AGV单向运行，增加了AGV的绕行距离，降低了系统效率。基于双向路径网络布局的AGVS中每条路径都允许AGV双向行驶，大大减少了AGV的运行距离，因此双向路径网络在冲突和死锁很少发生且AGV数量较少的AGVS中可以发挥其优势。双向路径网络规划的难点在于死锁和冲突的解决，即规划一条从起始点到目标点的无死锁无冲突路径。为了实现该目标，学者们提出了时间窗、petri网等复杂的路径规划算法，同时也验证了此类算法对控制系统和硬件的高要求以及对AGVS规模的限制，因此双向路径网络在实际生产系统中未能广泛应用。为此，本文将双向路径的优势引入单向路径网络中，设计了单双向混合路径网络。

1单双向混合路径网络的结构和交通管理
1.1路径结构
    本文借用文献［9］所运用的路径模型来阐述本文中单双向混合路径网络的结构特点。图1（a）为该案例的无向路径网络，其有6个工作单元，每个工作单元配置一对装/卸站点。节点{2，4，9，11，12，14，19，20}表示路径交叉点。本文假设所有的装/卸站点都设置在路径段上，即不存在既表示装/卸站点又表示路径交叉点的节点。在该假设下，将每个度为2的节点所连接的两条路径合并为一条合成路径。合并之后，各路径段的两端节点都将是路径交叉点，如边{（2，9），（9，19），（9，11）}。图1（b）和图1（c）分别表示了图1（a）中无向路径网络所对应的单向路径网络和单双向混合路径网络。经对比可以发现,该例中的单向路径网络和单双向混合路径网络除了各路径段所允许的AGV的运行方向不同之外，其他均相同，这就意味着将已存在的单向路径网络改造成单双向混合路径网络只需要重新设计路径方向，这个通过计算机就可以完成，不需要其他的改造费用。在图1（c）的路径网络中，路径段{（2，4），（9，11），（14，20）}是双向路径，同时所有路径交叉点最多只有一条双向路径与之相连，这就是本文中单双向混合路径网络的最大特点，该特点使系统只需要采用简单
的交通管理算法就可以实现系统无死锁运行。
1.2交通管理
单向AGVS中会发生节点冲突和循环死锁，双......


作者简介：王江华(1989—)，女，江苏丹阳人，南京航空航天大学硕士研究生，主要研究方向为计算机集成及柔性制造。


（文章来源《机械设计与制造工程》如需详细资料请联系江苏机械门户网客服QQ:2980918915,电话025-83726289）