求解动态最优路径的混合优化算法  

Hybrid optimization algorithm for routing problem in dynamic networks

作　　者：王江晴[1] 覃俊[1] 李子茂[1] 

机构地区：[1]中南民族大学计算机科学学院,湖北武汉430074

出　　处：《通信学报》2008年第7期135-140,共6页Journal on Communications

基　　金：国家自然科学基金资助项目(60603008)~~

摘　　要：对动态网络环境下动态需求的最优路径搜索问题进行了研究,首次提出了一个能同时利用演化算法的全局优化能力和蚁群算法的局部探索能力的混合智能优化算法Evo-Ant,并将其应用于DVRP。为了验证算法的有效性,给出了DVRP的混合整数规划模型,建立了DVRP的动态性能测试类,并进行了大量的仿真实验和比较。结果表明,Evo-Ant算法能够根据实时接收到的信息对当前规划路径进行及时调整,具有明显改善的性能优势。A routing problem was investigated where both dynamic network environment and real-time customer requests were considered, a hybrid optimization algorithm called Evo-Ant was proposed. The advantage of the algorithm is that it incorporates ant colony algorithm for exploration and evolutionary algorithm for exploitation, and uses real-time infor mation during the optimization process. In order to discuss the performance of the proposed algorithm, a mixed integral programming model for dynamic vehicle routing problem was formulated, and benchmark functions were constructed. The performance of the algorithm is evaluated by comparing its results with some exact algorithms and heuristic algorithms for randomly generated test problems. The results show that the proposed algorithm can achieve a higher performance gain, and is well suited to problems containing dynamic network environment and real-time customer requests.

关 键 词：动态网络 路由问题 演化算法 蚁群算法 

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