基于有向图强连通改进变邻域搜索算法的AGV单向导向路径网络设计

为最小化物料搬运成本，结合有向图强连通性理论，提出一种改进变邻域搜索算法。首先，以最小化AGV的运载和空载成本为目标，建立相应的数学规划模型。接着，给出一种初始解生成方法，并构建目标函数计算的网络流模型。然后，为提高局部搜索能力，以有向图强连通性中反转路、反转圈保持强连通性为基础，提出3种邻域结构生成方法，以保证邻域解搜索过程中解的可行性，提高求解效率和质量。最后，针对6个基准案例，运用算法求解，并将其与其他多种启发式算法进行比较。实验结果表明，对于中小规模问题案例，算法求得案例的最优解；对于两个大规模案例，算法求得新的最好解，验证了提出算法的有效性。