有时间窗车辆路径问题的混合智能算法  

Hybrid intelligence algorithm based on vehicle routing problem with time windows

作　　者：张有华[1] 张翠军[1] 崔忠强[1] 

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

出　　处：《计算机工程与应用》2008年第20期54-56,60,共4页Computer Engineering and Applications

基　　金：国家高技术研究发展计划(863)(the National High-Tech Research and Development Plan of China under Grant No.2006AA06Z233);河北省科学技术研究与发展项目(the Science and Technologies Research Project of Hebei Province; China under Grant No.06213559);河北省教育厅科学研究计划项目(the Scientific Research Project of Department of Hebei Education of China under Grant No.2004454)

摘　　要：有时间窗的车辆路径问题属于组合优化领域中的NP-hard问题。在对该问题进行分析的基础上,为之建立了数学模型,提出了一种求解该问题的混合智能算法。该算法通过使用蚁群算法和遗传算法交替优化,并且及时交换信息,弥补了蚁群算法和遗传算法各自的不足,达到了优势互补的效果,增强了算法的寻优能力,避免了停滞现象。实验结果表明,该算法能有效解决有时间窗的车辆路径问题。Vehicle routing problem with time windows is a NP-hard problem in combinatorial optimization field.Based on the analysis about it,a mathematical model is built and a hybrid intelligence algorithm for solving it is designed.The algorithm lets ant colony algorithm and genetic algorithm execute alternately and communicate timely in the optimization process.It learns the colony algorithm＇s and genetic algorithm＇s advantages and makes up their disadvantages.Thus its ability of optimization is enhanced and premature phenomenon is avoided.The experiment results show that the hybrid algorithm is efficient in solving vehicle routing problem with time windows.

关 键 词：有时间窗车辆路径问题 NP-HARD问题 蚁群算法 遗传算法 混合智能算法 

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