一类面向仓库车辆路径优化的改进禁忌搜索算法及其应用  

A Kind of Improved Tabu Search for Warehouse Vehicle Routing Optimization and Its Application

作　　者：吴胜昔 刘威 卢文建 顾幸生 WU Sheng-xi;LIUWei;LU Wen-jian;GU Xing-sheng(Key Laboratory of Advanced Control and Optimization for Chemical Processes,Ministry of Education,East China University of Science and Technology,Shanghai 200237,Chin)

机构地区：[1]华东理工大学化工过程先进控制和优化技术教育部重点实验室,上海200237

出　　处：《华东理工大学学报（自然科学版）》2018年第4期581-587,共7页Journal of East China University of Science and Technology

基　　金：国家自然科学基金(61573144);上海市重点学科建设项目(B504)

摘　　要：在立体仓库中常需考虑车辆路径规划问题,传统的禁忌搜索算法在解决该类问题时,最终解的质量依赖于初始解。针对此问题并结合实际立体仓库,本文提出了改进的禁忌搜索算法。该算法的初始解部分由模拟退火算法生成,有效地克服了禁忌搜索算法对初值的依赖;规定禁忌搜索算法的特赦准则为模拟退火算法关联,在限定始末库位条件下,尽可能地寻找更短车辆路径,提高禁忌搜索算法的搜索能力。将改进的禁忌搜索算法与标准禁忌搜索算法进行仿真对比,改进算法在平均最短路径和稳定性上都有较大提升。将本文算法应用于立体仓库调度过程,在实际应用中效果良好,具备可行性。Vehicle routing problem is a hot topic in the three dimensional warehouse. When the traditional Tabu search is used to handle the above problem, the quality of the final solution usually depends on the initial solution, which implies that a randomly generated initial solution may reduce the reliability of the algorithm. This paper proposes an improved Tabu search algorithm for this kind of vehicle routing problem by using the simulated annealing algorithm to generate the initial solution so that the dependence of Tabu search on the initial value can be effectively overcome. Two cases of generating the initial value are considered： the one is that the initial values include all messages from beginning location to end location about simulated annealing in an ideal condition; the other is that the initial values ignore the first position and the last position through simulated annealing in an actual condition. The amnesty criterion of Tabu search is assumed to be simulated annealing, which can improve the searching ability of Tabu search algorithm to find shorter vehicle paths under the constraint of the beginning and ending locations. Especially, the proposed algorithm can also give better searching result for the case without the above constraint. Fina work and the standard lly, the comparison experiments between the improved Tabu search algorithm in this Tabu search algorithm are made with the examples coming from a well known test library. It is shown from simulation results that the improved algorithm attains greater improvement on the average shortest path and the stability. three dimensional warehouse by taking the In addition, the improved algorit second algorithm of getting initia tion. m is also applied in the actual solution, whose result is also

关 键 词：立体仓库 车辆路径问题 禁忌搜索算法 模拟退火算法 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]