计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (30): 36-39.DOI: 10.3778/j.issn.1002-8331.2010.30.011
葛洪伟,王银年
GE Hong-wei,WANG Yin-nian
摘要: 配送和回收一体化的车辆路径问题(VRPSDP)是一种非常复杂的NP难题。针对这一问题,设计了一种改进的模拟退火遗传算法ISAGA,采用非零自然数编码机制和弱可行解到强可行解的解码机制,将3PM交叉算子和退火选择相结合,形成贪心3PM交叉算子,引进insert 、swap和2-opt分别对解进行迭代优化,并将模拟退火算法和遗传算法巧妙地结合,使得遗传算法在前期发挥着全局搜索的强大功能;后期用模拟退火算法来处理遗传算法前期的全局较优解,充分利用模拟退火算法后期局部搜索的强大功能。经过国际公认的测试算例验证,ISAGA算法在Min算例、Salhi和Nagy算例中均找到了比现有算法已知最好解更优的解。
中图分类号: