基于有时间窗车辆路径问题的混合蚁群算法  

Hybrid ant colony algorithm based on vehicle routing problem with time windows

作　　者：张翠军[1] 张有华[1] 秦彭[1] 王占锋[1] 

机构地区：[1]石家庄经济学院信息工程学院,河北石家庄050031

出　　处：《计算机工程与设计》2008年第4期920-922,共3页Computer Engineering and Design

基　　金：国家863高技术研究发展计划基金项目(2006AA062233);河北省科学技术研究与发展基金项目(06213553);河北省教育厅科学研究计划基金项目(2004454)

摘　　要：有时间窗的车辆路径问题是目前组合优化领域研究的热点问题,其归属于NP-hard问题。在对该问题进行分析的基础上,为之建立了数学模型,提出了一种求解该问题的混合蚁群算法。该算法通过在蚁群算法中引入λ-interchange变异算子,增强了算法的局部搜索能力,避免了早熟现象。实验结果表明,该算法能有效解决有时间窗的车辆路径问题。Vehicle routing problem with time windows is a focus and a NP_hard problem in combinatorial optimization field. Based on the analysis about it, a mathematical model is built and a hybrid ant colony algorithm for solving it is designed. λ-interchange mutation operator is added to ant colony algorithm to improve the algorithm＇s ability of local search and to avoid premature phenomenon. The experiment results show that the algorithm is efficient in solving vehicle routing problem with time windows.

关 键 词：有时间窗车辆路径问题 组合优化 混合蚁群算法 λ-interchange变异算子 局部搜索 

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