基于通用变邻域搜索的多AGV分拣调度优化  

General variable neighborhood search for the multi-AGV scheduling problem with sorting operations

作　　者：郭超 陈香玲[3] 郭鹏 王强 GUO Chao;CHEN Xiangling;GUO Peng;WANG Qiang(Technology and Equipment of Rail Transit Operation and Maintenance Key Laboratory of Sichuan Province,Chengdu,Sichuan 610031,China;School of Intelligent Manufacturing,Yibin Vocational and Technical College,Yibin,Sichuan 644003,China;School of Mechanical Engineering,Southwest Jiaotong University,Chengdu,Sichuan 610031,China)

机构地区：[1]轨道交通运维技术与装备四川省重点实验室,四川成都610031 [2]宜宾职业技术学院智能制造学院,四川宜宾644003 [3]西南交通大学机械工程学院,四川成都610031

出　　处：《河北科技大学学报》2021年第5期523-534,共12页Journal of Hebei University of Science and Technology

基　　金：国家重点研发计划项目(2020YFB1712200);宜宾职业技术学院科研平台建设计划资助项目(YBZY21KYPT-03);轨道交通运维技术与装备四川省重点实验室开放课题(2020YW004)。

摘　　要：为了解决物流仓储分拣中心多台AGV处理大量包裹调度优化困难的问题,在考虑分拣作业时间窗和充电需求的基础上,研究了大规模AGV调度问题。以最小化分拣作业周期为目标,提出了一种通用变邻域搜索(general variable neighborhood search,GVNS)算法,为各台AGV指定转运任务和作业排序,采用遍历插入启发式策略生成满足时间窗约束的初始解,设计了10种邻域算子对初始解迭代寻优,并对比不同规模算例的算法性能,分析AGV充电速率和数量配置对分拣效率的影响。结果表明,GVNS算法具有计算时间和求解性能方面的优势,能在较短时间内求得近似最优解,平均计算时间仅为532.78 s,明显优于混合整数规划模型和约束规划模型;当包裹数为100时,最合适的AGV配置为14辆。因此,GVNS可以有效解决分拣中心考虑充电需求和硬时间窗的大规模多AGV调度问题,提高物流分拣效率,帮助企业找到科学、合理的AGV配置方案。To solve the intractable multiple automatic guided vehicles(AGVs)scheduling problem encountered in the sorting processes of the logistics sorting centers,a large-scale AGV scheduling problem was studied on the basis of considering the sorting time windows and charging requirements.A general variable neighborhood search(GVNS)algorithm was proposed to minimize the makespan of the sorting operations,in which the assignment of transferring packages to AGVs and the sequence of sorting tasks for each AGV were determined.The traversal insertion heuristic was developed to generate the initial solution of the developed algorithm to ensure the constraint of time windows.Ten neighborhood operators were designed to optimize the initial solution for the iteration of the algorithm.Different sized test instances were compared,and the impacts of AGV charging rate and quantity configuration on sorting efficiency were analyzed.The results show that the GVNS algorithm is superior in computing time and solution performance.It can obtain the approximate optimal solution in a short time.The average computing time of GVNS is only 532.78 s,which is obviously better than the mixed integer and constraint programming models;when the number of packages is 100,the most suitable number of AGVs is 14.Therefore,GVNS can effectively solve the large-scale and multi-AGV scheduling problem with charging demand and hard time window,improve the efficiency of logistics sorting,and help enterprises find the scientific and reasonable AGV configuration scheme.

关 键 词：物流系统管理 分拣作业 自动导引小车 调度 充电需求 变邻域搜索 

分 类 号：F252.1[经济管理—国民经济] TP301[自动化与计算机技术—计算机系统结构]