Abstract: In order to solve the task allocation problem of multi-Automated Guided Vehicle (AGV) storage system, a Variable Neighborhood_Simulated Annealing (VN_SA) algorithm was proposed. Firstly, according to the system operation process and operating characteristics of AGV, with the path cost, time cost and task equilibrium value cost of AGV during the task execution as the goals, and adding the power consumption situations of AGV driving with and without load to the constraints, a more practical multi-objective optimization model of task allocation for multi-AGV storage system was built. Then, aiming at the characteristics of the problem, a VN_SA algorithm was designed. The search range of the simulated annealing algorithm was expanded by the neighborhood perturbation operation in the algorithm, and the local optimum was jumped out by the algorithm and the global development effect was obtained by combining the probability mutation characteristics. The simulation experiments were carried out on works with the number of tasks of 20, 50, 100 respectively. Experimental results show that, the optimized total cost of the proposed algorithm is reduced by 6.4, 7.5 and 13.2 percentage points respectively compared with Genetic Algorithm (GA), which verifies the effectiveness of the proposed algorithm under different task sizes. It can be seen that the proposed algorithm has better convergence and search efficiency.

Key words: Automated Guided Vehicle (AGV), "Goods to Person" picking, task allocation, Variable Neighborhood Search （VNS）, Simulated Annealing algorithm, neighborhood disturbance

摘要： 针对多自动导引车（AGV）仓储系统任务分配问题，提出了变邻域模拟退火（VN_SA）算法。首先，根据系统作业流程及AGV运行特征，以AGV执行任务的路径代价、时间代价以及任务均衡值代价为目标，并在约束中加入AGV空载行驶和负载行驶的耗电情况，构建更贴合实际的多AGV仓储系统任务分配多目标优化模型；其次，针对问题特点，设计了一种变邻域模拟退火算法。算法中的邻域扰动操作拓展了模拟退火算法的搜索范围，且概率突变特性的结合使算法跳出局部最优，并获得全局开发的效果。分别设置任务量为20、50、100的作业进行仿真实验，实验结果表明，所提算法优化后的总代价相较于遗传算法（GA）分别降低了6.4、7.5、13.2个百分点，验证了所提算法在不同任务规模下的有效性。可见所提算法具有更好的收敛性和搜索效率。

关键词: 自动导引车, “货到人”拣选, 任务分配, 变邻域搜索, 模拟退火算法, 邻域扰动