混合禁忌搜索算法求解关联运输调度问题  

Hybrid Tabu Search Algorithm for Solving Incident Vehicle Routing Problem

作　　者：蔡延光[1] 汤雅连[1] 朱君[1] 

机构地区：[1]广东工业大学自动化学院,广州510006

出　　处：《计算机科学》2015年第4期230-234,273,共6页Computer Science

基　　金：国家自然科学基金(61074147;61074185);广东省自然科学基金(S2011010005059;8351009001000002);广东省教育部产学研结合项目(2012B091000171;2011B090400460);广东省科技计划项目(2012B050600028;2010B090301042)资助

摘　　要：考虑到实际生活中车辆受发车时间限制以及道路路况影响运输成本等因素,建立了带客户软时间窗、车场硬时间窗、多车型、道路路况等约束的关联运输调度问题模型。结合禁忌搜索与遗传算法的优势,构造了混合禁忌搜索算法,以通过构造多个初始解来增大搜索空间;设计了两种禁忌表,分别为局部禁忌表和全局禁忌表,这不仅能加快寻优速度,还可以摆脱对单个解的依赖;将禁忌搜索生成的优化解作为遗传算法的初始解,可以加快寻优速度;自适应调整禁忌表长度可以避免早熟收敛;提取核心路径便于进行后期优化,relocate算子能减少路径网络回路数目。对实例进行的仿真表明,提出的IVRP优于一般的VRP,可节约大量成本,且提出的算法在收敛速度和寻优结果两方面都优于遗传算法和禁忌搜索算法。由3种算法求解得到的总成本、总里程及收敛时间的标准差体现出该算法的稳定性比另外两种算法的好。Considering these factors that vehicles have the departure time limit and road conditions affect the transportation cost,etc,we established the incident vehicle routing problem（IVRP）mathematical model based on clients＇ soft time windows,depots＇ time windows,heterogeneous vehicles,road conditions constraints,etc.Making full use of the advantages of genetic algorithm（GA）and tabu search（TS）,hybrid tabu search algorithm（HTSA）was constructed.Search space was increased by constructing multiple initial solutions,and two kinds of tabu list：local tabu list and global tabu list were designed,which not only can speed up the optimization,but also can get rid of the reliance on initial solution.Adjusting the tabu list length adaptively can avoid premature convergence,extracting core routes is conducive to late optimization and the relocate operator can reduce route number.Experiments show that IVRP is superior to the general VRP,which can save cost greatly.Moreover,HTSA is better than GA and TS in convergence speed and optimal results,and the stability of HTSA is better by comparing the standard deviation of total cost,total distance and convergence time.

关 键 词：关联运输调度问题 禁忌搜索 遗传算法 核心路径 自适应交叉 混沌变异 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]