带软时间窗车辆路径问题的求解算法研究  

Solving algorithm of vehicle routing problem with soft time windows

作　　者：汪秋云 蒋文保 

机构地区：[1]北京信息科大学信息管理学院,北京100192

出　　处：《北京信息科技大学学报（自然科学版）》2013年第4期57-59,63,共4页Journal of Beijing Information Science and Technology University

基　　金：国家自然科学基金面上项目(60873202);北京市自然科学基金面上项目(4132011)

摘　　要：针对带软时间窗车辆路径问题难以使用精确算法求解的问题,设计了一种基于爬山遗传混合的智能启发式算法来对带软时间窗车辆路径问题进行求解,并构建该混合算法相应的算法程序与爬山、禁忌搜索、模拟退火、遗传4种基本智能启发式算法进行标准数据对比测试。测试结果表明,该混合算法用于求解带软时间窗车辆路径问题具有计算效率高、计算结果稳定的特点。Since it is difficult to use precise algorithm to solve vehicle routing problem with soft time windows, an intelligent hybrid algorithm based on hill-climbing and genetics is proposed. Then corresponding algorithm program is constructed to compare with hill-climbing algorithm, tabu search algorithm, simulated annealing algorithm and genetic algorithm. The simulation experiment with standard test data from Solomon demonstrate the effectiveness of the hybrid algorithm, which is high in computational efficiency and stability.

关 键 词：车辆路径问题 软时间窗 爬山算法 禁忌搜索算法 模拟退火算法 遗传算法 混合算法 

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