改进禁忌算法求解考虑实时路况的车辆路径问题  

Improved tabu search algorithm for vehicle routing problems considering real-time road conditions

作　　者：陈荣虎[1] 赵李丽 CHEN Rong-hu;ZHAO Li-li(School of Management Science & Engineeringt Anhui University of Technology, Maanshan 243032,China)

机构地区：[1]安徽工业大学管理科学与工程学院

出　　处：《青岛理工大学学报》2019年第5期113-118,共6页Journal of Qingdao University of Technology

基　　金：国家社会科学基金资助项目(15BJL041)

摘　　要：车辆路径问题作为经典的组合优化问题,随着电子商务的蓬勃发展而广受关注.基于实时路况和禁忌搜索算法在求解该问题时过于依赖初始解的特点,提出了一种改进的禁忌搜索算法,即根据实时路况,先运用竞争决策算法的资源分配方式取得较优的初始解,再在此基础上进行禁忌搜索运算.实验案例中将改进后的禁忌搜索算法和改进前的禁忌搜索以及其他算法进行了对比,发现它不仅保持了禁忌搜索的高效率,而且计算结果更优更稳定,应用范围更加广泛.As a classic combinatorial optimization problem,the vehicle routing problem has attracted much attention along with the booming of e-commerce.Based on the real-time traffic conditions and the fact that the tabu search algorithm relies too much on the initial solution when solving the problem,an improved tabu search algorithm is proposed in this paper.According to the real-time traffic conditions,the resource allocation method of the competition decision algorithm is used first to obtain a better initial solution,and then the tabu search operation is performed on this basis.In the experimental case of this paper,the improved tabu search algorithm is compared with the tabu search before improvement and other algorithms.It is found that it not only maintains the high efficiency of tabu search algorithm,but also has more stable calculation results and wider application scope.

关 键 词：禁忌搜索算法 竞争决策算法 初始解 路径优化 

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