求解带时间窗车辆路径问题的动态混合蚁群优化算法  

Dynamic Hybrid Ant Colony Optimization Algorithm for Solving the Vehicle Routing Problem with Time Windows

作　　者：葛斌[1,2] 韩江洪[1] 魏臻 程磊 韩越[2] 

机构地区：[1]合肥工业大学计算机与信息学院,合肥230009 [2]安徽理工大学计算机科学与工程学院,淮南232001 [3]合肥工大高科信息科技股份有限公司,合肥230088

出　　处：《模式识别与人工智能》2015年第7期641-650,共10页Pattern Recognition and Artificial Intelligence

基　　金：国家自然科学基金项目(No.61070220);安徽省自然科学基金项目(No.1408085ME110);安徽省高等学校省级自然科学研究重大项目(No.KJ2013ZD09)资助

摘　　要：为求解带时间窗车辆路径问题,针对传统蚂蚁遗传混合算法中参数静态设置、冗余迭代及收敛速度慢等缺点,提出一种动态混合蚁群优化算法(DHACO).该算法首先借助最大最小蚁群得到初始解,利用蚁群优化算法求解带时间窗车辆路径问题的基本可行解.然后采用遗传算法交叉和变异操作对局部解和全局最优解进行二次优化,从而得到最优解.最后利用蚂蚁遗传混合算法融合策略,动态交叉调用蚂蚁算法、遗传算法,根据云关联规则自适应控制蚁群算法参数.DHACO有效减少无效迭代次数,加快收敛速度.仿真结果表明,与其他相关的启发式算法相比,DHACO优于某些实例的已知最优解.To solve the vehicle routing problem with time windows （VRPTW）, a dynamic hybrid ant colony optimization algorithm （DHACO） is proposed, so as to avoid the disadvantages of traditional ant genetic hybrid algorithm, such as static setting, redundant iteration and slow convergence. Firstly, an initial solution is obtained through get a basic feasible solution are employed to re-optimize based on the fusion strategy max-min ant system, and the ant colony optimization algorithm is adopted to to VRPTW. Then, the crossing and mutation operations of genetic algorithm local and global solutions, thus the of ant genetic hybrid algorithm, and optimal solution is obtained. Finally, by employing ant algorithm and geneticalgorithm dynamically and alternately, the parameters according to cloud association rules. DHACO reduces rate of the convergence. Simulation results show that algorithms as to the optimal solutions. of ant colony algorithm is self-adaptively controlled the times of redundant iteration and speeds up the DHACO is better than the other related heuristic

关 键 词：动态最大最小蚂蚁系统 融合策略 带时间窗车辆路径问题 蚁群优化算法 遗传算法 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]