郭超 陈香玲 郭鹏 王强

摘 要：為了解决物流仓储分拣中心多台AGV处理大量包裹调度优化困难的问题，在考虑分拣作业时间窗和充电需求的基础上，研究了大规模AGV调度问题。以最小化分拣作业周期为目标，提出了一种通用变邻域搜索（general variable neighborhood search，GVNS）算法，为各台AGV指定转运任务和作业排序，采用遍历插入启发式策略生成满足时间窗约束的初始解，设计了10种邻域算子对初始解迭代寻优，并对比不同规模算例的算法性能，分析AGV充电速率和数量配置对分拣效率的影响。结果表明，GVNS算法具有计算时间和求解性能方面的优势，能在较短时间内求得近似最优解，平均计算时间仅为532.78 s，明显优于混合整数规划模型和约束规划模型;当包裹数为100时，最合适的AGV配置为14辆。因此，GVNS可以有效解决分拣中心考虑充电需求和硬时间窗的大规模多AGV调度问题，提高物流分拣效率，帮助企业找到科学、合理的AGV配置方案。

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

中图分类号：F252.1;TP301   文献标识码：A

doi：10.7535/hbkd.2021yx05011

收稿日期：2021-08-20;修回日期：2021-09-19;责任编辑：张士莹

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

第一作者简介：郭 超（1984—），男，四川宜宾人，讲师，主要从事智能制造方面的研究。

通讯作者：郭 鹏副教授。E-mail：pengguo318@swjtu.edu.cn

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

GUO Chao1，2，CHEN Xiangling3，GUO Peng1，3，WANG Qiang2

（1.Technology and Equipment of Rail Transit Operation and Maintenance Key Laboratory of Sichuan Province，Chengdu，Sichuan 610031，China;2.School of Intelligent Manufacturing，Yibin Vocational and Technical College，Yibin，Sichuan 644003，China;3.School of Mechanical Engineering，Southwest Jiaotong University，Chengdu，Sichuan 610031，China）

Abstract：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.

Keywords：

logistics system management;sorting operation;automatic guided vehicle;scheduling;charging demand;vari-able neighborhood search

随着电子商务产业的不断发展壮大，中国快递包裹经历了连续十多年的爆炸式增长，从2010年的不足24亿件迅速攀升到2020年的833.6亿件，目前快递总量已超过美国、日本及欧洲发达国家的快递量总和，成为名副其实的“快递大国”。……